A Comparative Study of Exact Algorithms for the Two Dimensional Strip Packing Problem

نویسندگان
Kacem, Imed ID 1
Bekrar, Abdelghani ID 2
Chu, Chengbin ID 3

1 ICD-LOSI, (CNRS FRE 2848) UNIVERSITE DE TECHNOLOGIE DE TROYES FRANCE

2 ICD-LOSI, (CNRS FRE 2848) UNIVERSITE DE TECHNOLOGIE DE TROYES FRANCE

3 ICD-LOSI, (CNRS FRE 2848) UNIVERSITE DE TECHNOLOGIE DE TROYES FRANCE

doi
چکیده

In this paper we consider a two dimensional strip packing problem. The problem consists of packing a set of rectangular items in one strip of width W and infinite height. They must be packed without overlapping, parallel to the edge of the strip and we assume that the items are oriented, i.e. they cannot be rotated. To solve this problem, we use three exact methods: a branch and bound method, a dichotomous algorithm and a branch and price method. The three methods were carried out and compared on literature instances.

کلیدواژه‌ها
Strip packing, lower and upper bound, Branch and bound, dichotomous search, column generation, branch and price