- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies online makespan scheduling on identical machines, with and without rejection, using predicted machine assignments or rejection decisions. Processing times and rejection penalties are revealed on arrival, and decisions are immediate and irrevocable. The algorithms achieve -consistency, bounded robustness, and smooth guarantees in terms of the predicted solution's excess cost. General deterministic lower bounds establish exact optimality in sufficiently stringent consistency regimes and approximation guarantees elsewhere. Synthetic experiments illustrate the resulting trade-offs.
Critical strengths
-
The paper provides substantive lower bounds under a prescribed consistency requirement.
The results compare against all deterministic algorithms satisfying -consistency, rather than only a particular algorithmic family. Without rejection, the lower bound and the algorithm's robustness bound closely characterize the trade-off for small . With rejection, the geometric-sum parameter governs both the algorithm and a general lower bound. These results clarify an unavoidable price of exploiting assignment predictions, rather than merely proposing another scheduling heuristic.
-
The algorithms address standard scheduling problems with explicit, efficient mechanisms.
The dual load caps and the reference-based budget selection provide concrete ways to override predictions while preserving consistency. The algorithms require time per job and apply to arbitrary input sequences within the stated identical-machine model. The guarantees concern integral, irrevocable assignments, distinguishing them from prediction schemes based on fractional allocation and online rounding. The main feasibility, potential-function, and lower-bound arguments appear coherent.
Critical weaknesses
-
The strength of the near-optimality guarantee varies substantially across parameter regimes. The exact results concern sufficiently stringent consistency requirements. In the no-rejection regime , the optimal robustness is , which is already attained by directly following predictions; the main advance there is the lower-bound characterization. For rejection outside the exact regime, the uniform approximation factor is below , rather than a tight characterization throughout the parameter range. These qualifications limit how broadly the near-optimality claim should be interpreted.
-
The experiments illustrate the theoretical trade-off but provide limited evidence of practical advantage. Predictions are obtained by perturbing offline-optimal assignments rather than by training a predictor. The inputs are synthetic, and the principal baselines are Follow the Prediction, List Scheduling, and RTP. Figure 1 shows improvements over the classical baselines at low prediction error, but the proposed algorithms perform worse than LS or RTP at larger errors. Thus, bounded robustness should not be interpreted as matching the best classical online algorithm or providing an empirical safe fallback.
The experiments do not establish whether realistically obtainable predictions usually lie in the beneficial error range, or how should be selected without knowledge of the realized error. This limits the evidence for practical usefulness.
Questions for authors
-
For the machine counts and values used experimentally, please report the applicable robustness upper and lower bounds, especially with rejection. How large are the remaining parameter-specific gaps outside the exact-optimality regime?
-
What prediction-quality range supports an empirical advantage over LS or RTP, and how would be selected without knowing or the realized prediction error? Please distinguish what the current experiments establish from what would require learned predictions or additional baseline comparisons.
2 comments
W2 & Q2: Choice of and practical advantages with learned predictions
How to choose
The parameter specifies the user's preferred trade-off between consistency and robustness. Smaller values prioritize performance under perfect predictions, while larger values relax consistency in favor of worst-case protection. There is therefore no single best value of independent of the user's priorities. Users can use our theoretical guarantees to choose according to their desired consistency level or acceptable worst-case bound. Importantly, this choice is made before execution and requires neither OPT nor the realized prediction error. Our use of a user-selected consistency–robustness trade-off parameter follows established learning-augmented designs [1, 2, 3, 4, 5, 6, 7]. We have revised the Introduction to explicitly state this role of (highlighted in blue).
[1] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving Online Algorithms via ML Predictions. NeurIPS, 2018.
[2] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The Primal-Dual Method for Learning Augmented Algorithms. NeurIPS, 2020.
[3] Etienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning Augmented Energy Minimization via Speed Scaling. NeurIPS, 2020.
[4] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A Regression Approach to Learning-Augmented Online Algorithms. NeurIPS, 2021.
[5] Alexander Lindermayr, Nicole Megow, and Bertrand Simon. Double Coverage with Machine-Learned Advice. ITCS, 2022.
[6] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal Robustness-Consistency Tradeoffs for Learning-Augmented Metrical Task Systems. AISTATS, 2023.
[7] Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. Chasing Convex Functions with Long-term Constraints. ICML, 2024.
Learned predictions and empirical advantage over LS and RTP
We have added experiments using trained neural assignment predictors (Figure 1, right; newly added Appendix K). For each setting, we train on 5,000 synthetic instances using offline optimal assignments as labels, select models on 200 separate validation instances, and evaluate on 500 disjoint test instances with three training seeds. At prediction time, the models use only the current job and observed prefix, without access to future jobs or offline optimal information.
Figure 1 (right) shows that our algorithms achieve lower mean costs than LS and RTP, respectively, for every tested . As decreases, their costs approach Follow the Prediction, consistent with our consistency analysis: the cost is bounded by times that of the predicted assignment.
Figure 9 in Appendix K.2 further shows how frequently these improvements occur across the 500 test inputs and three training seeds. Depending on , our algorithms achieve strictly lower costs than the classical baselines in 90.3%–95.9% of evaluations without rejection and 70.3%–95.5% with rejection. These win rates show that the learned predictions are empirically beneficial when used by our algorithms.
These results demonstrate the practical value of our algorithms: predictions from trained models lead to substantial gains on the test workloads while the worst-case guarantees remain intact. Users can therefore benefit from learned predictions with the assurance that the competitive ratio remains bounded even if prediction quality deteriorates arbitrarily.
We sincerely thank the reviewer for their careful reading, constructive feedback, and positive assessment of our lower bounds and efficient algorithms.
W1 & Q1: Robustness bounds and optimality gaps for the experimental parameters
The tables below report the strongest applicable bounds for both m=10 (main experiments) and m=20 (additional experiments), at the ε values used in the experiments. Here, L is the lower bound established in our paper on the best achievable robustness among all deterministic (1+ε)-consistent online algorithms, and U is our algorithm's robustness upper bound. The ratio U/L therefore bounds the multiplicative gap to that optimum, which may lie between L and U.
Without rejection
Outside the exact regime, for example at m=20 and ε=0.1, Dual-Cap preserves 1.1-consistency while improving robustness from 20 for directly following predictions to 10.50625. This is within a factor 1.050625 of the best achievable by any deterministic online algorithm under the same consistency constraint, leaving little room for further improvement. Also, our contribution in the exact regime is to rule out robustness improvements over simply following predictions, even for deterministic online algorithms that strategically ignore predictions or use unrestricted computation.
With rejection
With rejection, directly following predictions has unbounded robustness, whereas our algorithm achieves the best possible robustness in the exact regime while preserving (1+ε)-consistency. Outside that regime, the guarantee is a constant approximation factor independent of the number of machines. Both algorithms use only O(m) time per job and O(m) memory, while the lower bounds apply to all deterministic consistent algorithms without computational restrictions.
W2: Why classical worst-case guarantees cannot be retained for small ε
We would like to clarify that one of the central consequences of our lower bounds is that matching the classical guarantees while retaining (1+ε)-consistency is impossible for small ε. This limitation applies to every deterministic online algorithm, regardless of how it uses predictions or how much computation is available.
Without rejection, Theorem 4 rules out LS's 2−1/m guarantee for every 0<ε<1/2. With rejection, Theorem 10 rules out RTP's guarantee ρm whenever K>ρm. For example, at m=10 and ε=0.1, every 1.1-consistent algorithm in this class must have robustness at least 10 without rejection and K≈11 with rejection. The corresponding classical guarantees are 1.9 for LS and ρ10≈2.456 for RTP.
Such lower bounds are important for learning-augmented algorithm design because they identify the unavoidable worst-case price of strong consistency. Despite this trade-off, our algorithms can outperform classical baselines when predictions are accurate while retaining bounded robustness under arbitrary predictions. They achieve this with robustness that is optimal or near-optimal among deterministic algorithms with the same consistency requirement, as quantified above.