# Learning-Augmented Online Scheduling with Parsimonious Preemption

arXiv: https://arxiv.org/abs/2605.23255 · HTML: https://mlsanity.com/paper/2605.23255/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 56 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 22 of 22)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary](https://mlsanity.com/paper/2302.00985/) (2023)
- [Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints](https://mlsanity.com/paper/1404.1097/) (2014)
- [SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors](https://mlsanity.com/paper/1404.1943/) (2014)
- [Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling](https://mlsanity.com/paper/1703.01634/) (2017)
- [Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines](https://mlsanity.com/paper/1511.07826/) (2015)
- [Fast Algorithms for Packing Proportional Fairness and its Dual](https://mlsanity.com/paper/2109.03678/) (2021)
- [Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2211.02044/) (2022)
- [Improved Approximations for Unrelated Machine Scheduling](https://mlsanity.com/paper/2211.10398/) (2022)
- [Malleable scheduling beyond identical machines](https://mlsanity.com/paper/1903.11016/) (2019)
- [Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time](https://mlsanity.com/paper/2308.07476/) (2023)
- [Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs](https://mlsanity.com/paper/2404.04773/) (2024)

## Abstract (arXiv)

Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include O(1)-competitive algorithms for single and unrelated parallel machines with only O(1) preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.