Pith. sign in

REVIEW 5 major objections 5 minor 17 references

Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem

T0 review · 5 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read MCTS beats constraint programming on large job-shop instances

desk verdict 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. read the letter →

arxiv 2501.17991 v1 pith:ZM7OHIWB submitted 2025-01-29 cs.AI math.OC

Laurie Boveroux , Damien Ernst , Quentin Louveaux This is my paper · ORCID
classification cs.AImath.OC MSC 90B3568T20
keywords jobshopschedulingMonteCarlotreesearchconstraintprogrammingMarkovdecisionprocessweightedcompletiontimerecirculationsyntheticbenchmarkprioritydispatchingrules
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

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.

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 (5)
  1. [Section 3.5] 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.
  2. [Sections 5.1 and 5.2, Table 2] 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.
  3. [Section 5.2, Figures 4-6] 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).
  4. [Sections 5.1 and 5.2, Table 2] 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.
  5. [Section 4] 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.
minor comments (5)
  1. [Section 5.2] 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.
  2. [Section 3.3] 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.
  3. [Section 5.1] 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.
  4. [Section 1] Typo: 'as been applied' should be 'has been applied'.
  5. [Figures 2-6] The performance profile curves are not labeled; add a legend or direct labels to make the figures interpretable.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the MCTS/CP comparison is self-contained empirical work; configuration selection on the same benchmark is a statistical issue, not definitional circularity.

full rationale

The paper makes no formal derivation claim that could reduce to its own inputs. The central statement is an empirical comparison: MCTS configurations are defined by explicit MDP components (state representation, action space, reward) and evaluated against an independent OR-Tools constraint-programming model. The terminal reward is the negative weighted sum of completion times, i.e. the objective itself, but that is a direct modelling choice, not a hidden equivalence between a predicted quantity and a fitted input. No parameter is fitted to the benchmark results; the MCTS hyperparameters (six repetition steps, 30 backpropagation evaluations, UCB constant) are fixed in Section 5.1 without tuning to the reported means. The claimed advantage of Types 4 and 5 over CP comes from a construction heuristic plus idle-gap insertion, and the comparison is fully stated in the paper. The only internal-selection concern is that the best MCTS configurations are identified from performance profiles on the same 20 generated instances (Figures 4 and 5) and then reported as the final comparison in Table 2 and Figure 6; this is in-sample model selection, which can inflate apparent performance, but it is not circularity because the winning configuration's value is not equal by construction to the criterion used to select it. Likewise, the new synthetic benchmark derived from one anonymized factory instance affects external validity and representativeness, not the logical independence of the experimental comparison. There are no self-citations to prior work of Boveroux, Ernst, or Louveaux, no imported uniqueness theorem, and no ansatz smuggled in via citation. The paper is self-contained against its own stated baselines, so the honest finding is no significant circularity.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim rests on manually chosen MCTS hyperparameters (C, search budget, percentages, PDR sets) and on benchmark representativeness assumptions. None of these are fitted to the final result, so circularity is low, but the parameter choices are not justified by sensitivity analysis.

free parameters (5)
  • MCTS exploration constant C = not reported
    Controls the UCB exploration-exploitation trade-off in Equation 1; affects tree shape and solution quality, chosen by hand.
  • MCTS search budget = 6 repetition steps and 30 evaluations
    Stopping and convergence parameters in Section 5.1; selected without sensitivity analysis.
  • Idle-gap percentage p = sets {0.3, 0.6, 0.8} and {0.6, 0.8, 1.0}
    Action types 3 and 4 schedule operations in idle time based on p (Section 3.3, Table 1); values chosen by hand.
  • PDR set per environment = e.g. {FIFO, LWR, MWR}, {LWF, MWF}, etc.
    Each Type 1, 2, 4, and 5 configuration chooses a small set of dispatching rules; the choice changes the action space and is manually specified in Table 1.
  • Benchmark size and workload parameters = jobs U(600,1000), machines U(50,70), Gaussian parameters from original instance
    Section 4 generation rules define the instances; representativeness is assumed, not validated.
assumptions (4)
  • domain assumption MCTS with a random default policy and 30 evaluation rollouts gives stable estimates of schedule quality.
    Section 3.2 and 5.1; if rollouts are too few, node values are noisy and the UCB selection is unreliable.
  • domain assumption The OR-Tools CP-SAT model with LWR search guidance is an appropriate baseline for a good-quality comparison.
    Section 3.5 and 5.1; if the CP baseline is weak or under-resourced, the MCTS advantage is not meaningful.
  • domain assumption The synthetic benchmark generated from one anonymized factory instance represents the target class of large-scale industrial job shops.
    Section 4; the central claim of practical value depends on this representativeness.
  • domain assumption The relative state representation with idle-gap insertion can always be realized by shifting operations when needed.
    Section 3.3 Types 3 and 4; the flexibility claim assumes no infeasibility is hidden by the representation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem." pith.science (2026). https://pith.science/paper/ZM7OHIWB

@misc{pith2026250117991,
  author       = {Pith},
  title        = {Pith review of: Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZM7OHIWB}},
  note         = {Machine review of arXiv:2501.17991}
}
read the original abstract

The Job Shop Scheduling Problem (JSSP) is a well-known optimization problem in manufacturing, where the goal is to determine the optimal sequence of jobs across different machines to minimize a given objective. In this work, we focus on minimising the weighted sum of job completion times. We explore the potential of Monte Carlo Tree Search (MCTS), a heuristic-based reinforcement learning technique, to solve large-scale JSSPs, especially those with recirculation. We propose several Markov Decision Process (MDP) formulations to model the JSSP for the MCTS algorithm. In addition, we introduce a new synthetic benchmark derived from real manufacturing data, which captures the complexity of large, non-rectangular instances often encountered in practice. Our experimental results show that MCTS effectively produces good-quality solutions for large-scale JSSP instances, outperforming our constraint programming approach.

Figures

Figures reproduced from arXiv: 2501.17991 by the authors.

Figure 1
Figure 1. The four fundamental steps of the MCTS algorithm and the addi [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Performance profiles of the configurations of Type 1. [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Performance profiles of the configurations of Type 2. [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performance profiles of configurations of Type 4. [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]
Figure 5
Figure 5. Figure 5: Performance profiles of the configurations of Type 5. [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: Performance profiles comparing the best-performing configuration [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages

  1. [1]

    Modeling and solving scheduling problems in practice

    Michael L Pinedo. Modeling and solving scheduling problems in practice. Scheduling: Theory, Algorithms, and Systems , pages 431–458, 2012

    work page 2012

  2. [2]

    The shifting bottleneck procedure for job shop scheduling

    Joseph Adams, Egon Balas, and Daniel Zawack. The shifting bottleneck procedure for job shop scheduling. Management science, 34(3):391–401, 21 1988

    work page 1988

  3. [3]

    The one-machine sequencing problem

    Jacques Carlier. The one-machine sequencing problem. European Jour- nal of Operational Research, 11(1):42–47, 1982

    work page 1982

  4. [4]

    Gelatt, and M

    Scott Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science (New York, N.Y.) , 220:671–80, 06 1983

    work page 1983

  5. [5]

    Rutenbar

    R.A. Rutenbar. Simulated annealing algorithms: an overview. IEEE Circuits and Devices Magazine , 5(1):19–26, 1989

    work page 1989

  6. [6]

    Applying tabu search to the job- shop scheduling problem

    Mauro Dell’Amico and Marco Trubian. Applying tabu search to the job- shop scheduling problem. Annals of Operations Research , 41:231–252, 09 1993

    work page 1993

  7. [7]

    Nowicki and C

    E. Nowicki and C. Smutnicki. A fast taboo search algorithm for the job shop problem. Management Science, 42(6):797–813, 1996

    work page 1996

  8. [8]

    An advanced tabu search algorithm for the job shop problem

    Eugeniusz Nowicki and Czes law Smutnicki. An advanced tabu search algorithm for the job shop problem. Journal of Scheduling , 8:145–159, 04 2005

    work page 2005

Show all 17 references
  1. [9]

    Learning to dispatch for job shop scheduling via deep rein- forcement learning

    Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep rein- forcement learning. Advances in neural information processing systems , 33:1621–1632, 2020

    2020

  2. [10]

    Mastering the game of go with deep neural networks and tree search

    David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016

    2016

  3. [11]

    Benchmarks for basic scheduling problems

    Eric Taillard. Benchmarks for basic scheduling problems. european journal of operational research, 64(2):278–285, 1993

    1993

  4. [12]

    A monte-carlo tree search algorithm for the flexible job-shop scheduling in manufacturing systems

    M Saqlain, S Ali, and JY Lee. A monte-carlo tree search algorithm for the flexible job-shop scheduling in manufacturing systems. Flexible Services and Manufacturing Journal , 35(2):548–571, 2023

    2023

  5. [13]

    A new mcts-based algorithm for multi-objective flexible job shop scheduling problem

    Jen-Jai Chou, Chao-Chin Liang, Hung-Chun Wu, I-Chen Wu, and Tung- Ying Wu. A new mcts-based algorithm for multi-objective flexible job shop scheduling problem. In 2015 Conference on technologies and ap- plications of artificial intelligence (TAAI) , pages 136–141. IEEE, 2015. 22

    2015

  6. [14]

    A survey of monte carlo tree search methods

    Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intel- ligence and AI ...

    2012

  7. [15]

    Job shop scheduling benchmark: Environments and instances for learning and non-learning methods

    Robbert Reijnen, Kjell van Straaten, Zaharah Bukhsh, and Yingqian Zhang. Job shop scheduling benchmark: Environments and instances for learning and non-learning methods. arXiv preprint arXiv:2308.12794 , 2023

    2023 arXiv

  8. [16]

    Benchmarks for shop scheduling problems

    Ebru Demirkol, Sanjay Mehta, and Reha Uzsoy. Benchmarks for shop scheduling problems. European Journal of Operational Research , 109(1):137–141, 1998

    1998

  9. [17]

    Laurent Perron and Fr´ ed´ eric Didier. Cp-sat. 23

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.