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

arXiv: https://arxiv.org/abs/2501.17991 · HTML: https://mlsanity.com/paper/2501.17991/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 17 references that are in the map.
- First posted on arXiv 29 Jan 2025.

## Builds on (most cited first, 1 of 1)

- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)

## Abstract (arXiv)

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.