A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts

A new heuristic algorithm for solving the two-dimensional bin-packing problem with guillotine cuts (2DBP vertical bar*vertical bar G) is presented. The heuristic constructs a solution by packing a bin at a time. Central to the adopted solution scheme is the principle of average-area sufficiency proposed by the authors for guiding selection of items to fill a bin. The algorithm is tested on a set of standard benchmark problem instances and compared with existing heuristics producing the best-known results. The results presented attest to the efficacy of the proposed scheme. (c) 2010 Elsevier Ltd. All rights reserved.