ABSTRACT
Scheduling theory is concernedwith the optimal allocation of scarce resources to activities over time. The practice of this field dates to the first time two humans contended for a shared resource and developed a plan to share it without bloodshed. The theory of the design of algorithms for scheduling is younger, but still has a significant history-the earliest papers in the field were published more than forty years ago. Scheduling problems arise in a variety of settings, as is illustrated by the following examples:
Example 20.1
Consider the central processing unit of a computer that must process a sequence of jobs that arrive over time. In what order should the jobs be processed in order to minimize, on average, the time that a job is in the system from arrival to completion?
