Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479787 | European Journal of Operational Research | 2014 | 12 Pages |
•We apply three successful ideas for the 2D strip packing with guillotine-cut.•We pack a block of rectangles instead of a single rectangle in each step.•We divide the strip into horizontal layers and pack layer by layer.•We unload and repack the last portion of a solution repeated to improve it.•We outperform all existing approaches on standard benchmark instances.
We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches.