Single-Machine Scheduling: Moore-Hodgson, Smith's Rule & EDF

1. Problem and Motivation

Single-machine scheduling asks a deceptively small question: given a set of jobs, each with a processing time $p_i$ and possibly a deadline $d_i$ and a weight $w_i$, and exactly one machine that can run one job at a time, in what order should the jobs run? The order is a permutation of $n$ jobs, so brute force costs $O(n!)$ — completely impractical past a dozen jobs. Yet for many natural objectives, a single sorting rule, checkable in $O(n \log n)$, is provably optimal.

The catch is that the objective determines the rule. "Minimize the number of jobs that miss their deadline" wants one ordering. "Minimize the total weighted time customers wait for their job to finish" wants a different ordering. "Minimize the worst deadline miss" wants yet another. Confusing these rules — or assuming one greedy trick solves every scheduling objective — is the most common single-machine scheduling mistake. This lesson treats each objective as its own small theorem: state the rule, trace it by hand, prove it safe, then implement it.

2. Prerequisites

This lesson assumes you are comfortable with:

• Greedy exchange arguments — the proof pattern of showing that any optimal solution can be reshaped, one adjacent swap at a time, into the greedy solution without losing value. See Part 16: Activity Selection & the Exchange Argument for the pattern in its simplest form.
• Job Sequencing with deadlines and profits — choosing which jobs to run (not just their order) to maximize profit, where every job takes one unit of time. That problem is already fully worked out, including its $O(n^2)$ implementation and a note on an $O(n \log n)$ Union-Find optimization, in Part 16, Section 7: Job Sequencing with Deadlines and Profits. This lesson does not repeat it — every job here has an arbitrary processing time and (except in Job Sequencing) every job eventually runs.
• Earliest Deadline First's staying-ahead proof — Part 16 is being extended with a new Section 8: Staying-Ahead Arguments that proves EDF optimal for minimizing maximum lateness, using the full inductive "staying ahead" technique. Section 6 below covers the EDF algorithm and states its correctness conclusion; the formal proof lives there.
• Basic heap operations (insert, extract-max) and array sorting, both used throughout the implementations below.

3. A Concrete Example

The trace shows the entire algorithm in miniature: sort by deadline, add jobs one at a time, and whenever the running completion time overshoots the deadline just added, evict the largest job seen so far — not necessarily the one that triggered the overflow.

4. Moore-Hodgson's Algorithm (Minimizing Late Jobs)

Given $n$ jobs with processing times $p_i$ and deadlines $d_i$ on one machine (no preemption, all available at time 0), find a schedule that minimizes the number of jobs that finish after their deadline. Unlike Job Sequencing, every job eventually runs — on time or late — there is no profit to skip for.

Plain-English Steps

1. Sort all jobs by deadline, ascending.
2. Maintain a running total time (initially 0) and a max-heap of the processing times of jobs currently considered "scheduled."
3. For each job in deadline order: add it to the scheduled set (push onto the heap) and add its processing time to time.
4. If time now exceeds the current job's deadline, pop the largest processing time from the heap, subtract it from time, and mark that job late.
5. After all jobs are processed, the heap holds exactly the on-time jobs (schedule them in deadline order); everything popped out along the way is late.

Correctness: an Exchange Argument

Two facts make the greedy eviction rule safe:

1. Any violation forces at least one eviction. Once the running time exceeds the just-added job's deadline $d$, at least one job among those scheduled so far (all with deadline $\le d$, since jobs are processed in deadline order) must be dropped, or every remaining scheduled job's completion time is provably too late.
2. Evicting the largest processing time is never worse than evicting anything else. Removing any single job from the scheduled set fixes the overflow (by definition of "one job over," since the schedule was feasible one job ago). Among all jobs whose removal fixes it, removing the one with the largest $p$ frees the most slack in the remaining schedule for the same cost of "one job lost" — so it can only make it easier, never harder, to keep every job added afterward on time. A standard interchange argument then shows: for any optimal solution that evicts a different job at this point, swapping its choice for the largest-$p$ job produces another optimal solution with at least as much slack, and by induction the greedy sequence of evictions is optimal throughout.

This is a different proof flavor from Job Sequencing's "schedule as late as possible" argument and from EDF's staying-ahead argument (see Part 16, Section 8) — it reasons about which single element to discard rather than about ordering the elements that remain.

Complexity

Sorting is $O(n \log n)$. Each of the $n$ jobs causes at most one heap push and at most one heap pop, each $O(\log n)$, so the scan is $O(n \log n)$ as well. Total time: $O(n \log n)$; space: $O(n)$ for the heap.

flowchart TD
    A(["Sort jobs by deadline, ascending"]) --> B["Take next job in deadline order"]
    B --> C["Push job onto max-heap (by processing time)\nrunning_time += p"]
    C --> D{"running_time > this job's deadline?"}
    D -->|"No"| E["Job stays scheduled (on time so far)"]
    D -->|"Yes"| F["Pop job with LARGEST p from the heap\nMark it late; running_time -= its p"]
    E --> G{"More jobs left?"}
    F --> G
    G -->|"Yes"| B
    G -->|"No"| H(["Heap contents = on-time jobs\nPopped jobs = minimum possible late jobs"])
                

The heap makes the eviction step efficient: it always holds exactly the processing times of the currently-scheduled jobs, so "find and remove the largest" is one $O(\log n)$ pop instead of an $O(n)$ scan.

import heapq

def moore_hodgson(jobs):
    """
    Moore-Hodgson's Algorithm: minimize the number of late jobs.
    jobs: list of (job_id, processing_time, deadline)
    Returns (on_time_ids, late_ids). Time: O(n log n), Space: O(n).
    """
    jobs = sorted(jobs, key=lambda j: j[2])  # sort by deadline, ascending
    max_heap = []       # stores (-processing_time, job_id) to simulate a max-heap
    current_time = 0
    late = []

    for job_id, p, deadline in jobs:
        heapq.heappush(max_heap, (-p, job_id))
        current_time += p
        if current_time > deadline:
            neg_p, evicted_id = heapq.heappop(max_heap)  # largest p, since it's most negative
            current_time += neg_p                        # neg_p is negative, so this subtracts p
            late.append(evicted_id)

    on_time = [job_id for _, job_id in max_heap]
    return on_time, late

jobs = [("A", 1, 2), ("B", 2, 3), ("C", 6, 4), ("D", 4, 5), ("E", 2, 6)]
on_time, late = moore_hodgson(jobs)
print("On time:", sorted(on_time))   # On time: ['A', 'B', 'E']
print("Late:", late)                 # Late: ['C', 'D']
print("Minimum late jobs:", len(late))  # Minimum late jobs: 2

// Moore-Hodgson's Algorithm: minimize the number of late jobs.
// Time: O(n log n), Space: O(n)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

struct Job {
    std::string id;
    int processingTime;
    int deadline;
};

struct HodgsonResult {
    std::vector<std::string> onTime;
    std::vector<std::string> late;
};

HodgsonResult mooreHodgson(std::vector<Job> jobs) {
    std::sort(jobs.begin(), jobs.end(),
              [](const Job& a, const Job& b) { return a.deadline < b.deadline; });

    // Max-heap of (processingTime, jobId): largest processing time on top.
    std::priority_queue<std::pair<int, std::string>> scheduled;
    int currentTime = 0;
    std::vector<std::string> late;

    for (const auto& job : jobs) {
        scheduled.push({job.processingTime, job.id});
        currentTime += job.processingTime;
        if (currentTime > job.deadline) {
            auto evicted = scheduled.top();
            scheduled.pop();
            currentTime -= evicted.first;
            late.push_back(evicted.second);
        }
    }

    std::vector<std::string> onTime;
    while (!scheduled.empty()) {
        onTime.push_back(scheduled.top().second);
        scheduled.pop();
    }
    return {onTime, late};
}

int main() {
    std::vector<Job> jobs{
        {"A", 1, 2}, {"B", 2, 3}, {"C", 6, 4}, {"D", 4, 5}, {"E", 2, 6}
    };
    HodgsonResult result = mooreHodgson(jobs);
    std::cout << "Late jobs: ";
    for (auto& id : result.late) std::cout << id << " ";
    std::cout << "\nMinimum late jobs: " << result.late.size() << "\n"; // Minimum late jobs: 2
}

// Moore-Hodgson's Algorithm: minimize the number of late jobs.
// Time: O(n log n), Space: O(n)
import java.util.*;

public class MooreHodgson {
    static class Job {
        String id;
        int processingTime;
        int deadline;
        Job(String id, int processingTime, int deadline) {
            this.id = id;
            this.processingTime = processingTime;
            this.deadline = deadline;
        }
    }

    static int schedule(List<Job> jobs, List<String> onTimeOut, List<String> lateOut) {
        jobs.sort(Comparator.comparingInt(j -> j.deadline));

        // Max-heap keyed on processing time.
        PriorityQueue<Job> scheduled = new PriorityQueue<>(
            (a, b) -> b.processingTime - a.processingTime);
        int currentTime = 0;

        for (Job job : jobs) {
            scheduled.offer(job);
            currentTime += job.processingTime;
            if (currentTime > job.deadline) {
                Job evicted = scheduled.poll();
                currentTime -= evicted.processingTime;
                lateOut.add(evicted.id);
            }
        }

        for (Job job : scheduled) onTimeOut.add(job.id);
        return lateOut.size();
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>(List.of(
            new Job("A", 1, 2),
            new Job("B", 2, 3),
            new Job("C", 6, 4),
            new Job("D", 4, 5),
            new Job("E", 2, 6)
        ));
        List<String> onTime = new ArrayList<>();
        List<String> late = new ArrayList<>();
        int numLate = schedule(jobs, onTime, late);
        System.out.println("On time: " + onTime);
        System.out.println("Late: " + late);              // Late: [C, D]
        System.out.println("Minimum late jobs: " + numLate); // Minimum late jobs: 2
    }
}

5. Smith's Rule (Weighted Shortest Processing Time)

Given $n$ jobs with processing times $p_i$ and weights $w_i$ (no deadlines at all), order them to minimize the total weighted completion time $\sum_i w_i C_i$, where $C_i$ is the time at which job $i$ finishes. A heavier weight represents a job whose customer cares more about a fast finish.

Proof Sketch: an Adjacent-Swap Exchange Argument

Consider two jobs $i$ and $j$ scheduled consecutively, with $i$ immediately before $j$, and let $t$ be the time everything before them finishes (fixed regardless of their internal order, since the pair still occupies exactly $p_i+p_j$ time either way). The weighted contribution of just this pair is:

$$\text{$i$ before $j$}: \quad w_i(t+p_i) + w_j(t+p_i+p_j)$$

$$\text{$j$ before $i$}: \quad w_j(t+p_j) + w_i(t+p_j+p_i)$$

Subtracting the two, every term involving $t$ and $p_i+p_j$ together cancels, leaving:

$$(\text{$i$ before $j$}) - (\text{$j$ before $i$}) = w_j p_i - w_i p_j$$

Running $i$ before $j$ is at least as good exactly when $w_j p_i \le w_i p_j$, i.e. when $p_i/w_i \le p_j/w_j$. So any adjacent pair that violates increasing-ratio order can be swapped without increasing the total weighted completion time, and swapping strictly decreases it whenever the ratios differ. Repeating this bubbles any schedule into Smith's Rule order without ever making things worse, so the fully-sorted order is optimal. This "adjacent swap" argument is a third distinct proof style in this lesson — different from Job Sequencing's exchange-with-optimal argument and from EDF's staying-ahead argument.

Complexity

A single sort by ratio: $O(n \log n)$ time, $O(n)$ space.

def smiths_rule(jobs):
    """
    Smith's Rule (WSPT): minimize sum(weight_i * completion_time_i).
    jobs: list of (job_id, processing_time, weight)
    Returns (order, total_weighted_completion_time). Time: O(n log n), Space: O(n).
    """
    # Sort by processing_time / weight ascending (equivalently weight/processing_time descending)
    ordered = sorted(jobs, key=lambda j: j[1] / j[2])

    current_time = 0
    total = 0
    order = []
    for job_id, p, w in ordered:
        current_time += p
        total += w * current_time
        order.append(job_id)
    return order, total

jobs = [("J1", 2, 1), ("J2", 3, 4), ("J3", 4, 3)]
order, total = smiths_rule(jobs)
print("Order:", order)                              # Order: ['J2', 'J3', 'J1']
print("Total weighted completion time:", total)      # Total weighted completion time: 42

// Smith's Rule (WSPT): minimize sum(weight_i * completion_time_i).
// Time: O(n log n), Space: O(n)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Job {
    std::string id;
    double processingTime;
    double weight;
};

double smithsRule(std::vector<Job> jobs, std::vector<std::string>& orderOut) {
    std::sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return (a.processingTime / a.weight) < (b.processingTime / b.weight);
    });

    double currentTime = 0.0;
    double total = 0.0;
    for (const auto& job : jobs) {
        currentTime += job.processingTime;
        total += job.weight * currentTime;
        orderOut.push_back(job.id);
    }
    return total;
}

int main() {
    std::vector<Job> jobs{
        {"J1", 2, 1}, {"J2", 3, 4}, {"J3", 4, 3}
    };
    std::vector<std::string> order;
    double total = smithsRule(jobs, order);
    std::cout << "Order: ";
    for (auto& id : order) std::cout << id << " ";
    std::cout << "\nTotal weighted completion time: " << total << "\n"; // 42
}

// Smith's Rule (WSPT): minimize sum(weight_i * completion_time_i).
// Time: O(n log n), Space: O(n)
import java.util.*;

public class SmithsRule {
    static class Job {
        String id;
        double processingTime;
        double weight;
        Job(String id, double processingTime, double weight) {
            this.id = id;
            this.processingTime = processingTime;
            this.weight = weight;
        }
    }

    static double schedule(List<Job> jobs, List<String> orderOut) {
        jobs.sort(Comparator.comparingDouble(j -> j.processingTime / j.weight));

        double currentTime = 0.0;
        double total = 0.0;
        for (Job job : jobs) {
            currentTime += job.processingTime;
            total += job.weight * currentTime;
            orderOut.add(job.id);
        }
        return total;
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>(List.of(
            new Job("J1", 2, 1),
            new Job("J2", 3, 4),
            new Job("J3", 4, 3)
        ));
        List<String> order = new ArrayList<>();
        double total = schedule(jobs, order);
        System.out.println("Order: " + order);                          // [J2, J3, J1]
        System.out.println("Total weighted completion time: " + total); // 42.0
    }
}

6. Earliest Deadline First (EDF)

EDF is a policy rather than a one-shot sort: at every decision point, run whichever available job has the nearest deadline. On a single machine with no preemption and all jobs available at time 0, always running in nearest-deadline order is equivalent to sorting once by deadline, which is exactly the order Moore-Hodgson and the worked example above scan in.

EDF answers two related questions:

• Feasibility: can every job meet its deadline at all? Simulate the deadline order once; if any job's cumulative completion time exceeds its own deadline, no schedule can meet every deadline (EDF is the most forgiving order, so if EDF fails, everything fails).
• Minimizing maximum lateness $L_{\max} = \max_i (C_i - d_i)$: when not every job can meet its deadline, EDF order still minimizes the worst single overrun.

The correctness argument, briefly: if two adjacent jobs run out of deadline order, swapping them to put the nearer deadline first cannot increase either job's lateness and cannot increase the schedule's maximum lateness — the later job in the swapped pair finishes exactly where the earlier one used to, and the lateness of every other job is unaffected. Repeating this bubbles any schedule into EDF order without ever increasing $L_{\max}$, so EDF order is optimal. That is a "staying ahead" style claim; the full inductive proof, with the loop invariant made precise, is worked out in Part 16, Section 8: Staying-Ahead Arguments, using EDF-minimizing-maximum-lateness as its worked example. Running the feasibility check on the five jobs from the worked example above reports infeasible right at job C (cumulative time 9 exceeds its deadline of 4) — exactly the point where Moore-Hodgson had to drop a job.

Feasibility-Check Implementation

def edf_feasible(jobs):
    """
    EDF feasibility check: can every job meet its deadline on one machine?
    jobs: list of (job_id, processing_time, deadline)
    Returns (feasible, first_violator_or_None). Time: O(n log n), Space: O(n).
    """
    ordered = sorted(jobs, key=lambda j: j[2])  # earliest deadline first
    current_time = 0
    for job_id, p, deadline in ordered:
        current_time += p
        if current_time > deadline:
            return False, job_id
    return True, None

feasible_jobs = [("X", 2, 3), ("Y", 1, 2), ("Z", 3, 6)]
print(edf_feasible(feasible_jobs))  # (True, None)

infeasible_jobs = [("A", 1, 2), ("B", 2, 3), ("C", 6, 4), ("D", 4, 5), ("E", 2, 6)]
print(edf_feasible(infeasible_jobs))  # (False, 'C')

// EDF feasibility check: can every job meet its deadline on one machine?
// Time: O(n log n), Space: O(n)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <optional>

struct Job {
    std::string id;
    int processingTime;
    int deadline;
};

bool edfFeasible(std::vector<Job> jobs, std::string& firstViolator) {
    std::sort(jobs.begin(), jobs.end(),
              [](const Job& a, const Job& b) { return a.deadline < b.deadline; });

    int currentTime = 0;
    for (const auto& job : jobs) {
        currentTime += job.processingTime;
        if (currentTime > job.deadline) {
            firstViolator = job.id;
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<Job> feasibleJobs{{"X", 2, 3}, {"Y", 1, 2}, {"Z", 3, 6}};
    std::string violator;
    std::cout << std::boolalpha << edfFeasible(feasibleJobs, violator) << "\n"; // true

    std::vector<Job> infeasibleJobs{{"A", 1, 2}, {"B", 2, 3}, {"C", 6, 4}, {"D", 4, 5}, {"E", 2, 6}};
    std::cout << edfFeasible(infeasibleJobs, violator) << " at " << violator << "\n"; // false at C
}

// EDF feasibility check: can every job meet its deadline on one machine?
// Time: O(n log n), Space: O(n)
import java.util.*;

public class EdfFeasibility {
    static class Job {
        String id;
        int processingTime;
        int deadline;
        Job(String id, int processingTime, int deadline) {
            this.id = id;
            this.processingTime = processingTime;
            this.deadline = deadline;
        }
    }

    static String isFeasible(List<Job> jobs) {
        jobs.sort(Comparator.comparingInt(j -> j.deadline));
        int currentTime = 0;
        for (Job job : jobs) {
            currentTime += job.processingTime;
            if (currentTime > job.deadline) return job.id; // first violator, or null if feasible
        }
        return null;
    }

    public static void main(String[] args) {
        List<Job> feasible = new ArrayList<>(List.of(
            new Job("X", 2, 3), new Job("Y", 1, 2), new Job("Z", 3, 6)));
        System.out.println("Feasible: " + (isFeasible(feasible) == null)); // true

        List<Job> infeasible = new ArrayList<>(List.of(
            new Job("A", 1, 2), new Job("B", 2, 3), new Job("C", 6, 4),
            new Job("D", 4, 5), new Job("E", 2, 6)));
        System.out.println("First violator: " + isFeasible(infeasible)); // C
    }
}

7. Shortest Processing Time (SPT)

SPT always runs the shortest remaining job next. It is exactly Smith's Rule (Section 5) with every weight set to $w_i = 1$: the ratio $p_i/w_i$ collapses to $p_i$, so sorting by increasing ratio becomes sorting by increasing processing time. SPT minimizes the total (unweighted) completion time $\sum_i C_i$, which is equivalent to minimizing the average completion time and average waiting time across jobs — a common goal when every job matters equally and there are no deadlines.

SPT in Practice

Because SPT is Smith's Rule with unit weights, the Smith's Rule code above already implements it — call it with every weight equal to 1. A short illustrative version, sorting directly by processing time:

def spt_order(jobs):
    """
    SPT: minimize total (unweighted) completion time.
    jobs: list of (job_id, processing_time). Time: O(n log n), Space: O(n).
    """
    ordered = sorted(jobs, key=lambda j: j[1])  # shortest processing time first
    current_time = 0
    total_completion = 0
    for job_id, p in ordered:
        current_time += p
        total_completion += current_time
    return [job_id for job_id, _ in ordered], total_completion

order, total = spt_order([("J1", 2), ("J2", 3), ("J3", 4)])
print("Order:", order)                  # Order: ['J1', 'J2', 'J3']
print("Total completion time:", total)  # Total completion time: 2 + 5 + 9 = 16

8. Complexity Comparison

Every one of these algorithms is dominated by its sort, so all four share the same $O(n \log n)$ time and $O(n)$ space bound. What differs is the comparator — and, for Moore-Hodgson, an extra data structure (the max-heap) needed to make the eviction step as cheap as the sort that surrounds it.

On the same three jobs, EDF order (P2, P3, P1) leaves only P1 late, and only by 1 unit — the minimum possible maximum lateness. SPT order (P3, P1, P2) finishes P2 five units after its deadline, but its total completion time (2+5+10=17) beats EDF's (5+7+10=22) — the minimum possible total completion time. Neither ordering is "better" in general; each is optimal for its own objective.

9. Applications and Alternatives

These four rules only cover single-machine, non-preemptive, deadline-independent-of-order problems. Multiple machines, preemption, precedence constraints between jobs, and setup times between different job types each require different (and often NP-hard) formulations — the exercises below touch on precedence constraints as a preview of that harder territory.

10. Exercises and Mastery

Easy

1. Given jobs (processing times only) $\{6, 2, 5, 1\}$, give the SPT order and compute the total completion time.
2. For the same four jobs, compute the average (mean) completion time and explain why SPT minimizes it.

Medium

1. Trace Moore-Hodgson on: P (p=3, d=3), Q (p=2, d=5), R (p=5, d=6), S (p=1, d=7), T (p=4, d=8). List the on-time set, the late set, and the running-time value at each step.
2. Prove (or disprove with a counterexample) that the late set Moore-Hodgson produces is unique — is there ever more than one minimum-size late set for the same input?

Hard

1. Suppose jobs carry weights and processing times as in Smith's Rule, but a precedence constraint requires job B to run only after job A completes (a chain of two jobs). Sorting each job independently by $p_i/w_i$ can now produce an infeasible order. Describe, in words, how you would adapt the ratio idea — consider treating the constrained chain as a single combined "super-job" with a combined ratio, and decide what that combined ratio should be. Code is optional; a correct written argument for why your combined-ratio approach preserves optimality is the goal.

Review rhythm: tomorrow, reconstruct all four ordering rules and which objective each solves, from memory. Next week, re-derive Smith's Rule's adjacent-swap inequality without looking it up, and re-implement Moore-Hodgson's eviction step with a heap. Several weeks later, work the precedence-constrained Hard exercise again and check whether your combined-ratio idea still holds up. Finally, teach someone who already knows Job Sequencing why deadlines-with-arbitrary-processing-times needs a completely different algorithm.

11. Summary Cheat Sheet

• Moore-Hodgson: minimize late jobs — sort by deadline, evict the largest-processing-time scheduled job whenever the running time overflows a deadline (max-heap).
• Smith's Rule (WSPT): minimize total weighted completion time — sort by increasing $p_i/w_i$ (adjacent-swap exchange argument).
• EDF: feasibility check and minimizing maximum lateness — always run the nearest deadline next (staying-ahead argument, proved in Part 16).
• SPT: minimize total/average completion time — Smith's Rule with every weight equal to 1.
• All four share $O(n \log n)$ time (one sort) and $O(n)$ space; the objective, not the machinery, is what changes.
• Job Sequencing (deadlines + profits, unit processing time, jobs can be skipped) is a related but distinct problem, covered in Part 16, not repeated here.