## Bin Packing
Example 1:Suppose we have bins of size 10. How few of them are required to store weights of size 3, 6, 2, 1, 5, 7, 2, 4, 1, 9? The weights to be packed above have been presented in the form of a list L ordered from left to right. For the moment we will seek procedures (algorithms) for packing the bins that are "driven" by a given list L and a capacity size C for the bins. The goal of the procedures is to minimize the number of bins needed to store the weights.A variety of simple ideas as to how to pack the bins suggest themselves. One of the simplest approaches is called Next Fit (NF). The idea behind this procedure is to open a bin and place the items into it in the order they appear in the list. If an item on the list will not fit into the open bin, we close this bin permanently and open a new one and continue packing the remaining items in the list. Of course, if some of the consecutive weights on the list exactly fill a bin, the bin is then closed and a new bin opened. When this procedure is applied to the list above we get the packing shown below. The bins are displayed here, and in the similar procedures we will develop later, from left to right. If you wish, you can think of the leftmost bin as being numbered 1, the next one 2, etc. The blue in the diagram is the amount of room in each bin which remains vacant or empty.
The appealing thing about Next Fit is that it is very simple and, in certain applied settings of the bin packing problem, it allows for bins to be shipped off quickly, because even if there is some extra room in a bin, we do not wait around in the hope that an item will come along later in the list which will fill this empty space. One can imagine having a fleet of trucks with a weight restriction (the capacity C) and one packs weights into the trucks. If the next weight can not be packed into the truck at the loading dock, this truck leaves and a new truck pulls into the dock. As Next Fit is carried out all that is required is that we keep track of how much room remains in the bin open at that moment. In terms of how much time is required to find the number of bins for
So far, both methods we have tried have yielded 5 bins. We know that this is not the best we can hope for. One simple insight is obtained by computing the total sum of the weights and dividing this number by the capacity of the bins. Since we are dealing with integers, the number of bins we need must be at least where . (Note that denotes the smallest integer that is greater than or equal to
For Worst Fit, one places the item into that currently open bin into which it will fit with the most room left over. You should verify that Best Fit will give the same packing as the First Fit packing and Worst Fit packing the same as the Next Fit packing, though in general this will not always be true. Note that in Example 1, the fact that such a large weight item (weight 9) occurred as the last item in the list, was unforgiving in trying to use the given list to pack the items. In terms of tradeoffs with Next Fit, the amount of time necessary to find the minimum number of bins using either FF, WF or BF is higher than for NF. What is involved here is Edward Coffman, Jr. Michael Garey Ronald Graham David Johnson Interestingly, at various times in their careers all of these men worked in the communications industry, typically as researchers in a think-tank environment. They have not only excelled as scholars but as administrators and group leaders of research teams. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |