next up previous contents index CD CD Algorithms
Next: Medial-Axis Transformation Up: Computational Geometry Previous: Intersection Detection

Bin Packing



Input description: A set of n items with sizes tex2html_wrap_inline30248 . A set of m bins with capacity tex2html_wrap_inline30250 .

Problem description: How can you store all the items using the smallest number of bins?

Discussion: Bin packing arises in a variety of packaging and manufacturing problems.     Suppose that you are manufacturing widgets with parts cut from sheet metal, or pants with parts cut from cloth. To minimize cost and waste, we seek to lay out the parts so as to use as few fixed-size metal sheets or bolts of cloth as possible. Identifying which part goes on which sheet in which location is a bin-packing variant called the cutting stock problem.   After our widgets have been successfully manufactured, we will be faced with another bin packing problem, namely how best to fit the boxes into trucks to minimize   the number of trucks needed to ship everything.

Even the most elementary-sounding bin-packing problems are NP-complete (see the discussion of integer partition in Section gif),   so we are doomed to think in terms of heuristics instead of worst-case optimal algorithms.   Fortunately, relatively simple heuristics tend to work well on most bin-packing problems. Further, many applications have peculiar, problem-specific constraints that would frustrate highly tuned algorithms for the problem. The following factors will affect the choice of heuristic:

The standard heuristics for bin packing order the objects by size or shape (or in an on-line problem, simply the order they arrive in) and then insert them into bins. Typical insertion rules include (1) select the first or leftmost bin the object fits in, (2) select the bin with the most room, (3) select the bin that provides the tightest fit, or (4) select a random bin.

Analytical and empirical results suggest that the best heuristic is first-fit, decreasing.   Sort the objects in decreasing order of size, so that the biggest object is first and the smallest last. Insert each object one by one into the first bin that has room for it. If no bin has room for it, we must start another bin. In the case of one-dimensional bin packing, this can never require more than 22% more bins than necessary and usually does much better. First-fit decreasing has an intuitive appeal to it; we pack the bulky objects first and hope that the little objects can be used to fill up the cracks. First-fit decreasing is easily implemented in tex2html_wrap_inline30252 time, where tex2html_wrap_inline30254 is the number of bins actually used, by doing a linear sweep through the bins on each insertion. A faster tex2html_wrap_inline30256 implementation is possible by using binary tree to keep track of the space remaining in each bin.

We can fiddle with the insertion order in such a scheme to deal with problem-specific constraints. For example, it is reasonable to take ``do not stack'' boxes last (perhaps after artificially lowering the height of the bins to give some room up top to work with) and to place fixed-orientation boxes at the beginning (so we can use the extra flexibility later to stick boxes into cracks).

Packing boxes is much easier than packing arbitrary geometric shapes, enough so that a reasonable approach for general shapes is to pack each part into its own box and then pack the boxes. Finding an enclosing rectangle for a polygonal part is easy; just find the upper, lower, left, and right tangents in a given orientation.   A minimum-area enclosing rectangle can be found by determining the orientation that leads to the smallest box.

In the case of nonconvex parts, considerable useful space can be wasted in the holes created by placing the part in a box.     One solution is to find the maximum empty rectangle within each boxed part and use this to contain other parts if it is sufficiently large. More advanced solutions are discussed in the references.

Implementations: Codes for the one-dimensional version of bin packing, the so-called knapsack problem, are presented in Section gif.

XTango (see Section gif)   includes an animation of the first-fit bin packing heuristic.   Test data for bin packing is available from

Notes: See [CGJ96] for a survey of the extensive literature on approximation algorithms for bin packing. Expositions on heuristics for bin packing include [Baa88]. Experimental results on bin-packing heuristics include [BJLM83].

Sphere packing is an important and well-studied special case of bin packing, with applications to error-correcting codes. Particularly notorious is the ``Kepler conjecture,'' the apparently still-open problem of establishing the densest packing of unit spheres in three dimensions. Conway and Sloane [CS93] is the best reference on sphere packing and related problems. Sloane provides an extensive set of tables of the best known packings, available from    

Victor Milenkovic and his students have worked extensively on two-dimensional bin-packing problems for the apparel industry, minimizing the amount of material needed to manufacture pants and other clothing.   Recent reports of this work include [DM97, Mil97].

Related Problems: Knapsack problem (see page gif), set packing (see page gif).    

next up previous contents index CD CD Algorithms
Next: Medial-Axis Transformation Up: Computational Geometry Previous: Intersection Detection

Mon Jun 2 23:33:50 EDT 1997