Bin Packing (9/17/2004)
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451
Email: email@example.com (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.
bin 1 bin 2 bin 3 bin 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.)
Here is a problem that will give you a chance to check that you understand
the 8 different algorithms.
Items to pack:
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!
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 and Machine Scheduling
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).
Back to list of tidbits