Run the quickest task next, and the average wait is as small as it can possibly be. Non-preemptive SJF is not a heuristic — it is provably optimal: for jobs present at once, running them shortest-first gives an average waiting time equal to the minimum over all n! orderings. Down the center, data flows: the burst times go in, the scheduler orders them, the proven minimum comes out. The blue team builds and defends it; the red team tries to break it.
source Conway, Maxwell & Miller, Theory of Scheduling (Addison-Wesley, 1967) — no stable DOI, cited AMBER by author/title/year; scan at archive.org/details/TheoryOfScheduling. Rendered, not quoted.
All jobs are present at time 0. Whatever the order, a job's waiting time is just the sum of the bursts run before it. So the total wait is
Σ (n − i) · b(i)
— each burst is charged once for every job still behind it. To shrink the total, put the small bursts where the multiplier is large: sort ascending. Any out-of-order pair can be swapped for a strictly smaller total (the exchange argument). That is the whole proof.
Live schedule for the current set:
| run # | job | burst | wait |
|---|
Shortest-first is the floor on average waiting time — nothing beats it, but it will happily starve a long job to reach that floor.
The round robin gives that floor up on purpose: it slices time into fair quanta so no job waits forever, paying a little average wait to buy bounded response. SJF is the optimum RR approximates while staying fair — this sphere is the number the neighbour is measured against.
The blue team's live check: recompute the engine's order and compare its total wait to the brute-force minimum over all orderings — plus the fixed battery (SJF<FCFS, starvation, SRTF-optimal). If red tampers, this badge is where it shows.
A job is one number: its CPU burst — how long it needs the processor. Here every job arrives at time 0; the only freedom is the order you run them in. Feed a comma-separated list of bursts into the panel below.
Example: 6, 8, 7, 3 is the textbook set (Silberschatz). Four jobs, and 4! = 24 possible orderings — the engine will show that shortest-first hits the best of all 24.
Mode: SJF — run the smallest remaining burst next. Non-preemptive; all jobs present at t=0.
| ordering | total wait | avg wait |
|---|
Change the bursts — the order and every waiting time are computed live, and the minimum is found by brute force over all n! orderings, never looked up.
What the machine produces, proven: SJF's average waiting time equals the minimum over all n! orderings of the same jobs — the optimum, not an approximation. It also beats first-come-first-served (the convoy effect avoided), and its preemptive twin SRTF is optimal once jobs arrive over time.
The blue team's witness (left) confirms optimality live; the red team (right) tries to make the engine run the wrong order.
Drop any assumption and it breaks: online arrivals demand preemption (SRTF); a fairness or deadline metric makes shortest-first the wrong objective; and it will starve a long job to shave the average. The minimum is real — its price is everything it ignores.
"SJF gives the best turnaround for every job." Cut. It minimizes the average. Long jobs are made worse — and can starve indefinitely — to pay for it.
"SJF is usable in a real scheduler as-is." Cut. Burst length is unknown before a job runs; practical schedulers estimate it. SJF is the optimum they approximate.
"Preemptive and non-preemptive SJF are the same." Kept, corrected. With arrivals over time, preemptive SRTF can strictly beat non-preemptive SJF — each is optimal only within its own class.
The red team's move: flip the scheduler to run the longest job first (LJF). The average waiting time is now maximized — it exceeds the SJF minimum, so the optimality check must fail. The blue team's witness (window 7) is watching.
Flip to LJF and the engine's total wait no longer equals the brute-force minimum — the witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.