3. More approaches to bin packing
In contrast to an on-line point of view is the possibility of using an off-line approach. When thinking of the bin packing problem from an off-line point of view, one thinks of having all of the items to be packed in advance. Thus, one can consider other types of approaches to packing the items. In particular, one can ask for the given weights to be packed if there is some rearrangement of the weights into a list different from the original which might be used to give a better result for the number of bins required. If there are n items to pack, the number of potential lists for these n items is n!, since the first item can be chosen in n ways, the second in n-1, etc., giving n! as the number of different possible lists. Intuitively, since given a packing we typically find a list which would have given rise to this packing for a particular packing algorithm, we see that choosing a list for an optimal packing has the flavor of looking for a needle in a haystack. (Even for 20 items to pack, say, 20! is a very large number.)
We have already discussed four packing algorithms: NF, FF, BF, and WF and we now have four new approaches which we will call NFD, FFD, BFD, and WFD where in each case the "D" refers to decreasing. For example, FFD means First Fit Decreasing, and would give rise to the packing for the weights in Example 1 shown below. Note that this packing is optimal.
Not only can one not pack these weights into fewer bins but also there is no wasted space. Of course, there are many situations where optimal packings still have unused space. Among all packings of this kind one might look for that packing with various characteristics, say, that the fewest bins have extra space. Alternatively, one might want a packing where the number of bins used is minimal but as many bins as possible have some extra room. (A little extra space might allow putting packing material into the bin to prevent breakage during shipment.) Note also that once one has an optimal packing, one can often either rearrange the items in one of the bins or between bins in a way that achieves some secondary goal beyond minimizing the number of bins.
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