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

Volume

2

fYear

2006

Firstpage

940

Lastpage

946

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICSSSM.2006.320758

Filename

4114617