Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling

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 $\lambda \in (0,1)$, any $(1+\lambda )$-consistent algorithm must be $1+\mathrm{\Omega }(\sqrt{1\mathrm{/}\lambda })$-robust. On the other hand, the best known upper bound gives $(1+\lambda )$-consistency and $1+O(1\mathrm{/}\lambda )$-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\mathrm{/}2$ of our lower bound, and thus our algorithm is within a multiplicative factor $3\mathrm{/}2$ of the online optimal. In particular, our lower bound shows that any $(1+\lambda )$-consistent algorithm must have robustness at least $1\mathrm{/}\sqrt{\lambda }$ as $n\to \mathrm{\infty }$, while our algorithm achieves robustness at most $\frac{1}{2}+\sqrt{\frac{5}{4}+1\mathrm{/}\lambda }$ for any $n$, matching the lower bound in the leading term as $\lambda \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.