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

Lijun Wei and Andrew Lim

European Journal of Operational Research, 2015, vol. 242, issue 1, 63-71

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.

Keywords: Cutting and packing; Guillotine-cut; 2D knapsack; Block-building (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171400808X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:242:y:2015:i:1:p:63-71

DOI: 10.1016/j.ejor.2014.10.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().