Title: An improved heuristic and an exact algorithm for the 2D strip and bin packing problem

Authors: Abdelghani Bekrar, Imed Kacem, Chengbin Chu, Cherif Sadfi

Addresses: DynaSys, SA, Espace Europeen de l'Entreprise, 3 Allee de Stockholm, F-67300 Schiltigheim, France. ' LITA/UFR M.IM, Universite Paul Verlaine Metz, France. ' Ecole Centrale Paris, Grande Voie des Vignes, 92295 Chatenay Malabry Cedex, France. ' ICD-LOSI, Universite de Technologie de Troyes, 12, Rue Marie Curie, 10010 Troyes, France

Abstract: In this paper, we consider a two-dimensional (2D) packing problem. It consists of packing a given set of rectangular items either into a strip with a fixed width and infinite height or into identical bins. This problem has industrial applications such as cutting glass and Very-Large-Scale Integration (VLSI) design. The guillotine constraint is imposed in this paper. For this problem, we propose some strategies to improve the Shelf Heuristic Filling (SHF) introduced by Ben Messaoud et al. (2003). In a second part, we present a branch-and-bound algorithm for the 2D Strip Packing (2SP) problem that uses a new lower bound and the improved heuristic. All our algorithms are tested on generated and literature-based instances and give good results compared to the existing algorithms.

Keywords: packaging; guillotine constraint; lower bounds; branch-and-bound algorithm; bin packing; 2D strip packing; 2SP; exact algorithm; glass cutting; very-large-scale integration; VLSI design; shelf heuristic filling; SHF; production management; advanced production systems; production design; product development.

DOI: 10.1504/IJPD.2010.029994

International Journal of Product Development, 2010 Vol.10 No.1/2/3, pp.217 - 240

Published online: 03 Dec 2009 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article