Learning-Based Approaches for Job Shop Scheduling Problems: A Review
Karima Rihane, Adel Dabah, Abdelhakim AitZai · 2025
Read Learning-Based Approaches for Job Shop Scheduling Problems: A Review by Karima Rihane, Adel Dabah, Abdelhakim AitZai (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-2505-04246.txt.
Introduction
Karima Rihane, Adel Dabah, and Abdelhakim AitZai present a 2025 review of machine learning for job shop scheduling. That classic puzzle asks how to route many jobs through shared machines to finish fast and on time. Exact methods and hand-tuned heuristics have long dominated. Learning-based approaches promise schedulers that improve with experience.
The review collects the main learning models tried so far. It weighs what each gains and where each falls short, including data hunger and weak guarantees beside established methods. It maps how learning has been bolted onto classic solvers as well as used alone. The authors close with research directions meant to make learned schedulers competitive in real factories, not just benchmarks.
Catalog record
| CREATOR | Karima Rihane, Adel Dabah, Abdelhakim AitZai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04246
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning-Based Approaches for Job Shop Scheduling Problems: A Review Karima Rihane, Adel Dabah, Abdelhakim AitZai Abstract Job Shop Scheduling (JSS) is one of the most studied combinatorial optimization problems. It involves scheduling a set of jobs with predefined processing constraints on a set of machines to achieve a desired objective, such as minimizing makespan, tardiness, or flowtime. Since it introduction, JSS has become an attractive research area. Many approaches have been successfully used to address this problem, including exact methods, heuristics, and meta-heuristics. Furthermore, various learning-based approaches have been proposed to solve the JSS problem. However, these approaches are still limited when compared to the more established methods. This paper summarizes and evaluates the most important works in the literature on machine learning approaches for the JSSP. We present models, analyze their benefits and limitations, and propose future research directions. 1 1 1 This paper has been accepted to appear at The International Conference on the Dynamics of Information Systems (DIS 2025) June 1-5, 2025, London, UK. 1 Introduction Scheduling problems are concerned with the allocation of a set of tasks (jobs) to a limited number of resources (machines) under certain constraints to optimize one or more objective functions. One of the most studied scheduling problems in the literature is the classical Job Shop Scheduling Problem (JSSP). This problem, which is among the NP-hard combinatorial optimization problems (COPs) [ 1 ] , has an exponentially increasing search space. JSSP involves scheduling the processing of a finite set of n jobs on a finite set of m machines. Each job consists of n_{i} operations, each representing the processing step of a job on a specific machine for an uninterrupted period. Each machine can handle one operation at a time. The classical objective of the JSSP is to find a schedule that minimizes the completion time of all jobs. JSSP is a decision-making problem that appears in many real-world situations. Therefore, developing efficient algorithms to solve such problems has become an attractive area of research. Over the years, diverse approaches have been used to solve the JSSP. The first attempts to solve it to optimality were based on mixed-integer linear programming and Branch and Bound (B&B) algorithms. However, due to the complex nature of the JSSP, these approaches can only solve small instances and remain inefficient for large problem instances. In this context, heuristics and meta-heuristics have been primarily used. These approaches make a trade-off between the quality of the solution and the time needed to obtain it. In other words, they return an acceptable solution quality in a reasonable time. In the literature, we find the adaptation of many meta-heuristics to solve the JSSP. These include Genetic Algorithms (GA), Tabu Search (TS), Variable Neighborhood Search (VNS), Simulated Annealing (SA), Particle Swarm Optimization (PSO), and hybrid systems that combine heuristics and meta-heuristics. These methods have proven effective in solving the JSSP. However, most real-world problems involve a large number of complex constraints, and adapting these classical approaches is still very challenging. In this context, there is a significant need for more robust and scalable approaches that can efficiently deal with the evolving complexity of real-world problems. One of the most active research areas today is the use of learning-based approaches for solving COPs via a data-driven approach. This helps in tackling the tremendous complexity of modern problems. Machine Learning (ML) is a collection of Artificial Intelligence (AI) techniques that allow computers to learn and improve from data. Depending on how the learning is conducted, three sub-categories of ML can be distinguished: supervised learning, unsupervised learning, and reinforcement learning. In particular, Neural Networks (NN), Reinforcement Learning (RL), and the combination of these two approaches are the new trends in ML for addressing COPs. This paper aims to summarize and analyze the most important contributions of neural networks and reinforcement learning approaches proposed for JSSPs. Furthermore, our study discusses the different techniques used and provides a comparison between them. The remainder of the paper is structured as follows: Section 2 introduces the classical JSSP and the approaches used to solve it. Section 3 describes learning-based approaches used to solve JSSPs, with a particular focus on NN and RL methods. Section 4 discusses and proposes insights on NN and RL models for JSSPs. Finally, conclusions are presented in Section 5 . 2 Preliminaries 2.1 Formulation of the Problem The Job Shop Scheduling Problem is a classical combinatorial optimization problem in scheduling. It consists of determining the optimal time allocation of operations on a finite set of machines while satisfying all problem constraints. The primary objective is to minimize the makespan C_{max} , which represents the maximum completion time of all jobs. Formally, the JSSP has a finite set of n jobs J=\{J_{1},J_{2},...,J_{n}\} that needs to be processed on a finite set of m machines M=\{M_{1},M_{2},...,M_{m}\} . Each job J_{i},i=1,...,n consists of k operations \left\{O_{i1},O_{i2},...,O_{ik}\right\} , k=1...,m , each of them needs to be processed during an uninterrupted period p on a given machine. Each machine can handle at most one operation at a time. Let us consider N the set of all operations N=\{O_{1},O_{2},...,O_{n.m}\} . The objective is to find a schedule (feasible solution) that minimizes the makespan C_{max} , which represents the maximum completion time of all jobs. The mathematical formulation is given as: • t_{i} : Start time of operation O_{i} ; • p_{i} : Processing time of operation O_{i} ; • c_{i} : Completion time of operation O_{i} ; • PC : Set of precedence constraints between operations of the same job; • E_{k} : Set of operations requiring processing on machine M_{k} . The constraints of the JSSP are as follows: \displaystyle$$t_{i}+p_{i}\leq t_{j},\forall(O_{i},O_{j})\in PC$$ (1) \displaystyle$$(t_{j}-t_{i})\geq p_{i}\ or\ (t_{i}-t_{j})\geq p_{j}\forall(O_{i},O_{j})\in E_{k},\forall k=\left\{1...,m\right\}$$ (2) \displaystyle$$t_{i}\geq 0,\forall O_{i}\in N$$ (3) Equation ( 1 ) represents the precedence constraints between the operations of the same job. Equation ( 2 ) enforces the sequencing constraints for operations that require processing on the same machine, ensuring no overlap in their execution times. Equation ( 3 ) indicates the earliest starting time of all operations. The classical objective is to minimize the makespan, C_{\text{max}}=\max\{c_{i}\},\forall i\in\{1,\dots,n\cdot m\} , which represents the maximum completion time of all operations. From a complexity perspective, the JSSP is known to be NP-hard [ 1 ] , implying that the search space grows exponentially with the number of jobs and machines. This computational difficulty requires the use of advanced techniques to efficiently find feasible and near-optimal solutions. The JSSP can also be represented using a disjunctive graph [ 2 ] , a powerful graphical tool for modeling scheduling problems. A disjunctive graph, denoted as G=(V,C,D) , is a mixed graph where: • V represents the set of vertices, with each vertex corresponding to an operation. This includes two dummy vertices, start and end, both with zero processing time. • C is a set of directed arcs (conjunctions) that describe precedence constraints between operations within the same job. • D is a set of undirected edges (disjunctions) connecting pairs of operations that require the same machine, but whose execution order is not yet determined. Consequently, finding a solution to a JSSP instance is equivalent to fixing the direction of each disjunction, such that the