# On Preemption and Learning in Stochastic Scheduling

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [An Adversarial Model for Scheduling with Testing](https://mlsanity.com/paper/1709.02592/) (2017)
- [Scheduling Jobs with Stochastic Holding Costs](https://mlsanity.com/paper/2105.13655/) (2021)

## Built on by (most cited first, 6 of 6)

- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [Online Packet Scheduling with Deadlines and Learning](https://mlsanity.com/paper/2606.00835/) (2026)
- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)

## Abstract (arXiv)

We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.