ABSTRACT
Let a1, . . . , an be a given collection of items with sizes s (ai ) > 0, 1 ≤ i ≤ n. In mathematical terms, bin packing is a problem of partitioning the set {ai } under a sum constraint: Divide {ai } into a minimum number of blocks, called bins, such that the sum of the sizes of the items in each bin is at most a given capacity C > 0. To avoid trivialities, it is assumed that all item sizes fall in (0, C]. Research into bin packing and its many variants, which began some 35 years ago [1,2], continues to be driven by a countless variety of applications in the engineering and information sciences. The following examples give an idea of the scope of the applications:
• (Stock cutting) Lumber with a fixed cross section comes in a standard board C units in length. The items are demands for pieces that must be cut from such boards. The objective is to minimize the number of boards (bins) used for the pieces {ai }, or equivalently, to minimize the trim loss or waste (the total board length used minus the sum of the s (ai )). It is easy to see that this type of application extends to industries that supply cable, tubing, cord, tape, and so on from standard lengths.
