Shortest Job First Scheduling

Shortest Job First (SJF) Scheduling is a classic greedy problem. You are given a set of jobs, each with a known running time, and you want to schedule them on one machine so the average waiting time is as small as possible.

The slow way first

You could try every possible ordering of the jobs and compute the average wait for each, keeping the best. With n jobs that is n! orderings — hopeless for anything but tiny inputs. We need to know which order is best without enumerating them all.

The question to ask: which job should I run first? Whatever job I run first delays every job behind it by its own burst time. So a long job at the front punishes everyone. It is always cheaper to put the shortest job first.

The idea: shortest first, accumulate the clock

Sort the jobs by burst time and run them shortest-first. Keep a running elapsed clock of how much time has passed. When a job starts, it has already waited exactly elapsed, so add that to the total wait. Then advance elapsed by the job's burst time and move on.

The key insight: a job's waiting time equals the sum of the bursts of every job before it. Running the smallest bursts first keeps that growing sum as low as possible for every later job.

Walk through it

Step through the animation. The cells start unsorted [3, 1, 4, 2] and reorder to [1, 2, 3, 4]. The pointer i runs left to right. Each step, the elapsed clock is added to wait before the clock advances, so wait grows 0 → 1 → 4 → 10.

Pseudocode

sort jobs by burst time (ascending)
elapsed = 0          # total time used so far = next job start time
wait = 0             # running total of waiting times
for each burst in sorted jobs:
    wait = wait + elapsed     # this job waited "elapsed" before starting
    elapsed = elapsed + burst # the clock advances by this job run time
return wait / number_of_jobs  # the average waiting time

The Python solution

def average_wait(jobs):
    jobs.sort()
    elapsed = wait = 0
    for burst in jobs:
        wait += elapsed
        elapsed += burst
    return wait / len(jobs)

• jobs.sort() puts the shortest burst times first — the whole greedy choice in one line.
• elapsed doubles as the clock and as the start time of the next job to run.
• wait += elapsed records that the job about to start has been waiting exactly elapsed.
• elapsed += burst advances the clock past this job so the next one waits a bit longer.
• At the end we divide the total wait by the number of jobs to get the average.

Complexity

The sort costs O(n log n) and the single pass is O(n), so the whole thing is O(n log n). We use only a couple of running totals, so extra space is O(1) (ignoring the sort).

When this pattern shows up

Practice