Heuristics for the variable sized bin-packing problem

We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a l...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2009-10, Vol.36 (10), p.2877-2884
Main Authors: Haouari, Mohamed, Serairi, Mehdi
Format: Article
Language:English
Subjects:
Applied sciences
Bin-packing problem
Comparative analysis
Exact sciences and technology
Flows in networks. Combinatorial problems
Genetic algorithm
Heuristic
Heuristics
Operational research and scientific management
Operational research. Management science
Optimization
Packing problem
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a large set of randomly generated test instances with up to 2000 items and seven bin types. The first contribution of this paper is to provide evidence that a set covering heuristic proves to be highly effective and capable of delivering very-high quality solutions within short CPU times. In addition, we found that a simple subset-sum problem-based heuristic consistently outperforms heuristics from the literature while requiring extremely short CPU times.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2008.12.016