A block-based layer building approach for the 2D guillotine strip packing problem

• 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.