Bin Packing (9/17/2004)



Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)



Imagine that you have identical bins, say, of size or capacity 10. You also have items of different sizes that are to be packed into these bins . Obviously, unless all the items to be packed have size at most 10 we can not carry out the process. We are given a large collection of such bins but they are expensive, so we would like to carry out the packing of the items into the bins in a way which uses as few bins as possible. This type of problem is known as bin packing .

Can you think of situations which require solving problems of this kind? Examples include making wooden bookcases by making cuts of different lengths from (costly) boards of a fixed length, packing advertisements of different lengths into fixed length station breaks on radio or television, or taking a large number of pieces of music of different time lengths and recording them on tape cassettes or (audio) compact discs which allow for a fixed amount of recording time. In the last example, the capacity of the bins might be cassettes with 60 minutes of recording time and one might have pieces with times (in minutes) of: 12, 16, 23, 31, 25, 27, 9, 11, 15, 7, 52, 48, 25, 43, 26, 4, 4, 5, 5, 7, 7, 34, and 32. What is the minimum number of cassettes needed to record all the music?


How does one solve bin packing problems? One way would be to use trial and error. This involves trying different clusters of items and checking whether or not they fit into the bins. This might be acceptable if one only required the solution of a few problems of this type. However, if one has thousands of such problems to solve, one needs a systematic method of solving them, ideally a method that is suitable for solution on a computer. Such methods of solving problems are known as algorithms. An algorithm for a problem is a step-by-step description of how to solve problems of a particular type that terminates with an answer in a finite amount of time.

What might an algorithm for solving bin packing problems be? The items to be packed are typically given to us in a list. Using this list we would like to develop an algorithm or procedure which systematically tells us how to go about packing the items as given in the list into the bins, rather than trying to pack them using trial and error:

Here are examples of such procedures. When the addition of an item just fills a bin, that bin is closed. It is convenient to think of the bins as having numbers starting at 1. (Since the bins are displayed vertically, as the items are placed in the bins they fill the bins up from bottom to top.)

1. Next fit: Place the next item in the list into the current bin if it fits; if it does not, close the current bin (though it may not be full) and start a new bin.

2. First fit: Place the next item in the list into the lowest numbered bin that it will fit into. If it will not fit into any bin, open a new one for it.

3. Worst fit: Place the next item in the list into that bin which will leave the largest amount of room left over after the item is placed in the bin. (Here is where being able to subtract comes in handy.)

4. Best fit: Place the next item in the list into that bin which will leave the least room left over after the the item is placed in the bin.

Here is an example that will help illustrate the idea:

Pack 8, 5, 7, 6, 2, 4, 1 into bins of capacity 10, using next fit, first fit, worst fit, and best fit. In the diagrams below, space without a number label is empty space in the bin.


Next fit:





bin 1               bin 2                 bin 3           bin 4           bin 5


Figure 1

First fit:




Figure 2


Worst fit:



Figrue 3

Best fit:



Figure 4


In this particular example, it is not difficult to see that one can not pack these items in fewer than 4 bins and, thus, we have achieved several different optimal packings. (If one add the values of the items to be packed: 8 + 5 + 7 + 6 + 2 + 4 + 1 one gets 33. Now 33 divided by 10 is 3.3 which means that one can not possibility pack these items into only 3 bins.) In general, there is no guarantee that any of these 4 algorithms will yield an optimal solution. (In fact, it is fun to produce examples which show that for a particular list which one might create, next fit, say, yields an optimal solution, while the other three methods do not. This is the type of "entertainment" that mathematicians enjoy!) It may surprise you to learn that no one knows any procedure (algorithm) for solving bin packing problems that always guarantees a minimum number of bins and that is fast and easy to carry out. (One can always try all the different possibilities, "brute force," to obtain an answer, but this is not practical for even modest sized problems because it would take too long.)

In our discussion of the four procedures above, although next fit requires more bins, it does not require as much memory (human or computer), since it is not necessary to keep track of how much space is left in many bins, since one only examines one bin at a time. This is a "baby" example. Realistic examples might have millions of items to pack into hundreds or thousands of bins, and for such problems the trade off between time and space issues (using memory to keep track of how much room is left in the many partially filled bins) can be significant.

If you experiment with problems similar to this one and with different sized bins and longer lists of items to pack, you will notice a problem that often occurs. Large or medium size items occurring late in a list are hard to pack since there is little room left over in the partially filled bins to accommodate them. This suggests a different approach to solving bin packing problems. First sort the items in the list in decreasing order (i.e. largest items down to smallest items) and then use one of the four algorithms described above, using the newly generated decreasing time list. Sorting numbers by size is something 2nd graders should practice. Bin packing provides a meaningful context. (The sorted list for the problem above is: 8, 7, 6, 5, 4, 2, 1.) This gives rise to four new algorithms: next fit decreasing, first fit decreasing, worst fit decreasing and best fit decreasing. Usually, this approach will use fewer bins (but not always!) but there is a price to pay. One needs to sort what are sometimes very long lists first, which can be time consuming. (Is the trade-off between the extra time to sort worth the fact that often fewer bins will be needed?) Although first fit or best fit decreasing do not always give optimal answers, there work remarkably well on most problems.

I began this discussion with commenting on the role mathematics is playing in scheduling problems. Though some of the many applications of bin packing were mentioned above, what does bin packing have to do with scheduling?

Machine Scheduling Independent Tasks

The problem of scheduling processors to accomplish a collection of tasks is extremely complicated, even in the simple case we look at here, where the processors are all identical. Some of the complications that are involved are that the tasks may have a complex collection of requirements for the order in which they can be done. For example, before one can put up the walls of a house, the foundation must be poured. In some rare cases, however, the tasks are independent of one another, and, thus, can be scheduled in any order whatsoever. (One example is processing jobs at a photocopy shop after the shop has closed for the day, and all jobs are to be finished by the morning.) Suppose we have a collection of independent tasks (each requiring a specific amount of time) which we would like to schedule so that they are completed by a fixed time W. We can think of this problem as a bin packing problem!. The items to be packed are the tasks with their different times to accomplish, and the bins play the role of the processors. The fact that each processor must finish no later than a particular time corresponds to the (fixed) capacity of the bins. The goal is to find the minimum number of bins that will be required, which corresponds in the scheduling context to finding the minimum number of machines necessary to finish all the tasks by the fixed time W (the capacity of the bins.)

Practice:

Here is a problem that will give you a chance to check that you understand the 8 different algorithms.

Items to pack:

6,6,5,5,5,4,4,4,4,2,2,2,2,3,3,7,7,5,5,8,8,4,4,5

Bin size: 10


(Partial answers: next fit 14 bins; first fit 14 bins; worst fit 14 bins; first fit decreasing 11 bins.) 11 bins is optimal.

Experiments: (If you have children at home who are in higher grades you might encourage them to read these notes and try out these questions.)

1. Once you have mastered the 8 algorithms involved you can try experiments with other bin sizes. What happens when the bin size is 9? What happens when the bin size is 11? Experiments of these kinds provide interesting practice at arithmetic, estimation (will the number of bins go up or down when the bin size is changed from 10 to 9 or 11, and can you estimate by how much?), and logical thinking.

2. If you double the capacity of the bins will you halve the number of bins necessary?

3. If you halve the capacity of the bins will you double the number of bins necessary? (Can you always carry out the packing in this case?)

4. Can you find an example where next fit requires fewer bins than first fit?
Can you find an example where first fit requires fewer bins than next fit?

5. Can you find an example where first fit requires fewer bins than worst fit?
Can you find an example where worst fit requires fewer bins than first fit?

6. Try making up a few problems of your own and exploring new algorithms of your invention to solve bin packing!
References:
1. Graham, R., Combinatorial scheduling theory. In Lynn Steen (ed.), Mathematics Today, Springer-Verlag, New York, 1978.

2. Graham, R., The combinatorial mathematics of scheduling, Scientific American, March, 1978, pp. 124-132.

3. Malkevitch, J., (et al.), For All Practical Purposes, 4th edition (also earlier editions), W.H. Freeman, New York, 1997, pp. 102-106.


Some additional information can be found at:

Bin Packing

Bin Packing and Machine Scheduling


Acknowledgement

Thanks to Sunil Roy for pointing out an error in an earlier version.

Some of this work was prepared with partial support from the National Science Foundation (Grant Number: DUE 9555401) to the Long Island Consortium for Interconnected Learning (administered by SUNY at Stony Brook, Alan Tucker, Project Director).





Figure 5

Back to list of tidbits