Heuristics for Two-Dimensional Bin-Packing Problems
| Autor: | Tak Ming Chan, J. M. Valério de Carvalho, Elsa Silva, Filipe Pereira e Alvelos |
|---|---|
| Přispěvatelé: | Universidade do Minho |
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
Sequence Engineering drawing 021103 operations research Theoretical computer science Computer science business.industry Bin packing problem Aggregate (data warehouse) 0211 other engineering and technologies Two dimensional bin packing and cutting stock problems 02 engineering and technology STRIPS law.invention 020901 industrial engineering & automation Operator (computer programming) 2D rectangular SBSBPP Guillotine law Software system business Heuristics Graphical user interface |
| Zdroj: | Intelligent Systems ISBN: 9781315218427 |
| DOI: | 10.1201/9781315218427-27 |
| Popis: | 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. (undefined) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|