Scheduling

Scheduling is the allocation of limited resources to competing demands over time. In operating systems, it is the algorithm that decides which process runs on the CPU and for how long. In operations research, it is the sequencing of tasks across machines to minimize makespan or maximize throughput. In project management, it is the coordination of interdependent activities subject to temporal and resource constraints.

Despite these domain differences, scheduling problems share a common structure: a set of tasks with durations, dependencies, and resource requirements; a set of resources with capacities and availabilities; and an objective function to optimize. The theory of scheduling classifies problems using a three-field notation (machine environment, job characteristics, optimality criterion) that reveals deep structural similarities between apparently unrelated allocation problems.

The fundamental tension in scheduling is between optimality and fairness. An optimal schedule may starve low-priority tasks indefinitely; a fair schedule may achieve only a fraction of the theoretically possible throughput. This tension is not resolvable by better algorithms. It is a value judgment encoded in the objective function — a reminder that scheduling is not merely a technical problem but a political one in formal dress.