Advances in Operations Research
Volume 2009 (2009), Article ID 732010, 20 pages
doi:10.1155/2009/732010
Research Article

An Exact Method for the 2D Guillotine Strip Packing Problem

Abdelghani Bekrar1 and Imed Kacem2

1Research and Development Department in Algorithmic, DynaSys S.A., Allee de Stockholm, 67300 Schiltigheim, France
2LITA Laboratory, University of Paul Verlaine Metz, Ile du Saulcy, 57000 Metz, France

Received 24 August 2008; Revised 13 January 2009; Accepted 16 April 2009

Academic Editor: Mhand Hifi

Copyright © 2009 Abdelghani Bekrar and Imed Kacem. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We consider the two-dimensional strip packing problem with guillotine cuts. The problem consists in packing a set of rectangular items on one strip of width W and infinite height. The items packed without overlapping must be extracted by a series of cuts that go from one edge to the opposite edge (guillotine constraint). To solve this problem, we use a dichotomic algorithm that uses a lower bound, an upper bound, and a feasibility test algorithm. The lower bound is based on solving a linear program by introducing new valid inequalities. A new heuristic is used to compute the upper bound. Computational results show that the dichotomic algorithm, using the new bounds, gives good results compared to existing methods.