Online Scheduling / Load Balancing

Why Online Scheduling / Load Balancing Matters

Imagine a service with several identical workers and a stream of tasks. Each task reveals how much processing it needs when it is submitted, and the router must immediately commit it to one worker. It cannot move old tasks when a larger one appears later. The objective is to finish the whole collection as early as possible, which means minimizing the largest worker workload.

A natural rule is list scheduling: assign each newly revealed job to the worker with the least total work already committed to it. This greedy choice is cheap, causal and easy to inspect. It cannot predict future large jobs, so it can be worse than a hindsight schedule even when it makes the best immediate choice. Competitive analysis quantifies that loss.

We will study the classical online list model on identical machines, prove list scheduling's $2-1/m$ competitive guarantee, and construct an input that attains the bound. A complete simulation records every assignment, planned start/finish time, worker load, work/span lower bound and decision comparison. Python, C++ and Java use identical logic and produce identical output.

Task routing, batch-worker pools and distributed work queues provide useful motivations, but their actual constraints need checking before applying the theorem. Unknown job durations, release timestamps, machine speeds, data locality and migration change the model. The prerequisites on algorithm analysis and queues supply the cost and state reasoning needed to make these distinctions precise.

Core Concepts and Terminology

There are $m\ge1$ identical unit-speed workers, numbered 0 through $m-1$, and a finite sequence $\sigma=(p_1,\ldots,p_n)$ of independent jobs with nonnegative processing times. Job j reveals its duration $p_j$ when it is presented. Before the next job is revealed, the algorithm must assign j permanently to exactly one worker. A job cannot be split, preempted, rejected or migrated. Each worker executes its assigned jobs sequentially in assignment order.

Revelation order is not a clock. The list model has no release timestamps and no elapsed execution between reveal events. All jobs may be viewed as available at planned execution time zero; only their descriptions are revealed sequentially to the assignment policy. Thus an assignment made at the seventh reveal can have planned start time 2. This would not be valid for a job actually released at physical time 7. Online-over-time scheduling needs a different feasibility model.

Let $a_j$ be job j's assigned worker. After the first k assignments, the committed load is

$$L_i^{(k)}=\sum_{\substack{1\le j\le k\\a_j=i}}p_j,\qquad C_k=\max_{0\le i\lt m}L_i^{(k)}.$$

The final makespan is $C_{\max}=C_n$. A job appended to worker i has planned interval $[L_i,L_i+p_j)$, after which its load increases by $p_j$. Half-open intervals allow consecutive jobs to meet at one endpoint without overlap. A zero-duration job has an empty interval, contributes no load and still receives one assignment.

Work and intrinsic span for a prefix are

$$W_k=\sum_{j=1}^k p_j,\qquad S_k=\max_{1\le j\le k}p_j,$$

with both zero for an empty prefix. Jobs have no dependencies on each other, so the intrinsic critical path consists of one longest job and has length $S_k$. Ordering several jobs on one worker is a scheduling constraint, not an added intrinsic dependency in the input. For a real task DAG the span may be larger than its longest individual task, and readiness must also be respected.

The offline optimum knows the full collection and may choose another assignment, but uses the same m workers and the same nonpreemptive, indivisible jobs. Equivalently it partitions the jobs among workers to minimize the maximum sum:

$$\operatorname{OPT}(\sigma)=\min_{a_1,\ldots,a_n\in\{0,\ldots,m-1\}}\max_{0\le i\lt m}\sum_{j:a_j=i}p_j.$$

Any feasible schedule needs enough aggregate processing capacity and enough time for its longest indivisible job. Therefore

$$B_k=\max\left(\frac{W_k}{m},S_k\right)\le\operatorname{OPT}(\sigma_k)\le C_k.$$

B is a lower bound, not generally the optimum. On two workers with jobs $[3,3,3]$, $B=9/2$ but OPT=6 because one worker must receive two jobs. The program prints B as LB and $C_k/B_k$ as C/LB. When B is positive, this is an upper bound on the actual observed ratio $C_k/\operatorname{OPT}(\sigma_k)$, not a claimed exact ratio. In this example C/LB is $4/3$, while the actual ratio is 1. If all jobs are zero or no jobs arrive, both C and OPT are zero; the multiplicative inequality holds directly and the undefined ratio is printed as NA.

A deterministic policy is online if two streams with the same revealed prefix produce the same assignments on that prefix. It may know m and its own past state. Our controller receives only one duration per call; it receives neither a future array nor the final n. Ties among equal loads go to the smallest worker ID, making every trace reproducible.

How Online Scheduling / Load Balancing Works, Step by Step

1. Initialize one controller. Create m zero loads, zero jobs seen, zero total work, zero longest job, zero makespan and zero load-comparison count. The teaching programs accept integer m from 1 through 8, at most 64 jobs, and integer durations from 0 through 1,000,000. These caps bound the display and arithmetic; the theorem covers arbitrary finite lists and nonnegative durations under the abstract model.
2. Reveal one current duration. Validate it before modifying state. The controller does not ask how many later jobs exist or what their sizes will be. A rejected duration or a 65th job leaves all existing assignments and counters unchanged.
3. Scan worker loads in ID order. Initialize the candidate to worker 0. For each worker i from 1 to m−1, replace the candidate only when $L_i\lt L_{\mathrm{candidate}}$. Equal loads retain the earlier, smaller ID. This performs exactly m−1 load comparisons for every accepted job, even a zero-duration one.
4. Append the whole job. Let selected worker be q, start s equal its old load and finish f equal $s+p_j$. Assign the interval $[s,f)$ to that worker and update only its load to f. The new job's duration is identical on every worker, so minimizing old load also minimizes its immediate completion time. This local fact does not claim a globally optimal assignment for the eventual list.
5. Update counters and return a receipt. Increment the job count, add duration to work, update span as the largest revealed duration, and update makespan as the maximum of its prior value and f. Copy the new load vector into the receipt so later assignments cannot rewrite an earlier trace snapshot.
6. Audit outside the decision. The driver formats work, span, makespan, B and C/B after the commitment. It can inspect the whole completed test input for verification, but neither future jobs nor offline results feed back into the controller. It prints exact reduced fractions rather than floating-point approximations.

For the sample's seventh job, prior loads are $[2,2,2]$ and duration is 3. Both later-worker comparisons fail to improve on worker 0. The job starts at planned time 2 and ends at 5, leaving loads $[5,2,2]$. Work rises from 6 to 9, span from 1 to 3, and makespan from 2 to 5. The separate lower-bound audit gives B=3. No old unit job moves to accommodate the new large job.

A binary min-heap keyed by the pair (load, worker ID) implements exactly the same rule in $O(1+\log m)$ worst-case update time. It needs one current entry per worker, removal of the minimum, then insertion with the increased load. The code uses a scan so every comparison and tie can be explained directly. A heap changes the decision data structure, not the schedule or competitive proof, provided it preserves the same pair ordering.

flowchart TD
    A["Validate worker count and initialize zero loads"] --> B{"Another job is revealed?"}
    B -->|No| C["Driver prints final audit"]
    B -->|Yes| D["Read only current duration"]
    D --> E{"Valid duration and trace capacity?"}
    E -->|No| F["Reject without changing state"]
    E -->|Yes| G["Candidate is worker zero; scan later worker IDs"]
    G --> H{"Another worker to compare?"}
    H -->|Yes| I{"Its load is strictly smaller?"}
    I -->|Yes| J["Replace candidate"]
    I -->|No| K["Retain candidate, including ties"]
    J --> L["Advance scan index"]
    K --> L
    L --> H
    H -->|No| M["Append job and update loads and counters"]
    M --> N["Return copied receipt; driver audits revealed prefix"]
    N --> B

Worked Example with a Full Trace

Take three workers and the revealed list $[1,1,1,1,1,1,3]$. The driver stores this sample, but the controller sees only one duration at a time. Worker IDs are 0, 1 and 2. Initially all loads, work, span and makespan are zero.

1. J1, duration 1. Before $[0,0,0]$: compare worker 1's 0 with candidate 0 and worker 2's 0 with candidate 0; neither is strictly smaller. Choose worker 0 and interval $[0,1)$. After $[1,0,0]$, W=1, S=1, C=1, B=1, C/B=1.
2. J2, duration 1. Before $[1,0,0]$: worker 1's 0 improves on candidate load 1; worker 2's 0 ties the new candidate, so retain worker 1. Assign $[0,1)$ there. After $[1,1,0]$, W=2, S=1, C=1, B=1, C/B=1.
3. J3, duration 1. Before $[1,1,0]$: worker 1 ties candidate load 1, then worker 2's 0 improves it. Assign worker 2 interval $[0,1)$. After $[1,1,1]$, W=3, S=1, C=1, B=1, C/B=1.
4. J4, duration 1. Before $[1,1,1]$: both comparisons tie, so choose worker 0 interval $[1,2)$. After $[2,1,1]$, W=4, S=1, C=2, $B=4/3$, and $C/B=3/2$.
5. J5, duration 1. Before $[2,1,1]$: worker 1 improves from load 2 to 1, and worker 2 ties it. Assign worker 1 interval $[1,2)$. After $[2,2,1]$, W=5, S=1, C=2, $B=5/3$, and $C/B=6/5$.
6. J6, duration 1. Before $[2,2,1]$: worker 1 ties candidate load 2, then worker 2 improves it to 1. Assign worker 2 interval $[1,2)$. After $[2,2,2]$, W=6, S=1, C=2, B=2, C/B=1.
7. J7, duration 3. Before $[2,2,2]$: both comparisons tie and worker 0 remains selected. Assign $[2,5)$ there. After $[5,2,2]$, W=9, S=3, C=5, B=3, and $C/B=5/3$.

Each accepted job uses two comparisons, for 14 total. Each job appears in exactly one nonoverlapping interval on its assigned worker. All seven durations sum to 9, which equals the sum of final loads. The planned idle intervals on workers 1 and 2 from time 2 to 5 reflect the irreversible packing; they are not times when the online controller failed to process an arrival.

For this completed list, the lower bound is attained by a feasible offline packing: put J7 alone on one worker, J1/J2/J3 on another, and J4/J5/J6 on the third. Each worker load is 3. Since $B=3\le\operatorname{OPT}\le3$, OPT is exactly 3 and the actual observed ratio is $5/3=2-1/3$. This is a proof of optimality for this particular offline packing, not an assumption that B is always exact. For the fourth and fifth prefixes, indivisibility similarly makes OPT=2 even though the displayed rational lower bounds are below 2; their actual online ratios are 1.

If the same multiset were revealed with duration 3 first, least-load scheduling would give final loads $[3,3,3]$ and makespan 3. That is a different online input order. Sorting the entire original list before its first decision would use future information and would implement an offline heuristic instead.

Implementation in Python, C++, and Java

Each panel is a complete standalone program with the same seven-job sample. Run the Python panel with Python 3; compile the C++ panel as C++17; save the Java panel as Main.java, compile it and run Main. All three print exactly the output below. No external packages, threads or wall-clock timing are involved.

The controller's constructor receives only m, and its next-job method receives only the current duration. The complete sample list lives in the driver. The controller stores loads and prefix counters, returns a per-job receipt with an independent load snapshot, and never sorts, buffers or inspects future jobs. This interface makes the information boundary concrete.

The teaching API validates integer m from 1 through 8, duration from 0 through 1,000,000, and at most 64 accepted jobs. Python explicitly rejects booleans and non-integer values; C++ and Java use integer argument types. Validation occurs before any mutation. Arithmetic uses exact integers, with 64-bit loads/totals in C++ and Java. Under these caps total work is at most 64,000,000, so the displayed products and counters fit safely. Removing caps requires reviewing overflow and text costs.

The audit helper is separate from the choice rule. It computes the exact rational B using integer numerator $Q=\max(W,mS)$, so $B=Q/m$, and formats $C/B=mC/Q$. It does not solve the offline partition problem. A denominator of zero returns NA, covering empty and all-zero workloads without inventing a ratio. The final guarantee is the theorem's factor, not a measured running time or a computed optimum.

Each checks value counts only load comparisons in the worker-selection scan. It excludes validation, counter maxima, copying and formatting. The planned interval uses time units of processing, while the comparison count measures scheduler computation. Worker IDs start at zero; job IDs start at one. Receipts copy the loads so they remain valid as later jobs arrive; callers should treat controller state and returned receipts as read-only outside the supplied methods.

from dataclasses import dataclass
from math import gcd


@dataclass(frozen=True)
class Step:
    job: int
    duration: int
    worker: int
    start: int
    finish: int
    loads: tuple
    work: int
    span: int
    makespan: int
    comparisons: int


class ListScheduler:
    def __init__(self, workers):
        if type(workers) is not int or not 1 <= workers <= 8:
            raise ValueError("worker count must be an integer from 1 through 8")
        self.loads = [0] * workers
        self.seen = self.work = self.span = self.makespan = 0
        self.comparisons = 0

    def next_job(self, duration):
        if type(duration) is not int or not 0 <= duration <= 1_000_000:
            raise ValueError("duration must be an integer from 0 through 1000000")
        if self.seen == 64:
            raise ValueError("teaching trace supports at most 64 jobs")
        chosen = 0
        for worker in range(1, len(self.loads)):
            if self.loads[worker] < self.loads[chosen]:
                chosen = worker
        start = self.loads[chosen]
        finish = start + duration
        self.loads[chosen] = finish
        self.seen += 1
        self.work += duration
        self.span = max(self.span, duration)
        self.makespan = max(self.makespan, finish)
        checks = len(self.loads) - 1
        self.comparisons += checks
        return Step(self.seen, duration, chosen, start, finish, tuple(self.loads),
                    self.work, self.span, self.makespan, checks)


def numbers(values):
    return "[" + ",".join(map(str, values)) + "]"


def fraction(numerator, denominator):
    if denominator == 0:
        return "NA"
    divisor = gcd(numerator, denominator)
    return str(numerator // divisor) + "/" + str(denominator // divisor)


def audit(work, span, makespan, workers):
    lower_numerator = max(work, workers * span)
    return (fraction(lower_numerator, workers),
            fraction(workers * makespan, lower_numerator))


def show_step(step):
    lower, upper_ratio = audit(step.work, step.span, step.makespan, len(step.loads))
    return ("J" + str(step.job) + " p=" + str(step.duration) + " -> W" + str(step.worker) +
            " [" + str(step.start) + "," + str(step.finish) + ") loads=" + numbers(step.loads) +
            " W=" + str(step.work) + " span=" + str(step.span) +
            " Cmax=" + str(step.makespan) + " LB=" + lower + " C/LB=" + upper_ratio +
            " checks=" + str(step.comparisons))


def show_final(policy):
    workers = len(policy.loads)
    lower, upper_ratio = audit(policy.work, policy.span, policy.makespan, workers)
    return ("FINAL Cmax=" + str(policy.makespan) + " W=" + str(policy.work) +
            " span=" + str(policy.span) + " LB=" + lower + " C/LB=" + upper_ratio +
            " guarantee=" + fraction(2 * workers - 1, workers) +
            " comparisons=" + str(policy.comparisons))


def main():
    policy = ListScheduler(3)
    jobs = [1, 1, 1, 1, 1, 1, 3]
    print("m=3 tie=lowest worker ID; online list model")
    print("INIT loads=" + numbers(policy.loads) + " W=0 span=0 Cmax=0 LB=0/1 C/LB=NA")
    for duration in jobs:
        step = policy.next_job(duration)
        print(show_step(step))
    print(show_final(policy))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct Step {
    int job;
    long long duration;
    int worker;
    long long start, finish;
    std::vector<long long> loads;
    long long work, span, makespan;
    int comparisons;
};

class ListScheduler {
public:
    std::vector<long long> loads;
    int seen = 0;
    long long work = 0, span = 0, makespan = 0, comparisons = 0;
    explicit ListScheduler(int workers) {
        if (workers < 1 || workers > 8)
            throw std::invalid_argument("worker count must be from 1 through 8");
        loads.assign(static_cast<std::size_t>(workers), 0);
    }
    Step next_job(long long duration) {
        if (duration < 0 || duration > 1000000)
            throw std::invalid_argument("duration must be from 0 through 1000000");
        if (seen == 64) throw std::invalid_argument("teaching trace supports at most 64 jobs");
        int chosen = 0;
        for (int worker = 1; worker < static_cast<int>(loads.size()); ++worker)
            if (loads[worker] < loads[chosen]) chosen = worker;
        long long start = loads[chosen], finish = start + duration;
        loads[chosen] = finish;
        ++seen;
        work += duration;
        span = std::max(span, duration);
        makespan = std::max(makespan, finish);
        int checks = static_cast<int>(loads.size()) - 1;
        comparisons += checks;
        return {seen, duration, chosen, start, finish, loads, work, span, makespan, checks};
    }
};

std::string numbers(const std::vector<long long>& values) {
    std::string out = "[";
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i) out += ",";
        out += std::to_string(values[i]);
    }
    return out + "]";
}
std::string fraction(long long numerator, long long denominator) {
    if (denominator == 0) return "NA";
    long long divisor = std::gcd(numerator, denominator);
    return std::to_string(numerator / divisor) + "/" + std::to_string(denominator / divisor);
}
std::pair<std::string, std::string> audit(long long work, long long span,
                                        long long makespan, int workers) {
    long long lower_numerator = std::max(work, workers * span);
    return {fraction(lower_numerator, workers), fraction(workers * makespan, lower_numerator)};
}
std::string show_step(const Step& step) {
    auto bounds = audit(step.work, step.span, step.makespan, static_cast<int>(step.loads.size()));
    return "J" + std::to_string(step.job) + " p=" + std::to_string(step.duration) +
           " -> W" + std::to_string(step.worker) + " [" + std::to_string(step.start) +
           "," + std::to_string(step.finish) + ") loads=" + numbers(step.loads) +
           " W=" + std::to_string(step.work) + " span=" + std::to_string(step.span) +
           " Cmax=" + std::to_string(step.makespan) + " LB=" + bounds.first +
           " C/LB=" + bounds.second + " checks=" + std::to_string(step.comparisons);
}
std::string show_final(const ListScheduler& policy) {
    int workers = static_cast<int>(policy.loads.size());
    auto bounds = audit(policy.work, policy.span, policy.makespan, workers);
    return "FINAL Cmax=" + std::to_string(policy.makespan) + " W=" + std::to_string(policy.work) +
           " span=" + std::to_string(policy.span) + " LB=" + bounds.first +
           " C/LB=" + bounds.second + " guarantee=" + fraction(2 * workers - 1, workers) +
           " comparisons=" + std::to_string(policy.comparisons);
}

int main() {
    ListScheduler policy(3);
    std::vector<long long> jobs = {1, 1, 1, 1, 1, 1, 3};
    std::cout << "m=3 tie=lowest worker ID; online list model\n";
    std::cout << "INIT loads=" << numbers(policy.loads)
              << " W=0 span=0 Cmax=0 LB=0/1 C/LB=NA\n";
    for (long long duration : jobs) {
        Step step = policy.next_job(duration);
        std::cout << show_step(step) << '\n';
    }
    std::cout << show_final(policy) << '\n';
    return 0;
}

public class Main {
    static final class Step {
        final int job, worker, comparisons;
        final long duration, start, finish, work, span, makespan;
        final long[] loads;
        Step(int job, long duration, int worker, long start, long finish,
             long[] loads, long work, long span, long makespan, int comparisons) {
            this.job = job;
            this.duration = duration;
            this.worker = worker;
            this.start = start;
            this.finish = finish;
            this.loads = loads.clone();
            this.work = work;
            this.span = span;
            this.makespan = makespan;
            this.comparisons = comparisons;
        }
    }

    static final class ListScheduler {
        final long[] loads;
        int seen = 0;
        long work = 0, span = 0, makespan = 0, comparisons = 0;
        ListScheduler(int workers) {
            if (workers < 1 || workers > 8)
                throw new IllegalArgumentException("worker count must be from 1 through 8");
            loads = new long[workers];
        }
        Step nextJob(long duration) {
            if (duration < 0 || duration > 1000000)
                throw new IllegalArgumentException("duration must be from 0 through 1000000");
            if (seen == 64) throw new IllegalArgumentException("teaching trace supports at most 64 jobs");
            int chosen = 0;
            for (int worker = 1; worker < loads.length; ++worker)
                if (loads[worker] < loads[chosen]) chosen = worker;
            long start = loads[chosen], finish = start + duration;
            loads[chosen] = finish;
            ++seen;
            work += duration;
            span = Math.max(span, duration);
            makespan = Math.max(makespan, finish);
            int checks = loads.length - 1;
            comparisons += checks;
            return new Step(seen, duration, chosen, start, finish, loads,
                            work, span, makespan, checks);
        }
    }

    static String numbers(long[] values) {
        StringBuilder out = new StringBuilder("[");
        for (int i = 0; i < values.length; ++i) {
            if (i > 0) out.append(',');
            out.append(values[i]);
        }
        return out.append(']').toString();
    }
    static long gcd(long a, long b) {
        while (b != 0) { long remainder = a % b; a = b; b = remainder; }
        return a;
    }
    static String fraction(long numerator, long denominator) {
        if (denominator == 0) return "NA";
        long divisor = gcd(numerator, denominator);
        return (numerator / divisor) + "/" + (denominator / divisor);
    }
    static String[] audit(long work, long span, long makespan, int workers) {
        long lowerNumerator = Math.max(work, workers * span);
        return new String[] {fraction(lowerNumerator, workers),
                             fraction(workers * makespan, lowerNumerator)};
    }
    static String showStep(Step step) {
        String[] bounds = audit(step.work, step.span, step.makespan, step.loads.length);
        return "J" + step.job + " p=" + step.duration + " -> W" + step.worker +
               " [" + step.start + "," + step.finish + ") loads=" + numbers(step.loads) +
               " W=" + step.work + " span=" + step.span + " Cmax=" + step.makespan +
               " LB=" + bounds[0] + " C/LB=" + bounds[1] + " checks=" + step.comparisons;
    }
    static String showFinal(ListScheduler policy) {
        int workers = policy.loads.length;
        String[] bounds = audit(policy.work, policy.span, policy.makespan, workers);
        return "FINAL Cmax=" + policy.makespan + " W=" + policy.work +
               " span=" + policy.span + " LB=" + bounds[0] + " C/LB=" + bounds[1] +
               " guarantee=" + fraction(2 * workers - 1, workers) +
               " comparisons=" + policy.comparisons;
    }

    public static void main(String[] args) {
        ListScheduler policy = new ListScheduler(3);
        long[] jobs = {1, 1, 1, 1, 1, 1, 3};
        System.out.println("m=3 tie=lowest worker ID; online list model");
        System.out.println("INIT loads=" + numbers(policy.loads) +
                           " W=0 span=0 Cmax=0 LB=0/1 C/LB=NA");
        for (long duration : jobs) {
            Step step = policy.nextJob(duration);
            System.out.println(showStep(step));
        }
        System.out.println(showFinal(policy));
    }
}

Identical expected output (each item below is one printed line):

• m=3 tie=lowest worker ID; online list model
• INIT loads=[0,0,0] W=0 span=0 Cmax=0 LB=0/1 C/LB=NA
• J1 p=1 -> W0 [0,1) loads=[1,0,0] W=1 span=1 Cmax=1 LB=1/1 C/LB=1/1 checks=2
• J2 p=1 -> W1 [0,1) loads=[1,1,0] W=2 span=1 Cmax=1 LB=1/1 C/LB=1/1 checks=2
• J3 p=1 -> W2 [0,1) loads=[1,1,1] W=3 span=1 Cmax=1 LB=1/1 C/LB=1/1 checks=2
• J4 p=1 -> W0 [1,2) loads=[2,1,1] W=4 span=1 Cmax=2 LB=4/3 C/LB=3/2 checks=2
• J5 p=1 -> W1 [1,2) loads=[2,2,1] W=5 span=1 Cmax=2 LB=5/3 C/LB=6/5 checks=2
• J6 p=1 -> W2 [1,2) loads=[2,2,2] W=6 span=1 Cmax=2 LB=2/1 C/LB=1/1 checks=2
• J7 p=3 -> W0 [2,5) loads=[5,2,2] W=9 span=3 Cmax=5 LB=3/1 C/LB=5/3 checks=2
• FINAL Cmax=5 W=9 span=3 LB=3/1 C/LB=5/3 guarantee=5/3 comparisons=14

Complexity, Correctness, and Invariants

Feasibility and state invariants. After k accepted jobs, worker i's load equals the sum of durations assigned to it, total load equals work, and the cached makespan is the largest load. Every job is assigned exactly once; its start equals the chosen worker's previous load and its finish equals start plus duration. Appending these half-open intervals creates no overlap on a worker. Since no release times or precedence constraints exist, starting that worker's first job at zero is feasible. The maximum-duration counter is exactly the independent-job span. These statements follow by induction: initialization establishes zero sums, and each step changes exactly one load by the new duration while updating the corresponding counters.

Why the minimum scan is correct. After comparing worker i, the candidate is the smallest-ID worker with minimum load among workers 0 through i. The invariant holds initially for worker 0. A strictly smaller new load replaces the candidate; a tie retains the smaller already-scanned ID. At the end, the candidate minimizes the pair (load, ID) over all workers. The receipt records that worker's old load before changing it. Future jobs cannot affect an already returned assignment.

Competitive proof. Let C be the final list-scheduling makespan on a positive-work list. Choose a worker finishing at C, and let j be the last job appended to that worker. Write p for that job's duration and s for its start, so $C=s+p$. At its assignment the selected worker had minimum load s, hence every worker had load at least s. The total work assigned before j was therefore at least ms. It is at most W−p, because all other job durations are nonnegative, including any revealed after j. Consequently

$$s\le\frac{W-p}{m},\qquad C\le\frac Wm+\left(1-\frac1m\right)p.$$

Both $W/m\le\operatorname{OPT}$ and $p\le S\le\operatorname{OPT}$. Therefore

$$C\le\left(2-\frac1m\right)\operatorname{OPT}.$$

More strongly, because $W/m\le B$ and $p\le B$,

$$C\le\left(2-\frac1m\right)B\le\left(2-\frac1m\right)\operatorname{OPT}.$$

This also explains why the printed C/LB upper estimate never exceeds the guarantee for a positive-work prefix. The proof applies to every prefix considered as a completed input. All-zero inputs satisfy the inequality directly with C=OPT=0. For m=1 the factor is 1 and the only worker is optimal. No average-case distribution or amortization is needed for this quality guarantee.

Tightness for this algorithm. Give m workers $m(m-1)$ unit jobs, followed by one job of duration m. Least-load assignment balances the unit jobs at m−1 per worker, then assigns the last job to one of them. Thus

$$C=2m-1,\qquad W=m^2,\qquad S=m,\qquad B=m.$$

Offline puts the size-m job alone and packs m unit jobs on each of the other m−1 workers, attaining OPT=m. The ratio is exactly $2-1/m$. For m=1 the same construction is simply one unit job. This is a matching lower-bound example for list scheduling; it does not claim that every possible online policy has this exact optimal factor for every m.

Scheduler time and memory. The scan performs exactly $n(m-1)$ load comparisons. Each accepted job takes $\Theta(m)$ time including reading/scanning the loads and copying its receipt, in the best and worst cases; the same bound holds under any distribution because the scan does not stop early. Constructor cost is $\Theta(m)$, and processing n jobs takes $\Theta(m+nm)$ overall. For fixed m this is linear in n. An empty stream still pays initialization cost. Validation failures stop before assignment. No meaningful “average competitive factor” is specified without a distribution over lists; that is distinct from these runtime bounds.

The live controller uses $\Theta(m)$ memory. One current receipt and its load snapshot use $\Theta(m)$ additional memory. The shown driver prints each receipt immediately instead of retaining a history; its stored sample input adds O(n) space. Keeping all n load snapshots for later inspection would cost $\Theta(nm)$ storage, while retaining only each job's worker/start/finish costs O(n). Output itself contains $\Theta(nm)$ load values. Decimal formatting depends on integer digit length; exact reduced-fraction formatting uses a gcd, so the operation counts treat the bounded machine integers in the teaching API as constant-size. An arbitrary-precision unbounded analysis would account for those bit costs separately.

A heap version reduces the choice/update component to $O(1+\log m)$ worst-case time per job with $\Theta(m)$ live state, after O(m) heap construction. Copying and printing a full load vector after every job still takes $\Theta(m)$ values per receipt, so end-to-end full-trace output would mask that improvement. Round robin can choose a worker in constant time but does not use workload sizes and does not inherit the least-load proof. Competitive quality, decision overhead and processing makespan are three different measures.

The programs were tested against an independent worker-choice and interval reference, including exhaustive small lists, zeros, one worker, many ties, large durations, invalid inputs, capacity rejection and shared-prefix causality. Short workloads were also checked against exact offline partition enumeration. The tight construction was exercised for each supported worker count; receipt snapshots were checked after later updates, and all three programs' sample output was byte-identical.

Variants, Pitfalls, and Optimizations

Online list versus real-time arrivals. If jobs have release dates $r_j$, a planned start must satisfy $s_j\ge r_j$; cumulative work alone no longer describes a worker's next available physical time without accounting for elapsed service and idle periods. Assigning a genuinely late job to an interval in the past is infeasible. An event simulator must advance a clock, process completions, maintain remaining work or availability, and define its allowed decisions. Reuse neither this simulator nor its proof unchanged for that setting.

Known durations versus unknown service. The classical list policy is clairvoyant only about the current job's size, not future jobs. Many actual services know only an estimate. Replacing sizes with estimates makes the least-load decision minimize predicted load; a deterministic guarantee for actual processing times then needs an error model. A few heavy tasks can make equal queue lengths highly unequal in work. The diagram below shows that even a causal count-based rule can violate the least-work bound.

Sorting, lookahead and migration change the contract. Longest-processing-time-first (LPT) sorts a fully known list in decreasing duration, then uses least-load assignment. Its classical offline approximation factor is $4/3-1/(3m)$, but the improved packing uses information an online list policy lacks. A bounded reordering buffer, future predictions or permission to move already assigned jobs are meaningful extensions; name their extra powers rather than calling the resulting experiment the same online algorithm. The code preserves the original reveal order and never repairs the sample after seeing the last job.

Worker heterogeneity and restrictions break the simple choice. With related machine speeds, duration depends on speed; with unrelated machines it may depend arbitrarily on the job/worker pair. Affinity, GPU memory, data locality, setup costs and eligibility constraints may forbid the current least-loaded worker. Choosing minimum projected finish time can be a sensible different heuristic, but the identical-machine proof does not establish the same competitive factor for those variants. Multi-resource load is a vector, so one scalar sum may not capture feasibility.

Dependencies require readiness. For an input DAG, the intrinsic span is the longest dependency path, not just the longest job. A worker cannot start a task before its predecessors complete. Greedy ready-task scheduling has related work/span analysis under stated assumptions, but appending arbitrary revealed tasks to a least-load queue here does not implement that algorithm. Do not use the displayed independent-job span for a workflow with chains, barriers or communication delays.

State consistency and ties matter. With a heap, remove an old worker entry before adding its updated key; leaving stale duplicates can choose an obsolete load. Compare (load, ID) lexicographically for the same deterministic schedule. A distributed router that reads stale loads concurrently may send several jobs to the same worker; the sequential proof assumes a consistent state and one committed assignment at a time. Snapshots should copy load values so later mutation cannot silently rewrite past evidence.

Change the objective only with a new analysis. Makespan minimizes the largest final load. It is not mean response time, total completion time, lateness, deadline misses, maximum queue length or fairness. Shortest-job-first, weighted fair queuing and deadline policies answer other objectives or constraints. Adding more workers reduces the average-work bound but cannot shrink an indivisible longest job; idle capacity may reflect an indivisibility bottleneck rather than a scheduling bug.

Use diagnostics honestly. B is only a lower bound. Label C/B as a ratio upper estimate until an exact optimum or a matching feasible packing establishes OPT. Empty and all-zero lists need direct zero-cost handling. A tight example proves the bound cannot be improved for this algorithm, not that every online algorithm is equally limited. Repeated favorable random tests do not replace a worst-case argument. Measure scheduler CPU overhead separately from the planned makespan; these programs simulate assignments rather than launching workers or measuring speedup.

Practice Problems and Real-World Use

Build a tiny offline oracle before comparing schedule quality. Enumerate each job's possible worker and minimize the maximum resulting sum. For a faster tiny reference, merge states that differ only by worker permutation; this preserves the optimum because workers are identical. The online trace must retain actual worker IDs to check deterministic ties. Use an independently written argmin rule for assignment checks, then compare every interval, prefix sum, span and makespan.

Include no jobs, all-zero jobs, m=1, more workers than jobs, repeated equal loads, a large job first, and a large job last. Verify $\sum_i L_i=W$, every interval length equals its duration, and successive intervals on the same worker meet without overlap. Feed two different futures after an identical prefix and require identical prefix receipts. Submit an invalid job after a valid prefix and ensure validation leaves the prior state untouched.

For each m, generate the unit-jobs-plus-large-job construction and prove its offline packing as well as measuring the online result. Then permute the same multiset and observe how order affects the schedule while offline OPT remains unchanged. Compare scan and heap policies with identical tie rules; their assignments should match exactly even though decision comparison counts differ. For an empirical random policy, specify the seed, size model, run count and what probability/expectation is being estimated.

The applications below are design exercises and possible abstraction points, not claims that the exact policy or its theorem applies to a named production system. Before adopting it, decide whether durations are known, workers are interchangeable, communication matters, assignments may migrate, and actual arrival times constrain starts. Instrument those assumptions along with the load metric.

Primary reading: MIT's approximation-algorithm notes develop the average-load/longest-job lower-bound proof for list scheduling. Leah Epstein's List Scheduling reference entry describes the online identical-machine model and its scheduling context. For the LPT comparison, Della Croce and Scatamacchia’s paper recalls its classical bound and studies refinements. The driver/controller split, validation limits, exact fraction displays, sample trace and test harness here are specific to this lesson.