摘要
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.
学科与关键词
- A recursive algorithm for the rectangular guillotine strip packing problemCui, Y.*; Gu, T.; Zhong, Y.ENGINEERING OPTIMIZATION, 2008, 40(4): 347-360.被引 2
- A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi HuangWang, Lei*; Yin, AihuaJOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32(2): 416-444.被引 4
- A simple randomized algorithm for two-dimensional strip packingYang, Shuangyuan*; Han, Shuihua; Ye, WeiguoCOMPUTERS & OPERATIONS RESEARCH, 2013, 40(1): 1-8.被引 23
