A Branch and Bound Algorithm for solving the 2D Strip Packing Problem - Université de technologie de Troyes Access content directly
Conference Papers Year :

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
Not file

Dates and versions

hal-02473352 , version 1 (10-02-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
22 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More