Organizations: Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University · College of Computer Science and Technology, Jilin University · Nanyang Technological University
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.
Figures & tables
Figure 1: Graph representations of FJSP. (a) FJSP instance in a disjunctive graph; (b) feasible solution in a disjunctive graph; (c) feasible solution in our graph.
Figure 2: Nopt2 neighborhood structure.
Figure 3: The architecture of MIStar .
Figure 4: The network architecture of the memory-enhanced heterogeneou GNN.
Size
Sample
Greedy
100 Iterations
200 Iterations
400 Iterations
OR-Tools 1
DANIEL
HGNN
DANIEL
HGNN
GD
FI
BI
MIStar
GD
FI
BI
MIStar
GD
FI
BI
MIStar
SD1
10×5
Obj.
101.67
105.59
106.76
111.67
100.00
100.91
100.55
100.02
100.00
100.91
100.54
99.88
100.00
100.91
100.53
99.69
96.32(5%)
Gap
5.55%
9.62%
10.84%
15.94%
3.82 %
4.77%
4.39%
3.84%
3.82%
4.77%
4.38%
3.70%
3.82%
4.77%
4.37%
3.50%
Time 2
0.26s
0.44s
0.16s
0.17s
8.13s
12.60s
12.09s
5.64s
16.43s
27.54s
26.21s
11.23s
32.95s
58.71s
54.73s
23.00s
20×5
Obj.
192.78
207.53
197.56
211.22
191.31
191.79
191.36
190.87
191.31
191.79
191.36
190.79
191.31
191.79
191.36
190.67
188.15(0%)
Gap
2.46%
10.30%
5.00%
12.26%
1.68%
1.93%
1.71%
1.45%
1.68%
1.93%
1.71%
1.40%
1.68%
1.93%
1.71%
1.34%
Table 1: Results on small synthetic instances
Size
Sample
Greedy
100 Iterations
200 Iterations
400 Iterations
OR-Tools 1
DANIEL
HGNN
DANIEL
HGNN
GD
FI
BI
MIStar
GD
FI
BI
MIStar
GD
FI
BI
MIStar
SD1
30×10
Obj.
286.77
308.55
288.61
314.71
286.04
286.19
285.95
285.79
286.04
286.19
285.95
285.75
286.04
286.19
285.95
285.68
274.67(6%)
Gap
4.41%
12.33%
5.08%
14.58%
4.14%
4.19%
4.11%
4.05%
4.14%
4.19%
4.11%
4.03%
4.14%
4.19%
4.11%
4.01%
Time 2
5.60s
6.25s
0.97s
0.97s
7.67m
10.51m
10.73m
57.03s
15.32m
22.00m
21.49m
1.83m
30.65m
47.10m
43.11m
3.77m
40×10
Obj.
379.71
410.76
379.28
417.87
379.04
379.05
378.92
378.82
379.04
379.05
378.92
378.76
379.04
379.05
378.92
378.63
365.96(3%)
Gap
3.76%
12.24%
3.64%
14.18%
3.57%
3.58%
3.54%
3.51%
3.57%
3.58%
3.54%
3.50%
3.57%
3.58%
3.54%
3.46%
Table 2: Generalization results on large synthetic instances
Method
mk
la(rdata)
la(edata)
la(vdata)
Obj.
Gap
Time(s)
Obj.
Gap
Time(s)
Obj.
Gap
Time(s)
Obj.
Gap
Time(s)
OR-Tools
174.20
0.99%
1447.08
935.80
0.16%
1397.43
1028.93
0.01%
899.60
919.60
-0.01%
639.17
2SGA
175.20
1.57%
57.60
-
-
812.20 1
0.39%
51.43
DANIEL(S) 2
180.80
4.81%
1.71
984.63
5.39%
1.99
1120.28
8.88%
2.00
934.75
1.64%
2.02
HGNN(S)
192.20
11.42%
1.72
1004.60
7.53%
1.84
1123.10
9.16%
2.44
934.23
1.58%
2.12
DANIEL(G)
184.30
6.84%
0.45
1044.85
11.84%
0.48
1176.40
14.34%
0.48
965.38
4.97%
0.48
Table 3: Results on public benchmarks
Instance Size
Method
Objective
Time (min)
Optimality Gap
50×15
OR-Tools
881.45
60.0
39.05%
(LB:537.2)
MIStar-200
969.7
10.6
44.60%
60×15
OR-Tools
1075.1
60.0
46.94%
(LB:570.2)
MIStar-200
1109.8
14.2
48.62%
100×10
OR-Tools
1922.65
60.0
62.22%
(LB:726.5)
MIStar-200
2138.4
15.9
66.03%
Table 4: Generalization Performance on Larger-Scale Instances
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Infeasible exchange caused by the N5 neighborhood in FJSP. Dotted lines of different colors are critical blocks.
Figure 6: Graph representations in H [ 8 ] . (a) FJSP instance; (b) feasible solution.
The Flexible Job Shop Scheduling Problem (FJSP) originates from real production lines, while some practical constraints are often ignored or idealized in current FJSP studies, among which the limited buffer problem has a particular impact on production efficiency. To this end, we study an extended problem that is closer to practical scenarios--the Flexible Job Shop Scheduling Problem with Limited Buffers and Material Kitting. In recent years, deep reinforcement learning (DRL) has demonstrated considerable potential in scheduling tasks. However, its capacity for state modeling remains limited when handling complex dependencies and long-term constraints. To address this, we leverage a heterogeneous graph network within the DRL framework to model the global state. By constructing efficient message passing among machines, operations, and buffers, the network focuses on avoiding decisions that may cause frequent pallet changes during long-sequence scheduling, thereby helping improve buffer utilization and overall decision quality. Experimental results on both synthetic and real production line datasets show that the proposed method outperforms traditional heuristics and advanced DRL methods in terms of makespan and pallet changes, and also achieves a good balance between solution quality and computational cost. Furthermore, a supplementary video is provided to showcase a simulation system that effectively visualizes the progression of the production line.
Shishun Zhang, Juzhan Xu, Yidan Fan +4
National University of Defense Technology · Shenzhen University · Institute of AI for Industries, Chinese Academy of Sciences
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 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