Scheduling jobs more reliably using prediction guidance
Pareto-optimal Scheduling with Predictions
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
Scheduling tasks efficiently on a single machine can be tricky, especially when task durations are unknown. The authors study how to use predictions about job order or size to improve scheduling while keeping guarantees even if predictions are wrong. They find the best balance between trusting predictions and staying safe against errors, using a simple greedy method. This improves prior methods by allowing better performance when predictions are accurate without losing too much if they are not.
What this means in practice
- •For cloud resource schedulers: Design schedulers that use estimated job orders or sizes to reduce overall completion times while bounding worst-case delays regardless of prediction accuracy.
- •For manufacturing process managers: Plan single-machine job sequences guided by predicted order with guarantees on total completion time even when forecasts are inaccurate.
A theory result. No direct application yet.
Authors
Ziyad Benomar, Vianney Perchet
Abstract
We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\eps$ is achievable with robustness $\eps^{-1/2}+\frac16+O(\sqrt\eps)$, whereas all previous algorithms required robustness $Θ(1/\eps)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions.