Scheduling in computing and related fields is the process of deciding the order and duration with which a set of tasks (jobs, processes, threads) are assigned to resources (processors, machines, network links). In computer science scheduling appears in operating systems, real-time control, databases and distributed systems; in combinatorial optimisation scheduling denotes formal models used to analyse performance and find optimal or near-optimal plans.

Core concepts

A scheduling problem is defined by its tasks, resources, constraints and an objective function. Tasks may have release times, deadlines, durations, precedence relations and priorities. Resources can be identical, unrelated or heterogeneous. Typical objectives include minimizing makespan (total completion time), average response time, lateness, or maximizing throughput and fairness.

Common models and distinctions

  • Preemptive vs non-preemptive: whether a running task can be interrupted.
  • Offline vs online: whether all jobs are known beforehand.
  • Single-machine, parallel machines, flow-shop, job-shop: standard combinatorial models.

Algorithms and approaches

Simple heuristics include first-come-first-served, shortest-job-first, round-robin and priority scheduling. More advanced methods used in research and practice include list scheduling, greedy algorithms, dynamic programming for small instances, branch-and-bound and approximation algorithms. For real-time systems, rate-monotonic and earliest-deadline-first provide provable guarantees under specific assumptions.

Complexity and history

Many scheduling problems are computationally hard: classic formulations such as job-shop scheduling are NP-hard, motivating approximation, heuristics and specialized solvers. The study of scheduling grew from early industrial planning and from operating system research in the mid-20th century, later connecting closely with complexity theory and optimization.

Applications and notable facts

Scheduling is essential in operating systems (CPU and I/O scheduling), cloud and cluster resource management, manufacturing, project planning and network packet scheduling. Practical systems balance theoretical optimality with responsiveness, fairness and implementation cost. For further technical surveys and models, consult resources in theoretical computer science and optimisation literature via the linked topics above.