Evolutionary Strategies with Dual Graph Reinforcement Learning for Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem (FJSP) is a strongly NP-hard combinatorial optimization problem (COP) in the manufacturing field. Traditional methods typically rely on heuristic or exact algorithms to solve FJSP. Recently, an increasing number of studies have explored the integration of graph neural networks (GNN) and reinforcement learning (RL) to solve FJSP. However, existing GNN-RL frameworks often face challenges such as training instability and convergence difficulties, which hinder solution quality. To address these limitations, this paper proposes the evolutionary strategies with dual graph reinforcement learning (ES-DGDRL) approach, which integrates ES into the GNN-RL framework. In the feature representation phase, a dual-graph representation method is introduced to capture relationships between nodes, embedding these into the decision-making model. During training, the policy network parameters are updated with graph embeddings using policy gradient for global refinements. Then ES generates perturbations and iteratively updates the policy network, further enhancing exploration and updating the parameters. Experimental results on five synthetic instances demonstrate that the proposed approach outperforms four traditional baselines. Furthermore, compared with conventional reinforcement learning, ES-DGDRL achieves faster convergence within the same number of episodes.