Evolution strategies-based optimized graph reinforcement learning for solving dynamic job shop scheduling problem

The job shop scheduling problem (JSSP) with dynamic events and uncertainty is a strongly NP-hard combinatorial optimization problem (COP) with extensive applications in the manufacturing system. Recently, growing interest has been aroused in utilizing machine learning techniques to solve the JSSP. However, most prior arts cannot handle dynamic events and barely consider uncertainties. To close this gap, this paper proposes a framework to solve a dynamic JSSP (DJSP) with machine breakdown and stochastic processing time based on Graph Neural Network (GNN) and deep reinforcement learning (DRL). To this end, we first formulate the DJSP as a Markov Decision Process (MDP), where disjunctive graph represent the states. Secondly, we propose a GNN-based model to effectively extract the embeddings of the state by considering the features of the dynamic events and the stochasticity of the problem, e.g., the machine breakdown and stochastic processing time. Then, the model constructs solutions by dispatching optimal operations to machines based on the learned embeddings. Notably, we propose to use the evolution strategies (ES) to find optimal policies that are more stable and robust than conventional DRL algorithms. The extensive experiments show that our method substantially outperforms existing reinforcement learning-based and traditional methods on multiple classic benchmarks.