In the previous page, we stated that Shortest Job First (SJF) provably minimizes average waiting time among all non-preemptive scheduling algorithms. This is a remarkable claim—not a heuristic observation, not a "usually works well" guideline, but a mathematical guarantee.

Understanding why SJF is optimal matters for several reasons:

1. Verification: We can be confident in SJF's theoretical superiority rather than relying on empirical testing
2. Extension: The proof structure reveals what conditions are necessary for optimality
3. Foundation: Understanding optimality proofs enables evaluating new scheduling proposals
4. Insight: The proof illuminates the fundamental trade-offs in scheduling

This page presents multiple approaches to understanding and proving SJF's optimality, from intuitive arguments to formal mathematical proofs.

Before formal proofs, let's build intuition about why scheduling shorter jobs first minimizes average waiting time.

The Waiting Time Cascade

Consider what happens when a process runs. Every process behind it in the queue must wait for it to complete. If a process with burst time B runs first, every subsequent process waits at least B time units.

This creates a cascade effect:

• The first process's burst time affects the wait of all n-1 remaining processes
• The second process's burst time affects n-2 remaining processes
• And so on...

Mathematically, if we schedule processes in order j₁, j₂, ..., jₙ with burst times b₁, b₂, ..., bₙ:

Total Waiting Time = (n-1)·b_{j₁} + (n-2)·b_{j₂} + ... + 1·b_{j_{n-1}} + 0·b_{jₙ}

Each burst time is weighted by how many processes must wait for it.

A Concrete Example

Consider 3 processes with bursts: A=1, B=2, C=3

Schedule A→B→C (SJF order):

• Wait for A: 0
• Wait for B: 1 (after A)
• Wait for C: 1+2=3 (after A and B)
• Total: 0+1+3 = 4

Schedule C→B→A (reverse order):

• Wait for C: 0
• Wait for B: 3 (after C)
• Wait for A: 3+2=5 (after C and B)
• Total: 0+3+5 = 8

The SJF order produces half the total waiting time!

Using our formula:

• SJF: 2×1 + 1×2 + 0×3 = 2+2+0 = 4 ✓
• Reverse: 2×3 + 1×2 + 0×1 = 6+2+0 = 8 ✓

By assigning large weights (2, 1, 0) to small values (1, 2, 3), SJF minimizes the weighted sum.

Before proving optimality, we must precisely state what we're proving.

Assumptions and Conditions

Given:

• n processes: P = {p₁, p₂, ..., pₙ}
• CPU burst times: B = {b₁, b₂, ..., bₙ} where bᵢ > 0 for all i
• All processes arrive at time t=0 (simultaneous arrival)
• Non-preemptive scheduling (once started, runs to completion)
• Single CPU

Define:

• A schedule S is a permutation π of {1, 2, ..., n} specifying execution order
• Waiting time W(pᵢ, S) = time from arrival to start of execution for process pᵢ under schedule S
• Average waiting time = (1/n) · Σᵢ W(pᵢ, S)

To Prove: The schedule S* that orders processes by non-decreasing burst times (SJF order) minimizes average waiting time over all possible schedules.

Mathematical Formulation

Let π* be the SJF permutation where b_{π*(1)} ≤ b_{π*(2)} ≤ ... ≤ b_{π*(n)}.

For any permutation π:

Total Waiting Time(π) = Σᵢ₌₁ⁿ [Σⱼ₌₁^{i-1} b_{π(j)}]

This says: the waiting time for the i-th process in schedule order is the sum of burst times of all processes before it.

Equivalently:

Total Waiting Time(π) = Σᵢ₌₁ⁿ (n - i) · b_{π(i)}

The i-th scheduled process's burst time is weighted by how many processes come after it.

The exchange argument is a powerful proof technique. We show that any schedule not in SJF order can be improved by swapping adjacent out-of-order elements. Since every non-SJF schedule can be incrementally improved toward SJF, no non-SJF schedule can be optimal.

The Core Lemma

Lemma: If schedule S has two adjacent processes pᵢ and pⱼ where pᵢ precedes pⱼ but bᵢ > bⱼ (longer job before shorter), then swapping them produces schedule S' with strictly lower total waiting time.

Proof of Lemma:

Consider processes at positions k and k+1 in the schedule:

• Before swap: process pᵢ at position k, pⱼ at position k+1
• After swap: pⱼ at position k, pᵢ at position k+1

Let W_before and W_after denote total waiting times.

Key observation: The swap only affects:

1. Waiting time of pᵢ (now must wait for pⱼ instead of nothing extra)
2. Waiting time of pⱼ (now waits for nothing extra instead of pᵢ)

All other processes are unaffected—their relative positions and the total burst time before them remain unchanged.

Before swap:

• pⱼ waits for pᵢ (additional wait = bᵢ)

After swap:

• pᵢ waits for pⱼ (additional wait = bⱼ)

Change in total waiting time: W_after - W_before = bⱼ - bᵢ < 0 (since bⱼ < bᵢ)

The total waiting time decreases by (bᵢ - bⱼ) > 0.

∎

Main Theorem

Theorem: The SJF schedule (processes ordered by non-decreasing burst times) achieves minimum total waiting time.

Proof:

Let S be any schedule that is not SJF order. Since S is not sorted by burst times, there must exist at least one pair of adjacent processes where a longer process precedes a shorter one.

Step 1: By the Lemma, we can swap these adjacent processes to reduce total waiting time, producing schedule S₁ with W(S₁) < W(S).

Step 2: If S₁ is still not in SJF order, repeat the swap process. Each swap reduces total waiting time.

Step 3: Since there are finitely many possible swaps (at most n(n-1)/2 inversions to fix), and each swap strictly decreases waiting time, this process terminates.

Step 4: When no more improving swaps are possible, the schedule must be sorted by burst times—the SJF order.

Step 5: Therefore, starting from any non-SJF schedule, we can reach the SJF schedule through a series of improvements. This means no non-SJF schedule can have lower waiting time than SJF.

Conclusion: SJF achieves the minimum total (and hence average) waiting time.

∎

A more elegant proof uses the Rearrangement Inequality, a fundamental result from mathematical analysis.

The Rearrangement Inequality

Theorem (Rearrangement Inequality): Let a₁ ≤ a₂ ≤ ... ≤ aₙ and b₁ ≤ b₂ ≤ ... ≤ bₙ be sorted sequences of real numbers. For any permutation π:

aₙb₁ + aₙ₋₁b₂ + ... + a₁bₙ ≤ a_{π(1)}b₁ + a_{π(2)}b₂ + ... + a_{π(n)}bₙ ≤ a₁b₁ + a₂b₂ + ... + aₙbₙ

In words:

• The minimum sum is achieved by pairing the sequences in opposite order (largest with smallest)
• The maximum sum is achieved by pairing in the same order (largest with largest)

Application to SJF

Recall our total waiting time formula:

Total Waiting Time = Σᵢ₌₁ⁿ (n - i) · b_{π(i)}

We can view this as a dot product of two sequences:

• Weights w = (n-1, n-2, ..., 1, 0) — fixed in descending order
• Burst times arranged according to permutation π

To minimize the sum, by the Rearrangement Inequality, we should pair:

• Largest weight (n-1) with smallest burst time
• Second largest weight (n-2) with second smallest burst time
• And so on...

This means burst times should be in ascending order — exactly the SJF order!

∎

Numerical Verification

With 3 bursts [1, 2, 3] and weights [2, 1, 0]:

SJF (ascending bursts): 2×1 + 1×2 + 0×3 = 2 + 2 + 0 = 4

Reverse (descending bursts): 2×3 + 1×2 + 0×1 = 6 + 2 + 0 = 8

The Rearrangement Inequality guarantees 4 ≤ any permutation ≤ 8.

All 6 permutations produce values in [4, 8], confirming the theory.

SJF's optimality is proven under specific conditions. Understanding these conditions clarifies when the guarantee applies and when it doesn't.

Conditions for Optimality

What Happens When Conditions Are Violated?

The proof above assumes all processes arrive at time 0. When processes arrive at different times, the analysis requires extension.

The Adapted SJF Rule

With non-simultaneous arrivals, SJF becomes:

At each scheduling decision point, select the shortest job among all currently ready (arrived and waiting) processes.

This is still SJF—applied dynamically to the available process set.

Optimality Under Different Arrivals

Local Optimality: At each decision point, selecting the shortest available job is optimal for that decision, given the processes present.

Global Optimality: However, SJF is not necessarily globally optimal with different arrival times. Consider:

SJF Execution:

• t=0: Only P1 available → P1 starts (burst=7)
• P1 runs until t=7 (P2 arrived at t=2 but couldn't preempt)
• t=7: P2 runs (burst=1), completes at t=8
• Wait times: P1=0, P2=5 → Average = 2.5

If we could see the future (and wait for P2):

• t=0-2: CPU idle
• t=2: P2 runs (burst=1), completes at t=3
• t=3: P1 runs (burst=7), completes at t=10
• Wait times: P1=3, P2=0 → Average = 1.5

Waiting for P2 produces lower average waiting time!

When SJF Remains Optimal

With different arrival times, SJF still provides:

1. Optimal at each decision point — Given current ready processes, no other choice produces lower average wait for available jobs
2. Strong approximation — In typical workloads, SJF is near-optimal even without clairvoyance
3. No idle time — If any process is ready, SJF runs it (no artificial waiting)

For truly optimal scheduling with arrivals, preemptive SRTF (covered in Page 4) provides significant improvements by allowing re-evaluation when new processes arrive.

From an algorithmic standpoint, the SJF optimality result connects to broader complexity concepts.

Connection to Sorting

Finding the SJF schedule is equivalent to sorting processes by burst time:

• Sort n processes by burst length: O(n log n) comparisons
• The sorted order directly gives the optimal schedule

This makes SJF a remarkably efficient algorithm to compute (when burst times are known).

Contrast with Hard Scheduling Problems

Many scheduling problems are NP-hard—no efficient algorithm guarantees optimal solutions:

SJF's polynomial-time optimality is special. Most realistic scheduling problems have no efficient optimal algorithm.

The Greedy Property

SJF is a greedy algorithm—at each step, it makes the locally optimal choice (shortest job) and never reconsiders.

Greedy algorithms are optimal when:

1. Optimal substructure — Optimal solutions to subproblems combine into optimal overall solutions
2. Greedy choice property — Locally optimal choices lead to globally optimal solutions

For SJF with simultaneous arrivals, both properties hold:

• Scheduling the shortest job first is the greedy choice
• After scheduling it, the remaining subproblem has the same structure
• Inductive reasoning confirms global optimality

This connects SJF to the broader family of greedy scheduling algorithms, including variants like weighted job scheduling and activity selection.

We have rigorously established SJF's optimality property. Let's consolidate the key insights:

Looking Ahead:

The optimality proof assumes we know burst times exactly—which we don't in practice. The next page tackles the critical challenge of burst time prediction: How can a scheduler estimate future CPU burst lengths using past behavior? We'll explore exponential averaging and other prediction techniques that make SJF practical.