View article

This paper updates a survey [53J written about 3 years ago. All of the results mentioned there are covered here as well. However, as a major justification for this second edition we shall be presenting many new results, some of which represent important advances. As a measure of the impressive amount of research in just 3 years, the present reference list more than doubles the list in [53].

Characteristic of bin-packing applications is the necessity to pack or fit a collection of objects into well-defined regions so that they do not overlap. From an engineering point of view the problem is normally one of making efficient use of time and/or space. A basic mathematical model is defined in the classical one-dimensional bin packing problem: We are given a positive integer bin capacity C and a set or list of items L-(P\, P2,..., Pn), each item Pi having an integer size s (Pi) satisfying 0<; S (Pi)<; C. What is the smallest integer m …