A Novel reinforcement learning framework based on Simplified Graph Transformer for large-scale fuzzy Flexible Job Shop Scheduling Problem

The Large-scale Flexible Job Shop Scheduling Problem (FJSP) is a classic NP-hard problem known for its complex solution space and formidable computational challenges. This paper investigates a more realistic variant of FJSP featuring fuzzy processing times, with the objective of minimizing job completion times. Addressing the inefficiencies of metaheuristic algorithms in solving large-scale FJSP instances, characterized by low efficiency and suboptimal heuristic rules, we propose a novel reinforcement learning (RL) framework called Soft Actor-Critic based simplified graph transformers (SGFormer-SAC) as a fundamental optimization approach for addressing this problem. Firstly, we introduce the use of Graph Transformer to capture the topological structure of the fuzzy disjunctive graph and the long-term dependencies among multiple operations. Secondly, We critically demonstrate that even with a single-layer, single-headed attention mechanism, remarkable competitive performance can be achieved in large-scale disjunctive graph models. This encourages a reconsideration of the design principles behind Transformers. Finally, we reduce the quadratic complexity of the Transformer to linear complexity, significantly improving the training and inference times for large-scale fuzzy FJSP instances. Experimental results demonstrate that our model exhibits strong robustness and generalization across both generated instances and public datasets after a single training session. In generalization experiments, our approach outperforms the optimal scheduling rule (MOPNR+SPT) with an average improvement of 31.23%. For large-scale instances, the inference time does not exceed 5 s, and our model achieves an 11.4% improvement over the state-of-the-art (SOTA) CARL framework on the Beh41-45 (100 × 60) benchmark. Furthermore, analysis of variance (ANOVA) tests confirm the significant effectiveness of our method.