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

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• The job shop scheduling problem (JSSP) is a computationally challenging NP-hard problem.
• Realistic JSSP variants often involve uncertainties, such as fuzzy processing times, complicating optimization.
• Existing methods struggle with the heterogeneity and long-range dependencies inherent in large-scale JSSP instances.

Purpose of the Study:

• To address the fuzzy job shop scheduling problem (JSSP) with the objective of minimizing the maximum completion time.
• To propose a novel algorithm, Proximal Policy Optimization with Graph Transformer (GT-PPO), for solving this complex scheduling variant.
• To enhance state and action representations for improved scheduling performance.

Main Methods:

• The study employs Proximal Policy Optimization (PPO) as the core reinforcement learning framework.
• A Graph Transformer (GT) architecture is utilized to capture complex relationships in fuzzy disjunctive graphs and long-range dependencies.
• Computational complexity of the GT is reduced to O(n) for efficient processing of large-scale JSSP instances.

Main Results:

• The proposed GT-PPO algorithm demonstrates strong robustness across various scales of generated and public JSSP instances after a single training session.
• Exceptional robustness was observed on large-scale DMU and Taillard public datasets.
• The algorithm effectively handles fuzzy processing times and optimizes the maximum completion time.

Conclusions:

• The GT-PPO algorithm offers an effective and efficient solution for the large-scale fuzzy job shop scheduling problem.
• The integration of Graph Transformers addresses limitations of conventional Graph Neural Networks in handling JSSP complexities.
• The model's robustness and efficiency pave the way for practical applications in complex scheduling environments.