用于车间作业调度的变分方法

《JOURNAL OF MANUFACTURING SYSTEMS》：Variational approach for Job Shop Scheduling

　　

•带有最大熵强化学习的变分 ELBO 解耦了表示学习和策略学习
•两阶段训练产生了结构化潜在空间，提升了稳定性和鲁棒性
•UMAP 显示变分图编码器学习到了一个结构感知的潜在流形
•VG2S 在零样本泛化方面显著优于 GNN-DRL 基线
•VG2S 比元启发式算法提供了更好的可扩展性和速度 - 质量权衡

引言

作业车间调度问题（JSSP）是制造领域的基本挑战，直接影响各种制造系统的运行效率和资源利用率。虽然传统方法——如启发式算法、元启发式算法和数学规划——已被广泛使用，但它们对实例特定优化的需求往往限制了它们在动态车间环境中的灵活性。最近，深度强化学习（DRL）作为一种强大的替代方案在制造 [1], [2], [3]、物流 [4], [5]、交通控制 [6], [7] 和国防 [8], [9] 等各种调度领域崭露头角。通过利用学习到的策略，它实现了卓越的性能和强大的跨场景泛化能力。与需要为每个新任务进行耗时再优化的传统方法不同，训练好的 DRL 模型可以立即部署到多样化的问题实例中 [10], [11], [12], [13]，为制造操作提供了必要的时效性决策。

从根本上说，这种能力取决于模型如何捕捉生产组件（如作业、机器和工序）之间错综复杂的依赖关系 [14]。因此，近期研究 [2], [10], [15], [16], [17], [18] 专注于设计有效的神经网络（NN）架构，以便将原始 JSSP 实例转换为用于决策的结构信息表示。从架构角度来看，早期将 DRL 应用于 JSSP 的研究利用了多层感知机（MLP）[2], [14], [15], [16] 或卷积神经网络（CNN）[10], [17], [18]。这些神经网络非常有效地从以向量或矩阵格式表示的 JSSP 实例中提取隐式调度相关特征 [19]。然而，通过神经网络处理以向量或矩阵形式表示的 JSSP 实例在跨不同问题规模泛化方面存在困难 [13], [19], [20], [21], [22]，这是现实世界制造系统中的一个关键限制。

传统基于神经网络方法的这种局限性源于 JSSP 的固有性质。JSSP 约束表示为析取图，体现了独特的拓扑关系，这些关系无法轻易在欧几里得空间中捕捉 [23]。这一特征使得 JSSP 本质上比旅行商问题和车辆路径问题等其他组合优化问题更难解决 [24]。事实上，即使是许多用于 JSSP 的非 DRL 算法——包括快速分支定界算法 [25] 和移动瓶颈程序 [26]——也是专门开发来利用这种析取图结构的 [21]。因此，这突显了需要能够有效处理此类图结构的 DRL 方法。

在 DRL 背景下利用这种拓扑结构的关键在于有效的表示学习。图神经网络（GNNs）专门用于处理图结构数据，使其非常适合捕捉 JSSP 中固有的复杂关系模式。这种能力使得 GNN 成为学习 JSSP 中析取图结构表示的自然框架，其中工序和机器形成了错综复杂的优先级和资源约束网络 [19]。JSSP 中基于 GNN 的研究可以沿两个与表示学习相关的关键方面进行分类：(1) 图表示和 (2) 架构设计。图表示定义了编码什么信息：如何将以图拓扑和节点/边特征的形式结构化 JSSP 实体（工序、机器）和关系（优先级、析取约束）。架构设计定义了如何处理这些信息：哪些 GNN 架构和训练方法论用于提取表示和学习策略。

在图表示方面，它已被逐步完善以适应每个问题变体的独特特征。[20], [24] 提出了一个将工序表示为带特征节点的基础框架，该框架已被后续工作广泛采用 [19], [22], [27], [28], [29], [30]。在此基础上，研究人员开发了针对多样化 JSSP 变体的专用表示：无效动作掩蔽（IAM）[30]、用于动态环境的异构图 [19], [22], [29]、用于分布式多工厂设置的拼接析取图 [27], [28], [31]，以及用于柔性作业车间问题的异构表示 [11], [32], [33]。这些研究通过开发能够编码每个问题变体独特约束的通用图结构，有效地扩展了 JSSP 建模的范围。

在架构设计方面， prior 工作主要专注于采用现有的 GNN 架构。各种 GNN 架构已被应用——包括图同构网络（GIN）[22], [24], [27], [28], [30], [31]、标准 GNN 层 [20]、随机游走嵌入 [21] 和图注意力网络（GAT）[19], [29], [34]。一些近期工作 [21], [34] 探讨了图到序列架构，该架构在结构上解耦了静态图特征的处理和动态调度决策。尽管图表示和网络架构存在变化，但这些方法普遍采用端到端方式进行训练。这种范式实现了表示级特征提取和策略级任务执行的联合优化。

虽然近期基于 GNN 的端到端 DRL 方法在 JSSP 领域证明了有效性，但它们依赖于一个隐含假设，即这些网络具有表示能力，能够有效地捕捉 JSSP 的复杂约束，从而跨多样化问题实例泛化。然而在实际中，这些端到端方法的有效性因其有限的泛化能力而受损。虽然这些模型在经典 JSSP 设置中显示出潜力，但即使是最新方法 [22], [30], [34] 在轻微偏离这些条件的情况下也会经历显著的性能下降。这在他们于 Demirkol 等人（DMU）和 Storer 等人（SWV）基准数据集上的性能降低中得到证实，这些数据集因其固有的难度而被广泛认可 [35], [36]。这种有限的泛化对部署在现实世界制造系统构成了关键障碍，这些系统 inherent 特征是高变异性复杂性。

这些缺陷源于标准端到端学习范式处理表示学习的方式：它将表示学习与策略学习紧密耦合，意味着表示仅由标量奖励信号驱动。然而，此类信号关于目标表示结构包含的有效信息很少 [37], [38]。因此，这些方法无法确保稳健的表示，最终产生泛化能力有限的策略 [37], [38], [39]。这些表示瓶颈进一步导致训练不稳定、对超参数敏感以及整体性能下降 [37]。JSSP 领域也不免受这些缺陷的影响，如在 DMU 和 SWV 等具有挑战性的基准上观察到的有限泛化能力便是例证。为了弥补 JSSP 领域的这一差距，我们提出了一种变分方法，明确解耦表示学习和策略学习，并作出以下贡献：
•我们推导了一个基于证据下界（ELBO）和最大熵强化学习（RL）的严格概率目标用于 JSSP。这不仅提供了处理制造环境中固有潜在随机性的理论框架，还明确解耦了图结构 JSSP 实例的表示学习和奖励驱动的策略学习。
•我们介绍了 VG2S，一种变分图到调度器框架，集成了变分图编码器和基于序列的策略解码器。通过采用基于 ELBO 的两阶段训练策略，我们的方法实现了高学习稳定性。
•我们经验性地证明，在 JSSP 领域，通过两阶段训练的变分表示学习产生了结构感知的潜在空间，并提供经验证据表明这种结构化潜在空间是卓越零样本泛化的关键贡献者。

章节片段
问题定义
JSSP 由三元组〈J,O,M〉表征，包括一组 n 个作业 J={J1,…,Jn}，一组 m 台机器 M={M1,…,Mm}，和一组工序 O。每个作业 Jj∈J 受优先级约束，要求其组成工序按固定、预定的序列处理。工序 Oij 属于作业 Jj，在机器 Mi∈M 上处理，并具有加工时长 pij。
目标是最小化最大完工时间 Cmax，定义为完成所有...所需的总时长

表示 JSSP 实例
为了有效建模 JSSP 实例，我们区分了其静态属性和动态特征。这种在数据表示方面的分离自然对应于第 5 节中介绍的变分图编码器和策略解码器之间的架构解耦。表示问题不变拓扑的静态信息在第 3.1 节中被建模为异构图。动态信息（在第 3.2 节中详述）捕捉了状态...

用于 JSSP 的带有最大熵强化学习的证据下界
虽然单个 JSSP 实例内的状态转移是确定的，但要在多样化调度实例上实现鲁棒泛化，需要解决贯穿问题空间的固有不确定性。处理这种不确定性构成了我们框架中用于 JSSP 表示学习概率形式化的基础。为了建模不确定性，我们引入了实例分布 p(G)，代表遇到特定问题实例 G 的可能性，以及条件...

用于 JSSP 的变分图到调度器框架
我们为 JSSP 提出了一种变分图到调度器（VG2S）框架，该框架将上述理论见解与变分自编码器（VAE）方法 [40] 和图到序列架构 [21], [34] 相结合。所提出的框架由变分图编码器（第 5.1 节）和策略解码器（第 5.2 节）组成，如图 1 所示。训练过程分为两个阶段：变分表示学习和策略学习。在变分...期间

实验
本节提供了对所提出的 VG2S 框架的多方面验证。在第 6.1 节中，我们使用各种基准数据集展示了所提模型的零样本泛化和可扩展性，在受控实验设置下进行统计分析，并将 VG2S 与来自根本不同学习范式的代表性方法进行比较。第 6.2 节提出了消融研究，以分析变分方法对策略学习及...的影响

讨论
我们讨论了 VG2S 观察到的性能背后的关键因素：
1.对抗分布偏移的概率鲁棒性：第 4 节明确将实例分布 p(G) 纳入目标函数，为跨多样化问题实例的泛化提供了有原则的概率基础。在端到端方法中，表示学习被吸收进奖励驱动的优化过程中。由于 JSSP 中的奖励信号仅携带目标函数...

结论
在这项研究中，我们提出了 VG2S 框架，首次将变分表示学习引入 JSSP 领域。通过推导基于最大熵 DRL 的 ELBO 的概率目标，VG2S 在数学和结构上解耦了表示学习和策略学习。两阶段训练策略通过防止移动目标问题，充分发挥了基于 ELBO 的表示学习的有效性。广泛的实验验证了...

CRediT 作者贡献声明
Seung Heon Oh: 监督，写作 – 原稿，验证，项目管理，方法论，数据管理，概念化。Jiwon Baek: 写作 – 原稿，可视化，概念化。Hyunjin Oh: 验证。Kiyoung Cho: 写作 – 原稿。Heechang Yoon: 写作 – 原稿，数据管理。Jong Hun Woo: 资源，项目管理，方法论，资金获取，概念化。

利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系，这些利益或关系可能影响本报告所述工作。

Seung Heon Oh|Jiwon Baek|Hyunjin Oh|Kiyoung Cho|Heechang Yoon|Jong Hun Woo