Single-Machine Scheduling
SFC · Operational · Foundation of scheduling theory
Graham three-field classification 1 | β | γThe single-machine scheduling problem is the foundation of the entire scheduling literature. A single processor, n jobs, each with a processing time pj, weight wj and due date dj. Choose the sequence that minimises a chosen objective — total completion time, weighted completion time, maximum lateness, tardy-job count, or weighted tardiness. Objectives that look similar can be strikingly different computationally: ΣwjCj is solved in O(n log n) by Smith’s rule, but ΣwjTj is strongly NP-hard.
Where This Decision Fits
APICS planning hierarchy — the highlighted level is what this page optimises
The Problem
Eight jobs, one machine, six objectives
A single bottleneck resource must process n = 8 jobs. Each job j has a processing time pj, a weight wj, and a due date dj. No preemption: once started, a job runs to completion. All jobs are available at time 0 (no release dates). The sequence we pick determines every job’s completion time Cj and therefore every objective.
Historically, single-machine theory was the first and most fundamental area of scheduling research. Every optimal dispatching rule here becomes a subroutine for multi-machine algorithms: SPT and EDD are embedded in Giffler-Thompson job-shop active schedules; WSPT appears inside Shifting-Bottleneck; ATC drives parallel-machine tardiness heuristics.
| Job | pj | wj | dj |
|---|
min Σ Cj // total completion — SPT optimal, O(n log n)
min Σ wjCj // weighted — WSPT (Smith 1956), O(n log n)
min Lmax = max(Cj−dj) // maximum lateness — EDD (Jackson 1955), O(n log n)
min Σ Uj, Uj=[Cj>dj] // tardy-job count — Moore (1968), O(n log n)
min Σ Tj, Tj=max(0,Cj−dj) // total tardiness — NP-hard (Du & Leung 1990)
min Σ wjTj // weighted tardiness — strongly NP-hard
There are n! = 40,320 possible sequences for eight jobs — small enough to brute-force for verification, but the point here is the algorithmic landscape. For five of the six objectives there is a provably optimal rule that runs in O(n log n); only ΣTj and ΣwjTj require dynamic programming or branch-and-bound.
Manufacturing framework Multi-machine extension (PFSP)Try It Yourself
Six algorithms, six objectives — see which rule is optimal for which goal
Single-Machine Scheduler
8 jobs · 1 machine · 6 objectivesClick “Solve & Compare” to run all six algorithms on the current scenario.
| Algorithm | ΣCj | ΣwjCj | Lmax | ΣUj | ΣTj | ΣwjTj |
|---|---|---|---|---|---|---|
| Click Solve to run | ||||||
The Algorithms
Six rules, each optimal for a specific γ
SPT — Shortest Processing Time
Exact for ΣCj O(n log n) 1 || ΣCjSort jobs by non-decreasing processing time. The smallest pj goes first. A pairwise-swap argument proves optimality: in any schedule, if the job at position k has a larger p than the one at position k+1, swapping them strictly reduces ΣCj.
Conway, Maxwell & Miller (1967). Also optimal for average flow time, which differs from ΣCj only by a constant factor of 1/n.
WSPT — Smith’s Weighted Shortest Processing Time Rule
Exact for ΣwjCj O(n log n) 1 || ΣwjCjSort jobs by non-decreasing ratio pj / wj. Smith (1956) proved optimality by the same adjacent-swap argument generalised to weighted completion times. Equivalent to prioritising high-weight short jobs — the intuition behind WSJF in modern dispatching.
EDD — Earliest Due Date
Exact for Lmax O(n log n) 1 || LmaxSort jobs by non-decreasing due date. Jackson (1955). Minimises maximum lateness Lmax = max(Cj−dj) and also maximum tardiness Tmax. A staple heuristic for deadline-sensitive applications where the worst late job matters more than the average.
Moore’s Algorithm
Exact for ΣUj O(n log n) 1 || ΣUjMinimises the number of tardy jobs. Schedule jobs in EDD order; whenever a newly added job becomes tardy, discard the longest-processing job seen so far. The discarded jobs form the tardy set; the kept jobs are on-time.
Moore (1968), refined by Hodgson. Remarkable result: a polynomial-time algorithm for ΣUj despite the weighted variant ΣwjUj being NP-hard.
ATC — Apparent Tardiness Cost
Heuristic for ΣwjTj O(n²) 1 || ΣwjTjComposite dispatching rule. At each step, schedule the job with the largest priority index πj(t) = (wj/pj) · exp(−max(0, dj−t−pj)/(k·p̅)), where t is the current time, p̅ is the average processing time, and k is a look-ahead parameter (typically 1–5).
Vepsalainen & Morton (1987). ATC blends WSPT (urgency via w/p) with EDD (lateness via the exponential slack term). Typically achieves within 5–10% of the optimum on ΣwjTj benchmarks — the warm-start of choice for B&B implementations.
DP — Bitmask Dynamic Programming
Exact for ΣTj O(2n · n) 1 || ΣTjEnumerate subsets S ⊆ N. State f(S) is the minimum total tardiness to complete all jobs in S. Since all jobs are available at time 0, the completion time of any last-scheduled job j ∈ S is simply Σk∈S pk, regardless of order. Recurrence:
Base case f(∅) = 0; answer is f(N). Du & Leung (1990) proved that 1 || ΣTj is NP-hard in the ordinary sense — pseudo-polynomial DP exists in processing-time magnitude, but exponential in n. Practical limit ~20–24 jobs. For weighted tardiness, B&B with ATC warm-start is preferred.
| Problem | Complexity | Optimal rule / method | Reference |
|---|---|---|---|
| 1 || Cmax | Trivial | Any order (Cmax = Σpj) | — |
| 1 || ΣCj | O(n log n) | SPT | Conway et al. (1967) |
| 1 || ΣwjCj | O(n log n) | WSPT (Smith’s rule) | Smith (1956) |
| 1 || Lmax | O(n log n) | EDD | Jackson (1955) |
| 1 || ΣUj | O(n log n) | Moore’s algorithm | Moore (1968) |
| 1 || ΣTj | NP-hard | Bitmask DP O(2n·n) | Du & Leung (1990) |
| 1 || ΣwjTj | Strongly NP-hard | B&B, ATC warm-start | Potts & Van Wassenhove (1985) |
| 1 | rj | Lmax | NP-hard | B&B; SRPT preemptive | Lenstra et al. (1977); Schrage (1968) |
| 1 | sjk | Cmax | NP-hard | Reduces to TSP | — |
References
Foundational papers on single-machine scheduling
- (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1–2), 59–66. — Smith’s rule (WSPT).
- (1955). Scheduling a production line to minimize maximum tardiness. UCLA Management Science Research Project, Research Report 43. — EDD for Lmax.
- (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), 102–109. doi:10.1287/mnsc.15.1.102
- (1967). Theory of Scheduling. Addison-Wesley. — classical foundation; SPT optimality proof.
- (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.
- (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33(2), 363–377. doi:10.1287/opre.33.2.363
- (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3), 483–495. doi:10.1287/moor.15.3.483
- (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
- (1987). Priority rules for job shops with weighted tardiness costs. Management Science, 33(8), 1035–1047. doi:10.1287/mnsc.33.8.1035 — ATC rule.
- (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. doi:10.1016/S0167-5060(08)70356-X — three-field notation.
- (2022). Scheduling: Theory, Algorithms, and Systems (6th ed.). Springer. doi:10.1007/978-3-031-05921-6 — canonical reference; single-machine chapter covers all objectives above.