{"id":"310f9721-90a8-4fca-b536-2100abdf048f","arxiv_id":"2502.08684","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SEVAL, a learned scheduler that evaluates whole sets of job-machine assignments at once, reports mean optimality gaps of 6.5% on Taillard and 9.9% on Demirkol, ahead of prior deep learning schedulers.","lead":"This paper trains a policy and a learned self-evaluation model to generate and then score sets of scheduling decisions at once, rather than one step at a time. On standard job-shop benchmarks the method beats other learned schedulers and, for the largest Taillard instances, also beats OR-Tools CP-SAT.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SEVAL's reported gains over deep-learning baselines could stem from sampling 16 candidate subsets per step rather than from the self-evaluation score; no ablation isolates the evaluator's contribution.","rationale":"The strongest claim is that the self-evaluation mechanism improves scheduling quality. For that claim to hold, the score SE_phi must add value beyond the policy's own sampling. The paper's experimental design does not demonstrate this: SEVAL samples 16 subsets per step (Section 5.1), while every deep-learning baseline is run greedily. This confounds two factors. First, simply having 16 candidates and picking one (even randomly) can improve over greedy because the policy is stochastic and sampled subsets may include better joint assignments. Second, the evaluator might rank them well. The reader's weakest_assumption targets the training target and distribution shift of the evaluator; that is a real secondary risk, but the missing ablation is more fundamental because it affects whether self-evaluation is needed at all. The proposed test directly isolates the evaluator's contribution: if random or likelihood-based selection matches SEVAL's gaps, then the benchmark numbers do not support the paper's central design claim, even if the evaluator's proxy were perfectly calibrated. The paper does provide strong empirical support that the overall SEVAL pipeline is competitive, and the method is clearly described, so this is not a rejection but a conditional acceptance pending this control. The reader's verdict (CONDITIONAL) already notes the missing ablation in its rationale, so the verdict label need not change; our analysis sharpens why this is the single most load-bearing issue.","tokens_in":14249,"tokens_out":9977,"duration_ms":98991,"concrete_test":"On the Taillard 50x20 and 100x20 groups, re-run SEVAL's inference with the same 16 sampled subsets per state, but replace the self-evaluation argmax (Eq. 8) with (a) uniform random selection, and (b) selection by the highest sum of policy log-probabilities over the subset. If either baseline achieves an optimality gap within ~1 percentage point of SEVAL's reported 5.1%/0.5%, the self-evaluation model is not the source of the gains. Additionally, compare against sampling 16 complete solutions from the policy and keeping the best makespan, to account for the inference budget.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim depends on the self-evaluation score, not just the policy sampling, being responsible for SEVAL's benchmark gaps. But the inference procedure (Section 4.2.3) samples n=16 candidate subsets per state from the policy, and the self-evaluation model only selects among them. All deep-learning baselines are evaluated with greedy decoding (Section 5.1), i.e., no search. Thus the reported 6.5%/9.9% gaps combine the effect of (i) sampling 16 subsets per step and (ii) scoring them. The paper provides no ablation that replaces SE_phi with a cheaper selection rule (e.g., random choice or highest sum of policy log-probabilities) while keeping the same 16-subset sampling. Without such a control, the improvement over MAS/RLCP/SIGD cannot be attributed to self-evaluation rather than to the additional inference-time search. Moreover, the self-evaluation target TrueScore(Asub,Aopt) (Eq. 7) is the fraction of optimal assignments; because the evaluator is trained on random binary vectors, while inference subsets are policy-sampled, a distribution shift could make the score poorly calibrated on the actual candidates, potentially selecting worse subsets than random selection. Both issues are testable, but the missing ablation is the more direct threat to the claim that subset-level self-evaluation is effective.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14536,"tokens_out":2122,"duration_ms":24220,"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":[{"comment":"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.","section":"§5.2 (Tables 1–2) vs §4.2.3 (Eq. 8)"},{"comment":"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.","section":"§4.2.3 (Eq. 8) and training procedure (Algorithm 1, line 10)"},{"comment":"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.","section":"§4.2.3 (Eq. 7) and the use of TrueScore"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"The heading 'Execution time comparation' contains a typo; it should be 'Execution time comparison'.","section":"Appendix E"},{"comment":"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.","section":"Tables 1–2"},{"comment":"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.","section":"Algorithm 2 (Appendix C)"}],"recommendation":"major_revision","confidential_remarks":"The paper's contribution is potentially interesting, but the central attribution to self-evaluation is not yet demonstrated because of the missing ablation. The concern is not that the method is wrong, but that the reported gains may be reinterpretable as a sampling/search effect. The authors should also strengthen the discussion of the distribution shift between training random subsets and evaluating policy-sampled subsets. Given the paper's current form, I cannot recommend acceptance without these experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jonathan — quick take on arXiv:2502.08684. The paper is clearly written and reports numbers that would be a real advance in learned JSSP if they hold: 6.5% mean gap on Taillard and 9.9% on Demirkol, with 0.5% on 100x20, beating OR-Tools at one hour in 41 seconds. The idea — treating a self-evaluation network as a reranker over subsets of assignments, inspired by LLM self-evaluation — is a genuine extension of the authors' earlier MAS work and is worth taking seriously.\n\nWhat I think is actually new: the framework of generating multiple candidate assignment subsets per state and scoring them with a separate learned function is a clean departure from greedy stepwise decoding. The architecture (HGNN embeddings shared between policy and evaluator, Transformer heads) is sensible, and the training via supervised cloning from OR-Tools solutions avoids the usual RL instability. The experimental setup is also solid: two standard benchmarks, several state-of-the-art baselines using pretrained models, execution times reported.\n\nThe soft spot is the one the stress-test flags: no ablation isolates the evaluator. Inference samples 16 subsets per step and the evaluator picks one; all DL baselines are greedy. So the reported gain could come largely from trying 16 candidates instead of one. A control that keeps the 16-subsample procedure but selects randomly, or by highest sum of policy log-probabilities, would settle this. Without it, the paper's title claim — that self-evaluation is what works — is not demonstrated, even though the method as a whole may be competitive.\n\nTwo smaller issues: the subset size k is never specified in the paper, and the evaluator is trained on random binary vectors but applied to policy-sampled subsets, so a distribution shift could weaken the scores. Neither is fatal, but both should be addressed. Also, 'outperforms OR-Tools' is only true for the 100x20 group; elsewhere OR-Tools is clearly better. The text is careful to say 'on larger instances,' but it reads as a broader claim.\n\nOn reproducibility: no code or data yet, no error bars. That's fixable. The circularity concern raised elsewhere doesn't worry me — the evaluator is trained on solver-generated labels, not fitted to the benchmark results.\n\nBottom line: this deserves a serious referee and a revision. I'd want the ablation, k specified, and code released before citing the numbers. If the ablation holds, this is a solid contribution.","headline":"Strong JSSP results, but the self-evaluation mechanism is not yet isolated from the benefit of sampling multiple subsets.","tokens_in":15086,"tokens_out":3135,"would_cite":false,"duration_ms":30092,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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%.","keywords":["job-shop scheduling","self-evaluation","neural combinatorial optimization","heterogeneous graph neural network","Transformer","supervised learning","makespan","subset action selection"],"falsifier":"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.","tokens_in":14021,"feed_emoji":"⚙️","tokens_out":17017,"duration_ms":153699,"temperature":0.7,"pith_summary":"Job-shop scheduling is the problem of ordering every job's operations on machines so that all jobs finish as early as possible, and a wrong early assignment can poison the whole schedule. SEVAL approaches this by sampling and scoring blocks of job-machine assignments at each step instead of picking single assignments one by one: a policy proposes candidate blocks and a self-evaluation function scores each block by how many of its assignments would appear in an optimal solution, then the best-scored block is executed. Trained on 40,000 small synthetic instances and tested on two standard 80-instance benchmarks (one from the same distribution, one not), the method reports mean optimality gaps of 6.5% and 9.9%, better than all compared deep-learning schedulers, and a 0.5% mean gap on the largest class of instances, better than an exact solver given one hour per instance. The authors claim this shows that collective self-evaluation, rather than only multi-assignment prediction, is what prevents small errors from propagating.","feed_headline":"Whole-block assignment scoring cuts job-shop gap to 0.5%","feed_subtitle":"Mean gap 0.5 percent on the largest benchmark instances; exact solver gives 3.9 percent at one hour.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the heterogeneous graph state representation that the policy and the self-evaluation module both consume.","marker":"(Song et al., 2022)"},{"why":"Prior multi-assignment supervised scheduler whose action-space constraints SEVAL inherits and whose results serve as a key comparison.","marker":"(Echeverria et al., 2024a)"},{"why":"Defines the first benchmark and the instance-generation procedure used to create the 40,000 training instances.","marker":"(Taillard, 1993)"},{"why":"Defines the second, distribution-shifted benchmark used to test generalization.","marker":"(Demirkol et al., 1998)"},{"why":"CP-SAT solver that generates the optimal training trajectories and provides the exact-solver baseline.","marker":"(Perron & Didier)"},{"why":"The strongest compared deep-learning baseline on both benchmarks, so the method SEVAL must beat.","marker":"(Pirnay & Grimm, 2024)"},{"why":"A baseline that assigns multiple actions without self-evaluation, isolating the role of the evaluator module.","marker":"(Tassel et al., 2023)"},{"why":"Recent reinforcement-learning scheduling baseline and the source of the completed-operation removal used in state transitions.","marker":"(Ho et al., 2024)"},{"why":"Supplies the attention mechanism used inside the heterogeneous graph neural network layers.","marker":"(Brody et al., 2021)"}],"fun_headline_variants":["Self-evaluating subsets outdo stepwise job-shop solvers","Subset scoring lifts job-shop scheduling to 0.5% gap","Transformer self-evaluator picks best job-shop action blocks","Job-shop: sample subsets, self-score, then apply best","Self-evaluation for job-shop: score subsets, not steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Self-evaluating subsets outdo stepwise job-shop solvers","Subset scoring lifts job-shop scheduling to 0.5% gap","Transformer self-evaluator picks best job-shop action blocks","Job-shop: sample subsets, self-score, then apply best","Self-evaluation for job-shop: score subsets, not steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000641,"raw_usage":{"total_tokens":2907,"prompt_tokens":858,"completion_tokens":2049,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":1956}},"tokens_in":474,"tokens_out":2049,"duration_ms":16362,"temperature":1.0,"reasoning_tokens":1956,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:36:47.164645+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Flexible job-shop scheduling via graph neural network and deep reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Supplies the heterogeneous graph state representation that the policy and the self-evaluation module both consume."},{"cited_title":"Benchmarks for basic scheduling problems","cited_arxiv_id":null,"evidence_quote":"Defines the first benchmark and the instance-generation procedure used to create the 40,000 training instances."},{"cited_title":"Benchmarks for shop scheduling problems","cited_arxiv_id":null,"evidence_quote":"Defines the second, distribution-shifted benchmark used to test generalization."},{"cited_title":"An end-to-end reinforcement learning approach for job-shop scheduling problems based on constraint programming","cited_arxiv_id":null,"evidence_quote":"A baseline that assigns multiple actions without self-evaluation, isolating the role of the evaluator module."}],"review_version":1}