Feature Column from the AMS

Bin Packing and Machine Scheduling

4. Bin packing and machine scheduling

The branch of mathematics which deals with how to use mathematics in fields outside of mathematics itself is called mathematical modeling. The essence of mathematical modeling is controlled simplification. One takes the situation outside of mathematics, holds onto essential aspects of the problem and disregards "details" that are secondary to the situation. If one is fully successful doing this process, then after the mathematical problem associated with the model is solved, the mathematics can be used to get important insights into the original problem even though significant detail of the original problem was disregarded. To some extent the creation of the mathematics problem known as bin packing grew out of attempts to get insight into problems outside of mathematics.

The range of scheduling problems makes it virtually impossible for one mathematical model to be useful in all situations. In the kind of scheduling problems briefly discussed below, I will use the terms such as "processor," "machine," or "person" to describe the "thing" that does the work. However, sometimes a processor is something more surprising, for example, the runway of an airport. In scheduling the departures of airplanes, each plane needs a certain amount of time on a runway to get off the ground.

In describing scheduling problems we will sometimes refer to identical or parallel machines. Some machines, in fact, are pretty close to identical (but even for identical machines they may have different "ages" and be in different places in their repair cycles when actually used). However, when one has human processors it's rarely the case that they are truly identical. Carpenters are still not cloned but we will treat human processors with a particular expertise as if they have the same skills. This is an example of a modeling assumption.

How is bin packing connected with machine scheduling? Suppose that we have tasks which take differing times to complete which can be performed in any order on identical machines. Our goal is to determine the minimum number of machines needed to finish the tasks by a fixed time. The fixed desired completion time corresponds to the capacity of the bins, and weights can be thought of as the times to do the tasks. When we find the minimum number of bins needed to pack the weights we are finding the minimum number of machines needed to finish by the desired time!

Here is a sample of the many complexities that machine scheduling problems have.

1. A job that must be completed by scheduling the tasks that make up the job often has to be carried out on very different kinds of processors.

Example: To schedule the construction of your dream home requires the completion of a gigantic number of steps. One needs a building permit, someone to lay the foundation, and someone to put on the roof. The "processors" that must be scheduled for doing this work are not interchangeable. Plumbers rarely do electrical work and electricians rarely do roofing.

2 Schedules for the manufacturing of many identical products often require that each product get some time on a fixed number of different machines, where there may be several identical machines of one kind.

Example: Manufacturing a computer chip.

3. When schedules are constructed there are different approaches to how the processors work on the tasks assigned. One approach is that once a processor begins work on a task, that processor continues until the work on that task is complete. Alternatively, there may be conditions under which a processor will be permitted, perhaps even required, to interrupt work on one task to begin another task.

Examples: Whereas in manufacturing once a machine starts work on a task it usually continues to work on it until the task is complete, in medicine things are somewhat different. When doctors schedule patients they typically stay with a patient until the task is done. An exception would be an ophthalmologist who might put drops in a patient's eyes, see another patient while the first patient's pupils are increasing in size, and then return to complete the first patient's examination. Similarly, a doctor in regular practice who is seeing a patient who has a head cold would probably interrupt her work to see a patient who arrived in the office complaining of chest pains.