acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Learning-Augmented Online Scheduling with and without Rejection

Abstract

We study learning-augmented online scheduling on identical parallel machines, both with and without rejection. Each arriving job reveals its processing time and a predicted machine assignment, which may instead recommend rejection when allowed. Decisions are irrevocable, and the objective is makespan plus any rejection penalties. Our algorithms use two load caps in the no-rejection setting and cost comparisons with a prediction-free reference scheduler when rejection is allowed. Both are -consistent, degrade smoothly with prediction error, and retain worst-case guarantees under arbitrary predictions. We further establish robustness lower bounds for all deterministic online algorithms satisfying the same consistency requirement, showing that both algorithms attain optimal robustness for sufficiently small and remain near-optimal over wider parameter ranges. We conclude our work with an empirical analysis of our method.

Primary area:
optimization
Keywords:
Learning-Augmented Algorithm, Scheduling, Online Algorithm

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_BNYCOpenReview ↗
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 (1+ε)(1+\varepsilon)-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
  1. The paper provides substantive lower bounds under a prescribed consistency requirement.

    The results compare against all deterministic algorithms satisfying (1+ε)(1+\varepsilon)-consistency, rather than only a particular algorithmic family. Without rejection, the lower bound min⁡�0�\min �0� and the algorithm's robustness bound closely characterize the trade-off for small ε\varepsilon. With rejection, the geometric-sum parameter KK 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.

  2. 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 O(m)O(m) 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
  1. 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 ε≤1/m\varepsilon\le1/m, the optimal robustness is mm, 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 32(1+φ)≈3.927\frac32(1+\varphi)\approx3.927, rather than a tight characterization throughout the parameter range. These qualifications limit how broadly the near-optimality claim should be interpreted.

  2. 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 ε\varepsilon should be selected without knowledge of the realized error. This limits the evidence for practical usefulness.

Questions for authors
  1. For the machine counts and ε\varepsilon 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?

  2. What prediction-quality range supports an empirical advantage over LS or RTP, and how would ε\varepsilon be selected without knowing OPT\mathrm{OPT} or the realized prediction error? Please distinguish what the current experiments establish from what would require learned predictions or additional baseline comparisons.

2 comments

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=10m=10 (main experiments) and m=20m=20 (additional experiments), at the ε\varepsilon values used in the experiments. Here, LL is the lower bound established in our paper on the best achievable robustness among all deterministic (1+ε)(1+\varepsilon)-consistent online algorithms, and UU is our algorithm's robustness upper bound. The ratio U/LU/L therefore bounds the multiplicative gap to that optimum, which may lie between LL and UU.

Without rejection

mmε\varepsilonLower bound LLDual-Cap bound UUGap bound U/LU/L
100.110.000010.00001.0000
100.25.00005.51251.1025
100.42.50003.30631.3225
100.6—2.6042—
100.8—2.2781—
101—2.1025—
200.110.000010.50631.0506
200.25.00005.77811.1556
200.42.50003.45161.3806
200.6—2.7094—
200.8—2.3633—
201—2.1756—

Outside the exact regime, for example at m=20m=20 and ε=0.1\varepsilon=0.1, Dual-Cap preserves 1.11.1-consistency while improving robustness from 2020 for directly following predictions to 10.5062510.50625. This is within a factor 1.0506251.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

mmε\varepsilonLower bound L=KL=KCBS bound UUGap bound U/LU/L
100.111.000011.00001.0000
100.26.000010.00001.6667
100.43.500010.00002.8572
100.62.66649.00563.3774
100.82.24927.98073.5483
100.992.00827.38883.6793
200.111.000020.00001.8182
200.26.000017.75992.9600
200.43.500011.41713.2620
200.62.66679.30283.4886
200.82.25008.24573.6647
200.992.01017.63703.7993

With rejection, directly following predictions has unbounded robustness, whereas our algorithm achieves the best possible robustness in the exact regime while preserving (1+ε)(1+\varepsilon)-consistency. Outside that regime, the guarantee is a constant approximation factor independent of the number of machines. Both algorithms use only O(m)O(m) time per job and O(m)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 ε\varepsilon

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.

We would like to clarify that one of the central consequences of our lower bounds is that matching the classical guarantees while retaining (1+ε)(1+\varepsilon)-consistency is impossible for small ε\varepsilon. 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/m2-1/m guarantee for every 0<ε<1/20<\varepsilon<1/2. With rejection, Theorem 10 rules out RTP's guarantee ρm\rho_m whenever K>ρmK>\rho_m. For example, at m=10m=10 and ε=0.1\varepsilon=0.1, every 1.11.1-consistent algorithm in this class must have robustness at least 1010 without rejection and K≈11K\approx11 with rejection. The corresponding classical guarantees are 1.91.9 for LS and ρ10≈2.456\rho_{10}\approx2.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.

W2 & Q2: Choice of ε\varepsilon and practical advantages with learned predictions

How to choose ε\varepsilon

The parameter ε\varepsilon 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 ε\varepsilon independent of the user's priorities. Users can use our theoretical guarantees to choose ε\varepsilon 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 ε\varepsilon (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 ε\varepsilon. As ε\varepsilon decreases, their costs approach Follow the Prediction, consistent with our consistency analysis: the cost is bounded by (1+ε)(1+\varepsilon) 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 ε\varepsilon, 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.

Reviewer_LuWLOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3(+1)
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies learning-augmented scheduling for makespan minimization on parallel identical machines. We have m identical parallel machines. Jobs arrive over time. When a job arrives, its job size becomes known. The scheduler must then decide the job-to-machine assignment when the job arrives, and this assignment is irrevocable, i.e., one cannot later preempt the jobs running on a machine and/or assign it to another machine. The objective is minimizing makespan, the time when the last job completes. The paper considers two settings of the problem: one without job rejection and one with rejection. In the case where job rejection is allowed, rejecting a job means not running it, but this comes with a cost in the objective.

The learning-augmented setting is as follows. When a job arrives, we receive a predicted machine assignment or a rejection recommendation in the setting with rejection. We want to design a scheduling algorithm that uses the predictions. We aim for an algorithm with three properties: consistency, robustness, and smoothness. Consistency means performance close to the optimum when the predictions are perfect; robustness means a worst-case guarantee under arbitrarily bad predictions; smoothness means a smooth performance degradation of the algorithm as prediction worsens. These are the canonical contributions in the learning-augmented community.

The paper then proposes, for the case without rejection, a learning-augmented algorithm that is 1+ϵ1 + \epsilon consistent and β\beta robust, where ϵ\epsilon is user-defined, and β\beta is a function in ϵ\epsilon that is over 2−1/m2 - 1/m, corresponding to the classic bound without predictions. The algorithm works as follows. When a job arrives, it computes an admissible set of machines it can be assigned to. If the prediction happens to point to one of the machines in that admissible set, assign the job to that predicted machine. Otherwise, it is assigned to one machine in that admissible set. The admissible set is constructed so that the consistency and robustness requirements are maintained. The paper then shows that the consistency-robustness trade-off achieved by the algorithm is optimal under the condition that the consistency requirement is close to 1. The paper also discusses the smoothness of the algorithm.

Then, the paper extends the results to the case with rejection. A similar set of results are obtained. The paper ends with numerical evaluations on synthetic data. The evaluation compares the proposed algorithm with the benchmarks, including Follow the Prediction, List Scheduling, and RTP.

Critical strengths
  1. The paper advances the field of learning-augmented algorithms to parallel identical machines scheduling to minimize makespan with jobs arriving over time. The prediction form is the job-to-machine assignment. The paper’s contributions are aligned with the community: learning-augmented algorithms with consistency and robustness, plus some analysis on the consistency-robustness trade-off. The technique of using the admissible machine set to maintain the properties required by the consistency and robustness offers new insights into the design and analysis of learning-augmented scheduling algorithms.
  2. The results are presented in a clear way, in the structure of a theory followed by interpretation. In the age of AI generating massive amounts of proofs, offering human-understandable interpretations of results is itself a critical contribution and would help readers to gain understanding of the theory.

Given these strengths, I conclude that the paper is surely on the side of acceptance. However, it is at the margin of acceptance, for the reasons I will detail in the critical weaknesses.

Critical weaknesses

The critical weakness is the lack of sufficient contribution on the smoothness towards a clear acceptance. In my view, a clear acceptance of the paper at ICLR would require a solid smoothness guarantee of the algorithm, although having a smoothness bound is generally considered harder than consistency and robustness. The paper indeed has some discussions on smoothness, but they are not truly smoothness results. The issues are the following.

  1. The prediction error is defined directly as the difference between HnH_n and OPT, where HnH_n is the makespan constructed by following the assignment prediction. Thus, it is not problem-independent, and it is more of a solution quality rather than a prediction quality. Such a definition means i) the bound follows immediately, and ii) it is hard to imagine how one can learn to make such predictions where one is expected to link the prediction error to the objective of the learning task.
  2. The “smoothness” bound includes an OPT term, where one expects a smoothness bound to be a function in just the problem inputs, e.g., mm, and the prediction error.

Therefore, I would not say that the work obtains a solid smoothness result. Given the lack of such a result, the paper, with its main contribution in learning-augmented scheduling, is not a clear acceptance, but still at the margin of acceptance.

Questions for authors

It would be hard to materially affect my assessment, for what are detailed in the critical weaknesses, but if there is a question that would, it is the following. Can you show a non-trivial smoothness bound as a function in just the problem inputs with a problem-independent prediction error? To answer this, you need to first propose a problem-independent prediction error definition. Then, conduct the competitive analysis on it to yield the smoothness bound that is a function of the problem inputs and the prediction error.

Answering this question would mean (perhaps substantially) extending the scope of the original work, so I do not expect the authors to answer it, which is fine, but this is the only question that can materially affect my assessment, i.e., rating it to clear acceptance.

6 comments

We sincerely thank the reviewer for their careful reading of our paper and constructive feedback. We particularly appreciate the suggestion to introduce a prediction-quality error measure linked to the learning objective and establish a smoothness bound in terms of this error.

To address this concern, we have substantially extended our analysis and derived smoothness upper bounds (Theorems 6 and 12) and general lower bounds (Theorems 7 and 13) in terms of standard classification losses, establishing optimal or near-optimal smoothness (Theorems 8 and 14). The algorithms themselves are unchanged. We have incorporated these results into the revised paper and highlighted them in blue, with full proofs in the appendix. We summarize the new results below.

AuthorsOpenReview ↗

Summary of New Smoothness Results in Terms of Prediction-Quality Error

Prediction-quality error and an input-only smoothness bound (newly added Section 3.6)

Prediction-quality error

For predicted machine assignments hh and a comparison assignment aa, we define the Hamming error and its processing-time-weighted version as k(h,a)≔∑j1hj≠aj,W(h,a)≔∑jpj1hj≠aj.k(h,a)\coloneqq\sum_j\mathbf{1}\\{h_j\ne a_j\\},\qquad W(h,a)\coloneqq\sum_jp_j\mathbf{1}\\{h_j\ne a_j\\}. Here, kk counts incorrect predictions relative to aa, while WW sums the processing times of the jobs with incorrect predictions. These errors directly measure prediction quality rather than solution quality. No scheduling objective value enters either loss definition. Both losses are defined for any comparison assignment; we specialize to an optimal assignment a∗a^* when stating competitive ratios.

Input-only smoothness bound (Theorem 6)

For 0<ε≤10<\varepsilon\le1, we prove Cmax⁡DualCap(I,h)≤(1+ε)Cmax⁡(a)+W(h,a)C_{\max}^{\mathrm{DualCap}}(I,h)\le(1+\varepsilon)C_{\max}(a)+W(h,a). For any optimal assignment a∗a^*, this yields \frac{C_{\max}^{\mathrm{DualCap}}(I,h)}{\mathrm{OPT}(I)}\le\min\left\\{\beta,1+\varepsilon+\frac{W(h,a^*)}{B_n}\right\\}\le\min\\{\beta,1+\varepsilon+k(h,a^*)\\}, where Bn=max⁡max⁡jpj,∑jpj/mB_n=\max\\{\max_jp_j,\sum_jp_j/m\\} and β\beta is the original robustness bound determined by mm and ε\varepsilon.

Interpretation. This bound depends only on mm, ε\varepsilon, and the number of incorrect predictions, with no OPT term on the right-hand side. Retaining W/BnW/B_n gives a finer bound that accounts for the processing times of jobs with incorrect predictions. The proof uses a strengthened per-machine load invariant (Appendix C.2.1) to control the effect of misclassified jobs.

General smoothness lower bound and (near-)optimality (newly added Section 3.6)

General smoothness lower bound (Theorem 7)

Let SA(m,ε,k)\mathcal S_A(m,\varepsilon,k) denote an algorithm's worst-case competitive ratio with at most kk incorrect predictions relative to the closest optimal assignment, and let S∗(m,ε,k)\mathcal S^*(m,\varepsilon,k) be its infimum over all deterministic (1+ε)(1+\varepsilon)-consistent online algorithms, without any computational restrictions. For every integer k≥0k\ge0 and 0<ε<1/20<\varepsilon<1/2, Theorem 7 establishes S∗(m,ε,k)≥min⁡k+1,m,1/ε.\mathcal S^*(m,\varepsilon,k)\ge\min\\{k+1,m,1/\varepsilon\\}.

Optimality and near-optimality of smoothness (Theorem 8)

For 0<ε<1/m0<\varepsilon<1/m, our algorithm achieves exactly optimal smoothness at every error budget: SDualCap(m,ε,k)=S∗(m,ε,k)=min⁡m,k+1.\mathcal S_{\mathrm{DualCap}}(m,\varepsilon,k)=\mathcal S^*(m,\varepsilon,k)=\min\\{m,k+1\\}.

For 0<ε<1/20<\varepsilon<1/2, we obtain the following multiplicative and additive guarantees, uniformly in mm and kk: 1≤SDualCap(m,ε,k)S∗(m,ε,k)≤(1+ε2)2,0≤SDualCap(m,ε,k)−S∗(m,ε,k)≤1+ε4.1\le\frac{\mathcal S_{\mathrm{DualCap}}(m,\varepsilon,k)}{\mathcal S^*(m,\varepsilon,k)}\le\left(1+\frac{\varepsilon}{2}\right)^2,\qquad 0\le\mathcal S_{\mathrm{DualCap}}(m,\varepsilon,k)-\mathcal S^*(m,\varepsilon,k)\le1+\frac{\varepsilon}{4}.

Interpretation. Thus, with an error measure that directly captures prediction quality, our algorithm also achieves optimal smoothness for sufficiently small ε\varepsilon and near-optimal smoothness over a broader range, using only O(m)O(m) time per job and O(m)O(m) memory.

Connection to cross-entropy training (newly added Appendix D.1)

The Hamming error (k(h,a)k(h,a)) and the normalized processing-time-weighted error (W(h,a)/BnW(h,a)/B_n) in our smoothness bound are upper-bounded by the corresponding standard and processing-time-weighted cross-entropy losses. Let LCEL_{\mathrm{CE}} denote the cross-entropy loss against an optimal comparison assignment. When the predictor recommends the machine with the highest probability for each job, we obtain \frac{C_{\max}^{\mathrm{DualCap}}(I,h)}{\mathrm{OPT}(I)}\le\min\left\\{\beta,1+\varepsilon+\frac{L_{\mathrm{CE}}}{\log2}\right\\}.

Interpretation. Thus, standard cross-entropy training directly targets an upper bound on the algorithm's competitive ratio: lower prediction loss gives a tighter error-dependent performance guarantee.

Similar results for scheduling with rejection (newly added Section 4.5 and Appendix G)

In the rejection setting, we use the same processing-time-weighted Hamming loss to measure prediction quality. For 0<ε<10<\varepsilon<1, Theorem 12 establishes CCBS(I,h)OPT(I)≤min⁡βrej,(1+ε)(1+η),\frac{C^{\mathrm{CBS}}(I,h)}{\mathrm{OPT}(I)}\le\min\\{\beta_{\mathrm{rej}},(1+\varepsilon)(1+\eta)\\}, where η=W(h,a∗)/Brej(I)\eta=W(h,a^*)/B_{\mathrm{rej}}(I) and Brej(I)=max⁡∑jmin⁡pj/m,rj,max⁡jmin⁡pj,rjB_{\mathrm{rej}}(I)=\max\\{\sum_j\min\\{p_j/m,r_j\\},\max_j\min\\{p_j,r_j\\}\\}. This normalization is computed directly from processing times and rejection penalties. We also prove general lower bounds for all deterministic (1+ε)(1+\varepsilon)-consistent algorithms, establishing near-optimal smoothness of CBS for sufficiently small ε\varepsilon.

We also bound the competitive ratio directly in terms of the predictor's weighted cross-entropy loss (Appendix G.1).


The main experiments now use normalized weighted Hamming error; the previous solution-quality plots are retained in the appendix as a complementary evaluation.

I appreciate the author’s efforts in adding smoothness analysis with a problem-independent error metric. In particular, problem-independent error metrics are proposed, and smoothness bounds with respect to this error metric are derived. However, my assessment is that the bounds provide only limited information, i.e., it seems a trivial bound. The details are the following.

The smoothness bound, i.e., the competitive ratio as a function of the prediction error, for the proposed algorithm is 1+ϵ+k(h,a∗)1 + \epsilon + k(h, a^*). The metric kk is the number of disagreements between the predicted machine assignments and the optimal ones. Observe that k is 0 if predictions are perfect, or at least 1 if predictions are not perfect. Thus, when predictions are perfect, the bound is 1+ϵ1 + \epsilon (consistency); when the predictions are not perfect, the bound is at least 2, which is the competitive ratio for list scheduling for the problem. The bound itself means that list scheduling, which does not use predictions, has better performance than the proposed algorithm as long as predictions are not perfect. Put it in another way, the bound itself can hardly convince one that the proposed algorithm benefits from the (additional) information in predictions for decision-making or that it has performance tied to the prediction quality in a non-trivial way, which is what the smoothness bound ought to be revealing.

Despite the efforts, my assessment is that no non-trivial smoothness bounds have been supplied. I still feel overall positive about the paper, and it is sitting at the margin of acceptance. It is non-trivial to give non-trivial smoothness bounds, which I have acknowledged in my question section, so it is fine if the rebuttal does not address it. To conclude, I maintain my overall positive assessment.

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

This paper considers an online makespan minimization problem with mm identical machines. Each job tt comes with processing time ptp_t, along with a predicted assignment ht∈[m]h_t\in[m]. When job rejection is allowed, rtr_t is the rejection penalty for job tt. The paper develops algorithms that are simultaneously consistent (near-optimal under perfect predictions), robust (with a bounded competitive ratio under arbitrary predictions), and smooth (getting worse slowly as the prediction error increases). Without rejection, the paper proposes the Dual-Cap algorithm, and for the setting where job rejection is allowed, the CBS algorithm is proposed. The paper proves that both algorithms are (1+ε)(1+\varepsilon)-consistent with robustness of order 1/ε1/\varepsilon. Moreover, smoothness is also achieved with respect to the prediction error. The paper also provides lower bounds that are close to the upper bounds given.

Critical strengths
  • The paper is clearly written and well motivates the problem setting.
  • The algorithms are simple to implement with O(m)O(m) complexity for each job. As promised, the algorithms achieve consistency, robustness, and smoothness simultaneously.
  • For the setting without rejection, the robustness matches the lower bound up to an additive constant.
Critical weaknesses
  • For the setting where job rejection is not allowed, it seems that the gap from the lower bound can be significant.
  • The prediction model for suggesting job-server assignments has been established in the literature. However, it is not well explained how to realize such a prediction system in practice. The error EE is defined with respect to a fixed predicted plan, so it is not clear whether predictions that adapt to the algorithm's actual state can be captured. That said, the reviewer wonders if the error EE can also depend on the algorithm's mistakes, which is often the case in adaptive scheduling systems in practice. Elaborating on this will help convince readers of the setting.
Questions for authors

See the weakness part.

1 comment

We sincerely thank the reviewer for their careful reading, constructive feedback, and positive assessment of our algorithms' simplicity and performance guarantees.

Weakness1: Gap between the upper and lower bounds (without rejection)

Although the bounds do not coincide for all ε\varepsilon, Theorem 5 bounds the multiplicative gap for 0<ε<1/20<\varepsilon<1/2 by

\le\left(1+\frac{\varepsilon}{2}\right)^2,$$ with an additive gap of at most $1+\varepsilon/4$. For example, with $\varepsilon=0.1$, our algorithm is $1.1$-consistent and its robustness is at most $1.1025$ times the best achievable under the same consistency requirement, for any $m$. Furthermore, our algorithm achieves exactly optimal robustness when $\varepsilon\le 1/m$, where $\mathrm{Rob}(\mathrm{DualCap})=R^*(m,\varepsilon)=m$. Importantly, these comparisons are against all deterministic $(1+\varepsilon)$-consistent online algorithms, without restrictions on computational complexity or assignment rules. Our algorithm achieves these guarantees using only $O(m)$ time per job and $O(m)$ memory. Appendix C further tightens these bounds by refining the robustness cap without changing the assignment rule or $O(m)$ per-job complexity: - Theorem 15: For $m\ge 3$ and $1/m\le\varepsilon\le 1/(m-1)$ with $\varepsilon<1/2$, the multiplicative gap improves to at most $1+\varepsilon^2/4$, with an additive gap of at most $\varepsilon/4$. - Theorem 18: For $m\ge 5$ and $1/(m-1)<\varepsilon\le 2/(m+2)$, the multiplicative gap improves to at most $1+\varepsilon/6+\varepsilon^2/(3(1-\varepsilon))$, with an additive gap of at most $1/6+\varepsilon/(3(1-\varepsilon))$. Thus, while a gap remains in some ranges, we establish exact optimality for sufficiently small $\varepsilon$ and explicit near-optimality over broader ranges, further improved in Appendix C. # Weakness2: Practical realization of assignment predictions and adaptive predictions ## Practical realization Our prediction model does not require a fixed assignment plan to be specified in advance. As defined in Sections 3.1 and 4.1, each prediction $h_t$ is revealed upon the arrival of job $t$, before the algorithm makes its decision. In practice, one can train a standard multiclass classifier on historical workloads, using offline optimal or near-optimal assignments as targets and cross-entropy as the learning objective. At each job arrival, it uses job features and the current machine loads to output probabilities over machines, with rejection as an additional option when allowed. To further connect learning to scheduling performance, we now added smoothness analysis for the same algorithms using Hamming error $k(h,a)$, which counts incorrect predictions relative to a comparison assignment $a$, and processing-time-weighted Hamming error $W(h,a)$, which sums the processing times of these jobs (Sections 3.6 and 4.5; highlighted in blue). These errors can be bounded in terms of standard and processing-time-weighted cross-entropy losses, respectively. Our smoothness analysis therefore provides competitive-ratio guarantees directly in terms of the losses used for training (Appendices D.1 and G.1). For example, without rejection, when the predictor recommends the machine with the highest probability for each job, we obtain $$\frac{C_{\max}^{\mathrm{DualCap}}(I,h)}{\mathrm{OPT}(I)}\le\min\left\\{\beta,1+\varepsilon+\frac{L_{\mathrm{CE}}}{\log2}\right\\},$$ where $L_{\mathrm{CE}}$ denotes the cross-entropy loss against an optimal comparison assignment. Thus, standard supervised learning provides a practical way to realize the prediction system, while the cross-entropy objective directly targets the algorithm's performance guarantee. Lower prediction loss yields a tighter competitive-ratio upper bound. Validation losses can likewise be translated into competitive-ratio upper bounds for individual workloads. For a fixed predictor, averaging these bounds over independent validation workloads from the deployment distribution provides an empirical estimate of an upper bound on the expected cost ratio. We have also derived general smoothness lower bounds and established optimal or near-optimal smoothness for these prediction-quality errors. Please see our response to Reviewer LuWL and newly added Sections 3.6 and 4.5 for further details on these additions. ## Adaptive predictions Our guarantees also hold for adaptive predictions based on the algorithm's actual state and previous decisions. Both the original solution-quality error $E$ and the newly introduced Hamming errors $k(h,a)$ and $W(h,a)$ may therefore depend on the algorithm's previous decisions. Nevertheless, both the original and new smoothness bounds apply to every realized prediction sequence, with the corresponding errors evaluated on that sequence. We have now made this explicit in Sections 3.1 and 4.1 of the revised paper (highlighted in blue).

Comments on the paper

4 comments

Dear reviewers, dear authors,

thank you for engaging in the discussion on this submission.

Reviewer TZch: The authors have commented on your concerns and updated their submission. Please acknowledge their rebuttal and, if possible, have a look at their revised version and decide whether their rebuttal and changes affect your assessment.

Reviewer LuWL: The authors focused on your critical question that might affect your assessment. Please acknowledge their rebuttal and, if possible, have a look at their revised version and decide whether they have answered your question to an extent that affects your score.

Authors: Please also consider to answer the questions of Reviewer BNYC.

AC

Dear Area Chair,

Thank you very much for your message and for your efforts in coordinating the discussion.

We first posted our responses to Reviewers TZch and LuWL, which we completed first. We are currently preparing our response to Reviewer BNYC's comments and will post it as soon as it is ready.

Best regards,

The Authors

AuthorsOpenReview ↗

Summary of Revisions and Responses

Dear reviewers and Area Chair,

We sincerely thank the reviewers and Area Chair for their time and consideration.

With under 24 hours left for discussion, we summarize our updates and responses below. We would appreciate your feedback on whether these address your concerns and welcome any remaining questions.

  • Reviewer TZch: We clarified that our guarantees also hold for adaptive predictions (revised Sections 3.1 and 4.1). We also explained how small the robustness gap is under the same consistency requirement (Theorem 5).

  • Reviewer BNYC: We added learned-predictor experiments showing empirical advantage than LS and RTP (Figure 1, right; Appendix K). Our response also quantifies parameter-specific robustness gaps and explains how users choose ε\varepsilon before execution to specify the preferred consistency–robustness trade-off (now clarified in the Introduction, bottom of p. 1).

Summary of Paper Revisions

  • Smoothness and connection to learning losses. We added smoothness bounds under processing-time-weighted Hamming error, general lower bounds, and optimality or near-optimality of our algorithms (Sections 3.6 and 4.5). We also linked them to cross-entropy losses (Appendices D.1 and G.1). Reviewer LuWL confirmed that this addressed their concerns and updated to Clear Acceptance.

  • Learned predictions. We added learned-predictor experiments showing average gains over LS and RTP for all tested ε\varepsilon (Figure 1, right; Appendix K).

We are grateful for the reviewers' time and consideration and would be happy to address any remaining questions or concerns.

AuthorsOpenReview ↗

Final Summary of Responses and Revisions

Dear Area Chair and reviewers,

We sincerely thank you for your time and constructive feedback. We summarize our responses to each reviewer's main concerns and the corresponding paper revisions below.

Reviewer LuWL (Rating 4, Conf. 4): Prediction-quality error and smoothness

We added smoothness bounds under processing-time-weighted Hamming error and general lower bounds, establishing optimality or near-optimality (Sections 3.6 and 4.5). The weighted bound can improve on List Scheduling's classical guarantee even with imperfect predictions. We also linked the guarantees to cross-entropy losses used for training (Appendices D.1 and G.1). LuWL confirmed that their concerns were addressed and updated to Clear Acceptance. All individual scores (Presentation, Informativeness, and Soundness) are now at 3 (highest).

Reviewer TZch (Rating 3, Conf. 2): Robustness gaps and the prediction model

We clarified that our guarantees also hold for adaptive predictions (Sections 3.1 and 4.1). The connection to cross-entropy losses also address practical realization of the prediction model. We explained how small the robustness gap is relative to all deterministic online algorithms under the same consistency requirement (Theorem 5; Appendix C).

Reviewer BNYC (Rating 3, Conf. 3): Parameter-specific guarantees and practical advantages

We added learned-predictor experiments showing average gains over LS and RTP on synthetic test inputs for all tested ε\varepsilon (Figure 1, right; Appendix K). We explained why classical worst-case guarantees can be incompatible with strong consistency. We clarified how users choose ε\varepsilon before execution to specify their preferred consistency–robustness trade-off (Introduction, p. 1). We also reported robustness upper/lower-bound for the machine counts and ε\varepsilon used experimentally to answer their question. The reviewer BNYC rated all individual scores (Presentation, Informativeness, and Soundness) at 3 (highest).


The additions are highlighted in blue and green in the revised paper. We appreciate your time and consideration throughout the review process and hope our responses and revisions have addressed the reviewers' concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.