A Reinforcement Learning Control Framework Based on Scalable Graph Transformer for Large-Scale Fuzzy Job Shop Scheduling Problems

The job shop scheduling problem (JSSP) is a classic NP-hard problem. This article focuses on a realistic variant of the JSSP incorporating fuzzy processing times, with the objective of minimizing the maximum completion time. We propose a proximal policy optimization with graph transformer (GT-PPO) algorithm, which leverages proximal policy optimization (PPO) as the foundational framework, to address this problem for the first time. First, the intricate variability in states and actions often leads to suboptimal scheduling outcomes. To address this, we refine the representation of states and actions for improved performance. Second, to overcome inherent limitations of conventional graph neural networks (GNNs)-including difficulty in handling heterogeneity, over-squashing, and limited ability to capture long-range dependencies-we employ a graph transformer (GT) architecture for the first time in this study. These transformers effectively capture both the topological relationships in fuzzy disjunctive graph models and the long-range dependencies in large-scale JSSP instances. Additionally, we also reduce the computational complexity of the GT to $O(n)$ , enabling the agent to derive optimal scheduling solutions for large disjunctive graphs more efficiently, with reduced memory usage. Finally, the testing results demonstrate the strong robustness of our model across various scales of generated instances and public datasets after a single training session. Notably, on large-scale DMU and Taillard public datasets, the model exhibited exceptional robustness, further validating its effectiveness in addressing large-scale fuzzy JSSP.