Answers are grounded in this paper and cite their sources.
The Job Shop Scheduling Problem (JSSP) is a classical NP-hard combinatorial optimization problem in which minimizing makespan becomes increasingly challenging as problem size increases. Monte Carlo Tree Search (MCTS) has emerged as a promising optimization approach; however, its reliance on random rollouts can produce suboptimal schedules characterized by substantial machine idle time. This study aimed to integrate heuristic dispatching rules into MCTS to improve scheduling performance on the Taillard ta20 benchmark instance, comprising 20 jobs and 15 machines. Two heuristic-guided variants, MCTS + EDD and MCTS + LDD, were developed by incorporating the Giffler–Thompson conflict-set procedure and an ?-greedy selection strategy (? = 0.1). Their performance was compared with that of baseline MCTS using 1,000, 2,000, and 3,000 rollouts, with 10 independent runs per configuration. Performance was evaluated based on average makespan, best makespan, standard deviation, computation time, and schedule feasibility. At 3,000 rollouts, MCTS + EDD and MCTS + LDD reduced average makespan by 15.78% and 20.20%, respectively, relative to the baseline MCTS average of 2,369.40. Both heuristic-guided variants also exhibited lower variability, with standard deviations ranging from 15.12 to 36.91, compared with 41.86 to 58.07 for baseline MCTS. Furthermore, the heuristic-guided methods achieved higher machine utilization rates of 51.39% (EDD) and 54.53% (LDD), compared with 44.40% for baseline MCTS. All best-performing schedules satisfied the evaluated scheduling constraints. These findings demonstrated that incorporating heuristic dispatching rules improved scheduling performance and consistency within the tested configurations. Notably, MCTS + LDD with 1,000 rollouts achieved a lower makespan than baseline MCTS with 3,000 rollouts while requiring less computation time, suggesting that heuristic guidance offered greater performance benefits than increasing the rollout budget alone under the experimental conditions.
No takes yet. Share an insight, caveat, or question.
Firdaus et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: