Near optimal tradeoff found for scheduling jobs with uncertain times
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Data Structures and Algorithms
Summary
The paper deals with scheduling tasks when the exact time each job takes is unknown but predicted. It balances two goals: doing well when predictions are right (consistency) and not doing terribly when predictions are wrong (robustness). The authors improve previous work by tightly characterizing this balance for any number of jobs and proposing an algorithm that is nearly the best possible. They also show their method can handle some prediction errors without much loss in performance.
What this means in practice
- •For cloud computing engineers: Improve job scheduling algorithms to balance efficiency when predicted runtimes are accurate with resilience when predictions fail, enhancing resource use and responsiveness.
- •For data center operators: Deploy scheduling policies that adaptively maintain near-optimal throughput despite imperfect predictions on job durations, reducing delays and overload.
Authors
Sizhe Li, Nicolas Christianson, Tongxin Li
Abstract
We study the problem of characterizing the optimal consistency--robustness tradeoff for single-machine non-clairvoyant scheduling with predicted processing times. For a fixed number of jobs $n$, Wei and Zhang (2020) established a lower bound on the achievable consistency--robustness tradeoff which is known to be tight only in a few restrictive cases, leaving the optimal tradeoff for general $n$ unresolved. A different worst-case-$n$ regime was introduced by Benomar et al. (2025), who applied the former work's construction to show that for $λ\in (0, 1)$, any $(1+λ)$-consistent algorithm must be $1 + Ω(\sqrt{1/λ})$-robust. On the other hand, the best known upper bound gives $(1+λ)$-consistency and $1+O(1/λ)$-robustness, leaving a polynomial gap. In this work, we develop a new lower bound using a multi-stage adversarial construction and a new algorithm that together give a near-optimal characterization of the consistency--robustness tradeoff: for every $n$, our upper bound is within a multiplicative factor $3/2$ of our lower bound, and thus our algorithm is within a multiplicative factor $3/2$ of the online optimal. In particular, our lower bound shows that any $(1+λ)$-consistent algorithm must have robustness at least $1/\sqrtλ$ as $n \to \infty$, while our algorithm achieves robustness at most $\frac{1}{2}+\sqrt{\frac{5}{4}+1/λ}$ for any $n$, matching the lower bound in the leading term as $λ\downarrow 0$; our upper bound also closes the polynomial gap in the worst-case-$n$ regime. We additionally show how our algorithm can be made error-tolerant, preserving the near-optimal consistency-robustness tradeoff while incurring only slightly degraded performance under bounded prediction errors.