Three dispatching rules that come with a proof: SPT, WSPT and EDD, and where the proof stops
Shortest processing time, weighted shortest processing time and earliest due date are each provably optimal for one objective on one machine. A five-job example checked against all 120 orders shows what each one wins and what it gives up, and why a sorting rule stops being a theorem the moment a second machine appears.
On this page
A dispatching rule answers one question: a machine has just become free, several jobs are waiting, which goes next? Scheduling libraries ship a dozen or more rules, and most of them are folk wisdom that happens to work on some shops. Three of them are different. For one narrow situation each comes with a theorem that says no other order can beat it on a particular measure.
This article states those three theorems, shows on a five-job example what each rule wins and what it gives up, and marks the point where the theorems stop applying, which is where most real shops start.
The setting the theorems assume
All three results are about one machine, with every job ready at time 0, processing times known, and no setup between jobs. For a job j:
- pⱼ is its processing time and dⱼ its due date;
- Cⱼ is its completion time, the sum of the processing times of the jobs before it plus its own;
- Lⱼ = Cⱼ − dⱼ is its lateness (negative when early);
- Tⱼ = max(0, Lⱼ) is its tardiness;
- wⱼ is a weight, how much an hour of this job's waiting costs compared with the others.
The three rules and what each is optimal for
| Rule | Sort by | Minimizes |
|---|---|---|
| SPT, shortest processing time | pⱼ, smallest first | mean completion time (equivalently mean flow time) |
| WSPT, weighted shortest processing time | pⱼ / wⱼ, smallest first | the weighted sum Σ wⱼCⱼ |
| EDD, earliest due date | dⱼ, smallest first | the maximum lateness, max Lⱼ |
SPT is WSPT with all weights equal. W. E. Smith proved the weighted ratio rule in 1956, and J. R. Jackson gave the earliest-due-date result in a 1955 research report.
The proofs are short exchange arguments. Take any order in which two neighbours i, j sit the wrong way round by the rule, starting at time t. For SPT, putting i first gives completion times t + pᵢ and t + pᵢ + pⱼ, a sum of 2t + 2pᵢ + pⱼ; putting j first gives 2t + 2pⱼ + pᵢ. The first is larger by pᵢ − pⱼ, so whenever the longer job is first, swapping it behind the shorter one lowers the total, and nothing else in the schedule moves. Repeat until no neighbours are out of order and you have the rule. WSPT and EDD follow the same pattern with their own keys.
A five-job example
One machine, five jobs ready together. Times are in hours.
| Job | p (processing) | d (due) | w (weight) |
|---|---|---|---|
| A | 6 | 9 | 1 |
| B | 2 | 3 | 1 |
| C | 4 | 6 | 3 |
| D | 3 | 14 | 1 |
| E | 5 | 8 | 2 |
Run in arrival order (A B C D E), then by each rule:
| Rule | Order | Mean C | Max L | Σ T | Σ wC | Late jobs |
|---|---|---|---|---|---|---|
| Arrival order | A B C D E | 12.2 | 12 | 24 | 105 | 4 |
| SPT | B D C E A | 10.0 | 11 | 20 | 82 | 3 |
| EDD | B C E A D | 11.2 | 8 | 17 | 79 | 3 |
| WSPT | C B E D A | 11.0 | 11 | 17 | 74 | 3 |
We also tried all 120 possible orders. Exactly one of them reaches a mean completion time of 10.0, and it is the SPT order. Exactly one reaches Σ wC = 74, the WSPT order. The smallest possible maximum lateness is 8, reached by six orders, among them the EDD order. So each rule wins its own column, as the theorems say.
Read the other columns, though. SPT has the best mean but a maximum lateness of 11 hours, because job A, the longest, goes last and is 11 hours late. EDD protects the worst case, 8 hours, and pays 1.2 hours on the mean. WSPT puts the heavy job C first and wins the weighted total, and it still leaves A 11 hours late. None of the three theorems says anything about Σ T or the number of late jobs, so those two columns are information, not a result: they just happen to favour EDD and WSPT on these numbers.
The choice of rule is therefore the choice of what you are protecting: the average wait, the worst promise, or the cost-weighted wait.
Where the proof stops
The moment the situation differs from the one the theorems assume, the rules become heuristics:
- More than one machine, or a job that must visit several in a fixed order (a job shop). A rule picks the next job at each machine independently, and a locally optimal choice at one machine can starve the next.
- Jobs that arrive over time, so the best next job is not yet there.
- Setup times that depend on the previous job, which break the "sum of processing times" that every argument above relies on.
Heuristics can still be very good. Vepsalainen and Morton (1987) designed the ATC rule, apparent tardiness cost, for exactly the weighted-tardiness job shop where the theorems do not reach; they tested it in simulated job-shop experiments rather than proving it optimal. That is a different kind of evidence from an exchange argument, and it is worth knowing which one a rule stands on.
Try it in Forge Plan
Forge Plan offers 14 dispatching rules on its Schedule page. Under the rule you select, it prints the source: for SPT and WSPT the Smith (1956) result, for EDD Jackson (1955), for ATC Vepsalainen and Morton (1987). For the other rules there is no citation to print, and the page shows a Source unverified, verification recommended badge instead of inventing one.
To compare rules on your own data, run the same orders under different rules and save each result as a scenario. The Compare page lists the scenarios side by side by metric (makespan, total tardiness, max tardiness, late orders and others) and marks the best value in each row.
Two honest limits. The theorems above are statements about one machine; Forge Plan schedules a whole plant, so read a rule's citation as the reason it is a sensible default, not as a guarantee about your result. And the comparison shows makespan and tardiness measures, not mean flow time, so the mean-completion-time column in the table above is something to check by hand or in a spreadsheet.
References
- W. E. Smith, "Various optimizers for single-stage production", Naval Research Logistics Quarterly, 3(1–2), 1956, pp. 59–66, doi:10.1002/nav.3800030106.
- J. R. Jackson, "Scheduling a production line to minimize maximum tardiness", Research Report 43, Management Sciences Research Project, University of California, Los Angeles, January 1955. The result concerns maximum lateness, as in the table above.
- A. P. J. Vepsalainen and T. E. Morton, "Priority rules for job shops with weighted tardiness costs", Management Science, 33(8), 1987, pp. 1035–1047, doi:10.1287/mnsc.33.8.1035.
- M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed., Springer, 2016, doi:10.1007/978-3-319-26580-3. The general reference for the notation and the single-machine results above.