{"id":"a504d73b-c99f-4b00-b3f7-41477a88c94e","arxiv_id":"2501.17991","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"On 20 synthetic large job shop instances, the best MCTS configurations achieved lower mean weighted completion times than the authors' OR-Tools constraint programming model.","lead":"This paper applies Monte Carlo Tree Search to large job shop scheduling problems with recirculation, testing several ways to model the problem as a Markov decision process. It also releases a synthetic benchmark based on anonymized factory data and reports that MCTS beats its constraint programming baseline on these instances.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing time limits and error bars: reported MCTS advantage over CP could be a budget artifact rather than a solution-quality result.","rationale":"I read the paper as an empirical comparison paper: the central claim is the abstract's assertion that MCTS 'produces good-quality solutions for large-scale JSSP instances, outperforming our constraint programming approach.' For that claim to hold, the comparison must be budget-fair and statistically meaningful. The paper reports no runtimes anywhere, and the only MCTS stopping criterion mentioned is 'six repetition steps and 30 evaluations' (Section 5.1), which is not comparable to whatever time OR-Tools CP-SAT used. The reader's weakest_assumption focused on synthetic benchmark representativeness, which is a genuine limitation about external validity. I partially agree but think the more load-bearing, immediately testable weakness is the uncontrolled computational budget combined with selection on the same instances and no stochastic error bars. Even if the benchmark were perfectly representative, an under-resourced CP baseline would invalidate the comparison; conversely, if a matched-budget rerun reproduced the advantage, the benchmark concern would remain but the headline claim would be supported on the tested class. The paper does have independent value as a benchmark artifact and the MDP taxonomy is clearly described, and I found no internal contradiction in the algorithmic descriptions. The correct verdict is CONDITIONAL, as the reader said, but for a sharper reason: it is CONDITIONAL on a runtime-controlled, out-of-sample, repeated-seed reproduction rather than merely on benchmark realism.","tokens_in":10219,"tokens_out":1731,"duration_ms":15844,"concrete_test":"Rerun the comparison of the five best MCTS configurations (Types 4.1, 4.2, 5.1-5.6) against the OR-Tools CP model on the 20 instances with (i) an explicit matched wall-clock time limit per instance (e.g., 1,800 seconds each) rather than only MCTS repetition counts, and (ii) at least 5 MCTS seeds per configuration per instance to report mean and standard error. Additionally, split the 20 instances into configuration-selection (10) and evaluation (10) subsets, or use nested cross-validation, so the Table 2 means and Figure 6 profile are computed on instances not used for choosing the configurations. If the gap shrinks to within one standard error or reverses under matched budgets, the central claim should be weakened to 'MCTS is competitive with CP on these instances'.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The headline claim is that MCTS outperforms the paper's OR-Tools CP model on large-scale JSSP. The load-bearing premise is that a fair computational budget governed both methods, so the comparison reflects schedule quality rather than unequal runtime. The paper never states runtimes, iteration counts per instance, or per-run variance for the stochastic MCTS. The CP model (Section 3.5) is described as 'more sophisticated and involves a longer computational process than PDRs', yet the reader is given no runtime evidence that CP was given comparable or even reasonable effort. Compounding this, the best MCTS configurations were chosen on the same 20 instances used for the final performance profile (Type 4.1, 4.2, 5.1-5.6, selected in Figures 4-5), so the reported mean in Table 2 is optimism on the training set. Because MCTS is randomized, the absence of standard errors or repeated-seed statistics means the 1.54 vs 1.71 mean gap could be noise, and the '50%/40%/10% best-instance' split in Figure 6 could shift materially. The concern is experimental validity, not internal inconsistency; the synthetic-benchmark representativeness flagged by the reader is real but secondary, since the claim is about the benchmark class. The single most load-bearing check is a runtime-controlled, repeated-seed comparison with a holdout instance split; if the MCTS advantage persists under matched budgets and out-of-sample configurations, the central claim stands.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes several Markov Decision Process (MDP) formulations for solving large-scale job shop scheduling problems (JSSP) with Monte Carlo Tree Search (MCTS), targeting the minimization of the weighted sum of job completion times. It introduces a synthetic benchmark generated from characteristics of an anonymized real-world factory instance and compares a set of MCTS configurations against a single OR-Tools constraint programming model on 20 generated instances. The authors report that some MCTS configurations, particularly those using a relative state representation with idle-gap insertion, achieve lower mean weighted completion times than the CP model, and conclude that MCTS is a promising approach for large-scale JSSPs.","tokens_in":10592,"tokens_out":6177,"duration_ms":53778,"significance":"If the empirical claims were robustly supported, the paper would make a useful contribution: the systematic comparison of MDP formulations for MCTS in scheduling is not common, and the idle-gap insertion mechanism in the relative representation is an interesting idea. The synthetic benchmark is a concrete, reusable artifact (the authors provide a GitHub link). However, the current evidence is not sufficient to support the abstract's claim: the comparison lacks matched computational budgets, repeated-run statistics, out-of-sample validation, and even consistency between the CP objective and the stated weighted objective. The paper's value is therefore more in the formulation inventory and benchmark than in the demonstrated advantage over CP.","major_comments":[{"comment":"The CP model minimizes the unweighted total completion time (\"min sum over terminal operations of end_i\"), while the paper's stated objective (Section 2) and the MCTS reward (Section 3.3) minimize the weighted sum \\sum_j w_j C_j. If the benchmark instances have non-uniform weights, the CP baseline is optimizing a different objective, which would invalidate the comparison in Table 2. The authors must either incorporate the weights into the CP objective or explicitly state that all w_j are equal.","section":"Section 3.5"},{"comment":"The experimental comparison does not report any runtime, iteration budget, or time limit for either the MCTS variants or the OR-Tools CP model. Since Section 3.5 describes CP as 'more sophisticated and involves a longer computational process' and MCTS is given only an unexplained 'six repetition steps and 30 evaluations,' the reader cannot tell whether the lower mean values in Table 2 reflect better solution quality or simply more computation. A runtime-controlled comparison is necessary to support the claim that MCTS outperforms the CP approach.","section":"Sections 5.1 and 5.2, Table 2"},{"comment":"The best configurations within each type are selected by inspecting performance profiles on the same 20 instances that are later used for the final comparison in Figure 6 and Table 2. This in-sample selection makes the reported advantage of Types 4 and 5 over CP optimistically biased. The authors should validate configuration choices on a holdout set (e.g., a train/test split of the 20 instances or additional generated instances).","section":"Section 5.2, Figures 4-6"},{"comment":"MCTS is a stochastic algorithm (random tie-breaking in UCB, random simulation policy), yet Table 2 reports a single mean per configuration without standard errors or number of seeds. Differences such as 1.5415 vs 1.5532 may be within noise; even the 1.54 vs 1.71 gap should be accompanied by variance estimates or confidence intervals to be interpretable.","section":"Sections 5.1 and 5.2, Table 2"},{"comment":"The new benchmark is generated from one anonymized instance and depends on hand-set parameters (600-1000 jobs, 50-70 machines, Gaussian processing times, common/unique job types). No evidence is given that these parameters reproduce the structural features that make real large-scale job shops hard, and no comparison is made with existing benchmarks such as Taillard. The paper's scope claim should be restricted to this synthetic benchmark class, or the generation process should be validated against additional real instances.","section":"Section 4"}],"minor_comments":[{"comment":"The text states 'Configurations 5.6 and 5.7 outperform the other configurations,' but Table 1 lists Type 5.6 as the last Type 5 configuration; there is no Type 5.7.","section":"Section 5.2"},{"comment":"In the third action type, the formal definition uses PDR(\\bar J) but the explanatory text says 'where \\bar O is the set of operations'; this is inconsistent.","section":"Section 3.3"},{"comment":"The terms 'six repetition steps' and '30 evaluations' are not defined; please explain what these parameters control and how they relate to the standard MCTS iteration count.","section":"Section 5.1"},{"comment":"Typo: 'as been applied' should be 'has been applied'.","section":"Section 1"},{"comment":"The performance profile curves are not labeled; add a legend or direct labels to make the figures interpretable.","section":"Figures 2-6"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for the journal, but the experimental section needs substantial strengthening. In particular, the CP baseline appears to optimize the wrong objective, and the missing runtimes and variance estimates make the headline claim unsupported. The benchmark release is a positive feature. I would encourage the editor to require a runtime-controlled, repeated-seed comparison with a holdout configuration split before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a solid but incremental study of MCTS for large-scale job shop scheduling. The genuinely useful pieces are: a systematic comparison of five MDP formulations (two state representations, four action types) and a new synthetic benchmark derived from anonymized factory data that includes recirculation and unbalanced workloads, which addresses a real gap in the literature. The relative state representation with idle-gap insertion (Types 4 and 5) appears to help, and the authors are honest about Type 3 being computationally infeasible.\n\nThe main claim, though, is weaker than the abstract suggests. The reported advantage over OR-Tools CP may be a budget artifact: no runtimes are given for either method, and the CP model is described as \"more sophisticated\" yet we don't know how long it was allowed to run. MCTS is stochastic, but there are no error bars or repeated-seed statistics; \"six repetition steps and 30 evaluations\" is not enough to assess variance. The 1.54 vs 1.71 mean gap could shift with more runs.\n\nA second concern: the best configurations were selected on the same 20 instances used for the final performance profile. That makes the Table 2 means optimistic. A holdout split or cross-validation would fix this.\n\nAlso, the only baseline is a single CP model. It would help to include simple PDRs or a well-known metaheuristic to anchor the results, especially since the CP model is itself guided by the LWR rule.\n\nThe synthetic benchmark representativeness is a real but secondary issue, since the claim is about performance on this benchmark class.\n\nNone of these are internal contradictions—the paper is clearly written and the method descriptions are precise. It just needs more careful experimentation before the headline conclusion can be trusted.\n\nI'd send this to peer review, but with a request for major revision: report runtimes and variance, add a holdout scheme, and consider a stronger baseline set. If the MCTS advantage persists under matched budgets and out-of-sample configuration selection, the central claim will stand.","headline":"Useful MDP taxonomy and new benchmark, but the headline MCTS-vs-CP result lacks runtimes, error bars, and an out-of-sample configuration selection, so it is not yet convincing.","tokens_in":11033,"tokens_out":2921,"would_cite":false,"duration_ms":29153,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","68T20"],"pacs":[],"model":"deepseek-v4-flash","headline":"MCTS beats constraint programming on large job-shop instances","keywords":["job shop scheduling","Monte Carlo tree search","constraint programming","Markov decision process","weighted completion time","recirculation","synthetic benchmark","priority dispatching rules"],"falsifier":"Run the best MCTS configurations, for instance Types 4.1 and 5.5, and the OR-Tools constraint programming model on the original 51-machine, 828-job factory instance, or on fresh instances from the same generator with new random seeds, under identical time limits; if the constraint programming model's mean weighted completion time is lower, the paper's central claim collapses.","tokens_in":9970,"feed_emoji":"🏭","tokens_out":5653,"duration_ms":53106,"temperature":0.7,"pith_summary":"The paper is trying to establish that Monte Carlo Tree Search, a reinforcement-learning search heuristic, is a viable alternative to exact constraint programming for industrial-scale job shop scheduling with recirculation and unbalanced machine loads, under the weighted-completion-time objective. It proposes several Markov Decision Process formulations that differ in state representation (absolute versus relative), action granularity (operation versus whole job), and the dispatching rules used to select candidates, and tests them on a new synthetic benchmark generated from the size and workload statistics of one real factory instance. The reported result is that MCTS configurations using the relative representation with idle-gap insertion outperform the OR-Tools constraint programming model in mean objective on the 20 generated large instances. This would matter because exact methods scale poorly and existing benchmarks are too small and rectangular to reflect real production environments.","feed_headline":"MCTS beats constraint programming on large job shops","feed_subtitle":"Relative state representation with idle-gap insertion lowers weighted completion times across 20 large instances.","key_machinery":"The mechanism that carries the argument is the MDP formulation of schedule construction together with the relative state representation. In that representation a state records only the order of operations on each machine, not their scheduled times, so an action, choose a job by a priority dispatching rule and a percentage p, can insert the job's operations into an idle gap of at least p times the operation's processing time, even when the gap is shorter than the operation, and later operations are shifted to make it fit. The search itself is driven by UCB node selection with a normalized terminal reward of negative weighted completion time, and a final step that re-roots the search at the best current-depth node. This design lets MCTS explore the trade-off between greedily filling machines and preserving flexibility in completion times.","core_discovery":"The paper's central claim is that Monte Carlo Tree Search can produce better large-scale job-shop schedules than a standard constraint programming solver when the objective is the weighted sum of job completion times. Specifically, the authors report that MCTS environments with a relative state representation, where a state is the order of operations on each machine rather than their absolute completion times, combined with job-level actions that insert all operations of a chosen job into an idle gap of controllable minimum size, achieve lower mean weighted completion times than the OR-Tools constraint programming model on 20 generated instances with 600 to 1000 jobs and 50 to 70 machines. The paper attributes the gain to a less greedy, more flexible construction process: because timing is not fixed during search, operations can be backfilled into idle periods shorter than their processing time, and all later operations shift accordingly. MCTS with the absolute representation or with operation-level actions performs worse, and one environment type, single-operation selection with idle-gap percentage, had to be abandoned because recomputing completion times at every step was too expensive.","pith_inferences":["Editorial: if the benchmark generator truly mirrors factory data, the result suggests MCTS could be embedded in day-to-day scheduling software as a fast re-scheduling heuristic, a use case exact methods cannot serve at this scale.","Editorial: the relative-state formulation with gap insertion is essentially searching over left-shifted schedules; coupling it with a learned value network, the paper's own suggested future direction, could reduce the number of simulations needed.","Editorial: the comparison is only against one constraint programming configuration with one search heuristic and fixed time budgets; under additional constraints such as setups, deadlines, or machine eligibility, the relative ranking could change.","Editorial: a direct test on the original 51-machine, 828-job factory instance would tell whether the synthetic benchmark overstates or understates the MCTS advantage."],"forward_implications":["If the reported comparisons hold, MCTS with relative state and idle-gap insertion is a usable heuristic for large non-rectangular job shops where exact constraint programming times out.","The type of dispatching rule, not the gap percentage, is the main performance lever within the successful environments, so tuning effort can focus on the PDR set.","The new synthetic benchmark gives the community a way to compare scheduling methods on instances with recirculation, 600 to 1000 jobs, 50 to 70 machines, and unbalanced workloads.","Operation-level idle-gap insertion is impractical at this scale with the authors' implementation because completion times must be recomputed after every insertion."],"supporting_citations":[{"why":"Supplies the MCTS algorithm's four phases and the UCB selection formula used in every configuration.","marker":"[14]"},{"why":"Provides the OR-Tools constraint programming solver that is the baseline MCTS must beat.","marker":"[17]"},{"why":"Earlier MCTS application to flexible job-shop scheduling whose approach the paper extends to new MDP formulations.","marker":"[12]"},{"why":"Taillard benchmarks represent the kind of small rectangular instances the new benchmark is designed to supersede.","marker":"[11]"},{"why":"Further standard benchmark instances that motivate the need for a large non-rectangular test set.","marker":"[16]"},{"why":"Source of the shifting bottleneck heuristic and classic small benchmark instances used as comparison context.","marker":"[2]"},{"why":"Defines the priority dispatching rules used as the action set for MCTS selection.","marker":"[15]"}],"fun_headline_variants":["MCTS with relative state representation wins on large job shops","MCTS beats CP on 600–1000 job shops via idle-gap insertion","Large job shops: MCTS beats constraint programming on weighted completion","MCTS uses relative state to outperform CP on large-scale JSSP","Idle-gap MCTS tops OR-Tools CP on 20 large job shop instances"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole comparison rests on the 20 synthetic instances being representative of the large industrial job shops the conclusion is about, since they are built from the size and workload statistics of a single anonymized factory.","fun_headline_variants_meta":{"raw":{"variants":["MCTS with relative state representation wins on large job shops","MCTS beats CP on 600–1000 job shops via idle-gap insertion","Large job shops: MCTS beats constraint programming on weighted completion","MCTS uses relative state to outperform CP on large-scale JSSP","Idle-gap MCTS tops OR-Tools CP on 20 large job shop instances"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000757,"raw_usage":{"total_tokens":3339,"prompt_tokens":896,"completion_tokens":2443,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":512,"completion_tokens_details":{"reasoning_tokens":2345}},"tokens_in":512,"tokens_out":2443,"duration_ms":17563,"temperature":1.0,"reasoning_tokens":2345,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T04:26:09.172650+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the best MCTS configurations, for instance Types 4.1 and 5.5, and the OR-Tools constraint programming model on the original 51-machine, 828-job factory instance, or on fresh instances from the same generator with new random seeds, under identical time limits; if the constraint programming model's mean weighted completion time is lower, the paper's central claim collapses.","supporting_citations":[{"cited_title":"A survey of monte carlo tree search methods","cited_arxiv_id":null,"evidence_quote":"Supplies the MCTS algorithm's four phases and the UCB selection formula used in every configuration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the OR-Tools constraint programming solver that is the baseline MCTS must beat."},{"cited_title":"A monte-carlo tree search algorithm for the flexible job-shop scheduling in manufacturing systems","cited_arxiv_id":null,"evidence_quote":"Earlier MCTS application to flexible job-shop scheduling whose approach the paper extends to new MDP formulations."},{"cited_title":"Benchmarks for basic scheduling problems","cited_arxiv_id":null,"evidence_quote":"Taillard benchmarks represent the kind of small rectangular instances the new benchmark is designed to supersede."},{"cited_title":"Benchmarks for shop scheduling problems","cited_arxiv_id":null,"evidence_quote":"Further standard benchmark instances that motivate the need for a large non-rectangular test set."},{"cited_title":"The shifting bottleneck procedure for job shop scheduling","cited_arxiv_id":null,"evidence_quote":"Source of the shifting bottleneck heuristic and classic small benchmark instances used as comparison context."}],"review_version":1}