An Exact Algorithm for the Two-Dimensional Strip-Packing Problem

Marco Antonio Boschetti () and Lorenza Montaletti ()
Additional contact information
Marco Antonio Boschetti: Department of Mathematics, University of Bologna, 47023 Cesena, Italy
Lorenza Montaletti: Department of Mathematics, University of Bologna, 47023 Cesena, Italy

Operations Research, 2010, vol. 58, issue 6, 1774-1791

Abstract: This paper considers the two-dimensional strip-packing problem (2SP) in which a set of rectangular items have to be orthogonally packed, without overlapping, into a strip of a given width and infinite height by minimizing the overall height of the packing. The 2SP is NP-hard in the strong sense and finds many practical applications. We propose reduction procedures, lower and upper bounds, and an exact algorithm for the 2SP. The new lower bounds are both combinatorial bounds and bounds derived from different relaxations of mathematical formulations of the 2SP. The new upper bounds are obtained by constructive heuristics based on different strategies to place the items into the strip. The new exact method is based on a branch-and-bound approach. Computational results on different sets of test problems derived from the literature show the effectiveness of the new lower and upper bounds and of the new exact algorithm.

Keywords: production/scheduling; cutting stock/trim; programming; integer; algorithms; branch and bound (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0833 (application/pdf)

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:inm:oropre:v:58:y:2010:i:6:p:1774-1791

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().