Feature Column from the AMS

Bin Packing and Machine Scheduling

3. Applications of bin packing

Many applications of bin packing come to mind. For example, placing computer files with specified sizes into memory blocks of fixed size, or the recording of all of a composer's music, where the length of the pieces to be recorded are the weights and the bin capacity is the amount of time that can be stored on an audio CD (about 80 minutes). One power of mathematics is that, having abstracted the problem of packing bins with weights, there are many situations to which the mathematical techniques apply. So that once we have, say, the First Fit heuristic, it can be used in these different situations. We can now go out and look for problems where bin packing and the algorithms which have been developed to get insights into this problem can be put to use. However, applying mathematics originally developed in one context to other applications contexts which have "additional aspects" to them, encourages one to improve on the mathematics that has been done already.

Take, for example, the problem of preparing a collection of musical pieces to store on audio compact discs. An audio CD has a maximal capacity; in that regard it follows the bin packing model. The pieces one wants to put on the compact discs play the roles of the weights, and one would not want to have a piece start on one compact disc and finish on another. But there is a subtlety here. Classical music pieces often come in sections called movements. Although ideally one would prefer to have whole pieces on each CD, to keep costs down and give consumers more value for their money, it might be "acceptable" to have, say, the first three movements of a symphony on one CD and the last movement at the beginning of the next CD. If we just treat the weights as movements, we can not guarantee that all of the heuristics which might be applied to fitting the music onto the compact discs would respect the fact that the weights which correspond to the movements of a piece must be packed in order of the movements. This additional constraint on the problem might inspire one to find specialized algorithms for solving bin packing problems where some of the weights need to be packed in a particular order.

Inspired by various "packing" situations here are a variety of "extensions" of the original bin packing model that might surface:

a. Packings in which the number of items that can be placed in a bin is restricted in advance not to exceed a certain number.

This restriction might be required in the situation where one is packing trucks.

b. Restrictions on items which can be placed into the same bin.

This restriction might come about if items are being shipped from A to B in bins. In order to guarantee that if one bin gets lost or destroyed in transit to B, one could send redundant items and require that they not be packed in the same bin.

An alternate scenario is that the items being packed may be generating heat, perhaps because they have some level of radioactivity. Now one desires that the items in one bin not only fit in the bin but that the items not generate too much heat during the period they are in the bins.

c. Packings in which there is an ordering attached to some of the weights which limits the way those items can be packed.

This restriction is in the sprit of the example discussed in a little detail above where music is being packed into compact discs of the same size.

d. Packings in which the items being packed may be allowed to disappear during the packing process.

Thus, an item placed in a bin which has not yet been closed may be allowed to be removed from the bin either because fewer bins will be needed once this item is transferred to another bin, or because sometimes items not only enter the system but also leave the system.

Here is a scenario which offers a potential applications environment for this variant of bin packing. Imagine that when items are packed, a test is started to determine if the item which has been packed has spoiled. This test takes a certain amount of time to complete. If the packed item is put into a bin which is closed before the testing period is done, the packed bin is just shipped out. However, if the bin is still open during the period of packing and the finished test shows the item to have spoiled, then this item can be removed and the space used for items that haven't spoiled.

With cleverness one can perhaps find additional unexpected uses here.

One interesting variant of the bin packing problem involves a loosening of the requirement that all the bins have the same size. Suppose that we have bins of a standard capacity or size, say 1, and we think of this capacity also as having a cost of 1. Suppose that we can occasionally imagine that bins are stretched or enlarged but we must pay a penalty for doing this. The penalty or cost takes the form that a bigger bin is used. The goal is to pack the weights into stretched bins if necessary so that the total cost is a minimum. In the standard one-dimensional bin packing problem the bins are assumed to have the same size, but you may enjoy formulating a variety of problems with a limited number of sizes for bins where one wants to pack the weights so that the total size of the bins used is as small as possible. You may also want to think up applied situations were problems such as these might arise.

Another variant which uses the word bin but is in many ways quite far from the classical bin packing problem has to do with the common phenomenon of recycling bins. For simplicity we will assume that we have a collection of bins which contain three types of glass: clear, brown, and frosted. The goal is to sort the different kinds of glass so that after the sorting process one bin has only clear glass, one only brown glass, and one only frosted glass. (We do not specify which of the bins is to have which kind of glass, but one can imagine another variant where the bins are specified beforehand.) The goal of the problem is to conduct the sorting with as few moves as possible.