Abstract: Aiming at the flexible job shop scheduling problem with the goal of minimizing completion time and total energy consumption, an integrated algorithm framework based on graph neural networks and deep reinforcement learning is proposed. Firstly, the characteristics of the flexible job shop scheduling problem are analyzed, and a disjunctive graph is introduced to transform the problem into a sequential decision problem, which is then modeled as a Markov decision process. Secondly, a two-stage scheduling strategy is designed based on attention mechanism, which removes redundant scheduling states during the training process and significantly improves computational efficiency. Finally, a 2S-PPO algorithm based on proximal policy optimization is designed for training the two-stage scheduling strategy, aiming to achieve a joint scheduling strategy that can quickly respond to process selection and machine allocation. Experimental proof through standard FJSP examples and FJSP examples with energy consumption instances demonstrates that the proposed algorithm has better learning performance and generalization performance compared to traditional priority scheduling rules and other deep reinforcement learning algorithms.

Key words: flexible job-shop scheduling problem (FJSP), graph neural network, deep reinforcement learning, attention mechanism

摘要： 针对柔性作业车间调度问题，以完工时间最小化和总能耗为目标，提出了一种基于图神经网络和深度强化学习的集成算法框架。分析了柔性作业车间调度问题特点，引入析取图将问题转化为序列决策问题，并将其建模为马尔可夫决策过程。基于注意力机制，设计了一种两阶段调度策略；该策略在训练过程中删除了冗余的调度状态，提高了计算效率。针对两阶段调度策略设计了一种基于近端策略优化算法的2S-PPO算法进行训练，以快速响应工序选择和机器分配的联合调度策略。通过标准FJSP算例和带能耗的FJSP算例实验证明，提出的算法相较于传统的优先级调度规则和其他深度强化学习算法，具有较好的学习性能和泛化性能。

关键词: 柔性作业车间调度问题（FJSP）, 图神经网络, 深度强化学习, 注意力机制