Skip to Main content Skip to Navigation
Conference papers

A Branch and Bound Algorithm for solving the 2D Strip Packing Problem

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
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02473352
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, February 10, 2020 - 4:38:30 PM
Last modification on : Sunday, May 24, 2020 - 1:22:01 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Abdelghani Bekrar, Imed Kacem, Chengbin Chu, Cherif Sadfi. A Branch and Bound Algorithm for solving the 2D Strip Packing Problem. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.940-946, ⟨10.1109/ICSSSM.2006.320758⟩. ⟨hal-02473352⟩

Share

Metrics

Record views

38