A bidirectional building approach for the 2D constrained guillotine knapsack packing problem

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

13 Scopus Citations
View graph of relations

Author(s)

  • Lijun Wei
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)63-71
Journal / PublicationEuropean Journal of Operational Research
Volume242
Issue number1
Online published13 Oct 2014
Publication statusPublished - 1 Apr 2015

Abstract

This paper investigates the 2D guillotine knapsack packing problem, in which the objective is to select and cut a set of rectangles from a sheet with fixed size and maximize the total profit of the selected rectangles. The orientation of the rectangles is fixed. And the guillotine cut, in which the cut must be parallel to the sides of the sheet to divide it into two completely separated sheets, is required. Two well-known methods, namely the top-down and bottom-up approaches, are combined into a coherent algorithm to address this problem. Computational experiments on benchmark test sets show that the approach finds the optimal solution for almost all moderately sized instances and outperforms all existing approaches for larger instances.

Research Area(s)

  • 2D knapsack, Block-building, Cutting and packing, Guillotine-cut

Citation Format(s)