The idea: one machine, many deadlines, keep the worst delay small
One machine runs jobs one at a time, starting at time 0. Job j takes tj units of time and has a deadline dj. If it finishes at fj, its lateness is ℓj = max(0, fj − dj). Every job must run, so some may be late. The goal is the order with the smallest maximum lateness L = max ℓj. This is minimizing lateness, a classic greedy problem from Kleinberg and Tardos.
| job | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| length t | 3 | 3 | 1 | 5 | 2 | 3 |
| deadline d | 5 | 8 | 9 | 11 | 13 | 16 |
The greedy: earliest deadline first
- Sort the jobs by deadline.
- Run them in that order, back to back, from time 0.
The lengths play no part in the order. On the page the order is A B C D E F. D starts at 7, ends at 12 and its deadline is 11, so it is 1 late; E and F are pushed back by the same 1 unit. L = 1. The page tries all 720 orders of the 6 jobs: none has L = 0, so 1 is the best. (Demo: earliest deadline first) Sorting costs O(n log n).
Rules that look right but fail
Shortest job first gets small jobs out of the way: C E A B F D. But D, the long job with deadline 11, now runs last, [12, 17), and is 6 late. (Demo: shortest job first fails)
Smallest slack sorts by d − t, the latest time a job can start and still be on time: A 2, B 5, D 6, C 8. D goes before C, so C waits until 11 and ends 3 late. (Demo: smallest slack fails)
No idle time
A schedule may leave the machine idle between jobs, but that never helps: closing a gap moves later jobs earlier, and a job that finishes earlier is never more late. So some optimal schedule has no idle time, and the page always runs jobs back to back. EDF has no idle time either.
Why EDF is optimal: the exchange argument
An inversion is a pair of jobs i, j where i runs first but di > dj. EDF is the only kind of idle-free order with no inversions (jobs with equal deadlines can be in any order; that does not change L). Three facts finish the proof:
- If a schedule has an inversion, it has one between two neighbours: walk along the order; somewhere the deadline must go down.
- Swapping that neighbouring pair moves only those two jobs. Together they still fill the same interval, ending at the same f.
- After the swap, j ends earlier, so it is no later. i now ends at f, where j used to end, and f − di < f − dj: i is less late than j was. So L does not go up.
Each swap removes one inversion, so start from an optimal schedule, swap until none is left, and you reach EDF still optimal. On the page, the swaps start from the shortest-job-first order: 6 inversions, 6 swaps, and L goes 6 → 1 without ever rising. (Demo: exchange argument)
The demos in numbers
| rule | order | worst job | L |
|---|---|---|---|
| earliest deadline first | A B C D E F | D, E, F (1 late) | ✓ 1 |
| shortest job first | C E A B F D | D [12, 17), d = 11 | ✗ 6 |
| smallest slack | A B D C E F | C [11, 12), d = 9 | ✗ 3 |
| best of all 720 orders | — | — | 1 |
Press Random Set for new jobs: EDF always matches the best of all 720 orders. The other rules sometimes do too, but not always. (Demo: random set)
Related problems
EDF is also how real-time systems schedule tasks with deadlines; see Real-time Scheduling. Interval Scheduling and Interval Partitioning are the two other greedy problems from the same chapter, with fixed start times instead of a free order. CPU Scheduling shows shortest job first in its home: there it minimizes the average waiting time, a different goal.
What the page leaves out
Times are whole numbers from 0 to 18 and a set has 6 jobs. The page leaves out release times (jobs that arrive later, where the problem becomes NP-hard without preemption), several machines, weighted lateness, the number of late jobs (Moore–Hodgson's algorithm) and total tardiness.
See where this page fits on the String & Greedy Algorithms mind map.