 An improved heuristic and an exact algorithm for the 2D strip and bin packing problemAbdelghani Bekrar, Imed Kacem, Chengbin Chu and Cherif Sadfi International Journal of Product Development, 2010, vol. 10, issue 1/2/3, 217-240 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. (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:ids:ijpdev:v:10:y:2010:i:1/2/3:p:217-240 Access Statistics for this article More articles in International Journal of Product Development from Inderscience Enterprises Ltd |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.