- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 2
Read review
Paper summary
This paper studies non-clairvoyant scheduling through behavioral cloning of clairvoyant scheduling policies. The method is evaluated on ATLAS and ASTRA, a workload constructed from a public production GPU-cluster trace. Experiments cover total completion time and maximum stretch on a single machine, and makespan on parallel machines. The reported results improve over the evaluated prediction-based baselines.
Critical strengths
- The paper addresses a meaningful mismatch between prediction accuracy and scheduling quality. Optimizing processing-time regression does not necessarily optimize the downstream scheduling objective. Training on expert decisions is a reasonable way to introduce task-specific supervision.
- The architecture provides a simple way to handle variable-sized pending sets.
- The empirical improvements are promising, especially for maximum stretch. Makespan improvements appear on both workloads, and the expert-selection ablation usefully shows that the best expert to imitate can depend on the workload.
Critical weaknesses
- The central motivation does not adequately distinguish the method from existing order-prediction approaches. The paper broadly characterizes learning-augmented scheduling as relying on scalar processing-time predictions. However, Lindermayr's Permutation Predictions for Non-Clairvoyant Scheduling explicitly predicts relative job orderings rather than processing requirements, and studies both learnability and empirical performance. Although this work is cited in the introduction, its implications for the claimed distinction are not addressed in the related-work discussion or experiments.
- The comparisons do not cleanly isolate the benefit of decision supervision from predictor quality and baseline choice. The “without decoder” ablation uses SPRPT for the single-machine setting, whereas the strongest total-completion-time baseline in Table 1 is Meta-SPJF.
- The parallel-machine model is not fully connected to the stated network architecture. Section 4.1 includes predicted machine loads in the state, but Section 4.3 describes global inputs as current time and pending-job count, without explaining how the machine-load vector enters the decoder. The expert-data construction should also clarify whether teacher trajectories use true or predicted machine loads and how their states correspond to those encountered by the learned policy.
- The production-cluster interpretation is broader than the evaluated scheduling model. ASTRA contains heterogeneous GPU models and jobs requesting widely varying resources, including multi-GPU jobs, but the parallel-machine experiment assigns each job to one identical machine and releases all jobs simultaneously.
- Scalability is not sufficiently documented. Handling an arbitrary number of jobs architecturally does not establish practical efficiency. No scheduling-latency or scaling measurements are provided despite the emphasis on thousands of pending jobs.
Questions for authors
Please refer to the weaknesses.
9 comments
Table R2. Scheduling performance on ATLAS across three objectives, together with makespan on ASTRA; lower is better. Max-stretch on jobs; total completion time on jobs; makespan ratios averaged over and reported as ATLAS / ASTRA. Results are mean ± std over five test windows. The best learned result in each column is bolded; objective-specific reference values and bounds are also bolded.
| Algorithm | Algorithm | Algorithm | (ATLAS / ASTRA) | |||
|---|---|---|---|---|---|---|
| OPT (EDF at ) | 1.00 ± 0.00 | 1.00 ± 0.00 | SRPT | 1.0000 ± 0.0000 | LPT | 1.0000 ± 0.0000 / 1.0000 ± 0.0000 |
| SRPT | 1.57 ± 0.05 | 1.29 ± 0.04 | SJF | 1.0008 ± 0.0010 | SPT | 1.4864 ± 0.0820 / 1.3620 ± 0.0185 |
| Random | 1.8386 ± 0.1165 / 2.3317 ± 0.1194 | |||||
| LGBM-SPRPT | 1704.47 ± 316.07 | 49.11 ± 11.86 | LGBM-SPJF | 1.3873 ± 0.0525 | LGBM-SPPT | 1.6381 ± 0.1461 / 2.1931 ± 0.3775 |
| LGBM-EDF | 1735.04 ± 326.21 | 71.83 ± 13.06 | LGBM-PRR | 1.6201 ± 0.061 | LGBM-LPPT | 1.6499 ± 0.2464 / 2.3111 ± 0.4157 |
| Ours | 102.83 ± 44.32 | 7.16 ± 3.36 | Ours | 1.1687 ± 0.0575 | Ours | 1.4346 ± 0.1533 / 1.8178 ± 0.0932 |
Results and interpretation (Table R2).
Table R2 provides the direct test for the order-prediction alternative. If directly predicted priorities were sufficient, the pointwise ranker combined with predefined rules would approach our method. It does not: the mean ratios are 1.1687 against 1.3873 for total completion time, 1.4346 against 1.6381 for makespan on ATLAS, and 1.8178 against 2.1931 for makespan on ASTRA. Max-stretch and 99th-percentile stretch show gaps of similar size. The pointwise rank-prediction alternative does not close the gap, indicating that the state-conditioned architecture provides benefits beyond learning a relative order.
We will revise the introduction and related-work discussion to explicitly acknowledge permutation prediction as an existing action-prediction approach and clarify its distinction from our state-conditioned policy. We will also describe the additional rank-prediction experiment and its findings in the experimental section, making clear that it complements, rather than directly reproduces, the permutation-prediction study.
References.
- A. Lindermayr and N. Megow. Permutation Predictions for Non-Clairvoyant Scheduling. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 357–368, 2022. DOI: 10.1145/3490148.3538579. arXiv:2202.10199.
- Z. Jiang, T. Zhao, C. Xia, and A. Zomaya. ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling. In International Conference on Learning Representations (ICLR), pp. 137404–137421, 2026.
- G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Advances in Neural Information Processing Systems (NeurIPS), vol. 30, pp. 3146–3154, 2017.
- J. Lee, G. Bernier-Colborne, T. Maharaj, and S. Vajjala. Methods, Applications, and Directions of Learning-to-Rank in NLP Research. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 1900–1917, 2024.
We thank the reviewer for the helpful comments. We address the weaknesses and questions below.
[W2] The ablation does not isolate decision supervision from predictor quality and baseline choice
We agree with this observation. The strongest total-completion-time baseline, Meta-SPJF, is built on SPJF, whereas our original no-decoder row applied SPRPT. The original row therefore did not provide a rule-based control corresponding to SPJF, the rule used by the strongest baseline; consequently, it could not isolate the contribution of the learned decoder.
To address this, we re-evaluated the no-decoder variant using the non-preemptive SPJF rule, retaining the same trained processing-time predictor and evaluation settings, including the five test windows and SRPT normalization. The reported results are averages over the five test windows. The no-decoder variant attains , whereas the full model attains , corresponding to a 14.0% reduction relative to the matched no-decoder control (lower is better). By keeping the predictor and evaluation protocol fixed, this comparison isolates the contribution of the learned decoder.
In the revised manuscript, we will update the ablation section to report the matched no-decoder result of and clarify that it is obtained by applying the non-preemptive SPJF rule to the same trained processing-time predictor as the full model. We will also report the complete results of applying our processing-time predictor with all learning-augmented scheduling rules across all objectives in Appendix E.
Thank you for your valuable and constructive feedback.
[W1] Distinction from Existing Order-Prediction Approaches
We agree that our original characterization was too broad. The permutation-prediction model (Lindermayr & Megow, 2022) predicts relative job orderings rather than processing requirements. That work also studies the theoretical and empirical learnability of such predictions.
Permutation predictions in existing work.
Lindermayr and Megow conduct two types of experiments on synthetic job instances.
First, their sensitivity experiments construct permutation predictions by adding Gaussian noise to processing times and sorting the perturbed values. These experiments evaluate prediction robustness in single-machine and parallel-machine settings, rather than learning a ranking function from job features.
Second, their online-learning experiment considers a fixed synthetic base instance and generates successive instances by independently perturbing its job processing times. An ERM procedure uses historical instances to learn a permutation for the next round. Specifically, in the single-machine setting, it averages the historical processing times of each indexed job and sorts the jobs in ascending order of these averages. Thus, this experiment demonstrates learning a permutation, but its learned hypothesis is an ordering over a fixed set of indexed jobs, rather than a feature-based function that predicts priorities for previously unseen jobs.
Distinction from our setting and additional baseline.
The organization of ATLAS (Jiang et al., 2026) and ASTRA makes direct application of the index-based ERM procedure used for permutation predictions (Lindermayr & Megow, 2022) unsuitable. Jobs come from non-overlapping instances and time windows, so individual jobs do not recur under stable indices, leaving no aligned observations from which ERM can aggregate per-job histories. Instead, priorities must be predicted from job features to generalize across unseen jobs. Pointwise learning-to-rank provides a natural formulation: each candidate receives an independent relevance score (Lee et al., 2024). In our setting, the candidate is a job and the score is its dispatch priority; we derive per-job targets from processing times and deadlines. We therefore construct a feature-based LightGBM ranker as a task-compatible test of the order-prediction alternative, rather than a reproduction of the permutation-learning procedure in that work.
Pointwise rank-prediction baseline.
Using the same features, training data, and temporal splits as the size predictors, we fit two pointwise LGBM rankers (Ke et al., 2017) on normalized rank labels. Let Ftrp and Ftrd be the empirical CDFs of training processing times and synthetic deadlines. For a job j with observed training duration pj, its synthetic deadline is dj, obtained by adding ten times pj to its block-relative submission time (the multiplier is tuned on validation). The two targets are
yjdur=Ftrp(pj),
yjddl=1−Ftrd(dj).
Thus yjdur is a normalized duration score and yjddl a normalized earliness score: larger values mean longer training durations and earlier synthetic deadlines, respectively. The duration model drives SPJF, SPRPT, PRR, LPPT, and SPPT, whereas the deadline model drives EDF.
At test time, each job receives a scalar rank score s^j from the LGBM model. SPJF sorts jobs by ascending duration score; PRR alternates between this order and round-robin; EDF uses descending deadline scores. For SPRPT, the score is first clipped to [0,1], then inverted through the training processing-time CDF to give a pseudo-length p^j, and the remaining time is updated as r^j(t)=p^j−ej(t), with ej(t) the processing already received. The scheduler always dispatches the pending job with the smallest predicted remaining time. For parallel machines, LPPT/SPPT sort by pseudo-length (descending/ascending) and assign to the least-loaded machine; ground-truth test processing times are never used.