81

In a society as complex as ours, everyday problems such as providing services efficiently and on time require accurate planning of both people and machines. Take the example of a medical center in a major city. Around-the-clock scheduling of nurses, doctors, and emergency room staff must be provided to guarantee that people with particular expertise are available during each shift. The operating rooms must be scheduled in a manner flexible enough to deal with emergencies and scheduled procedures. Equipment used for X-ray, CT, or MRI scans must be in good working order and scheduled for maximum efficiency.

82

Although many scheduling problems are often solved on an ad hoc basis, we can also use mathematical ideas to gain insight into the complications that arise in scheduling. The ideas we develop in this chapter have practical value in a relatively narrow range of applications, but they shed light on many characteristics of more realistic, and hence more complex, scheduling problems.