Title :
A Branch and Bound Algorithm for solving the 2D Strip Packing Problem
Author :
Bekrar, Abdelghani ; Kacem, Imed ; Chu, Chengbin ; Sadfi, Chérif
Author_Institution :
ICD-LOSI, Universit de Technologies de Troyes
Abstract :
In this paper we consider the two dimensional strip packing problem with guillotine cuts. The problem consists on 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). For this problem, we give a new lower bound based on decomposing the set of the items in sub-sets. This lower bound is used in a branch and bound algorithm to solve the problem to optimality. Computational results are presented to show the performance of both the lower bound and the exact algorithm
Keywords :
bin packing; computational complexity; optimisation; tree searching; 2D strip packing problem; branch and bound algorithm; combinatorial optimization problem; guillotine constraint; guillotine cuts; lower bound; Approximation algorithms; Strips; Testing; Textile industry; Upper bound; Branch and bound; Guillotine cuts; Lower Bound; Strip packing;
Conference_Titel :
Service Systems and Service Management, 2006 International Conference on
Conference_Location :
Troyes
Print_ISBN :
1-4244-0450-9
Electronic_ISBN :
1-4244-0451-7
DOI :
10.1109/ICSSSM.2006.320758
