Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
This work addresses scheduling optimization in manufacturing, but it is incremental as it applies an existing method to a new domain with a synthetic benchmark.
The paper tackled the Job Shop Scheduling Problem by applying Monte Carlo Tree Search to minimize the weighted sum of job completion times, showing that MCTS effectively produces good-quality solutions for large-scale instances and outperforms a constraint programming approach.
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.