Bin Packing and Machine Scheduling
Posted June 2004.
As you listen to yet another advertisement as part of a block of ads "interrupting" your favorite TV show, do you have a sense of wonder that so many ads will fit into the allotted time? Perhaps it's because mathematics was put to use. Packing ads into breaks is an example of a bin packing problem. In this case, packing a collection of ads of different lengths into the minimum number of bins of fixed size (the length of the ad break). There are many problems which have the flavor of putting weights into bins of fixed size; the goal is to find the smallest number of bins into which the weights will fit.
Waiting is another frustration of modern life. We wait for trains and buses and to get our blood taken for a medical test. However, when good schedules have been designed, the waiting can be minimized. Scheduling problems are omnipresent in the operation of all large systems: scheduling classes and finals in schools; scheduling planes, trains, and buses in the transportation sector of the economy; and scheduling machines in the manufacture of the products that we use for everyday life. Machine scheduling may not seem to have much to do with mathematics or bin packing. However, mathematics has offered profound insights into scheduling problems and saved organizations and governments huge sums of money. Mathematics can also be used to save individual people and machines huge amounts of time!
York College (CUNY)
- Insights into solving hard problems
- Applications of bin packing
- Bin packing and machine scheduling
- The list processing algorithm for machine scheduling