Modi ed strip packing heuristics for the rectangular variable-sized bin packing problem

Abstract

Two packing problems are considered in this paper, namely the well-known strip packing problem (SPP) and the variable-sized bin packing problem (VSBPP). A total of 252 strip packing heuristics (and variations thereof) from the literature, as well as novel heuristics proposed by the authors, are compared statistically by means of 1 170 SPP benchmark instances in order to identify the best heuristics in various classes. A combination of new heuristics with a new sorting method yields the best results. These heuristics are combined with a previous heuristic for the VSBPP by the authors to nd good feasible solutions to 1 357 VSBPP benchmark instances. This is the largest statistical comparison of algorithms for the SPP and the VSBPP to the best knowledge of the authors.

Key words: Packing problems, heuristics.