Feature Column from the AMS

Bin Packing and Machine Scheduling

2. Insights into solving hard problems

The one-dimensional bin packing problem belongs to the complexity class of a group of problems for which no known algorithm solves the problems in a polynomial time function (polynomial in the number of weights) of effort. When problems of this kind were discovered (and there are now many with very applied flavors), the next step was to see how badly the various appealing "heuristic algorithms" which might be used to solve them might behave. We can think of a heuristic algorithm (one not always guaranteed to find the optimal solution to a problem) as finding an "approximate" solution to a problem. We can now ask the question: Given a collection of weights and bins of capacity C, how many bins--compared with the optimum number actually required--do these approximation algorithms require? This way of thinking about how badly an algorithm can perform in the worst case was pioneered by Ronald Graham in the context of machine scheduling problems and subsequently applied in the bin packing environment. Suppose we are given weights, a capacity, a list L, and an algorithm A. Denote by OPT(L) the optimum number of bins, and by A(L) the number of bins which are required by algorithm A applied to list L. How do OPT(L) and A(L) compare in size? To answer questions such as this, one can apply mathematical arguments to show that:

where r is some positive constant. One can then try to show by way of examples that the "r" in the equation above can actually occur. Many researchers in mathematics and computer science have contributed to insights in this vein for the literally dozens of different algorithms that have been investigated to understand one-dimensional bin packing.

To illustrate the idea above in one of the simplest cases, suppose we are dealing with the heuristic NF, Next Fit (note that this and some other terms used subsequently were defined in last month's column Bin Packing). It is not difficult to see that Next Fit obeys:

In the case where the capacity of the bins is 1, two consecutive bins that are packed by Next Fit can not both be filled to less than the halfway mark. The reason is that the contents of two such bins would then fit in only one of the bins, because of the way Next Fit fills the bins. The proof of the inequality above uses this fact. For a further insight, consider the following list of weights for the case where the bins have capacity 1:

L = (1/2, 1/2N, 1/2, 1/2N, ...., 1/2)

where N is a positive integer which is 2 or bigger. NF applied to this list will produce a packing which has 2N bins, each bin packed with an item of weight 1/2 at the bottom and an item of weight 1/2N on top. However, the optimal packing for this list uses N + 1 bins: N bins, each with two weights of size 1/2, and one additional bin to contain the N items of size 1/2N. Below are some diagrams to help visualize the packing which is optimal versus what happens when NF is used. (The optimal packing has N copies of the one bin pictured on the far left and one copy of the next bin. The NF packing has 2N copies of the bin on the far right. The blue denotes unused space.)

Next Fit can be as bad as about twice optimal

This analysis shows that we have a family of lists for which

Over a period of about 30 years, researchers have examined a wide variety of variants of bin packing algorithms and obtained increasingly better worst case analyses of the different algorithms. For example, First Fit does significantly better than NF but not spectacularly so:

where , the ceiling function, denotes the smallest integer greater than or equal to y. One can construct a family of lists that show that this bound is the best (asymptotically). Furthermore, examining examples for which particular algorithms do not perform well often provides clues for finding improved algorithms.

Intuitively, one would expect the "decreasing" heuristics to work better and this turns out to be the case. For First Fit Decreasing we have the result:

In addition to analyzing the worst-case performance of bin packing algorithms, one can also see how different heuristics perform on the average. Initially, doing simulations sometimes only hints at results. However, insights gleaned from these simulations often lead to probability models in which precise results can be obtained.