A Deep Reinforcement Learning Approach for FJSP Based on Job-Enhanced Heterogeneous Graph Neural Network
DOI:
https://doi.org/10.70088/hm896m21Keywords:
flexible job shop scheduling, deep reinforcement learning, graph neural network, job node embedding, bilinear interaction, adaptive decision-makingAbstract
The Flexible Job Shop Scheduling Problem (FJSP) is a critical combinatorial optimization problem in modern manufacturing systems, aiming to simultaneously determine optimal machine assignments and operation sequences. Traditional deep reinforcement learning (DRL) methods often face significant challenges in effectively modeling complex global constraints and designing adaptive action selection mechanisms for highly dynamic environments. To address these critical limitations, this paper proposes a novel end-to-end deep reinforcement learning framework based on the Proximal Policy Optimization (PPO) algorithm. By strategically introducing job nodes into the traditional operation-machine heterogeneous graph, the proposed framework constructs an innovative three-type-node heterogeneous graph consisting of jobs, operations, and machines, thereby significantly enhancing its representation ability for intricate scheduling constraints. Furthermore, to address the dynamic nature of the action space inherent in FJSP, the framework adaptively handles variable action dimensions by dynamically generating an interaction matrix via a multi-layer perceptron. It then calculates the priorities of feasible actions using a bilinear inner product, ultimately achieving highly adaptive and efficient decision-making. Extensive experimental results conducted on standard benchmark datasets demonstrate that the proposed framework achieves superior scheduling performance, including substantially reduced makespan and improved computational efficiency, compared to existing state-of-the-art methods. These findings comprehensively validate its effectiveness and robustness in solving complex, large-scale FJSP instances in real-world manufacturing scenarios.References
Q. Zhang, A. Wang, J. Li, L. Zheng, J. Bao, and D. Zhang, "A Production-Logistics prediction method integrating Spatial-Temporal features in flexible production workshop for buffer allocation problem," Computers & Industrial Engineering, vol. 200, p. 110761, 2025.
M. Saidi-Mehrabad and P. Fattahi, "Flexible job shop scheduling with tabu search algorithms," The International Journal of Advanced Manufacturing Technology, vol. 32, nos. 5-6, pp. 563–570, 2007.
G. Zhang, X. Shao, P. Li, and L. Gao, "An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem," Computers & Industrial Engineering, vol. 56, no. 4, pp. 1309–1318, 2009.
R. Chen, B. Yang, S. Li, and S. Wang, "A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem," Computers & Industrial Engineering, vol. 149, p. 106778, 2020.
B. A. Han and J. J. Yang, "Research on adaptive job shop scheduling problems based on dueling double DQN," IEEE Access, vol. 8, pp. 186474–186495, 2020.
X. Wu, X. Yan, D. Guan, and M. Wei, "A deep reinforcement learning model for dynamic job-shop scheduling problem with uncertain processing time," Engineering Applications of Artificial Intelligence, vol. 131, p. 107790, 2024.
K. Lei, P. Guo, W. Zhao, Y. Wang, L. Qian, X. Meng, and L. Tang, "A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem," Expert Systems with Applications, vol. 205, p. 117796, 2022.
J. P. Huang, L. Gao, and X. Y. Li, "An end-to-end deep reinforcement learning method based on graph neural network for distributed job-shop scheduling problem," Expert Systems with Applications, vol. 238, p. 121756, 2024.
W. Song, X. Chen, Q. Li, and Z. Cao, "Flexible job-shop scheduling via graph neural network and deep reinforcement learning," IEEE Transactions on Industrial Informatics, vol. 19, no. 2, pp. 1600–1610, 2023.
E. Yuan, L. Wang, S. Cheng, S. Song, W. Fan, and Y. Li, "Solving flexible job shop scheduling problems via deep reinforcement learning," Expert Systems with Applications, vol. 245, p. 123019, 2024.
R. Wang, G. Wang, J. Sun, F. Deng, and J. Chen, "Flexible job shop scheduling via dual attention network-based reinforcement learning," IEEE Transactions on Neural Networks and Learning Systems, vol. 35, no. 3, pp. 3091–3102, 2023.
K. H. Ho, J. Y. Cheng, J. H. Wu, F. Chiang, Y. C. Chen, Y. Y. Wu, and I. C. Wu, "Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem," IEEE Access, vol. 12, pp. 14703–14718, 2024.
C. Zhang, W. Song, Z. Cao, J. Zhang, P. S. Tan, and X. Chi, "Learning to dispatch for job shop scheduling via deep reinforcement learning," in Advances in Neural Information Processing Systems, vol. 33, pp. 1621–1632, 2020.
P. Brandimarte, "Routing and scheduling in a flexible job shop by tabu search," Annals of Operations Research, vol. 41, no. 3, pp. 157–183, 1993.
J. Hurink, B. Jurisch, and M. Thole, "Tabu search for the job-shop scheduling problem with multi-purpose machines," Operations-Research-Spektrum, vol. 15, no. 4, pp. 205–215, 1994.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Jian Zhang, Yusen Zhao, Cunrui Ying (Author)

This work is licensed under a Creative Commons Attribution 4.0 International License.









