Parallel greedy algorithms for packing unequal circles into a strip or a rectangle
Parallel greedy algorithms for packing unequal circles into a strip or a rectangle
复制标题
DOI：
10.1007/s10100-009-0103-5
复制
发表时间：
2009-07
影响因子：
1.7
通讯作者：
T. Kubach;Andreas Bortfeldt;H. Gehring
中科院分区：
文献类型：
--
作者：
T. Kubach;Andreas Bortfeldt;H. Gehring
给出一个有限个不同大小的圆集合，我们研究了带状装箱问题(SPP)和背包问题(KP)。SPP要求将所有圆放置在固定宽度的矩形条带内，以使条带的可变长度最小化。该算法要求对给定矩形内的圆的子集进行布局，从而使浪费的面积最小。为了解决这些问题，人们开发了一些贪婪算法，改进了Huang等人提出的算法。(J Oper res Soc 56：539-548,2005)。此外，使用主从式方法对新的贪婪算法进行并行化。使用Stoyan和Yaskov介绍的实例(EUJ Oper Res 156：590-600,2004)对产生的并行方法进行了测试。此外，还生成了两组实例，每组128个，分别用于SPP和KP，并报告了这些新实例的结果。
Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.