Shortest-Job-First and Average Waiting Time

The problem: you run one checkout counter, one CPU, or one trader's execution queue, and several jobs are waiting to be processed one at a time, each taking a known amount of time. In what order should you run them to minimize the average time people spend waiting? The answer — run the shortest job first — is one of the most useful small results in scheduling, both because it's easy to prove and because it shows up disguised in a lot of interview questions about queues, checklists, and task lists.

The rule and the intuition

Sort jobs by processing time, shortest to longest, and run them in that order. The intuition: a job's wait time equals the sum of the processing times of every job that ran before it. A job scheduled early affects the wait of everyone behind it, but a job scheduled late only affects its own wait. So the jobs that impose the least total cost on others when placed early are the short ones — placing a long job early "taxes" every job behind it for the full length of that long job, while a short job imposes only a small tax. Minimizing that cumulative tax means putting the smallest taxes first.

Worked example: four jobs, two orderings compared

Four jobs with processing times $8, 3, 5, 1$ (in minutes). Under shortest-job-first, the order is $1, 3, 5, 8$:

Order	Runs	Finishes	Wait (finish minus own time)
1st	Job(1)	1	0
2nd	Job(3)	4	1
3rd	Job(5)	9	4
4th	Job(8)	17	9

Average wait $= (0 + 1 + 4 + 9) / 4 = 14/4 = 3.5$ minutes.

Now run them in the original order $8, 3, 5, 1$ instead:

Order	Runs	Finishes	Wait
1st	Job(8)	8	0
2nd	Job(3)	11	8
3rd	Job(5)	16	11
4th	Job(1)	17	16

Average wait $= (0 + 8 + 11 + 16)/4 = 35/4 = 8.75$ minutes — more than double the shortest-job-first average, even though both orderings finish the last job at the same total time of 17 minutes. Total processing time is fixed regardless of order; only how that time is distributed across waiting jobs changes, and shortest-job-first distributes it as unevenly as possible in the good direction — most jobs wait very little, only the longest job absorbs a big wait.

What this means in practice

Shortest-job-first is the right instinct anywhere a single resource serves a queue and the goal is minimizing how long people wait on average — email triage, small-ticket support queues, a single execution algo working through a list of small orders before a large one. It's the wrong instinct when jobs have deadlines instead of just an average-wait objective, or when a long job is more urgent than its length suggests, at which point earliest-deadline-first or a priority weighting replaces pure shortest-job-first.