🤖 machine learning

Learning-Augmented Online Scheduling with Parsimonious Preemption

This paper introduces the first learning-augmented online scheduling algorithms that achieve constant competitive latency with only a constant number of preemptions per job, effectively bridging the gap between theoretical performance and preemption complexity across single, unrelated, and malleable machine settings.

Original authors: Mugen Blue, Sungjin Im, Alexander Lindermayr

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mugen Blue, Sungjin Im, Alexander Lindermayr

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy kitchen with several chefs (machines) and a long list of orders (jobs) coming in. You don't know exactly how long each dish will take to cook until it's finished. This is the classic "online scheduling" problem.

In the past, managers had two bad choices:

The "Blind" Chef: Guess the cooking time perfectly. If you guess right, you are incredibly efficient. But if you guess wrong (and you often will), the whole kitchen grinds to a halt, and orders pile up.
The "Constant Switcher": Since you don't know the times, you just chop every dish for a tiny bit, then switch to the next, then the next, like a hamster on a wheel. This ensures no single dish gets stuck, but the chefs spend so much time switching pans and cleaning counters (preemption) that they barely cook anything.

This paper introduces a new way to run the kitchen using AI predictions. Think of these predictions as a "magic recipe card" that gives a rough estimate of how long a dish will take. The card might be slightly wrong (noisy), but it's better than nothing.

The authors' goal was to build a system that uses these cards to be fast, without forcing the chefs to constantly switch tasks. They call this "parsimonious preemption"—which is just a fancy way of saying "switching tasks only when absolutely necessary."

Here is how their solution works, broken down into simple concepts:

1. The "Smart Queue" (Single Machine)

Imagine a single chef with a set of waiting lines (queues).

Old Way: Every new order goes to the very front line, regardless of what it is.
The New Way (PMLF): When a new order arrives, the chef looks at the "magic recipe card." If the card says "5 minutes," the order goes to the "5-minute line." If it says "30 minutes," it goes to the "30-minute line."
The Magic: As the chef works on a dish, they check the card. If the dish takes longer than the card predicted, the chef moves it to a "longer wait" line.
The Result: If the cards are accurate, the chef rarely has to switch tasks. They just finish the dish. If the cards are wrong, the system automatically corrects itself, but it doesn't panic-switch every second.

2. The "Simulated Reality" (Multiple Chefs)

Now imagine a kitchen with many different chefs, some great at baking, others great at grilling. This is the "Unrelated Machines" problem. A dish might take 1 minute on Chef A but 1 hour on Chef B.

The Problem: The best theoretical way to run this kitchen involves constantly swapping dishes between chefs to keep everyone busy. This causes massive "switching costs."
The New Solution (SNAP): Instead of constantly swapping, the kitchen runs in epochs (time blocks).
1. The Plan: At the start of the block, a computer calculates the perfect theoretical schedule (who should cook what and for how long).
2. The Checkpoint: The computer sets "milestones" based on the magic recipe cards. For example, "Cook until you've done 10 minutes of work."
3. The Execution: The chefs follow the plan. They don't switch tasks until a certain number of dishes hit their milestones.
4. The Switch: Once the milestones are hit, the computer recalculates the plan for the next block.
The Benefit: This limits the number of times chefs have to stop and switch pans. It's like running a relay race where you only pass the baton at specific, pre-determined spots, rather than running around the track trying to find the perfect moment to pass.

3. Handling Bad Guesses

What if the magic recipe card is wildly wrong?

Underestimates (Too Short): If the card says "5 minutes" but the dish takes 20, the system notices the delay and moves the dish to a longer queue. It handles this gracefully.
Overestimates (Too Long): If the card says "20 minutes" but the dish takes 5, the chef might waste time waiting. The authors found a clever trick: they intentionally "dial down" the predictions slightly at the start. This ensures that even if some cards are wrong, the system treats them as "safe" underestimates, preventing the kitchen from getting stuck waiting for dishes that are actually done.

The Bottom Line

The paper proves mathematically that you can have your cake and eat it too:

Speed: You get results almost as fast as the perfect, theoretical schedule.
Stability: You switch tasks (preempt) very few times—only a constant number of times per job, rather than hundreds.
Robustness: Even if the AI predictions are off by a lot, the system doesn't crash; it just slows down slightly in a predictable way.

In short, they built a scheduling algorithm that listens to AI predictions to be efficient, but has a "safety net" that prevents it from going crazy if the predictions are wrong, all while keeping the chefs from constantly switching pans.

Technical Summary: Learning-Augmented Online Scheduling with Parsimonious Preemption

Problem Definition

This work addresses the problem of online scheduling to minimize total completion time ( $\sum C_j$ ) in non-clairvoyant settings where job processing requirements ( $p_j$ ) are unknown until completion. The study integrates machine-learned predictions ( $\hat{p}_j$ ) of job sizes into the algorithmic design. A critical constraint introduced is the minimization of preemption complexity. In practical systems like data centers, frequent preemptions incur significant overheads (e.g., context switching, cache invalidation). While existing learning-augmented scheduling algorithms often achieve strong latency guarantees, they frequently rely on "blind" or frequent preemptions (e.g., Round-Robin), ignoring the trade-off between algorithmic performance and the cost of preemption.

The paper investigates whether it is possible to design algorithms that are constant-competitive (near-optimal) while restricting the number of preemptions per job to a constant factor of a theoretical lower bound, specifically when predictions are available.

Methodology

The authors propose a systematic framework that bridges the gap between theoretical latency bounds and preemption overheads. The core methodology involves three main components:

1. Predicted Multi-Level Feedback (PMLF)

For single and identical parallel machines, the authors adapt the classic Multi-Level Feedback (MLF) algorithm.

Mechanism: Instead of placing new jobs in the lowest queue (as in standard MLF), jobs are initially placed in a queue corresponding to their predicted size $\hat{p}_j$ . Specifically, a job $j$ starts in queue $Q_k$ where $(1+\delta)^k \le \hat{p}_j < (1+\delta)^{k+1}$ .
Preemption Logic: A job is only preempted (moved to a higher queue) when its cumulative processed time reaches the next power of $(1+\delta)$ .
Handling Overestimation: To handle cases where $\hat{p}_j > p_j$ , the algorithm employs a two-stage strategy. It runs PMLF until the number of unfinished jobs drops to a threshold (based on an upper bound $g$ of overestimated jobs). At this point, predictions for remaining jobs are reset to their current processed size, effectively treating them as underestimates to ensure robustness.

2. Simulated Non-preemptive Adaptive Prediction (SNAP)

For unrelated machines (where processing rates $\lambda_{ij}$ vary per job-machine pair), the authors introduce SNAP.

Epoch-Based Simulation: The algorithm operates in epochs. At the start of each epoch, it computes Proportional Fairness (PF) rates for the active jobs. PF is a known $O(1)$ -competitive algorithm for unrelated machines but is highly preemptive (fractional).
Checkpointing: Instead of following the fractional PF schedule continuously, SNAP defines "checkpoints" for each job based on powers of $(1+\delta)$ relative to $\hat{p}_j$ .
Non-preemptive Conversion: The algorithm determines an epoch duration such that a constant fraction ( $\beta$ ) of jobs reach their next checkpoint under the PF rates. It then converts this fractional schedule into a non-preemptive (or low-preemption) schedule using an offline rounding procedure (based on [CSV12]). This schedule is executed for the duration of the epoch.
Robustness: Similar to PMLF, SNAP handles overestimations by resetting predictions once the number of active jobs falls below a specific threshold.

3. General Framework for Polytope Scheduling (PSP)

The authors generalize the approach to Malleable Job Scheduling and the broader class of Polytope Scheduling Problems.

Robust PF Analysis: They introduce a $\beta$ -robust PSP model where an adversary can nullify the processing rates of a $\beta$ -fraction of jobs. They prove that PF remains $O(1)$ -competitive in this robust setting.
Application: By simulating this robust PF behavior and converting it to a low-preemption schedule, they derive algorithms for malleable jobs that maintain constant competitiveness.

Key Contributions

First Systematic Study of Preemption-Latency Trade-off: This is the first work to analytically ground the trade-off between job latency and preemption complexity in the learning-augmented scheduling paradigm.
Bounded Preemption Guarantees: The authors establish that constant-competitive algorithms can be achieved with only $O(1)$ $O (1)$ preemptions per job (relative to a benchmark $D$ $D$ ) under accurate predictions.
- Benchmark $D$ : Defined as $\sum_j (\log_2(p_j/\hat{p}_j) + 1)$ . This represents the minimum preemptions required even for non-clairvoyant algorithms to remain competitive.
Algorithmic Results:
- Single/Identical Machines: A $(2+\epsilon)$ -competitive algorithm with $O(\frac{1}{\epsilon} D)$ preemptions.
- Unrelated Machines: A $14.48(1+\epsilon)$ -competitive algorithm with $O(\frac{1}{\epsilon^3} D)$ preemptions.
- Malleable Jobs: A $\frac{27e}{e-1}(1+\epsilon)$ -competitive algorithm with $O(\frac{1}{\epsilon^3} D)$ preemptions.
Handling Overestimation: A robust framework is provided that scales the competitive ratio and preemption overhead logarithmically with the prediction error, ensuring performance degrades gracefully even when predictions are inaccurate.

Experimental Results

The authors validate their theoretical findings through experiments on synthetic instances involving 10 machines and 100 jobs, including heterogeneous "special" jobs.

SNAP vs. Baselines: SNAP significantly outperforms "Blind" strategies (which assume perfect predictions) as prediction error increases, while maintaining stability in competitive ratio.
Preemption Efficiency: SNAP utilizes far fewer preemptions than natural benchmarks like "Doubling" (which doubles estimates upon miss) while optimizing total completion time.
Hybrid Approach: A "Hybrid SNAP" algorithm, which combines the "Blind" strategy for small errors and SNAP for large errors, demonstrates the best of both worlds, consistently outperforming or matching other heuristics in both objective value and preemption minimization.

Significance and Claims

The paper claims to fill a significant gap in the learning-augmented literature by moving beyond "blind" preemptions. It demonstrates that predictions can be utilized not just to improve latency, but to fundamentally reduce the operational overhead (preemptions) of scheduling algorithms.

The authors assert that their results extend the theoretical reach of learning-augmented frameworks to more constrained and realistic settings (unrelated and malleable machines) where preemption costs are non-negligible. They emphasize that their algorithms provide the first bounded-preemption guarantees for these complex machine environments, proving that solid analytical foundations can bridge the gap between theoretical optimality and practical feasibility.

The work concludes that while future research could explore hybridizing frameworks further, the current results successfully demonstrate that constant-competitive scheduling with parsimonious preemption is achievable under job-size predictions.