Bin Packing and Machine Scheduling
3. Applications of bin packing
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.
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.
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
Comments: Email Webmaster