Skip to content

PATTERN Cited by 1 source

Earliest-finish-job greedy

Earliest-finish-job greedy is the online scheduling primitive of "iteratively [scheduling] the job that finishes earliest" among all queued candidates, revising the choice whenever a new job arrives that would finish earlier than the currently-running one (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

Under the interrupt-and- restart preemption policy — where interrupted jobs lose their partial work but remain in the queue — this greedy achieves a ½-competitive ratio against the offline optimum, which "matches the result in the offline setting". That is: no online algorithm (under interrupt-and-restart) beats ½, and this simple greedy achieves ½.

Why earliest-finish maximises throughput

The objective is throughput — the number of jobs completed. Every completed job brings "equal weight, regardless of its length" (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity). Under that objective, the economic shape is clear: one short job counts as much as one long job, so throughput is maximised by completing the cheapest (shortest-remaining- time) jobs first, in sequence.

Earliest-finish-job greedy operationalises this: at any decision point, pick the job whose completion time is soonest under the current capacity profile. Under interrupt- and-restart, "earliest finish" is a moving target — a newly-arrived job with a very short duration can jump to the front if it'd finish before the job currently running. The scheduler interrupts, runs the new short job, and returns to the older one once the new one completes.

Relationship to SRTF

In classical textbook scheduling, Shortest Remaining Time First (SRTF) is a preemptive CPU-scheduling discipline: always run the process with the shortest remaining burst time. SRTF optimises average turnaround time under the unweighted, single-CPU, known-burst-time model.

Earliest-finish-job greedy is closely related but not identical:

  • Different objective. SRTF optimises turnaround time; earliest-finish-job greedy optimises throughput (count of completed jobs). Under unweighted jobs these are closely correlated but not identical.
  • Different execution model. SRTF assumes known burst times; earliest-finish-job greedy in the 2026-02-11 paper operates over known job durations (the online aspect is that jobs arrive one at a time, not that durations are unknown).
  • Different preemption semantics. SRTF assumes checkpoint-and-resume (the process's partial state is preserved); earliest-finish-job greedy in the 2026-02-11 paper operates under interrupt-and-restart (partial work is lost).

The interrupt-and-restart semantics is what makes the ½- competitive bound non-trivial — under checkpoint-and-resume, SRTF can do strictly better.

Why ½ is tight

The ½-competitive bound is tight for interrupt-and-restart online throughput scheduling — no online algorithm can beat ½ in the worst case, and this greedy achieves ½. Intuition for the lower bound: the adversary can always construct an input where the online algorithm commits to one job that's slightly-but-not-significantly longer than the optimal choice, and the offline optimum uses the perfect choice for each decision. Any given online decision can be no more than a factor-of-2 off the offline optimum without the online algorithm reducing to random guessing.

The result is elegant: a very simple greedy — "run whichever queued job finishes earliest" — is already optimal among online algorithms under this preemption semantics. No elaborate online algorithm can do better.

Production applicability

Earliest-finish-job greedy maps onto real schedulers in contexts where:

  • Jobs have known durations (user-declared CPU requirements, or profile-derived estimates).
  • The preemption substrate is interrupt-and-restart (the runtime discards partial state on interrupt; the job is simply restarted).
  • The optimisation objective is count of completed jobs, not weighted throughput or latency.

Real cluster schedulers typically sit somewhere else in this design space — weighted priorities, QoS classes, deadline constraints, checkpoint-capable workloads — but the earliest-finish-job greedy is the theoretical baseline against which production heuristics can be compared. A scheduler whose behaviour on unweighted, known-duration, interrupt-and-restart inputs differs from earliest-finish- greedy is leaving throughput on the table relative to the theoretical optimum for that regime.

Seen in

Last updated · 200 distilled / 1,178 read