Ordinal Predictions Suffice for Non-Clairvoyant Scheduling: Closing the Gap in the Consistency–Robustness Trade-off

We study the scheduling of a set of jobs on a single machine, with the objective of minimizing the total completion time: the sum of the times at which the individual jobs finish. The problem has three variants, differing in what the algorithm is told about the running times. In the classical variant they are given in advance, and it is well known that the least possible total completion time, the optimum, is reached by the shortest-processing-time rule, which runs the jobs in increasing order of running time. In the non-clairvoyant variant the running times are hidden, revealed only as jobs finish; an algorithm must then allocate the machine before it can tell short jobs from long ones, which puts the optimum beyond reach. Round Robin, which shares the machine equally among the unfinished jobs, stays within a factor two of the optimum, and no deterministic algorithm does better. The third variant, learning-augmented scheduling, is the subject of this paper: the algorithm is given, in addition, a prediction of the running times. It is judged by two quantities. Its consistency is the largest ratio of its total completion time to the optimum when the prediction is correct, and its obustness is the largest such ratio over all instances and predictions. How favorably the two can be traded against each other has been open, with a quadratic gap between what is achievable and what is forbidden. At consistency $1+\epsilon$ the best robustness known was $\Theta (1/\epsilon )$, attained by time sharing, which divides the machine between Round Robin and an algorithm that follows the prediction. On the other side, the lower bound of Wei and Zhang forbids robustness below order $1/\sqrt{\epsilon }$ for every deterministic algorithm, and does so even when the prediction supplies the running times as numbers. We close the gap by introducing a new algorithm, Prediction-Drift Round Robin (PDRR). It is deterministic, and it consults only the order of the predicted running times, never their values, so the prediction it requires is purely ordinal. A single parameter $\epsilon$ controls how far PDRR follows that order. It holds the unfinished jobs at a common level of accumulated service, as Round Robin does, with one exception: the job predicted to be shortest is never more than a factor $1/\epsilon$ above that level. PDRR is $(1+\epsilon )$-consistent and $\min \{2/\sqrt{\epsilon },2+1/\sqrt{\epsilon }\}$-robust, matching the lower bound up to a constant factor. The optimal trade-off is thus reached from ordinal information alone.