Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning 通过图神经网络和深度强化学习进行灵活的作业车间调度

解决的问题

本文考虑了众所周知的灵活作业车间调度问题，并通过提出一种新颖的 DRL 方法来端到端地学习高质量的 PDR 来解决这些问题。操作选择和机器分配被组合为一个复合决策。此外，基于一种新颖的调度状态异构图表示，提出了一种基于异构图神经网络的体系结构来捕获操作和机器之间的复杂关系。

  • 背景

本文聚焦柔性车间调度问题(FJSP)，FJSP 允许在任何机器上处理一组可选机器的操作，因此更适合处理新制造范例（例如云制造）中任务-资源关系的灵活性和多样性。

JSP本来就是NP-hard问题，FJSP问题一般使用启发式方法，为效率牺牲最优性。优先调度规则 (PDR)是一种比较知名并且实践性强的启发式方法，它根据一些优先级规则 [例如，先进先出 (FIFO)] 将作业迭代地分配给机器。与元启发式相比，PDR 直观、易于实现且计算速度非常快，使其更适合处理云制造中的问题，这些问题通常是大规模的，甚至是动态的。

  • 提出问题

PDR调度结果远非最优。原因如下：

  1. 施工过程基于优先措施是贪婪的，这可能是短视的。
  2. 决策主要基于每个步骤中符合条件的工作和机器的信息，而全局信息在很大程度上被忽略了。
  3. 目前的PDR主要是根据人类经验设计的，通常不能保证最优性，缺乏适应特定问题和情况的能力

因此，在这个方向上，最近的一些工作尝试以端到端的方式使用 DRL 自动生成用于调度问题的 PDR，但他们都只关注于非柔性的JSP问题，因为要通过该方式改良FJSP问题的调度有两个重大挑战：

  1. FJSP 中的决策更加复杂，不仅有操作选择，还有机器分配
  2. 由于操作和机器之间复杂的一对多关系，调度状态可能更难使用神经网络进行编码。

因此，需要研究的问题就是：

  1. 如何制定调度流程以纳入机器分配
  2. 如何设计表示方案和神经架构以从原始调度状态中提取有用信息。
  • 解决思路
  1. 本文提出了一种基于 PDR 的 FJSP 调度的 MDP 公式，其中一个动作是选择一个符合条件的操作-机器（O-M）对，以便可以同时做出操作选择和机器分配决策。
  2. 通过用机器节点扩展 FJSP 的析取图，本文提出了一种新颖的异构图结构来表示 MDP 状态，从而可以捕获操作和机器之间的复杂关系。此外，提出了一种两阶段图神经网络（GNN）来获得异构图中节点的特征嵌入，在此基础上使用近端策略优化（PPO）设计和训练策略网络。
  3. 与现有的基于DRL的调度方法中使用的GNN不同，本文中提出的 GNN 适用于专用于 FJSP 的异构图，它不仅捕获操作的状态，还捕获机器和 O-M 关系的状态
  • 实验结果

在合成实例和公共基准上进行了广泛的实验。结果表明，在保持高计算效率的同时，所提出的方法可以优于传统的手工 PDR，并有效地泛化到训练中未见过的更大规模的问题和公共基准。

除了方法上的新颖性外，所提出的方法还具有良好的实用价值。它的神经结构与大小无关；因此，经过训练的策略可以应用于解决不同大小的实例，而不仅仅是训练大小。

实现方法

在每次迭代过程中，调度状态首先转化为异构图结构。然后，将具有两阶段嵌入过程的 HGNN 应用于异构图，以提取操作和机器的特征嵌入，决策网络使用这些嵌入来生成动作概率分布，从中采样调度操作。

MDP Formulation

调度过程：在每个决策步骤t(时间为0或操作完成时)，agent观察当前系统状态$s_t$并做出决策$a_t$,该决策分配一个未调度的操作给空闲的机器，并从当前时间开始，记为$T(t)$.然后，环境过渡到下一个决策步骤$t+1$。该过程迭代直到所有操作都被调度。

  • 状态（State）：在第t步的所有操作和机器的状态构成了状态$s_t$

  • 动作（Action）：本文中的动作将操作选择和机器分配结合为一个复合决策。具体来说，一个动作$a_t \in A_t$被定义为在第t步的一个可行的O-M对$(O_{ij}, M_K)$，其中的$O_{ij}$是可行的operation，$M_k$是空闲的机器。

  • 状态转移(Transition)：基于$s_t$和$a_t$，环境确定性的过渡到新状态$s_{t+1}$，这是操作完成的时间。在本文中，两种不同的状态由异构图的拓扑和特征来区分。

  • 奖励(Reward)：奖励定义为部分调度在 $s_t$ 和 $s_{t+1}$ 的完工时间之差，如$r(s_t, a_t, s_{t+1}) = C_{max}(s_t) - C_{max}(s_{t+1}))$.若折扣因子$\gamma = 1$时，一次求解过程中的累计奖励可以被记为$G = \sum_{t=0}^{|O|}r(s-t, a_t,s_{t+1}) = C_{max}(s_0) - C_{max}$.对于一个特定的问题实例，$C_{max}(s0)$ 是一个常数，这意味着最小化 $C_{max}$ 和最大化 $G$是等价的。

  • 策略(Policy):策略 $π(a_t|s_t)$ 为每个状态 $s_t$ 定义了动作集 $A_t$ 上的概率分布。接下来，本文将设计一个 DRL 算法，将 π 参数化为神经网络，并朝着最大化预期累积奖励的方向对其进行优化。

Heterogeneous Graph

用析取图表示FJSP调度更复杂的原因：

  1. 由于多台机器处理operation，析取弧集合D会明显变得更大。所以这种密集的图很难被有效处理。
  2. 一个操作在不同兼容机器上的处理时间是不同的，很难表示。

为了解决上述问题，本文通过修改析取图结构，定义了一个新颖的异构图结构$H = (O,M,C,E)$。如图所示，操作结点集合O和合取弧集C，增加了一组机器节点M，每个节点对应一台机器$M_k$。原本的析取弧集D由O-M弧集E替换。每个元素$E_{ijk} \in E$是一个将操作结点$O_{ij}$和兼容机器节点$M_k$连接起来的无向的弧。

该异构图结构拥有以下优点：

  1. 图密度显着降低。
  2. H 中的机器节点提供了一种方便的方式来注入机器信息并提取有用的特征以区分状态中的不同机器。
  3. 处理时间 $p_{ijk}$ 可以通过简单地附加为 $O-M$ 弧 $E_{ijk}$ 的特征来轻松表示。

定义异构图之后，每一个状态$s_t$可以由异构图$H_t = (O, M, C, E_t)$表示，其中$E_t$在求解过程中动态变化。具体来说：在第t步采取一个动作$(O_{ij},M_k)$后，只保留$E_{ijk}$，去掉$O_{ij}$的其他$O-M$弧，得到$H_{t+1}$。因此，节点之间的相邻关系也会动态变化。

在每个步骤t，定义$N_t(O_{ij})$ 是操作 $O_{ij}$ 的相邻机器，$N_t(M_k)$ 是机器 $M_k$ 的相邻操作。

Heterogeneous Graph Neural Network

作为组合问题中的典型，FJSP 实例具有不同的大小。要使用 DRL 学习实用的调度策略，神经架构必须能够在不同大小的状态图上运行。之前的一些工作表明GNN可以用于实现大小不可知的特性，然而它们都是对齐次图（Homogenous graph）进行处理的，在这里不可用。目前提出的HGNN都没有考虑到FJSP的异构图$H_t$，原因如下：

  1. 首先，$H_t$ 中的不同节点类型具有很强的连接模式。任何机器的邻居只能是通过无向弧连接的操作，而操作可以通过有向或无向弧连接到操作和机器。
  2. O-M 弧上的特征（即处理时间）对于解决 FJSP 非常重要。

然而，现有的 HGNN 通常只关注节点特征，不考虑弧特征。

为了利用异构图结构的特性和优势，本文提出了一种为 FJSP 定制的新型 HGNN 架构，以有效地编码 $H_t$.如图所示：

image-20230202204228094

所提出的方法具有两阶段嵌入过程的特点，以便将图的拓扑和数值信息（原始特征）考虑在内，并将 $H_t$ 中的节点映射到$ d$ 维嵌入。

在第一阶段，机器嵌入$ ν′k \in \R^d$ 通过聚合相关信息更新，而操作嵌入 $μ′{ij} \in \R^d$ 在第二阶段更新。详情如下.

Machine Node Embedding:

在 $H_t$ 中，机器 $M_k$ 的邻居是一组操作 $N_t(M_k)$，它可能对 $M_k$ 有不同的含义。例如，预计较早开始的操作可能比较晚开始的操作更重要。这促使我们考虑图形注意力网络（GAT）,它通过应用注意力机制自动学习不同节点的重要性.对于齐次图，给定具有特征 $x_i$ 的节点 $i$，GAT 首先计算 $i$ 和其一阶邻域 $N(i)$（包括 $i$ 本身）中的每个$j$ 之间的注意系数 $e_{ij}$（标量）为$e_{ij}=LeakyReLU(a^T[W_{x_i}||W_{x_j}])$.

换句话说，$x_i$ 和 $x_j$ 首先由共享线性变换 $W$ 处理，然后连接 $(||)$ 并馈入具有权重 a 和 LeakyReLU 激活的单层前馈神经网络。然后，使用 softmax 函数对邻域内的系数进行归一化:$\alpha_{ij}=\frac{exp(e_{ij})}{\sum_{q\in N(i)exp(e_{iq})}} \forall j\in N(i)$

最终，GAT 在 $N (i)$ 上聚合（线性变换）特征并应用非线性 $\sigma$ 来获得 $i$ 的嵌入:$x’i = \sigma(\sum{j \in N(i)}\alpha_{ij}W_{x_j})$.

但是原来的GAT只是针对齐次图的，没有考虑弧特征。在这里，为了满足本文的需要（即计算相邻操作对机器的重要性）.

  1. 可以观察到，对于每个机器 $M_k$，只有一个$O-M$ 弧将其与相邻操作连接起来。因此，每个 $O_{ij} \in N_t(M_k)$ 的原始特征向量通过将其原始原始特征与相应 O-M 弧的原始特征连接起来扩展为 $\mu_{ijk} =[\mu_{ij}||\lambda_{ijk}] \in \R^7$.
  2. 在这里，两个线性变换 $W^M \in \R^{d×3}$ 和 $W^O \in \R^{d × 7}$ 分别用于机器和操作节点，而不是使用共享的。
  3. 对于机器 $M_k$，注意系数 $e_{ijk}$，即每个相邻操作的重要性 $O_{ij} \in N_t(M_k)$，可以计算为:$e_{ijk} = LeakyReLU(a^T[W^Mv_k||W^O\mu_{ijk}])$,其中$a\in \R^{2d}$。

通过这种方式，来自异构节点和 O-M 弧的信息可以有效地纳入注意力计算。

上面的式子中有一件事情未被考虑：原始GAT中涉及的机器$M_k$对自身的注意力系数。这里，$e_{kk}$ 是使用机器特定权重 $W^M$ 计算的，如下所示：$e_{kk} = LeakyReLU(a^T[W^M_{V_k}||W^M_{v_k}])$.

所有 $e_{ijk} \forall O_{ij} \in N_t(M_k)$ 与 $e_kk$ 一起使用 softmax 函数进行归一化，以获得归一化的注意力系数 $α_{ijk}$ 和 $\alpha_{kk}$。

最终，机器嵌入$v’k$由融合相邻操作和自身的特征计算得到。计算$v’k$的聚合函数为：$v’k = \sigma(\alpha{kk}W^M{v_k} + \sum{O_{ij}\in N_t(M_k)}\alpha_{ijk}W^O\mu_{ijk})$

Operation Node Embedding:

本文直接使用多个MLP对每个源的信息（包括$O_{ij}$本身的特征）进行处理，将结果拼接起来，投影回d维空间作为$O_{ij}$的embedding。

具体来说，有5个MLP被定义，每一个都有d维的输出，两个 $d_h$ 维隐藏层和 ELU 激活.$O_{ij}$的embedding计算如下:

$\mu’{ij}=MLP{\theta_0}(ELU[MLP_{\theta_1}(\mu_{i,j-1})||MLP_{\theta_2}(\mu_{i, j+1})||MLP_{\theta_3}(\bar{v}’{ij})||MLP{\theta_4(\mu_{ij})}])$

请注意，无需计算两个虚拟操作 Start 和 End 的嵌入。

Stacking and Pooling:

上面的嵌入过程可以看作是一个HGNN层，它转换每个操作的原始特征$μ_{ij}$和$ν_k$，为了增强特征提取能力，这里将结构相同但可训练参数独立的 L个HGNN层堆叠起来，以获得最终的嵌入 $μ’^{(L)}_{ij}$ 和 $ν’^{(L)} _k$。

在HGNN的L层之后，分别对得到的操作嵌入集和机器嵌入集应用均值池化。然后，将生成的两个 d 维向量连接为异构图状态 $H_t$ 的嵌入 $ht \in \R^{2d}$，如下所示：$h_t=[\frac{1}{O}\sum_{O_{i,j\in O}\mu_{ij}^{‘(L)}}||\frac{1}{|M|}\sum_{M_{k\in M}}v’^{(L)}_k]$.

通过上述过程，一个可变大小的异构图可以转化为一个固定维度的嵌入。令 θ 为所有 HGNN 参数的集合。

Decision Making

由于上述异构图结构和 HGNN，策略 π(at|st) 使用提取的嵌入可以简单方便地表示.

对于在 $a_t =(O_{ij},M_k) \in A_t$ 处的每个可行动作，在步骤 t，相应的操作、机器和状态嵌入被连接起来并送入 MLP 以获得其在状态 $s_t$ 被选择的优先级索引，如下所示：$P(a_t, s_t)=MLP_\omega[\mu’^{(L)}{ij}||v’^{(L)}{k}||h_t]$

选择每个 $a_t$ 的概率是通过对所有 $P (a_t,s_t)$ 应用 softmax 来计算的:

$\pi_\omega(a_t|s_t)=\frac{exp(P(a_t,s_t))}{\sum_{a’_t\in A_t}exp(P(a’_t,s_t))} \forall a_t \in A_t$.

在训练过程中，根据策略 $\pi_\omega$ 对动作进行采样，以进行探索。

请注意，对于神经策略，采样的额外开销通常很小，因为图形处理单元 (GPU) 能够并行采样解决方案。

image-20230203000256621

Training

本文使用 PPO进行训练，它采用了 actor-critic 结构。 Actor 是策略网络 $\pi_\omega$，critic $v_\phi$ 是另一个预测状态 $s_t$ 的值 $v(s_t)$ 的网络。

image-20230203000557428

实验

本节显示合成和公共 FJSP 实例的实验结果，以验证所提出的方法。

Experimental Settings

数据来源

合成数据来自[1].

两个著名的 FJSP 基准测试数据:[1] 中的十个 mk 实例 (mk01–mk10) 和 [2] 中的三组 la 实例（rdata、edata 和 vdata，每组有 40 个实例）。

在四个较小的尺寸上进行训练，并使用最大的两个（30×10 和 40×10）来测试泛化能力

因此，对这些基准测试可以进一步验证所提出的方法在推广到分布外实例时的效果。有关这些实例的更多详细信息，请参见 [6]。

Baseline

与四个在实践中运行良好的著名 PDR 相比，包括 FIFO、剩余操作最多 (MOR)、最短处理时间 (SPT) 和剩余工作最多 (MWKR) 。

本文还与 Google OR-Tools 进行了比较。

对于公共基准，本文还与 DRL 方法 [3] 和 [4] 和 [5] 中的两种最新遗传算法 (GA) 的结果以及 [6] 中收集的最著名解决方案进行了比较。

对于具有最大完工时间 $C_{max}$ 的每个解决方案，其与最佳解决方案（不一定是最优）的最大完工时间 $C^{BS}_{max}$ 的相对差距计算如下：

$\epsilon = (C_{max}/C_^{BS} - 1) \times 100% $

Performance on Synthetic Instances

相当稳定并收敛于所有四种训练规模:

image-20230203002931755

  1. 训练大小实例的评估
  2. 大型实例的泛化性能
  3. 运行时间分析

Performance on Public Benchmarks

进一步评估经过训练的政策在传统研究中经常使用的两个公共基准上的泛化性能:

image-20230203003828665

结论

本文提出了一种新颖的端到端 DRL 方法来为 FJSP 学习高质量的 PDR，该方法在实践中得到广泛应用，但很少被现有的基于 DRL 的方法研究。

底层 MDP 是使用集成方法制定的，该方法将操作选择和机器分配结合为一个决策。然后，提出了一种异构图结构来表示调度状态，该结构由一种新颖的 HGNN 架构处理，以便将图中的数值和拓扑信息转换为特征嵌入。在 HGNN 的基础上，设计了一个 actor-critic 架构，并使用 PPO 进行训练。

结果表明，所提出的方法以合理的效率优于基线 PDR，并且可以很好地泛化到更大尺寸和公共基准的看不见的实例。

对于未来的工作，该方法将被扩展以处理实际生产中更具挑战性的因素，例如批次、到期日和不确定性。此外，将利用 FJSP 的多最优属性 [46]（即，一个实例可以有多个最优解）来提高训练性能。还将研究与 GA 等高级搜索机制相结合的可能性。

参考

[1] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Ann. Oper. Res., vol. 41, no. 3, pp. 157–183, 1993.

[2] J. Hurink, B. Jurisch, and M. Thole, “Tabu search for the job-shop scheduling problem with multi-purpose machines,” OR Spektrum, vol. 15, no. 4, pp. 205–215, 1994.

[3] B. Han and J. Yang, “A deep reinforcement learning based solution for flexible job shop scheduling problem,” Int. J. Simul. Model., vol. 20, no. 2, pp. 375–386, 2021.

[4] R. Chen, B. Yang, S. Li, and S. Wang, “A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem,” Comput. Ind. Eng., vol. 149, 2020, Art. no. 106778.

[5] D. Rooyani and F. M. Defersha, “An efficient two-stage genetic algorithm for flexible job-shop scheduling,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 2519–2524, 2019.

[6] D. Behnke and M. J. Geiger, “Test instances for the flexible job shop scheduling problem with work centers,” Helmut Schmidt Univ., Hamburg, Germany, Tech. Rep. RR-12-01-01, 2012.