Title | ||
---|---|---|
Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts |
Abstract | ||
---|---|---|
The problem of packing two-dimensional items into two-dimensional bins is considered in which patterns of items allocated to bins must be guillotine-cuttable and item rotation might be allowed (2BP|@?|G). Three new constructive heuristics, namely, first-fit insertion heuristic, best-fit insertion heuristic, and critical-fit insertion heuristic, and a new justification improvement heuristic are proposed. All new heuristics use tree structures to represent guillotine-cuttable patterns of items and proceed by inserting one item at a time in a partial solution. Central to all heuristics are a new procedure for enumerating possible insertions and a new fitness criterion for choosing the best insertion. All new heuristics have quadratic worst-case computational complexity except for the critical-fit insertion heuristic which has a cubic worst-case computational complexity. The efficiency and effectiveness of the proposed heuristics is demonstrated by comparing their empirical performance on a standard benchmark data set against other published approaches. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.cor.2012.07.016 | Computers & OR |
Keywords | DocType | Volume |
best-fit insertion heuristic,new constructive heuristics,new fitness criterion,possible insertion,first-fit insertion heuristic,new heuristics,best insertion,two-dimensional bin packing,critical-fit insertion heuristic,new justification improvement heuristic,new procedure,insertion heuristics,guillotine cut | Journal | 40 |
Issue | ISSN | Citations |
1 | 0305-0548 | 12 |
PageRank | References | Authors |
0.59 | 10 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Krzysztof Fleszar | 1 | 368 | 25.38 |