REVIEW 3 major objections 4 minor 35 references
Self-Evaluation for Job-Shop Scheduling
T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read A learned job-shop scheduler that scores blocks of job-machine assignments before executing them reports a 0.5% gap on the largest benchmark instances, below the exact solver's 3.9%.
desk verdict Strong JSSP results, but the self-evaluation mechanism is not yet isolated from the benefit of sampling multiple subsets. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the self-evaluation score $SE_\phi(A_{\mathrm{sub}})$, a Transformer-based regression trained to predict the true score $\mathrm{TrueScore}(A_{\mathrm{sub}}, A_{\mathrm{opt}})$, the share of a proposed assignment block that coincides with the optimal assignments for that state. This score is the bridge between 'which block is most likely under the policy' and 'which block is best to execute', and inference selects $A^*_t = \arg\max_{A \in \mathcal{A}_t} SE_\phi(A)$ over the sampled candidates. The policy side combines an attention-based heterogeneous graph neural network with a Transformer, and the evaluator's training target comes from random binary vectors rather than from the policy's own samples.
What would settle it
Keep the policy fixed and, on the benchmark instances, replace the evaluator's argmax with a random sampled subset or with the subset having the largest mean policy probability; if the optimality gap does not worsen against the reported SEVAL numbers, the self-evaluation module is not the source of the improvement. On small instances where an exact solver can supply the optimal assignment set, compare the evaluator's ranking of policy-sampled subsets with their true scores; a ranking mismatch would identify the learned proxy as the failure point.
Extended reading notes
Core claim
SEVAL redefines the job-shop Markov process so that an action is a subset $A$ of feasible job-machine pairs with no machine used twice, and the transition removes the chosen operations from the state graph. A heterogeneous graph neural network produces embeddings for jobs, machines, and edges, and a Transformer-based policy assigns a probability to every feasible assignment; the policy is trained to match the assignment distribution of optimal solver trajectories. A second Transformer, the self-evaluator, receives the same embeddings plus a binary vector encoding a candidate subset and is trained with mean-squared error to reproduce the true score $\mathrm{TrueScore}(A_{\mathrm{sub}}, A_{\mathrm{opt}})$, the fraction of assignments in the subset that also lie in the optimal assignment set. At inference the policy samples $n$ subsets, the evaluator scores each, and the highest-scored subset becomes the action, which is the mechanism the paper credits for the gains in Tables 1 and 2.
Load-bearing premise
The whole comparison rests on the assumption that the share of optimal assignments in a proposed block, learned as a supervised target, is a faithful proxy for how much executing that block improves the final makespan, and that an evaluator trained on random blocks will still rank the policy's sampled blocks correctly.
Editorial extensions
If this is right
- On the largest class of instances in the first benchmark (100 jobs by 20 machines), SEVAL reports a 0.5% mean gap, below the 3.9% that an exact solver needs an hour to reach; if reproducible, learned schedulers are approaching optimality on the hardest widely used benchmark class.
- On the second benchmark, whose instances come from a different distribution than the training data, the mean gap is 9.9% against 14.9% for the next-best compared deep-learning method, indicating the self-evaluation module also acts as a safeguard against distribution shift.
- The two compared methods that assign multiple actions at once but lack a self-evaluation module land behind SEVAL throughout both benchmark tables, which is the paper's within-paper evidence that collective evaluation, not merely multi-assignment prediction, drives the improvement.
- The framework is stated for any combinatorial problem with a graph state and feasible assignment sets, so the same policy-plus-evaluator recipe is claimed to be transferable to other constructive combinatorial problems, although only job-shop scheduling is tested here.
Reading between the lines
- Editorial inference: the evaluator is trained on random binary subsets but deployed on policy-sampled subsets; retraining it on policy-generated candidates and re-running the benchmarks would directly test whether the reported gaps depend on that distribution transfer.
- Editorial inference: if block-level evaluation generalizes, constructive neural solvers become a small search: propose many short blocks, score them, execute the best, which shortens the chain of sequential decisions and thereby reduces the opportunity for error accumulation.
- Editorial inference: the headline result on the largest instance class rests on ten benchmark instances at a single inference setting; varying seeds, sampling temperature, and subset size would show how much of the 0.5% margin is architecture and how much is sampling variation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes SEVAL, a supervised learning framework for the Job-Shop Scheduling Problem (JSSP) in which a policy model proposes subsets of job-machine assignments and a separate self-evaluation model scores each candidate subset, selecting the highest-scoring one for execution at each step. The policy combines a heterogeneous graph neural network (HGNN) with a Transformer, and the self-evaluation model is a Transformer trained to predict the fraction of optimal assignments in a binary-vector representation of a subset. Experiments on the Taillard and Demirkol benchmarks report mean optimality gaps of 6.5% and 9.9%, respectively, outperforming several deep learning baselines and, on 100x20 Taillard instances, exceeding OR-Tools' gap (0.5% vs 3.9%) despite much lower runtime. The authors attribute the improvement to the self-evaluation mechanism and to the shift from single-action to subset-level action spaces.
Significance. If the reported gains hold under closer scrutiny, SEVAL would be a meaningful advance: it is one of the first constructive JSSP methods to explicitly evaluate subsets of assignments, and the reported gaps on two standard benchmarks are substantially better than existing learned baselines. The paper's strengths include the breadth of compared methods (L2D, ResSch, RLCP, MAS, SPN, SIGD, L2S, OR-Tools), evaluation on two benchmarks with different distributions, and the inclusion of execution-time tables. However, the central claim that self-evaluation, rather than the added sampling/search, drives the improvement is not yet supported by the experiments as presented.
major comments (3)
- [§5.2 (Tables 1–2) vs §4.2.3 (Eq. 8)] The comparison against deep learning baselines conflates two effects: (i) sampling n=16 candidate subsets per state from the policy and (ii) scoring those subsets with the self-evaluation model SEφ. All baselines are evaluated with greedy decoding (§5.1), so the reported margin could come entirely from the extra inference-time search over 16 candidates, not from the self-evaluation score. The paper provides no ablation that keeps the same 16-subset sampling but replaces SEφ with a cheaper selection rule (e.g., random selection or highest sum of policy log-probabilities). Without such a control, the claim that subset-level self-evaluation is effective is not established. This is a load-bearing omission because the central contribution is the evaluator, not the sampling procedure.
- [§4.2.3 (Eq. 8) and training procedure (Algorithm 1, line 10)] The self-evaluation model is trained on randomly generated binary vectors BV(Asub), but at inference it scores subsets sampled from the learned policy πθ(a|s). This is a distribution shift: random subsets are likely to contain arbitrary combinations of actions with varying probabilities, whereas policy-sampled subsets are concentrated on high-probability actions. The paper does not report any evidence that SEφ remains calibrated on policy-sampled subsets; if the shift is severe, the arg max in Eq. 8 could select worse subsets than random selection. A simple test would be to compute the correlation between SEφ(Asub) and TrueScore(Asub, Aopt) on held-out policy-sampled subsets, or to train the evaluator on policy-sampled subsets and compare.
- [§4.2.3 (Eq. 7) and the use of TrueScore] The training target TrueScore(Asub, Aopt) is the fraction of optimal assignments in the subset, which is treated as a proxy for the effect of executing that subset on the final makespan. This proxy is not obviously valid: a subset with a high fraction of optimal individual assignments could still be a poor choice due to interactions among assignments (e.g., precedence constraints or machine contention), and a subset with a lower fraction might lead to a better makespan by preserving critical resources. The paper does not provide empirical evidence that this proxy correlates with final makespan on the benchmark instances. Adding a correlation analysis or an ablation that trains the evaluator on a makespan-based target would address this concern.
minor comments (4)
- [Throughout] The method name is rendered inconsistently as 'SEV AL' in the text (e.g., Sections 4.2, 5.1, Table 1) and 'SEVAL' elsewhere; please unify the notation.
- [Appendix E] The heading 'Execution time comparation' contains a typo; it should be 'Execution time comparison'.
- [Tables 1–2] The tables report only mean optimality gaps over 10 instances per size; no standard deviations or per-instance results are given. Since the margins over SIGD and MAS are small in several rows (e.g., 3.2 vs 2.7 on 50×15 Taillard), error bars or a full table of per-instance values would help assess whether the differences are meaningful.
- [Algorithm 2 (Appendix C)] The variable 'n' in 'Assign n optimal actions' is undefined and conflicts with the number of jobs n used in the main text; please use a different symbol and specify its distribution clearly.
Circularity Check
No circularity: solver-supervised training on small instances and evaluation on external Taillard/Demirkol benchmarks keep SEVAL's derivation self-contained.
full rationale
I find no circular step in the paper. SEVAL trains both the policy and the self-evaluation model by supervised learning on OR-Tools-generated trajectories for small instances (Section 4.2 and Algorithm 1), and reports makespan gaps on the external Taillard and Demirkol benchmarks (Tables 1 and 2). The self-evaluation target TrueScore(Asub, Aopt) is a ground-truth similarity computed from solver-provided optimal assignments, not a parameter fitted to the benchmark results; Eq. 7 is an MSE loss against that externally generated target, and Eq. 8 simply selects among policy-sampled subsets using the trained score. No equation in the paper reduces a reported optimality gap to a fitted value or to the training target by construction. The paper's self-citations to prior work by the same authors (Echeverria et al., 2024a; 2024b; 2025) are methodological borrowings, such as the simplified heterogeneous graph state, the restriction of the action space to a maximum number of assignments, and the removal of completed operations; they are not invoked as a uniqueness theorem or as the justification for the central performance claim. The lack of an ablation that isolates the self-evaluation score from the 16-subset sampling is an attribution or confound concern, not circularity, because the comparison is empirical and the claimed mechanism is independently testable.
Assumptions & free parameters
free parameters (4)
- candidate_subset_count_n =
16
- subset_size_k =
not reported
- dataset_perturbation_bounds =
n ~ Uniform(0, 0.7*|I|); add 1-30 random actions; accept if score ratio <= 1.1
- model_hyperparameters =
HGNN L=6, heads=3, hidden=32; Transformer layers=4, heads=8, dim=128; lr=3e-4; epochs=30; batch=256
assumptions (5)
- domain assumption Optimal trajectories produced by OR-Tools with a 60-second time limit provide a consistent target distribution for supervised training.
- ad hoc to paper The proportion of optimal assignments TrueScore(Asub, Aopt) is a valid proxy for the effect of executing Asub on final makespan.
- ad hoc to paper The self-evaluation model trained on random subsets generalizes to the policy-generated subsets used at inference.
- domain assumption Restricting subsets so each machine receives at most one assignment, and further constraining to the number of machines ordered by minimum start times, does not exclude the optimal schedule.
- domain assumption The heterogeneous graph state representation captures the information needed to predict optimal assignments.
Cite this review
Pith. "Pith review of Self-Evaluation for Job-Shop Scheduling." pith.science (2026). https://pith.science/paper/7CLYY5FX
@misc{pith2026250208684,
author = {Pith},
title = {Pith review of: Self-Evaluation for Job-Shop Scheduling},
year = {2026},
howpublished = {\url{https://pith.science/paper/7CLYY5FX}},
note = {Machine review of arXiv:2502.08684}
}
read the original abstract
Combinatorial optimization problems, such as scheduling and route planning, are crucial in various industries but are computationally intractable due to their NP-hard nature. Neural Combinatorial Optimization methods leverage machine learning to address these challenges but often depend on sequential decision-making, which is prone to error accumulation as small mistakes propagate throughout the process. Inspired by self-evaluation techniques in Large Language Models, we propose a novel framework that generates and evaluates subsets of assignments, moving beyond traditional stepwise approaches. Applied to the Job-Shop Scheduling Problem, our method integrates a heterogeneous graph neural network with a Transformer to build a policy model and a self-evaluation function. Experimental validation on challenging, well-known benchmarks demonstrates the effectiveness of our approach, surpassing state-of-the-art methods.
Figures
Reference graph
Works this paper leans on
-
[1]
Andres, A., Sch \"a fer, L., Albrecht, S. V., and Del Ser, J. Using offline data to speed up reinforcement learning in procedurally generated environments. Neurocomputing, 618: 0 129079, 2025
work page 2025
-
[2]
V., Norouzi, M., and Bengio, S
Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. In Proceedings of the 5th International Conference on Learning Representations (ICLR) Workshop Track, 2017
work page 2017
-
[3]
Blum, C. and Roli, A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35 0 (3): 0 268--308, 2003
work page 2003
-
[4]
How attentive are graph attention networks? arXiv preprint arXiv:2105.14491, 2021
Brody, S., Alon, U., and Yahav, E. How attentive are graph attention networks? arXiv preprint arXiv:2105.14491, 2021
arXiv 2021
-
[5]
B., Mann, B., Ryder, N., and et al
Brown, T. B., Mann, B., Ryder, N., and et al. Language models are few-shot learners, 2020
work page 2020
-
[6]
Self-play fine-tuning converts weak language models to strong language models
Chen, Z., Deng, Y., Yuan, H., Ji, K., and Gu, Q. Self-play fine-tuning converts weak language models to strong language models. arXiv preprint arXiv:2401.01335, 2024
arXiv 2024
-
[7]
Self-labeling the job shop scheduling problem
Corsini, A., Porrello, A., Calderara, S., and Dell'Amico, M. Self-labeling the job shop scheduling problem. arXiv preprint arXiv:2401.11849, 2024
arXiv 2024
-
[8]
Benchmarks for shop scheduling problems
Demirkol, E., Mehta, S., and Uzsoy, R. Benchmarks for shop scheduling problems. European Journal of Operational Research, 109 0 (1): 0 137--141, 1998
work page 1998
Show all 35 references
-
[9]
Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-M. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[10]
Multi-assignment scheduler: A new behavioral cloning method for the job-shop scheduling problem
Echeverria, I., Murua, M., and Santana, R. Multi-assignment scheduler: A new behavioral cloning method for the job-shop scheduling problem. In International Conference on Learning and Intelligent Optimization, pp.\ 138--152. Springer, 2024 a
2024
-
[11]
Offline reinforcement learning for job-shop scheduling problems
Echeverria, I., Murua, M., and Santana, R. Offline reinforcement learning for job-shop scheduling problems. arXiv preprint arXiv:2410.15714, 2024 b
2024 arXiv
-
[12]
Diverse policy generation for the flexible job-shop scheduling problem via deep reinforcement learning with a novel graph representation
Echeverria, I., Murua, M., and Santana, R. Diverse policy generation for the flexible job-shop scheduling problem via deep reinforcement learning with a novel graph representation. Engineering Applications of Artificial Intelligence, 139: 0 109488, 2025
2025
-
[13]
I., Ceberio, J., and Mendiburu, A
Garmendia, A. I., Ceberio, J., and Mendiburu, A. Neural improvement heuristics for graph combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 2023
2023
-
[14]
Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem
Ho, K.-H., Cheng, J.-Y., Wu, J.-H., Chiang, F., Chen, Y.-C., Wu, Y.-Y., and Wu, I.-C. Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem. IEEE Access, 2024
2024
-
[15]
and et al
Kadavath, S. and et al. Language models (mostly) know what they know, 2022
2022
-
[16]
Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018
Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018
2018 arXiv
-
[17]
Attention, learn to solve routing problems!, 2019
Kool, W., van Hoof, H., and Welling, M. Attention, learn to solve routing problems!, 2019
2019
-
[18]
Should i run offline reinforcement learning or behavioral cloning? In International Conference on Learning Representations, 2021
Kumar, A., Hong, J., Singh, A., and Levine, S. Should i run offline reinforcement learning or behavioral cloning? In International Conference on Learning Representations, 2021
2021
-
[19]
POMO : Policy optimization with multiple optima for reinforcement learning
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. POMO : Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33: 0 21188--21198, 2020
2020
-
[20]
Self-refine: Iterative refinement with self-feedback
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[21]
Papadimitriou, C. H. Computational Complexity. Addison-Wesley, 1998
1998
-
[22]
and Didier, F
Perron, L. and Didier, F. Cp-sat. URL https://developers.google.com/optimization/cp/cp_solver/
-
[23]
and Grimm, D
Pirnay, J. and Grimm, D. G. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. arXiv preprint arXiv:2403.15180, 2024
2024 arXiv
-
[24]
and Bagnell, D
Ross, S. and Bagnell, D. Efficient reductions for imitation learning. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp.\ 661--668. JMLR Workshop and Conference Proceedings, 2010
2010
-
[25]
A., Colmenarejo, S
Rusu, A. A., Colmenarejo, S. G., Gulcehre, C., Desjardins, G., Kirkpatrick, J., Pascanu, R., Mnih, V., Kavukcuoglu, K., and Hadsell, R. Policy distillation. arXiv preprint arXiv:1511.06295, 2015
2015 arXiv
-
[26]
Flexible job-shop scheduling via graph neural network and deep reinforcement learning
Song, W., Chen, X., Li, Q., and Cao, Z. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 19 0 (2): 0 1600--1610, 2022
2022
-
[27]
Benchmarks for basic scheduling problems
Taillard, E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 0 (2): 0 278--285, 1993
1993
-
[28]
An end-to-end reinforcement learning approach for job-shop scheduling problems based on constraint programming
Tassel, P., Gebser, M., and Schekotihin, K. An end-to-end reinforcement learning approach for job-shop scheduling problems based on constraint programming. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 33, pp.\ 614--622, 2023
2023
-
[29]
Pointer networks
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, 2015
2015
-
[30]
Flexible job shop scheduling via dual attention network-based reinforcement learning
Wang, R., Wang, G., Sun, J., Deng, F., and Chen, J. Flexible job shop scheduling via dual attention network-based reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 35: 0 3091--3102, 2023
2023
-
[31]
V., Zhou, D., et al
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35: 0 24824--24837, 2022
2022
-
[32]
X., Kan, M.-Y., He, J., and Xie, M
Xie, Y., Kawaguchi, K., Zhao, Y., Zhao, J. X., Kan, M.-Y., He, J., and Xie, M. Self-evaluation guided beam search for reasoning. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[33]
Deep reinforcement learning guided improvement heuristic for job shop scheduling
Zhang, C., Cao, Z., Song, W., Wu, Y., and Zhang, J. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In The Twelfth International Conference on Learning Representations, 2024
2024
-
[34]
and et al
Zhang, Y. and et al. Learning-based priority dispatching for flexible job shop scheduling under uncertainties. Robotics and Computer-Integrated Manufacturing, 61: 0 101844, 2020
2020
-
[35]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.