- 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 consistent (competitive ratio when prediction was correct), and 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
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.
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.