634. Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
Invited abstract in session TB-12: Emerging trends, challenges and innovations in scheduling and project management, stream Scheduling and Project Management.
Tuesday, 10:30-12:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Laurie Boveroux
|
| Montefiore Institute, University of Liège | |
| 2. | Damien Ernst
|
| SmartGrids, University of Liège | |
| 3. | Quentin Louveaux
|
| Montefiore Institute, Université de Liège |
Abstract
The Job Shop Scheduling Problem (JSSP) is a well-known optimization prob-
lem 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.
Keywords
- Combinatorial Optimization
- Artificial Intelligence
- Industrial Optimization
Status: accepted
Back to the list of papers