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

Boveroux Laurie, Ernst Damien, Louveaux Quentin · 2025

Read Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem by Boveroux Laurie, Ernst Damien, Louveaux Quentin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17991.txt.

Introduction

Laurie Boveroux, Damien Ernst, and Quentin Louveaux wrote a research paper in two thousand twenty-five on scheduling work in factories. The problem asks how to order jobs on machines so the weighted sum of finish times stays low. The authors test Monte Carlo Tree Search, a search method linked to learning from trial and reward.

Inside, they set up several ways to frame the task for the method, including cases where jobs loop back to machines. They also build a new test set from real factory data, with large shapes that are not simple grids. Tests show the method gave good plans for large cases and beat their constraint programming approach.

Catalog record

CREATORBoveroux Laurie, Ernst Damien, Louveaux Quentin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem Boveroux Laurie, Ernst Damien, Louveaux Quentin Abstract 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. 1 Introduction The Job Shop Scheduling Problem (JSSP) is a complex challenge faced by manufacturers. The JSSP involves determining the optimal sequence of jobs on different machines to ensure that production processes are carried out efficiently. This problem is important because it directly impacts a company’s productivity, operating costs and ability to meet delivery schedules. For example, delays in the production schedule can cause bottlenecks, higher inventory costs, and missed deadlines. These issues can lead to unhappy customers and financial penalties. Therefore, optimizing job scheduling is a practical need and a decisive strategy for success. Many mathematical programming-based approaches exist to solve the JSSP, such as mixed-integer linear programming and constraint programming. These methods are exact as they find optimal solutions by exhaustively exploring the search space. However, they have limitations in practice. The JSSP is known to be NP-hard. As the number of jobs and machines increases, the complexity of the problem grows exponentially. In practice, scheduling problems are often large-scale, dynamic and imbalanced. In such scenarios, some machines may be heavily loaded while others are idle and processing times of the tasks can vary widely from a few units of time to several hundreds units. In large-scale environments, exact methods often become impractical. To address these limitations, approximate solutions have been developed. Commonly used heuristics are Priority Dispatching Rules (PDRs) [ 1 ] . PDRs are simple heuristics that select the next operation to be scheduled based on a specific criterion. These rules are easy to implement and computationally efficient, but they often offer low-quality solutions. Another well-known heuristic approach is the Shifting Bottleneck Heuristic [ 2 ] . This procedure solves the problem by iteratively identifying the machine that creates a bottleneck and solving the schedule optimally on that unique machine using the one-machine schedule method by Carlier [ 3 ] . Different meta-heuristic approaches such as simulated annealing, tabu search and genetic algorithms have been used to produce good quality solutions for the JSSP. Simulated annealing [ 4 ] , an optimisation algorithm inspired by the process of physical annealing [ 5 ] , starts with an initial solution and iteratively refines it by making small random changes. The algorithm evaluates the modified solution and accepts improvements. However, it can also accept worse solutions with a probability that decreases over time, allowing the algorithm to escape local optima and explore a wider search space. Tabu search [ 6 , 7 , 8 ] also follows an iterative framework, but uses a deterministic acceptance-rejection criterion. The key of this heuristic is a “tabu list” that prevents the algorithm from revisiting previously explored states or undoing recent modifications. By searching the neighbourhood of the current solution and occasionally accepting worse schedules, the algorithm explores different solutions. The tabu list ensures that unnecessary moves leading to revisited states are not allowed, so the algorithm can bypass local optima and explore potentially global solutions. In recent years, learning-based methods have been developed. Techniques such as deep reinforcement learning have been applied to learn scheduling policies. For example, Zhang et al. [ 9 ] proposed a graph neural network model with an actor-critic algorithm to learn effective dispatching rules. One promising approach is the Monte Carlo Tree Search (MCTS) algorithm. MCTS is a heuristic search algorithm that combines tree search with random sampling to find solutions in large search spaces. Initially applied to the game domain, this reinforcement learning (RL) algorithm has shown its effectiveness in finding good strategies for complex games such as chess and Go [ 10 ] . The JSSP shares similarities with these games, as both involve making sequential decisions and optimizing outcomes based on a series of actions. More specifically, we note that MCTS algorithm as been applied successfully to solve Markov Decision, which suggests their applicability to JSSP as they can be effectively framed as a Markov Decision Process (MDP). States, actions, transition probabilities and rewards define an MDP. Different MDP formulations can be employed to represent the scheduling problems. Existing benchmarks, such as those proposed by Taillard et al. [ 11 ] and Adams et al. [ 2 ] , are commonly used for testing new algorithms. However, these benchmarks are designed for smaller and simplified cases. Such benchmarks do not capture the complexities of real-world scenarios, where machine loads can vary significantly, with some machines heavily loaded while others are idle. These benchmarks are less suitable for evaluating algorithm performance in large-scale industrial scheduling problems. To address this gap, we introduce a new synthetic benchmark derived from real-world manufacturing data that captures the complexity typical of large-scale industrial environments. In this work, we investigate the potential of MCTS in solving the real large-scale JSSP. The main contributions of this work are: 1. We investigate and evaluate different ways to model JSSP as an MDP for the MCTS algorithm. 2. We deliver a new benchmark created from anonymised real-world data 1 1 1 https://github.com/LaurieBvrx/large-scale-complex-JSSP-benchmark.git . The rest of the paper is organized as follows. In Section 2, we formally define the JSSP. Section 3 describes our approach, including how we model JSSP as an MDP for MCTS and the constraint programming model used for comparison. In Section 4, we explain the process of generating a new benchmark from anonymized real-world data. Section 5 presents the experimental setup and results. Finally, Section 6 concludes the paper and outlines directions for future research. 2 Problem Statement We consider the JSSP. In a general JSSP, we are given a set \mathcal{J} of n jobs J_{1},J_{2},...,J_{n} and a set \mathcal{M} of m machines. Each job J_{i}\in\mathcal{J} has an operation set \mathcal{O}_{i} which contains n_{i} operations O_{ij} that must be processed in a specific order (i.e., with precedence constraints). Each operation O_{ij} of job J_{i} requires a processing time p_{ij} on a specific machine M_{(ij)} . A job can have several operations that must be processed on the same machine (i.e., recirculation). Each machine can process at most one operation at a time with no preemption. To solve the JSSP, we must find a schedule that determines the order in which the operations are processed to minimize a specific objective function. The objective most commonly minimized in the literature is the makespan, the maximum completion time of all operations in the schedule. However, this objective does not consider the schedule’s internal

Read the complete text