2. Basic ideas
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 n weights, one can answer the question using a procedure that takes a linear amount of time in the number of weights (n). Clearly, NF does not always produce an optimal packing for a given set of weights. You can verify this by finding a way to pack the weights in Example 1 into 4 bins. Procedures such as NF are sometimes referred to as heuristics or heuristic algorithms because although they were conceived as ways to solve a problem optimally, they do not always deliver an optimal solution. Can we find a way to improve on NF so as to design an algorithm which will always produce an optimal packing?
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 x). Clearly, the number of bins must always be an integer. In Example 1, since is 40 and C is 10, we can conclude that there is hope of using only 4 bins. However, neither Next Fit nor First Fit achieves this value with the list given in Example 1. Perhaps we need a better procedure.
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 n log n implementation time in terms of the number n of weights.
Edward Coffman, Jr.
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