acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 the best robustness known was , 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 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 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 above that level. PDRR is -consistent and -robust, matching the lower bound up to a constant factor. The optimal trade-off is thus reached from ordinal information alone.

Primary area:
learning theory
Keywords:
Learning-Augmented Algorithms, Non-Clairvoyant Scheduling, Ordinal Predictions, Consistency–Robustness Trade-off, Competitive Analysis

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ZWxNOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper is a about one of the most elementary scheduling problems. Single machine. Schedule with preemption allowed. Minimize total completion time.

The problem is studied in a setting where the exact processing time of the jobs is not known. A prediction is given instead. The algorithm does not need the predicted processing time itself, but the rank in the order of the jobs by processing time.

At every moment in time these predictions indicate to the algorithm which would be the job with the smallest processing time, among the pending jobs. This distinguished between the lead jobs and the remaining set of pack jobs.

Two extreme schedules have been considered in the past. Follow the prediction, which gives all CPU power to the lead job. And Round Robin, which shares the CPU equally among the pending jobs, ignoring the prediction. Previous work studied a mixture of these schedules, sharing the CPU among both schedules.

This paper proposes a different approach. It follows the prediction, until the lead job obtained enough of its CPU share, then it follows this above mentioned mixture of the two strategies.

This algorithm is 1+ϵ1+\epsilon consistent (competitive ratio when prediction was correct), and min⁡(2/ϵ,2+1/ϵ)\min(2 / \sqrt \epsilon, 2 + 1 / \sqrt \epsilon) robust (competitive ratio when prediction is adversarial).

This closes finally the quadratic gap which existed in the literature on the lower and upper bound of the robustness of every (1 + epsilon) consistent algorithm.

AI was used for programming (experiments) and polishing the writeup, but not for the theoretical part.

Critical strengths

The paper closes a gap. The problem is central and important. I like that the algorithm only needs ordinal predictions. I find the idea of the algorithm clever. The analysis is not trivial, but still can be verified easily. The experiments are good.

Critical weaknesses

The next step would be to optimize the multiplicative constant in the robustness, upper or lower bound. For this the algorithm might need to make more subtle decisions, or a new lower idea could be needed.

Smoothness is usually studied as well in papers on consistency robustness tradeoff. This is still to be done.

Questions for authors

Can you add release times to the problem without affecting the algorithm's performance?

I found no typos.

3 comments

We thank the reviewer for the constructive comments.

Robustness constant

We agree that improving the constants is important. Our refined robustness bound is

\frac{2}{\sqrt{\varepsilon}}, 2+\frac{1}{\sqrt{\varepsilon}} \right\rbrace.$$ Proposition 16 establishes a lower bound of $1/\sqrt{\varepsilon}+1/2+\sqrt{\varepsilon}/2$ on PDRR's worst-case robustness ratio, showing that the leading coefficient of 1 in our upper bound is asymptotically tight. One promising direction is to investigate randomized variants of PDRR. Instead of fixing $f=1/\varepsilon$, we could sample a lead factor $F$ from a suitable distribution while retaining PDRR's original catch-up and advance phases. Investigating whether such randomization can preserve consistency in expectation while reducing the leading expected robustness coefficient below 1 remains an interesting open direction. ### Smoothness Achieving the optimal asymptotic order of the consistency–robustness trade-off does not, by itself, guarantee smoothness; even Pareto-optimal learning-augmented algorithms can be brittle (Benomar and Perchet, 2025). Following Lindermayr and Megow (2022), for true sizes $p_1\le\cdots\le p_n$ and predicted rank $\hat\pi(i)$, the **weighted inversion error** (unit weights) is $$\eta_{\mathrm{inv}} =\sum_{\substack{i<j\\\\hat\pi(j)<\hat\pi(i)}}(p_j-p_i).$$ This measures the direct scheduling cost of incorrect pairwise rankings. However, inversions can also propagate interference to correctly ordered jobs. To capture this, we define a **propagation-aware error** (equal-size jobs indexed by predicted rank): $$\begin{aligned} \eta_{\mathrm{prop}}(f) &=\eta_{\mathrm{cap}}(f)+\eta_{\mathrm{sharing}}(f),\\\\ \eta_{\mathrm{cap}}(f) &=\sum_{\substack{i<j\\\\\hat\pi(j)<\hat\pi(i)}} \min\\{p_j-p_i,(f-1)p_i\\},\\\\ \eta_{\mathrm{sharing}}(f) &=\sum_{i=1}^{n-1}(n-i) \min\\{(1-\varepsilon)p_i,\varepsilon\Delta_i\\}, \end{aligned}$$ where $f=1/\varepsilon$, $\Delta_i=\max_{\hat\pi(h)\le\hat\pi(i)}p_h-p_i$, and $\eta_{\mathrm{cap}}(f)\le\eta_{\mathrm{inv}}$ for all $f\ge1$. Our analysis establishes three results: 1. **Propagation-aware smoothness.** We prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\eta_{\mathrm{prop}}(f).$$ Under correct predictions, $\eta_{\mathrm{prop}}(f)=0$, recovering PDRR's consistency guarantee. Our analysis also establishes $$\mathrm{ALG}\le \left(2-\frac{2}{n+1}\right)\mathrm{OPT} +\eta_{\mathrm{inv}}.$$ 2. **Finite-$n$ smoothness.** Under the standard weighted inversion error, we prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\bigl(1+\varepsilon(n-1)\bigr)\eta_{\mathrm{inv}}.$$ For $0<\varepsilon<1$, the coefficient $1+\varepsilon(n-1)$ cannot be improved in the bound $\mathrm{ALG}\le(1+\varepsilon)\mathrm{OPT}-\varepsilon\sum_i p_i+(1+\varepsilon(n-1))\eta_{\mathrm{inv}}$, even for a single adjacent inversion. 3. **Impossibility of an $n$-independent bound for PDRR.** For fixed $f=1/\varepsilon>1$, consider one job of size $f$ incorrectly predicted before $m$ unit-size jobs. As $m\to\infty$, $$\frac{\eta_{\mathrm{inv}}}{\mathrm{OPT}}\to0, \qquad \frac{\mathrm{ALG}}{\mathrm{OPT}}\to2.$$ Thus, no $n$-independent linear coefficient on normalized weighted inversion error can recover PDRR's $1+\varepsilon$ consistency guarantee for $0<\varepsilon<1$. Full proofs are provided in Appendix E of the newly submitted supplementary material. These results quantify both the smooth degradation achievable by PDRR and its limitations under standard prediction-error measures. ### Release dates As already noted in Section 7, extending PDRR to dynamic arrivals is an interesting direction for future work. One possible approach is to retain its two-group structure, consisting of the preferred job and the pack. Upon a new arrival, the job could either join the pack or become preferred, in which case the previous preferred job would transition into the pack. By considering each pair of jobs from the arrival time of the later-arriving job between these two, one could formulate a pairwise multiplicative-drift invariant over the service accumulated while both jobs are present. This provides a promising basis for extending PDRR's analysis to dynamic arrivals. Establishing that the invariant is preserved across arrivals and proving the corresponding competitive guarantees remain open.

I hope that the other reviewers, in particular PPya will be convinced by the new discussion on smoothness, and make them increase their rate.

Thank you for your encouraging comment and continued support. We really appreciate it. The revised paper now contains the smoothness results in a new Section 6, with an empirical evaluation in Appendix D.5.

Reviewer_etWCOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the non-clairvoyant scheduling problem where there is a single machine, and all jobs are present at the beginning without any new arriving jobs. The objective is to minimize the total completion time, which is standard for the single-server static scheduling setting. Instead of receiving predictions on job processing times, the algorithm receives a predicted ordering of jobs. The paper proposes Prediction-Drift Round Robin (PDRR), which is designed to achieve consistency and robustness simultaneously. In particular, PDDR is (1+ε)(1+\varepsilon)-consistent and min⁡(2/ε,2+1/ε)\min(2/\sqrt{\varepsilon}, 2+1/\sqrt{\varepsilon})-robust. This improves upon the previously best-known robustness factor, closing the gap to the existing lower bound up to a constant factor.

Critical strengths
  • The paper resolves an open question by achieving an O(1/ε)O(1/\sqrt{\varepsilon}) robustness along with (1+ε)(1+\varepsilon) consistency, which matches the lower bound. The result is a quadratic improvement on the previously best-known robustness bound.
  • PDRR is based on a predicted ordering of jobs, not predictions on job processing times, making the algorithm more practically relevant.
  • The algorithm is simple to implement and deterministic.
Critical weaknesses
  • There is no notion of prediction error defined in this paper, although analyzing smoothness is not currently the scope of this paper. A predicted ordering of jobs is natural, for which the number of inversions compared to an optimal ordering or the Hamming distance from it can be a natural measure of prediction error. The paper has no discussion of this.
  • Although the paper completes the theory for the single-server static scheduling setting, one may argue that the setting is far from practice. A more relevant setting to practice would consider multiple servers or dynamic job arrivals. For these extensions, the predicted order is meaningless.
Questions for authors
  • Can the framework be extended to the single-server dynamic scheduling setting where the system receives new job arrivals? One may still restrict to the case where SPT is optimal for minimizing the total completion time, e.g., M/M/1 queues. For such cases, we may consider an oracle that updates the predicted order with new arriving jobs.
3 comments

We thank the reviewer for the constructive comments.

Smoothness. Achieving the optimal asymptotic order of the consistency–robustness trade-off does not, by itself, guarantee smoothness; even Pareto-optimal learning-augmented algorithms can be brittle (Benomar and Perchet, 2025).

Following Lindermayr and Megow (2022), for true sizes p1≤⋯≤pnp_1\le\cdots\le p_n and predicted rank π^(i)\hat\pi(i), the weighted inversion error (unit weights) is

=\sum_{\substack{i<j\\\\hat\pi(j)<\hat\pi(i)}}(p_j-p_i).$$ This measures the direct scheduling cost of incorrect pairwise rankings. We use weighted inversions because counting inversions or displaced positions ignores processing-time differences: an inversion between nearly equal-sized jobs has negligible weight, whereas a single misplaced large job can create substantial weighted inversion error and significantly increase the scheduling cost. However, inversions can also propagate interference to correctly ordered jobs. To capture this, we define a **propagation-aware error** (equal-size jobs indexed by predicted rank): $$\begin{aligned} \eta_{\mathrm{prop}}(f) &=\eta_{\mathrm{cap}}(f)+\eta_{\mathrm{sharing}}(f),\\\\ \eta_{\mathrm{cap}}(f) &=\sum_{\substack{i<j\\\\\hat\pi(j)<\hat\pi(i)}} \min\\{p_j-p_i,(f-1)p_i\\},\\\\ \eta_{\mathrm{sharing}}(f) &=\sum_{i=1}^{n-1}(n-i) \min\\{(1-\varepsilon)p_i,\varepsilon\Delta_i\\}, \end{aligned}$$ where $f=1/\varepsilon$, $\Delta_i=\max_{\hat\pi(h)\le\hat\pi(i)}p_h-p_i$, and $\eta_{\mathrm{cap}}(f)\le\eta_{\mathrm{inv}}$ for all $f\ge1$. Our analysis establishes three results: 1. **Propagation-aware smoothness.** We prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\eta_{\mathrm{prop}}(f).$$ Under correct predictions, $\eta_{\mathrm{prop}}(f)=0$, recovering PDRR's consistency guarantee. Our analysis also establishes $$\mathrm{ALG}\le \left(2-\frac{2}{n+1}\right)\mathrm{OPT} +\eta_{\mathrm{inv}}.$$ 2. **Finite-$n$ smoothness.** Under the standard weighted inversion error, we prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\bigl(1+\varepsilon(n-1)\bigr)\eta_{\mathrm{inv}}.$$ For $0<\varepsilon<1$, the coefficient $1+\varepsilon(n-1)$ cannot be improved in the bound $\mathrm{ALG}\le(1+\varepsilon)\mathrm{OPT}-\varepsilon\sum_i p_i+(1+\varepsilon(n-1))\eta_{\mathrm{inv}}$, even for a single adjacent inversion. 3. **Impossibility of an $n$-independent bound for PDRR.** For fixed $f=1/\varepsilon>1$, consider one job of size $f$ incorrectly predicted before $m$ unit-size jobs. As $m\to\infty$, $$\frac{\eta_{\mathrm{inv}}}{\mathrm{OPT}}\to0, \qquad \frac{\mathrm{ALG}}{\mathrm{OPT}}\to2.$$ Thus, no $n$-independent linear coefficient on normalized weighted inversion error can recover PDRR's $1+\varepsilon$ consistency guarantee for $0<\varepsilon<1$. Full proofs are provided in Appendix E of the newly submitted supplementary material. These results quantify both the smooth degradation achievable by PDRR and its limitations under standard prediction-error measures. **Dynamic arrivals and multiple servers.** As noted in Section 7, extending PDRR to dynamic arrivals and multiple servers is an important direction for future work. Ordinal predictions have also been studied in more general scheduling settings. Lindermayr and Megow (2022) establish error-dependent competitive guarantees for non-clairvoyant scheduling with permutation predictions on identical parallel machines with release dates and weighted completion times. Their framework requires only a single predicted permutation, without machine assignments. They also prove that permutation predictions for identical machines are PAC-learnable in the agnostic sense with respect to the weighted inversion error $\eta^S$ (our $\eta_{\mathrm{inv}}$ for unit weights; Theorem 20 in the extended version). These results provide a theoretical foundation for investigating ordinal-prediction algorithms beyond the single-server static setting. **Dynamic arrivals.** One possible approach is to retain its two-group structure, consisting of the preferred job and the pack. Upon a new arrival, the job could either join the pack or become preferred, in which case the previous preferred job would transition into the pack. By considering each pair of jobs from the arrival time of the later-arriving job between these two, one could formulate a pairwise multiplicative-drift invariant over the service accumulated while both jobs are present. This provides a promising basis for extending PDRR's analysis to dynamic arrivals. Establishing that the invariant is preserved across arrivals and proving the corresponding competitive guarantees remain open.

Multiple servers. On identical parallel machines, PDRR's structure could potentially be generalized to multiple preferred jobs while controlling their service advantage over the remaining jobs in the pack. However, coordinating processor allocation and preserving the multiplicative-drift invariant under parallel execution introduce additional challenges. Establishing corresponding consistency and robustness guarantees remains future work.

Thank you for your constructive comments.

Regarding the first weakness you raised, the revised manuscript now defines prediction errors explicitly. Section 6 introduces the weighted inversion error and the propagation-aware error, and presents the resulting smoothness guarantees and their limitations. The proofs are in Appendix C (referred to as Appendix E in our earlier response, before the appendices were reorganized). Appendix D.5 evaluates these errors empirically.

We hope these changes address the concern you raised. We would be happy to answer any follow-up questions.

Reviewer_PPyaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies non-clairvoyant (processing times of the jobs aren't known upfront) scheduling with preemption (jobs can be paused and resumed at no cost) on a single machine, where the algorithm is also given a predicted ordering of the job sizes. The goal is to minimize the total completion time, the sum of time taken to finish each individual job. Note that this form of prediction is a fairly natural one, as the optimal algorithm with known job sizes is to simply process the jobs in order, shortest to longest. Thus, simply following the prediction blindly yields an optimal solution if it is accurate.

They introduce a new deterministic algorithm for this setting, PDRR (prediction-drift round robin) that achieves performance within (1+ε)⋅OPT(1 +\varepsilon) \cdot OPT when the predicted ordering is correct (consistency),and within O(1ε⋅OPT)O(\frac{1}{\sqrt{\varepsilon}} \cdot OPT) when the prediction is incorrect (robustness). Moreover existing lower bounds for scheduling with numerical predictions for the job lengths imply that this is the best-possible consistency-robustness tradeoff possible in their setting (upto constant factors).

The main idea behind their algorithm is to adapt the Round-Robin algorithm, which processes unfinished jobs at equal rate and achieves optimal 22-competitiveness in the classical setting without predictions. Instead of processing all unfinished jobs at the same rate, they make the predicted shortest unfinished job run ahead by a factor of O(1/ε)O(1/\varepsilon) compared to the other jobs in terms of total time allocated, until it finishes (after which the preferred job switches to the next one in the ordering). This matches the intuition from the optimal strategy with known job lengths, i.e., to prioritize the shortest job, while limiting how much it can delay the other jobs in case the prediction is incorrect.

Critical strengths

The algorithm is fairly simple and well-motivated, and the scheduling problem is well-studied. The ordinal prediction model is also nice, as it seems quite plausible that a predicted ranking can be learnt directly without using estimates for each job length.

They also match the best-possible robustness consistency tradeoff possible for deterministic algorithms in their setting. Since the lower bound applies even for algorithms that are given predictions for each job length, their result shows that a predicted ordering suffices to attain the optimal tradeoff.

Critical weaknesses

While their algorithm is indeed consistent + robust, it seems to lack any smoothness guarantees. Ideally, one would want smooth degradation as the prediction quality decreases. For instance, we would want the algorithm to still perform well if one job is not in the right position in the ordering. Consider the construction in Proposition 16, take ε=1/m2\varepsilon = 1/m^2, and suppose there are mm unit jobs and 11 large job of size 1/(2ε)1/(2\varepsilon). If the large job is predicted before all the short unit jobs, then their bound shows that ALG=Ω(1/ε)⋅OPTALG = \Omega(1/\sqrt{\varepsilon}) \cdot OPT. Since in practice predictions are often inaccurate, this seems problematic to me.

Questions for authors

What is known about the consistency robustness tradeoff for randomized algorithms in this setting (for instance, could it be possible to improve on the 1/ε1/\sqrt{\varepsilon} robustness dependence)

Jobs can be paused and resumed at no cost in the preemptive setting, which could be a bit unrealistic in practice, Are any of the techniques extendable to the setting where only a bounded number of preemptions are allowed? What if only one job can be executed on the machine at a time, or if there is a switching cost to starting a new job?

5 comments

We thank the reviewer for the constructive comments.

Smoothness. Achieving the optimal asymptotic order of the consistency–robustness trade-off does not, by itself, guarantee smoothness; even Pareto-optimal learning-augmented algorithms can be brittle (Benomar and Perchet, 2025).

Following Lindermayr and Megow (2022), for true sizes p1≤⋯≤pnp_1\le\cdots\le p_n and predicted rank π^(i)\hat\pi(i), the weighted inversion error (unit weights) is

=\sum_{\substack{i<j\\\\hat\pi(j)<\hat\pi(i)}}(p_j-p_i).$$ This measures the direct scheduling cost of incorrect pairwise rankings. We use weighted inversions because counting inversions or displaced positions ignores processing-time differences: an inversion between nearly equal-sized jobs has negligible weight, whereas a single misplaced large job can create substantial weighted inversion error and significantly increase the scheduling cost. However, inversions can also propagate interference to correctly ordered jobs. To capture this, we define a **propagation-aware error** (equal-size jobs indexed by predicted rank): $$\begin{aligned} \eta_{\mathrm{prop}}(f) &=\eta_{\mathrm{cap}}(f)+\eta_{\mathrm{sharing}}(f),\\\\ \eta_{\mathrm{cap}}(f) &=\sum_{\substack{i<j\\\\\hat\pi(j)<\hat\pi(i)}} \min\\{p_j-p_i,(f-1)p_i\\},\\\\ \eta_{\mathrm{sharing}}(f) &=\sum_{i=1}^{n-1}(n-i) \min\\{(1-\varepsilon)p_i,\varepsilon\Delta_i\\}, \end{aligned}$$ where $f=1/\varepsilon$, $\Delta_i=\max_{\hat\pi(h)\le\hat\pi(i)}p_h-p_i$, and $\eta_{\mathrm{cap}}(f)\le\eta_{\mathrm{inv}}$ for all $f\ge1$. Our analysis establishes three results: 1. **Propagation-aware smoothness.** We prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\eta_{\mathrm{prop}}(f).$$ Under correct predictions, $\eta_{\mathrm{prop}}(f)=0$, recovering PDRR's consistency guarantee. Our analysis also establishes $$\mathrm{ALG}\le \left(2-\frac{2}{n+1}\right)\mathrm{OPT} +\eta_{\mathrm{inv}}.$$ 2. **Finite-$n$ smoothness.** Under the standard weighted inversion error, we prove $$\mathrm{ALG}\le \left(1+\left(1-\frac{2}{n+1}\right)\varepsilon\right)\mathrm{OPT} +\bigl(1+\varepsilon(n-1)\bigr)\eta_{\mathrm{inv}}.$$ For $0<\varepsilon<1$, the coefficient $1+\varepsilon(n-1)$ cannot be improved in the bound $\mathrm{ALG}\le(1+\varepsilon)\mathrm{OPT}-\varepsilon\sum_i p_i+(1+\varepsilon(n-1))\eta_{\mathrm{inv}}$, even for a single adjacent inversion. 3. **Impossibility of an $n$-independent bound for PDRR.** For fixed $f=1/\varepsilon>1$, consider one job of size $f$ incorrectly predicted before $m$ unit-size jobs. As $m\to\infty$, $$\frac{\eta_{\mathrm{inv}}}{\mathrm{OPT}}\to0, \qquad \frac{\mathrm{ALG}}{\mathrm{OPT}}\to2.$$ Thus, no $n$-independent linear coefficient on normalized weighted inversion error can recover PDRR's $1+\varepsilon$ consistency guarantee for $0<\varepsilon<1$. Full proofs are provided in Appendix E of the newly submitted supplementary material. The reviewer's construction highlights why the magnitude of prediction error matters more than simply counting misplaced jobs. For $m\ge2$ and $\varepsilon=1/m^2$, with one job of size $1/(2\varepsilon)$ predicted before $m$ unit jobs, the weighted inversion error is $\eta_{\mathrm{inv}}=m^3/2-m$, and $$\frac{\mathrm{ALG}}{\mathrm{OPT}} =\frac{m+1}{2} =\frac{\eta_{\mathrm{inv}}}{\mathrm{OPT}}+\frac{5m+7}{4m+6} <\frac{\eta_{\mathrm{inv}}}{\mathrm{OPT}}+\frac54.$$ Thus, although only one job is misplaced, PDRR's performance degradation tracks its weighted inversion error within an additive constant. Following the prediction has ratio $1+\eta_{\mathrm{inv}}/\mathrm{OPT}$ on this instance, so PDRR is within $1/4$ of it. This illustrates the value of error-dependent guarantees. Importantly, this construction chooses $\varepsilon=1/m^2$, requiring consistency $1+1/m^2$. The lower bound of Wei and Zhang (2020) implies that every deterministic algorithm with this consistency must incur a competitive ratio of $\Omega(m)$ on some instance and prediction. Thus, while Round Robin performs better on this particular instance, it does not satisfy the same consistency requirement. For any fixed $\varepsilon>0$, PDRR's robustness bound remains at most $2+1/\sqrt{\varepsilon}$, independently of $m$. These results quantify both the smooth degradation achievable by PDRR and its limitations under standard prediction-error measures.

Randomization. Motwani et al. (1994) established a randomized lower bound of 2−4/(n+3)2-4/(n+3) for classical non-clairvoyant scheduling without predictions, while deterministic Round Robin achieves 2−2/(n+1)2-2/(n+1). Thus, randomization cannot improve the asymptotic competitive ratio of 2 without predictions.

Whether randomization can improve robustness while preserving 1+ε1+\varepsilon consistency using only ordinal predictions remains an open question.

One promising direction is to investigate randomized variants of PDRR. Instead of fixing f=1/εf=1/\varepsilon, we could sample a lead factor FF from a suitable distribution while retaining PDRR's original catch-up and advance phases. Investigating whether such randomization can preserve consistency in expectation while reducing the leading expected robustness coefficient below 1 remains an interesting open direction.

Preemptions. In practical operating systems, Round Robin is implemented through time slicing; for example, Linux's SCHED_RR policy allocates a bounded execution quantum to each runnable thread at a given priority level (Linux sched(7)). On a single processor, only one job executes at a time, and the same time-slicing principle could be used to approximate PDRR's continuous processor sharing.

Our current analysis assumes continuous processor sharing and zero switching overhead; establishing competitive guarantees for a discrete implementation with nonzero switching costs remains future work.

To reduce preemptions, one possible approach is to use geometrically increasing cumulative service levels Sℓ=brℓS_\ell=br^\ell, where r=1/ε>1r=1/\varepsilon>1 for 0<ε<10<\varepsilon<1 and S−1=0S_{-1}=0. At each level ℓ\ell, a job executes for a quantum of size

qℓ=Sℓ−Sℓ−1.q_\ell=S_\ell-S_{\ell-1}.

The preferred job may advance one level ahead of the pack, preserving a multiplicative advantage while allowing jobs to execute in contiguous batches. Intuitively, the progressively increasing quanta reduce the frequency of preemptions while maintaining preferential treatment for the predicted shortest job. Establishing competitive guarantees for this discrete implementation, particularly with nonzero switching costs, remains future work.

I thank the authors for their detailed response, and for addressing my smoothness concern.

I feel smoothness is an important aspect of the paper and would suggest the authors discuss the new guarantees and their limitations in the main text, rather than primarily in the appendix. In particular, as the authors acknowledge, there are families of instances where ηinv/OPT→0\eta_{\mathrm{inv}}/OPT\to0 while PDRR’s competitive ratio approaches 22, and the Time Sharing algorithm approaches 1+ε1+\varepsilon. Highlighting this comparison would help clarify the tradeoff between improved worst-case robustness by PDRR, and performance under small prediction errors.

Furthermore, the experiments do not report normalized inversion error or propagation-aware error. It would be nice to add some comparison against the theoretical smoothness guarantees, as it would help clarify how tight/informative these bounds are in practice.

Subject to these revisions, I am raising my recommendation to weak acceptance.

Comments on the paper

1 comment

Dear reviewers,

please acknowledge the rebuttal by the authors and decide whether it affects your assessment of the paper and your score.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.