论文名：Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling

Authors: Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, Jie Zh…

论文发表致：ICLR 2024

论文链接：https://doi.org/10.48550/arXiv.2211.10936

Github: https://github.com/zcaicaros/L2S

文献简介：

该文献提出了一种新的DRL-based改进启发式求解方法JSSP，其中使用GNN表示来编码完整解。该文献设计了一种基于图神经网络的表示方案，方案由两个模块组成，以有效捕获改进过程中遇到的图中动态拓扑和不同类型节点的信息。为了加快解改进过程中的评价效率，提出了一种可以同时评估多个解的消息传递机制。论文证明了该方法的计算复杂度与问题规模成线性关系。在经典基准测试上的实验表明，我们的方法学习的改进策略在很大程度上优于最先进的基于drl的方法。

整体介绍：

算法整体框架如下图：

首先，基于调度规则生成一个初解。在对初解的迭代过程中，将解表述为析取图形式。该算法与传统启发式算法每一步都需要评估所有领域解不同，文献方法直接输出一个工序对，并根据N5领域更新当前解，不断迭代此过程直至达到终止条件。

MDP模型：

1. 状态：每一步的状态表述为对应的析取图，析取图中对应工序节点状态向量包含该工序的最早/晚开工时间(已完工工序对应实际开工时间，若在关键路径上的工序最早、最晚开完工时间相等)、该道工序加工时间；
2. 动作：动作即N5-领域的候选工序对；
3. 状态转移过程(如下图所示)：通过交换图中给入动作对应工序，状态即从st转移至st+1;
4. 奖励函数：该文献的最终目的时尽可能提升初解质量：仅新解优于当前解时，奖励>0

 网络架构：

网络架构具体设计可阅读作者原文：