Enhancing Graph Reconstruction: Uniting Dual-Level Graph Structure With Graph Reinforcement Learning.

Area of Science:

• Artificial Intelligence
• Operations Research
• Machine Learning

Background:

• Combinatorial optimization is often treated as a 1-D sorting problem, losing valuable information through dimension compression.
• Conventional reinforcement learning (RL) using convolutional neural networks (CNNs) struggles to capture relational information in feature matrices for these problems.

Purpose of the Study:

• To address limitations in existing RL approaches for combinatorial optimization.
• To propose a new method for the job shop scheduling problem (JSSP) that overcomes CNN constraints.

Main Methods:

• Re-framed the problem from a graph reconstruction perspective.
• Developed a graph RL (GRL) method integrating a double deep Q-network (DDQN) and a graph attention network (GAT).
• Constructed a dual-level graph representation to learn scheduling features and handle dynamic graphs.

Main Results:

• The proposed GRL method demonstrated improved solution quality compared to traditional deep RL (DRL) algorithms.
• Enhanced generalization performance was observed in the experimental results.
• The dual-level graph representation effectively captured complex scheduling information.

Conclusions:

• The GRL approach offers a significant advancement over CNN-based RL for combinatorial optimization.
• This method provides a more effective way to learn from and solve complex scheduling problems.