Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/15900

TitleHeuristics for two-dimensional bin-packing problems
Author(s)Chan, Tak Ming
Alvelos, Filipe Pereira e
Silva, Elsa
Carvalho, J. M. Valério de
KeywordsTwo dimensional bin packing and cutting stock problems
2D rectangular SBSBPP
Guillotine
Issue date2011
PublisherCRC Press
Abstract(s)This paper proposes a heuristic with stochastic neighborhood structures (SNS) to solve two-stage and three-stage two-dimensional guillotine bin packing and cutting stock problems. A solution is represented as a sequence of items which are packed into existing or new stacks, shelves or bins according to previously defined criteria. Moreover, SNS comprises three random neighborhood structures based on modifying the current sequence of items. These are called cut-and-paste, split, and swap blocks and are applied one by one in a fixed order to try to improve the quality of the current solution. Both benchmark instances and real-world instances provided by furniture companies were utilized in the computational tests. Particularly, all benchmark instances are bin packing instances (i.e. the demand of each item type is small), and all real-world instances are classified into bin packing instances and cutting stock instances (i.e. the demand of each item type is large). The computational results obtained by the proposed method are compared with lower bounds and with the solutions obtained by a deterministic Variable Neighborhood Descent (VND) meta-heuristic. The SNS provide solutions within a small percentage of the optimal values, and generally make significant improvements in cutting stock instances and slight to moderate improvements in bin packing instances over the VND approach.
TypeBook part
URIhttp://hdl.handle.net/1822/15900
ISBN978-1439-8028-30
Peer-Reviewedyes
AccessRestricted access (UMinho)
Appears in Collections:LES/ALG - Capítulos de livros

Files in This Item:
File Description SizeFormat 
Heuristics for two-dimensional bin-packing problems.pdf
  Restricted access
1,17 MBAdobe PDFView/Open    Request a copy!

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID