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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

15 Scopus Citations
View graph of relations

Author(s)

  • Lijun Wei
  • Tian Tian
  • Wenbin Zhu
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)58-69
Journal / PublicationEuropean Journal of Operational Research
Volume239
Issue number1
Online published24 Apr 2014
Publication statusPublished - 16 Nov 2014

Abstract

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. © 2014 Elsevier B.V. All rights reserved.

Research Area(s)

  • Best-fit heuristic, Cutting, Guillotine-cut, Layer-building, Packing

Citation Format(s)

A block-based layer building approach for the 2D guillotine strip packing problem. / Wei, Lijun; Tian, Tian; Zhu, Wenbin; Lim, Andrew.

In: European Journal of Operational Research, Vol. 239, No. 1, 16.11.2014, p. 58-69.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review