Did you ever arrive to catch a plane and discover that the gate had closed seconds before your arrival, or, more mundanely, arrive at the supermarket to do some last-minute shopping only to discover that the store was closed? Both people and businesses are often penalized when they run behind schedule. On the other hand, in some cases there is a bonus for work that is completed ahead of schedule. This is often done for work involving repairs after some infrastructure failure. Perhaps if a section of roadway collapses after an earthquake, the company repairing the road will get extra money if it completes the work before the estimated completion time.
Scheduling problems, figuring out how to complete a complex job by carrying out its constituent tasks on various processors (which can be thought of as machines, people, robots, etc.), can be exceedingly complex. Just think what is necessary to schedule the services and employees at a hospital, high school, or university. All of these environments have many kinds of tasks to schedule, many kinds of processors to schedule the tasks, and often uncertainties about how much time the various tasks require on the different processors. Earlier we looked at ways that mathematics has been used to get insights into such machine scheduling problems and the way that bin packing is related to these issues.
Mathematics often attacks complex problems via mathematical modeling, the process of controlled simplification. One dramatic simplification might be to consider the case where there is only one machine to schedule. In this situation every task must be scheduled on one single machine. It might seem at first glance that there is not much to say about scheduling tasks on a single machine. Do you agree?