Learning-Augmented Size-Based Job Scheduling

19 concepts13 papers3 proposals

In queueing theory and systems design, prioritizing shorter jobs—via policies like Shortest Job First (SJF) or Shortest Remaining Processing Time (SRPT)—is mathematically proven to minimize average latency and prevent small tasks from getting trapped behind massive ones (Adam Wierman et al., Heavy-traffic analysis of mean response time under Shortest Remaining Processing Time). However, implementing these policies in practice faces a fundamental roadblock: systems are typically non-clairvoyant. They do not know how long a job will take until it finishes. Historically, schedulers have relied on notoriously inaccurate user-provided estimates or defaulted to First-Come-First-Served (FCFS) logic, leading to severe head-of-line blocking and resource waste.

A rapidly growing body of research solves this dilemma by integrating machine learning predictions directly into the scheduling loop. By replacing blind execution with learning-augmented scheduling, these techniques unlock the performance of size-based policies even when future runtimes are completely unknown.

Why Order Matters More Than Numerical Accuracy

A natural skepticism arises when introducing machine learning into core infrastructure: what happens when the predictions are wrong? The core intuition for why learning-augmented scheduling works so well lies in a key insight formalized by Michael Mitzenmacher in [/paper/art_a7071c9acf794da1a32f48f717dcd666]: the scheduler's efficiency depends far more on the relative ordering of jobs than on the precise numerical accuracy of the runtime predictions.

If a predictor estimates that Job A will take 2 minutes and Job B will take 20 minutes, it does not matter if Job A actually takes 5 minutes and Job B takes 50 minutes. As long as the predictor correctly identifies that Job A is shorter than Job B, the scheduler will prioritize Job A, clearing it from the queue and avoiding head-of-line blocking. This ordinal robustness means that even highly imperfect ML models can yield massive performance gains over blind baselines.

Preemption as an Error-Correction Mechanism

When ordinal mistakes do happen—such as predicting a long job to be short—how does the system recover? The answer lies in the interplay between prediction and preemption (the ability to pause and resume tasks).

As analyzed by Matteo Dell'Amico in The Supermarket Model With Known and Predicted Service Times, non-preemptive scheduling is highly sensitive to prediction errors because once a mispredicted long job starts, it locks up the processor. Preemptive size-based scheduling, however, acts as a natural error-correction mechanism. If a long task is mistakenly prioritized because of a low duration estimate, it will eventually exceed its predicted runtime. At that point, the system can dynamically deprioritize or pause it, allowing new, genuinely shorter tasks to interrupt it. This continuous adjustment mitigates the "price of misprediction" and prevents system degradation (Evripidis Bampis et al., Non-Clairvoyant Makespan Minimization Scheduling with Predictions).

Balancing Consistency and Robustness

To be viable in production, learning-augmented schedulers must navigate the trade-off between consistency (how well the algorithm performs with perfect predictions) and robustness (how well it performs in the worst-case scenario with adversarial predictions).

Evripidis Bampis et al. design frameworks where the scheduling error scales linearly with the total prediction error, ensuring that performance degrades gracefully rather than catastrophically (Scheduling with Untrusted Predictions). One powerful mechanism to achieve this balance is proportional resource allocation. Instead of strictly running one job at a time, the system distributes processing capacity across active jobs proportionally to their estimated remaining requirements (Zhiyi Tan 0001, Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan). This simultaneous execution model smooths out the impact of any single bad prediction.

Furthermore, to prevent the indefinite starvation of long jobs that strict size-based policies can cause, modern mechanisms use "virtual arrival times." As demonstrated by George Yu et al., a scheduler can assign priority by subtracting a size-dependent value from a job's actual arrival time (Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1). This boosts smaller jobs while guaranteeing that older, larger jobs eventually accumulate enough priority to execute, optimizing tail latency.

From Theory to Production Systems

The practical implications of this paradigm span high-performance computing (HPC), deep learning clusters, and cloud infrastructure:

Key Foundational Work

Improving backfilling by using machine learning to predict running times (2015) — contributed 2 concept elements to this direction.
Multi-User Computation Partitioning for Latency Sensitive Mobile Cloud Applications (2015) — contributed 2 concept elements to this direction.
Heavy-traffic analysis of mean response time under Shortest Remaining Processing Time (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_shortest_job_first_backfilling_f146fb7b,
  title = {shortest-job-first backfilling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shortest-job-first-backfilling/rdr_f146fb7b35654015ac7944abb6ce7289},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_shortest_job_first_backfilling_f146fb7b_v1,
  title = {shortest-job-first backfilling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shortest-job-first-backfilling/rdr_f146fb7b35654015ac7944abb6ce7289/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake