A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem
A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem
复制标题
DOI：
10.1016/j.cor.2006.08.011
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
Yaodong Cui;Yuli Yang;Xian Cheng;Peihua Song
中科院分区：
文献类型：
--
作者：
Yaodong Cui;Yuli Yang;Xian Cheng;Peihua Song
提出了一种求解二维矩形条带堆积问题的启发式递归算法。它基于递归结构与分支定界技术相结合。尝试了几种长度来确定容纳所有物品的最小板长度。最初，板被视为块。对于当前考虑的块，算法选择一个项目，将其放在块的左下角，并使用正交切割将未占用区域划分为两个较小的块。如果块宽度等于板宽度，则分割切口是垂直的；否则它是水平的。下限和上限都用于修剪无希望的分支。一类基准问题的计算结果表明该算法的性能优于最近发布的几种算法。
A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.