Organizations: Information and Communications Technology Cluster, Singapore Institute of Technology, Singapore 138683 · Department of Electrical and Computer Engineering, National University of Singapore, Singapore 119077 · School of Information and Communication Engineering, Dalian University of Technology, Dalian, Liaoning Province, China, 116024 · College of Smart Energy, Shanghai Jiao Tong University, Shanghai, China, 200240
The Flexible Job-Shop Scheduling Problem (FJSP) is a fundamental and challenging optimization problem in smart manufacturing. Although recent deep reinforcement learning (DRL) approaches can learn effective scheduling policies through interaction with the environment, their performance often degrades as problem scale and processing-time uncertainty increase. In this paper, we propose DredRL, a dual representation enhanced diffusion-policy reinforcement learning scheduler. DredRL first constructs enhanced dual representations of operations and machines through self- and cross-attention mechanisms to capture both intra-entity and inter-entity dependencies. A diffusion model is further employed as the policy network, generating scheduling decisions through iterative denoising conditioned on the encoded state to enhance policy expressiveness and robustness. Extensive experiments on synthetic, public, large-scale, and stochastic FJSP benchmarks demonstrate that DredRL outperforms state-of-the-art learning-based schedulers across most configurations. Compared with SOTA learning-based methods, DredRL reduces makespan by up to 5.44% on synthetic instances. It also achieves the best learning-based performance on three of four public benchmarks and outperforms the stochasticity-aware algorithms on stochastic benchmarks. These results demonstrate that combining enhanced dual representations with diffusion-based policies provides an effective and robust approach for large scale scalable FJSP scheduling in complicated environment.
Figures & tables
Fig. 1: Overall system architecture of the proposed DredRL scheduler for FJSP. Raw operation, machine, and operation–machine pairing features are encoded by a dual-representation module to form the state embedding s . A diffusion-policy RL agent then samples an action distribution πθ(s) and selects compatible pairs for task assignment. The FJSP environment executes the assignment, computes reward r , updates status, and feeds back new raw features for the next decision step.
Fig. 2: Dual-representation encoder with self- and cross-attention blocks. Raw operation (Op) and machine (M) features are linearly projected and processed via masked dot-product attention, followed by mean pooling and ELU to derive embeddings.
Size
HGNN [ 7 ]
DANIEL [ 8 ]
DredRL (Ours)
OR-Tools
Greedy
Sampling
Greedy
Sampling
Greedy
Sampling
SD1
10×5
Makespan
111.67
105.59
106.71
101.67
106.24
9 9.79
96.32
Gap
15.94%
9.62%
10.79%
5.55%
10.30%
3 .60%
-
20×5
Makespan
211.22
207.53
197.56
1 92.78
197.86
193.45
188.15
Gap
12.26%
10.3%
5.01%
2 .46%
5.16%
2.82%
-
15×10
Makespan
166.92
161.28
160.86
153.22
160.54
1 52.86
143.53
TABLE I: Performance comparison of different algorithms on synthetic datasets SD1 and SD2 with different instance sizes. Results are included with makespan and corresponding relative gap (%) to OT-Tools.
Public Benchmarks
HGNN [ 7 ]
DANIEL [ 8 ]
DredRL (Ours)
OR-Tools
Greedy
Sampling
Greedy
Sampling
Greedy
Sampling
mk
Makespan
201.4
190.3
185.7
180.8
182.8
1 78.1
174.2
Gap
15.61%
9.41%
6.60%
3.79%
4.94%
2 .24%
-
la
rdata
Makespan
1030.83
985.3
1031.63
9 78.28
1026.6
979.9
935.8
Gap
10.15%
5.29%
10.24%
4 .54%
9.70%
4.71%
-
edata
Makespan
1187.48
1116.68
1194.98
1122.6
1164.8
1 106.7
1028.9
TABLE II: Performance comparison of different algorithms on public benchmarks.
Size
DANIEL [ 8 ]
SPM-DAN [ 10 ]
DredRL (Ours)
OR-Tools
Greedy
Sampling
Greedy
Sampling
Greedy
Sampling
CP-SAT
CP-Stoch [ 10 ]
SD3
10×5
Makespan
722.77
688.74
710.63
677.24
712.30
6 76.74
688.10
676.19
Gap
5.04%
0.09%
3.27%
-1.58%
3.52%
- 1.65%
-
-1.73%
20×5
Makespan
1307.48
1272.08
1279.70
1243.75
1276.49
1 236.30
1253.67
1271.71
Gap
4.29%
1.47%
2.08%
-0.79%
1.82%
- 1.39%
-
1.44%
15×10
Makespan
1111.55
1066.60
1090.92
1039.73
1091.03
1 039.59
1074.88
1105.90
TABLE III: Performance comparison of different algorithms on synthetic datasets SD3 with Different Instance Sizes.
Fig. 3: Comparison of relative makespan gaps to the OR-Tools reference on SD2 across different problem sizes.
The Flexible Job Shop Scheduling Problem (FJSP) is the optimal allocation of a set of jobs to machines. Two primary challenges persist in FJSP: the unpredictable arrival of future jobs and the combinatorial complexity of the problem, rendering it intractable for conventional mixed-integer linear programming solvers. This paper proposes an event-based \gls{DRL} approach to solve FJSP with random job arrivals. Specifically, we employ the Proximal Policy Optimization algorithm and use lightweight Multi-Layer Perceptrons to train the \gls{DRL} agent for minimizing the total completion time of all jobs. We design the state representation to be directly accessible from the environment, and limit the learning agent to selecting from among a set of well-established dispatching rules. Simulations show that our \gls{DRL} approach outperforms any of the individual dispatching rules on datasets with varying heterogeneity and job arrival rates. We benchmark our \gls{DRL} against an arrival-triggered mixed-integer linear programming solution and show that our method achieves good performance especially when the datasets are heterogeneous.
Yu Tang, Muhammad Zakwan, Efe Balta +2
Centre for Artificial Intelligence, Zurich University of Applied Sciences, Switzerland · Inspire AG, Zurich, Switzerland · Automatic Control Laboratory, ETH Zurich, Switzerland
Neural approaches to the Flexible Job Shop Scheduling Problem (FJSP), particularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely on complex feature-engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FJSP, we introduce ReSched, a minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formulation of FJSP, we condense the state space to just four essential features, eliminating historical dependencies through a subproblem-based perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that ReSched outperforms classical dispatching rules and state-of-the-art DRL methods on FJSP. Moreover, ReSched also generalizes well to the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.
Xiangjie Xiao, Cong Zhang, Wen Song +1
School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Marine Science and Technology, Shandong University, China
The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.
Jiaqi Wang, Zhiguang Cao, Peng Zhao +4
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University +2