Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917906605932544 |
|---|---|
| author | Boveroux, Laurie Ernst, Damien Louveaux, Quentin |
| author_facet | Boveroux, Laurie Ernst, Damien Louveaux, Quentin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17991 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem Boveroux, Laurie Ernst, Damien Louveaux, Quentin Artificial Intelligence Optimization and Control F.2.2 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. |
| title | Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem |
| topic | Artificial Intelligence Optimization and Control F.2.2 |
| url | https://arxiv.org/abs/2501.17991 |