Dynamic Graph-Based Reinforcement Learning for Efficient Scheduling in Large-Scale Flexible Job Shops

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is an NP-hard optimization challenge with significant industrial applications, especially for large-scale instances. Traditional approaches, such as Priority Dispatching Rules (PDRs), often struggle with time-intensive design processes and suboptimal performance as problem size increases. This paper introduces a scalable, dynamic graph-based reinforcement learning framework designed to address large-scale FJSP efficiently. By modeling FJSP as a dynamic graph and filtering out irrelevant operations, our approach reformulates the scheduling task as a Markov decision process (MDP). To capture complex task dependencies and machine constraints, we utilize a Heterogeneous Graph Attention Network (HGAT), while Proximal Policy Optimization (PPO) is employed to drive the reinforcement learning process, dynamically selecting actions that optimize makespan. Additionally, we introduce a multi-action selection strategy to further improve computational efficiency, enabling faster scheduling without compromising solution quality. Preliminary evaluations demonstrate that our method surpasses traditional heuristics and leading algorithms, achieving competitive makespan results and proving its robustness for large-scale scheduling needs. This approach offers a practical, scalable solution for real-world FJSP challenges.