Online Scheduling with a Stochastic Signal
2026-07-20 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study scheduling problems where the exact job lengths are unknown at the start. Previous models gave a signal only when a fixed small part of a job remained, but these signals had to be perfectly timed, which is unrealistic. They propose a new model where signals come randomly according to some distribution, better reflecting real situations. Using this, the authors design better scheduling algorithms with performance guarantees that beat previous worst-case limits. They also develop new mathematical tools to analyze these algorithms and suggest this approach connects ideas from learning-based and stochastic scheduling.
Nonclairvoyant schedulingOnline algorithmsCompetitive ratioTotal completion timeMakespanε-clairvoyanceStochastic clairvoyanceAmortized analysisLearning-augmented algorithmsBeyond-worst-case analysis
Authors
Romain Cosson, Jingwei Li, Alexander Lindermayr, Jens Schlöter
Abstract
Nonclairvoyant scheduling is a fundamental online model in which processing times are initially unknown to the scheduler. Unfortunately, for important objectives such as total completion time and makespan, worst-case analysis yields pessimistic guarantees: every nonclairvoyant algorithm has a competitive ratio of at least $2$ for these objectives. Recent work introduced $\varepsilon$-clairvoyance, where a scheduler receives a signal once an $\varepsilon$-fraction of a job remains (FOCS'25, NeurIPS'25). This model avoids giving the algorithm a priori predictions as done in learning-augmented algorithms, a practice that is often hard to justify in practice. However, existing algorithms and analyses rely crucially on signal times being precise, an assumption hardly justifiable in applications such as task profiling. We introduce stochastic clairvoyance, a beyond-worst-case model in which each job emits a randomly timed signal during its execution, drawn from a distribution over its processing length. For this model, we design new online scheduling algorithms whose competitive ratios are strictly below $2$ for minimizing total completion time and makespan. On the technical side, we prove a new black-box theorem that converts bounds on expected pairwise job delays into competitive guarantees via a continuous amortized charging argument. Our results show that stochastic clairvoyance is not merely a curiosity: it yields robust improvements across different scheduling objectives and machine environments. More broadly, stochastic clairvoyance suggests a new direction in beyond-worst-case analysis for online algorithms, and builds a bridge between learning-augmented algorithms and stochastic information models.