An Exact Method for the 2D Guillotine Strip Packing Problem

Autor: Abdelghani Bekrar, Imed Kacem
Jazyk: angličtina
Rok vydání: 2009
Předmět:
Zdroj: Advances in Operations Research, Vol 2009 (2009)
Druh dokumentu: article
ISSN: 1687-9147
1687-9155
DOI: 10.1155/2009/732010
Popis: 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.
Databáze: Directory of Open Access Journals
Externí odkaz: