DeepMAG: Deep reinforcement learning with multi-agent graphs for flexible job shop scheduling

Abstract

一般的柔性车间调度执行基于两个决策步骤：任务次序（比如在一个机器上任务的执行顺序）以及任务路由（比如一个任务到一个机器的路径）。大多数现有的研究利用DRL或者MARL在大的搜索空间进行调度。但是这些研究有两个主要的限制：在DRL和MARL之间没有进行结合，独立的智能体之间没有合作。DeepMAG有两个关键贡献：1. DRL和MARL之间的结合。DeepMAG 通过将不同的智能体与每台机器和作业相关联，将 DRL 与 MARL 集成。每个智能体都利用 DRL 来找到有关作业排序和路由的最佳操作。在作业关联智能体选择最佳机器后，该作业成为机器进行下一个操作的作业候选者，而机器关联智能体从其作业候选集中选择下一个作业进行处理。2. 合作智能体。基于机器和作业之间的操作关系构建多智能体图。一个智能体与其相邻的智能体合作采取一个合作行动。最后，我们进行实验来评估 DeepMAG 的性能，实验结果表明它优于最先进的技术。

Introduction

作业车间调度 (JSS) 是最流行的调度问题之一，由于其在实际工厂中的广泛适用性，已被研究了几十年 [1]。 JSS 的决策步骤是通过在特定时间在特定机器上执行作业来对作业进行排序，其中 (1) 每个作业的操作需要按给定顺序（即优先约束）处理，(2) 每台机器只能处理一个任何时候作业的操作（即排除约束），以及（3）每个作业操作都有一台唯一的机器（即唯一约束）。而FJSS满足优先和排除约束但将唯一约束放宽为常量约束，其中作业的每个操作都可以在给定的常量机器集(Set)中的任何机器上处理，而不是在一台唯一的机器上处理。除了 JSS 中的作业排序（即作业在机器上执行的顺序）之外，FJSS 在作业路由上还有一个额外的决策步骤（即作业的每个操作到给定恒定机器集中的机器的路线） .

image-20230525205309249

在现有的近似计算方法中，调度规则（Dispatching rules）很难得到满足真实生活应用的调度解；启发式搜索方法可以有效地到达可能的解，但是容易陷入局部最优；强化学习方法表现出了潜力，并且相较于其他方法更有到达精确最优解的潜能。但是这些方法有两个主要的缺陷：

  1. 没有把DRL和MARL进行结合。

    大多数研究工作将 DRL 用于大型状态空间 或将 MARL 用于大型动作空间。他们没有将 DRL 与 MARL 集成来解决 FJSS 中同时具有大状态和动作空间的难题。

  2. 独立的智能体。

    当前的研究利用多个智能体来管理大的动作空间，但这些智能体彼此独立。结果，每个智能体都为一个子空间找到了自己的最优阶乘动作，而来自所有智能体的这些阶乘动作不一定构成一个最优联合动作。

为了解决这两个限制，本文提出了一种基于深度强化学习和多智能体图的 FJSS 新模型，称为 DeepMAG，它具有两个重要特征。

  1. DRL与MARL的融合。 DeepMAG 通过将每台机器或作业与一个独特的智能体相关联，将 DRL 集成到 MARL 中，该智能体利用 DQN 为机器关联的智能体找到作业排序的最佳操作，以选择下一个要处理的作业（如果可用）或作业路由作业相关的智能体在当前操作完成时选择一台机器进行下一个操作。此外，所有与机器相关的智能体共享一个 DQN，而所有与作业相关的智能体共享另一个。
  2. 合作智能体。 DeepMAG 构建了一个多智能体图，由作为节点的智能体组成，节点基于机器处理作业操作的顺序和可以处理的作业的可能操作。每个智能体通过观察它们的操作关系并在每一步聚合相邻信息以采取一个合作行动来与其相邻智能体合作。

本文的主要贡献可以概括为：

  • 我们通过将 DRL 与 MARL 集成，为 FJSS 开发了一个新模型 DeepMAG。 DRL 利用 DQN 来处理大状态空间，而 MARL 利用多个智能体来管理大动作空间。
  • 我们设计了一个多智能体图，该图源自机器和作业之间的操作关系，包括机器的处理顺序和当前时间步正在机器上处理的作业的操作。所有智能体合作寻找最佳行动，以保证 DeepMAG 的良好回报。
  • 我们进行了广泛的实验，使用来自真实制造工厂的设置的模拟数据来评估 DeepMAG 的性能。实验结果表明，DeepMAG 明显优于其他竞争技术。

将对JSS和FJSS的研究分为四类：计算优化方法(Operational optimization methods)，调度规则(Dispatching rules)，启发式搜索方法(Heuristic search methods)，强化学习(Reinforcement learning (RL) methods)；具体介绍略

Problem statement

我们在第 3.1 节介绍了预备知识，并在第 3.2 节定义了 DeepMAG 的研究问题。在接下来的问题定义中，（1）大写字母表示一个随机变量，它相应的小写字母表示一个随机值，比如S是状态变量，s是S的状态值；（2）粗体字母表示向量，例如，S是状态变量向量，s是S的状态值向量。(3) 书法字母表示一组值，例如，S 表示一组状态值 s的集合。 (4) 黑板上的粗体字母表示函数，例如$\mathbb{P}$ 表示概率函数。 (5) 打字机字母表示一个常数，例如，p 表示生产率。

Preliminaries

Definition 3.1 (Markov Decision Process (MDP)).有限 MDP 是一个 4 元组 (S, A, R, P)，其中 S 是状态的有限集，A 是动作的有限集，R 是数字奖励的有限集，P 是四元组参数条件概率质量函数：

$\mathbb{P}(s’,r|s,a) = Pr{S_{t+1} = s’, R_{t+1} = r|S_t =s, A_t = a}, (1)$

对于所有 s，s′ ∈ S，r ∈ R，a ∈ A。P(s′, r|s, a) 表示状态 s′ 和奖励 r 在时间步 t + 1 发生的概率，给定前面的状态 s 和动作 a 在时间步 t，它完全体现了有限 MDP 的动态。

在 MDP 中，智能体在每个连续的离散时间步与环境交互。在每个时间步 t，智能体接收环境的状态 St，从中选择一个动作 At。一个时间步之后，作为其选择 At 的结果，智能体收到数字奖励 Rt+1，并发现自己处于新状态 St+1。智能体选择动作 At 来最大化它在未来收到的折扣奖励的总和，这称为回报(return)。

Definition 3.2 (Return).回报 Gt 定义为在时间步 t 后收到的折扣奖励的总和：

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3} + … = \sum_{n=1}^{\infty}\gamma^{n-1}R_{t+n}(2)$，其中$\gamma$为折扣率。

智能体的目标是最大化其奖励的总量，这意味着最大化的不是即时奖励，而是长期的累积奖励。贴现率决定未来奖励的现值：在第 n 个未来时间步收到的奖励 Rt+n 乘以贴现率的 n-1 次方，即 γ n−1Rt+n。现实世界的问题，例如 JSS 和 FJSS，对于集中式智能体来说往往太大而无法解决。因此，研究人员研究了一个分布式多智能体系统，其中多个智能体在同一环境中行动以完成特定任务。因此，MDP 的定义可以扩展到这样的多智能体系统（定义 3.3）。

Definition 3.3 (Multi-agent MDP).多智能体 MDP 是一个 5 元组$ (\mathcal{I, S, A, R}, \mathbb{P})$，其中 I 是一组智能体，S 是可以分解为 $\mathcal{I}$的状态集。分量 $S = S_1 × · · · × S_{|I|}$，$A = A_1 × · · · × A_{|I|}$因此，共享相同奖励集 R 的智能体要执行的联合动作集，条件概率质量函数 P 由下式给出

$\mathbb{P}(s’,r|s,a) = Pr{S_{t+1} = s’, R_{t+1}=r|S_t = s, A_t = a},(3)$，其中的s是所有智能体的状态$s_i$，A是所有智能体的动作$A_i$；

在多智能体 MDP 中，所有智能体在环境中观察自己的局部状态，采取各自的行动，并获得相同的奖励以相互合作完成相同的任务。 MARL 基于多智能体 MDP，通过将联合行动空间划分为多个具有阶乘行动的子空间来解决具有大联合行动空间的问题。每个智能体都可以直接应用各种 RL 方法将每个状态映射到最佳动作。具体来说，基于智能体 i ∈ I 的策略 π，使用 DQN 对具有大状态空间 Si 的状态-动作值函数 Q(si, ai) 进行参数化。

Definition 3.4 (Value Function).智能体 i ∈ I 在策略 π 下在状态 si 采取行动 ai 的值，表示为 Q(si, ai)，是在时间步 t 从 si 开始采取行动 ai，然后跟随 π 的预期回报，给定经过

$\mathbb{Q}(s_i, a_i) = \mathbb{E}[G_t|S_t^i = s_i, A_t^i = a_i]$;在 DQN 中，π 是关于学习到的状态-动作值函数 Q(si, ai) 的贪心策略。

Definition 3.5 (Greedy Policy).对于任何状态-动作值函数 Q，相应的贪心策略 π 是确定性地选择具有最大值的动作 $a_i^*$ 的策略：

$a_i^* = \pi(s_i) = arg max \mathbb{Q}(s_i, a_i), for each s_i \in S_i$

Problem definition

在本节中，我们定义了 MARL 框架中针对 FJSS 研究问题的重要概念。

环境(Environment)。 FJSS 的环境包括一组机器和一组作业，其中作业被路由到特定机器并在特定时间顺序处理。特别地，FJSS 环境包含第 1 节中提到的三个重要约束：（1）优先约束给出每个作业中操作的处理顺序，（2）排除约束要求在任何机器上处理的作业中最多有一个操作时间，以及（3）常量约束为作业的每个操作指定一个常量机器集。

智能体(Agents).每个智能体与环境交互，从中学习，然后做出决定。为了处理具有大动作空间的 FJSS，每台机器都与一个作业排序智能体相关联，方法是从机器的本地等待队列（即其作业候选集）中选择下一个作业，以便在可用时进行处理，而每个作业都是通过在当前操作完成时选择一台机器来处理其下一个操作，与作业路由的智能体相关联，然后该作业成为该机器的作业候选者。这些智能体一起工作，根据当前环境状态确定它们的最佳行动。

状态(States).状态是指环境的表示，包括机器和作业的各种特征，例如，机器的生产率及其关系、正在执行和可用于每个操作的机器数量，以及作业的工作量已完成或保留在不同的操作中。环境有一个全局状态，但每个智能体可能会观察到不同的局部状态。智能体在每个时间步采取行动后，全局状态会转换为新状态。

动作(Actions).有两种类型的智能体用于不同的操作。 与机器相关的智能体负责作业排序，并在相应机器可用时决定选择哪个作业进行处理。 与作业相关的智能体负责作业路由，并决定在当前操作完成时选择哪台机器来处理相应作业的下一个操作。 换句话说，机器相关智能体的动作是从工作候选集中选择一个工作，而工作相关智能体的动作是从一组固定的机器中选择一台机器。 重要的是要注意，智能体不会在每个时间步都采取行动； 该动作仅在机器可用或作业的当前操作在特定时间步完成时触发。

奖励(Rewards).在智能体人在时间步 t 采取行动后，他们从环境中收到相同的数字奖励 Rt+1。在每个时间步，奖励设置为 $R_{t+1} = r = −1$。在 FJSS 中，RL 的目标是最大化作为折扣奖励总和的回报，比如：最小化 makespan，即完成所有工作的总时间步数。

研究问题(Research problem).给定一组机器 M 和一组作业 J，每台机器 m ∈ M 在任何时候都只处理作业的一个操作（排除约束），并且具有指定每个时间步长完成的工作负载的生产率 pm；每个作业 j ∈ J 由 K 个有序操作组成 (oj,1, . . ., oj,K)（优先约束）；每个操作 oj,k 只能由一组常量机器 Mj,k ⊂ M（常量约束）处理，并且包含工作负载量 qj,k，表示 Mj,k 中给定机器上所需的时间步长。目标是在适当的时间段为特定机器的作业操作找到最佳计划，以最大限度地减少总处理时间，即完工时间。

The proposed DeepMAG

Overview of DeepMAG

简要的介绍了用于求解FJSS问题的DeepMAG，其通过两个DQN去进行job routing和job sequencing的决策。对于每一个时间步，DeepMAG按照以下的顺序进行执行。

  • Update agent graphs. DeepMAG 根据机器和作业之间的操作关系（第 4.2 节）更新多智能体图及其两种类型的变体（特定于机器的智能体图和特定于作业的智能体图）。
  • **Update features for each agent.**根据更新的智能体图，它提取基本特征、以机器为中心的特征和以作业为中心的特征（第 4.3 节）。
  • **Update the DQN for job routing.**对于每个准备好处理其对应作业的下一个操作的作业关联智能体，首先提取当前状态和所有候选动作（机器）的表示（第 4.4.2 节），然后深度 Q 学习算法用于从候选机器中选择一个动作来处理作业的下一个操作，更新重放内存，并通过随机梯度下降优化 DQN 的参数（第 4.5 和 4.6 节）。
  • Update the other DQN for job sequencing. 对于每个可用的机器相关智能体，首先提取当前状态和所有候选动作（作业）的表示（第 4.4.1 节），然后应用深度 Q 学习从其候选作业中选择一个动作进行处理，更新回放内存，并通过随机梯度下降优化 DQN 的参数（第 4.5 和 4.6 节）。

完成所有作业后，将为 FJSS 实例生成一个作业计划。通过在大量的 FJSS 实例上训练 DeepMAG，我们可以得到 DeepMAG 的近似最优参数。

Multi-agent graphs

为了在job sequencing 和 job routing上大的连续动作空间去掌握FJSS，DeepMAG通过将每个机器或者任务用智能体联系起来来使用MARL。此外，这些智能体能够通过基于机器和作业之间的操作关系（即机器的处理顺序和当前时间步在机器上正在处理的作业的操作）来构建多智能体图的相互协作。需要注意DeepMAG并没有假定有固定数量的operation，并且自然而然地适应具有不同操作数量的场景。以下是多智能体图的定义。

Definition 4.1 (Multi-agent Graph).给定一组机器 M、一组作业 J 和一组机器 Mj,k ⊂ M 对于每个作业 j ∈ J 的每个操作 k，它们构成一个多智能体图 G = (I, Es, Eu, Ev, Ew) 在一个时间步长，其中 I 是一组节点（即智能体）：

$I = M \cup J \ \ \ \ \ \ \ \ (6)$

Es是机器之间在连续操作方面（例如，从 k 到 k + 1）静态关系的一组有向边：

$\varepsilon_s = {m \rightarrow m’ |\exists j\in J, m \in M_{j,k}\and m’ \in M_{j, k+1}} \ \ \ \ \ \ \ (7)$

Eu是是机器在一个时间步处理的作业的动态关系上的一组无向边：

$\varepsilon_u = {(j,m)|j\in J \ executing \ at \ m\in M} \ \ \ \ (8)$

Ev是作业的动态关系上的一组有向边，这些作业刚刚完成第 (k − 1) 次操作，并准备好在某个时间步路由到机器进行第 k 次操作：

$\varepsilon_v = {m \rightarrow j|j \in J routing to m \in M_{j, k}} \ \ \ \ \ (9)$

Ew是在一个时间步等待在机器上的作业的动态关系的一组有向边：

$\varepsilon_w = {j \rightarrow m|j \in J \ waiting\ at \ m \in M} \ \ \ \ (10)$

其中有向边 i → i’ 表示父子关系，i 是父节点，i’ 是子节点。

需要强调的是，在多智能体图中，所有与作业相连的边都是动态的，并且取决于在当前时间步可以处理的可能操作。此外，每个作业最多有一种类型的边，用于随时在机器上执行、等待或路由到机器。当一个作业完成时，其关联的智能体成为一个孤立的节点。此后，智能体和节点可互换地用于机器或作业。

image-20230529180040531

image-20230529180231978

以图3为例：图3描述了一个多智能体图的例子，其中的M={1,2,3,4,5,6}, J = {7,8,9,10,11,12},表1显示了每个任务的每个操作的机器集合。在图3中，黑色的结点表示同机器有关的智能体，白色结点表示和job有关的智能体。根据式7，结点1和结点3之间有一个有向边，因为job=7（8，9 或10）在机器m=1上有两个连续的操作。结点3和结点7由无向边进行连接，这表示job j=7在现在的时间步在机器m=3上正在执行。此外，job=8和9都在第二个操作刚刚完成而且等待着路由第三个操作到机器m=5或者6上，所以由式9可知结点5和6到结点8和9需要被连接起来。最后，基于式10，从结点10，11到结点4的有向边表明job j=10和job j=11正在机器m=4上进行等待，此时的机器4正在执行job j = 12。

在FJSS中，总会有一些在所有operation中拥有相同固定机器集合的job，比如在表1中的job8，9，10.考虑到现实世界中的job的不同operation会有不同的需要，所以不同的job的相同的operation可能会需要不同的机器来执行。比如说，表1中的job 7和11在前两个操作中需要的机器是完全不同的。这意味着这两个job在执行前两个操作时并没有竞争关系。这个特性在智能体执行动作时应该被考虑到。接下来我们定义一些重要且相关的定义。

Definition 4.2 (Equivalent Jobs).给定一个机器集合M，一个任务集合J，以及一系列固定的机器$M_{j,k}$，它表示每一个$job \ j \in J$的操作k需要的机器集合。当且仅当两个job的每一个操作都有相同的固定机器集合时，这两个job就是相等的。

job相等的例子：表1中的$J = {7,8,9,10,11,12}$有子集({7},{8,9,10},{11,12}).这几个子集都是每一个操作的固定机器集合都相同的相等任务。因此，我们可以将相等的任务形成一个特定任务的智能体图(Job-specific Agent Graph)。

Definition 4.3 (Job-specific Agent Graph).给定一系列的机器M，一系列的任务J，以及对每一个job j的operation k的一系列固定的机器集合$M_{j,k} \subset M$，特定于作业 j ∈ J 的智能体图 G(j) 和定义 4.1 中的多智能体图 G 的子图由作业 j 的节点、其等效作业及其每个操作的机器集，以及这些节点之间的边组成。

以表1为例，G(8)就是job j = 8的特定任务智能体图，它由包括结点8，它的相等任务（9和10）以及固定的机器（1，3，4，5和6），以及这些结点之间的边组成。因此，我们可以通过移除结点2，7，11和12以及在图3中与他们相关的边构建G(8)。请注意，所有相等任务的特定任务的智能体图是一样的。举例来说，就是G(8) = G(9) = G(10).同样的，我们定义一个特定机器的智能体图。

Definition 4.4 (Machine-specific Agent Graph).给你一系列的机器集合M，一系列任务集合J，以及一系列固定机器集合$M_{j,k} \subset M$对于每一个任务j的每一个操作k，特定于机器 m ∈ M 的智能体图 $G(m)={I(m),\varepsilon_s(m),\varepsilon_u(m),\varepsilon_v(m),\varepsilon_w(m)}$和多智能体的子图定义 4.1 中的图 G 是所有作业 $G(j)={I(j),\varepsilon_s(j),\varepsilon_u(j),\varepsilon_v(j),\varepsilon_w(j)}$的作业特定智能体图的并集机器m可以处理的：$G(m) = \bigcup_{j \in {j’|\exist k, m\in M_{j’,k}}}G(j)$

其中图并集在节点集 I(j) 和边集 Es(j)、Eu(j)、Ev(j) 和 Ew(j) 上执行。

举例说明：在结点4上的特定机器的智能体图G(4)就是在结点8，9，10，11和12上特定任务的智能体图的并集。因此，我们可以通过移除结点7以及跟他相关的边来得到智能体图G(4).

Feature extraction

有两种动作，供两类智能体使用。一个同机器相关的智能体的动作就是在它的本地等待执行队列里选取一个任务来执行。同任务相关的智能体的动作就是在一系列的机器中选择一个机器，将它的下一个等待执行的operation放进这个机器对应的本地等待执行队列中。换言之，机器和工作的可交换性构成了两类智能体的状态和动作。因此，机器和作业的特征对于这些智能体人做出决定很重要。

**Basic features.**我们强调一些已知的基本特征，包括机器 m 的生产率 $p_m$ 和作业 j 在操作 k 的工作量 $q_{j,k}$ 。为了表述方便，我们还用 $q_j$ 表示作业 j 在当前操作的工作量，用 $q_{j,m}$ 表示作业 j 在机器 m 上的工作量，因为当前操作或机器 m 表示一个确定的操作 k，它可以很容易推断出来。此外，设 $x_{j,m}$ 为作业 j 在机器 m 上在当前时间步完成的工作量。则剩余工作量为 $y_{j,m} = q_{j,m} − x_{j,m}$。除了这些基本特征外，DeepMAG 还根据 4.2 节中定义的多智能体图提取机器和作业的特征。

Machine-centric features

在不失一般性的情况下，我们关注机器 m 的特性，其关联智能体负责作业排序，当机器可用时，它会从等待队列中选择一个作业进行处理。

Four types of machine-centric static relationships

我们在机器m和其他机器之间定义了四种静态关系。

父集合由拥有从m’指向m的有向边的每个机器m’组成。它的含义就是m’可能会发送任务的下一个operation给m。

$M_e(m) = {m’|m’ \in M \and (m’ \rightarrow m}\ \ \ \ \ \ \ (12)$

子集合由拥有从m指向m’的有向边的每个机器m‘组成。它的含义就是m’可能会接受来自机器m的job的operation。

$M_d(m) = {m’|m’ \in M \and (m \rightarrow m’)}\ \ \ \ \ \ \ \ \ (13)$

双亲集合是由至少与机器m‘拥有一个公共孩子的机器m的集合。它的含义就是机器m与机器 m’在普通孩子的资源上为竞争关系。

$M_c(m) = {m’|m’ \in M \and (M_d(m’) \cap M_d(m) \neq \emptyset} \ \ \ \ \ (14)$

兄弟集由每台机器 m’ 组成，这些机器至少有一个与 m 有共同的父代机器。它的含义就是与机器 m 合作完成共同父结点上即将发送来的的工作。

$M_b(m) = {m’|m’ \in M \and (M_e(m’) \cap M_e(m)\neq \emptyset}\ \ \ \ \ (15)$

以图3来说明刚才定义的四种静态关系。$M_e(4) = {1, 2}, M_d(4) = {5, 6}, M_c (4) = {3} , M_b(4) = {3}$ 在节点4上。

Two types of machine-centric dynamic relationships

接着，我们定义了在机器m和任务之间在一个时间步的两种动态关系。

正在执行的集合由拥有无向边(j,m)的job j组成。需要注意的是由于exclusion constraint的存在，在每一个时间步，$J_u(m)$至多拥有一个任务。

$J_u(m) = {j|j \in J \and (j,m} \ \ \ \ \ \ (16)$

正在等待执行的任务集合由拥有从j到m的有向边的job j组成。这个集合中的job将通过在未来消耗一定的时间的方式为机器m带来负担。

$J_w(m) = {j|j \in J \and (j \rightarrow m} \ \ \ \ \ \ (17)$

在图3中，这两种动态关系的举例如下：对于结点4，$J_u(4) ={12}, J_w(4) = {10,11}$。

Seven types of machine-centric numeric features.

基于机器的静态和动态提取一些数量特征。

具有不同关系的机器的数量（或度（入度出度））的特征 $f_{deg}$ 由下式给出：

$f_{deg}(m) = [|M_{(.)}(m)|] \ \ \ \ \ \ (18)$

其中的[]表示一个向量聚合，(.)是从式12到式15得到的b,c,d和e的集合，后文的式子中的符号也是如此表示。

在生产力值的总和上的特征$f_{prod}$由下式给出：

$f_{prod}(m) = [\sum_{m’\in M(.)(m)}p_{m’}] \ \ \ \ \ \ \ \ \ \ \ (19)$

在正在执行的任务的数量特征$f_{exe}(m)$由下式给出：

$f_{exe}(m) = [|J_u(m)|, \sum_{m’ \in M(.)(m)}|J_u(m’)|] \ \ \ \ \ \ \ \ \ (20)$

它们相应的已完成和剩余工作量的总和由下式给出:

$f_{exe}^{finish}(m) = [\sum_{m’ \in M(.)(m)} \sum_{j \in J_u(m’)}x_{j, m’}]\ \ \ \ \ \ \ \ (21)$

$f_{exe}^{remain}(m) = [\sum_{m’ \in M(.)(m)} \sum_{j \in J_u(m’)}y_{j, m’}]\ \ \ \ \ \ \ \ (22)$

相对的，正在等待的任务的数量特征$f_{wait}(m)$由下式给出：

$f_{wait}(m) = [|J_w(m)|, \sum_{m’ \in M_{(.)}(m)}|J_w(m’)|] \ \ \ \ \ \ (23)$

它的负载数量由下式给出：

$f_{wait}^{qty}(m) = [\sum_{j \in J_w(m)}q_{j, m}, \sum_{m’ \in M_{(.)}(m)}\sum_{j\in J_w(m’)q_{j,m’}}] \ \ \ \ \ \ (24)$

这些特征表示在机器m周围复杂的环境，并且它们对与机器相关的智能体决策很重要。

Job-centric features

在不失一般性的情况下，我们通过选择一台机器来处理作业的下一个操作来关注作业 j 的特征，其关联智能体已准备好进行作业路由。

Three types of job-centric dynamic relationships.

我们定义了三种在任务j和机器m之间的动态关系。

路由机器集合$M_v(j)$由从机器m指向任务j的有向边的机器m组成，它能够为下一个操作处理作业 j。

$M_v(j) = {m|m \in M \and(m \rightarrow j)} \ \ \ \ \ (25)$

拥有相同的路由机器的任务j’的路由任务集合$J_v(j)$由下式表示，它与相同路由机器上的作业j竞争。

$J_v(j) = {j’|j’ \in J \and (M_v(j’)\cap M_v(j)\neq \emptyset} \ \ \ \ \ \ (26)$

任务j的祖先集合$J_g(j)$是拥有到job j的路径的所有job $j’ \in J$的集合，式子中的虚线箭头表示一条路径，它是具有无向边$(j′, m_1)$ 或有向边 $j′ → m_1$，有向边 $m_l → m_{l+1}$ 的不同节点序列$(j’, m_1, . . . , m_n, j)$ 以及$m_n → j (l = 1, . . ., n−1)$。

$J_g(j) = {j’|j’ \dashrightarrow j} \ \ \ \ \ \ \ \ (27)$

祖先结点将会在未来对任务j的路由机器$m_n$带来负载。例如，在图3中，结点8上的$M_v(8) = {5,6}, J_v(8) = {9},J_g(8) = {7,10,11,12}$.

Four types of job-centric numeric features.

我们基于任务j的路由任务集合$J_v(j)$和祖先集合$J_g(j)$提取了四种数量特征。

和任务j有不同关系的任务数量$f_{num}$由下式表示，其中[]表示一个向量聚合，(.)由式26，27得到的v和g来设定，之后的符号也是这样的含义。

$f_{num}(j) = [|J_{(.)}(j)|]\ \ \ \ \ \ \ (28)$

这些任务的负载上的三个统计量由下式表示：

$f_{sum}(j) = [\sum_{j’\in J_{(.)}(j)}q_{j’}]\ \ \ \ \ \ (29)$

$f_{max}(j) = [max_{j’\in J_{(.)}(j)}q_{j’}]\ \ \ \ \ \ \ \ (30)$

$f_{min}(j) = [min_{j’\in J_{(.)}(j)}q_{j’}]\ \ \ \ \ \ \ \ (31)$

任务j的复杂环境由这些特征表示，这些特征在同任务相关的智能体采取最优动作时有重要作用。

Representations of states and actions

在FJSS的大型状态空间中，将每个状态表示为标识符并学习每个状态的每个动作的状态-动作值是不可行的，就像在经典的 Q-learning 算法中一样。我们的DeepMAG通过代表状态和动作作为4.3节描述的一系列特征去估计状态动作值函数$\mathbb Q(s_i,a_i)$。机器相关和任务相关的智能体拥有不同的表示。

Machine-associated agents

让同机器有关的智能体$i=m\in M$处于可用状态（用式16表示的话就是$J_u(m) = \emptyset$），并且在一个时间步有一个正在等待的任务集合$J_w(m)$（由式17表示）。状态$s_i$应该反映智能体的特征和周围环境以及应该能够使每一个动作$a_i=J\in J_w(m)$同其他动作区分开。

**State representations.**状态由向量$s_i$表示，它通过链接生产力$p_m$以及其中机器独有的数量特征（由式18～24表示）。此外，这些从式18～24提取出的向量是由定义4.1得到的多智能体图以及定义4.4的特定机器智能体图$g(m)$提取出来的.所有提取的特征对于智能体i或者机器m都是非常特别的，它们中的大多数都是依赖机器同相邻机器以及任务之间的关系。因此，智能体可以通过观察不同的状态来和其他的智能体合作去做出动作。

**Action representations.**一个可能的动作$a_i=j\in J_w(m)$被表示为一个向量$a_i$，这个向量是由基于定义4.3得到的特定任务的智能体图得到的工作数量$q_{j,m}$和由式18到24得到的七种以机器为中心的数量特征。所有的这些特征对于正在等待的任务j来说是特别的，并且不同于其他的任务或者正在等待的任务。值得注意的是四种以任务为中心的数量特征不适用于提取任务j的特征，因为根据式25，在机器m上等待的任务j以及它的路由机器集合空的。

Job-associated agents

相反，假设一个与工作相关的智能体 i = j ∈ J 准备就绪并且在一个时间步,由式25得知它中有一个路由机器集 $M_v(j)$。类似地，需要用任务 j 自身和周围的特征来表示状态 $s_j$，并表征每个可能的动作 $a_i = m ∈ M_v(j)$。

**State representations.**由一个向量$s_i$组成状态$s_i$，这个向量是通过将工作数量$q_j$和通过式28到31的四种以任务为中心的数量特征表示。这些特征由任务j和其他任务在多智能体图以及特定任务图之间提取得出。所有的特征依赖智能体i或者任务j，但是他的任何动作都是独立的。

**Action representations.**一个候选动作$a_i=m\in M_v(j)$由一个向量$a_i$表示，它通过将生产力$p_m$和七种类型的以机器为中心的数量特征，这些特征由多智能体图，特定任务的智能体图以及特定机器的智能体图得到。需要注意，等式18到24的定义是基于机器m，而不是这些种类的智能体图。

总的来说，无论什么样的智能体，表现出的状态或者动作都包含他们独特特征以及周围特征。接下来，这些智能体就能够一同工作以发现一个最优的连续动作(optimail joint action)。

Learning on DQNs

与单独的智能体分别学习各自的DQN的简单方法不同，DeepMAG为每一种做出不同动作的智能体学习一个DQN以降低成本，增加可扩展性并且能够去改变FJSS环境中的智能体个数。所有同机器相关的智能体共享一个DQN，它们在相应的机器到达可用状态时做出任务排序的动作。所有同任务相关的智能体共享另一个DQN，它们在机器现有的操作结束时，选择一个符合条件的机器去进行它的下一个操作。此外，两个DQN拥有同样的学习算法，比如deep Q-learning，只是在状态和动作上拥有不同的输入。deep Q-learning基于经验回放，他的目标是估计状态动作值函数$\mathbb Q(s_i, a_i)$.通常这种函数被建模为深度神经网络（如DQN）。智能体的经验就是根据马尔可夫过程将得到的$(s_i,a_i,s_i’,r)$进行存储。在学习过程中，Q-learning更新被应用在经验的mini-batches上。Q-learning的更新使用如下的损失函数:

$\mathbb L(\theta_n) = \mathbb E[\left(r + \gamma \ max_{a’_i\in A_i}\hat{\mathbb Q}(s_i’,a_i’|\hat \theta_n) - \hat{\mathbb Q}(s_i, a_i|\theta_n)\right)^2 ] \ \ \ \ \ \ \ (32)$

其中$\gamma$是折扣率，$\theta_n$是DQN的参数。$\hat \theta_n$是用来计算目标的参数。目标网络的参数只有每N步才会进行更新。参数$\theta_n$由随机梯度下降算法进行学习。

Training optimization

标准的深度 Q 学习算法是无模型的，它通过直接使用来自模拟器的样本训练 DQN 来估计方程式中的值函数 Q(si, ai)。 （4），而不是等式 (1)中的条件概率质量函数 P（s’，r | s，a）。通过学习等式中的贪心策略 a∗ i = π (si) 也是一种off-policy。 (5) 同时遵循确保对状态空间进行充分探索的行为分布。在实践中，行为分布通常由 ε-greedy policy 确定，该 ε-greedy policy 遵循概率为 1−ε 的贪婪策略并选择概率为 ε 的随机动作。 DeepMAG 将此算法扩展到多智能体系统，如算法 1 所示。

image-20230531161425827

在FJSS环境中，智能体的动作次序是重要的，这对他们知道其他智能体的表现以及互相合作很重要。所以，同任务相关的智能体的动作应该先进行执行，以确保在机器的等待执行队列中有已经被路由去的待执行任务的操作存在。此外，应该根据任务和机器的工作量数量递减排序，因为有大的负载的任务或者机器都对makespan有着很大的影响， 需要更多的关注。最后，两种智能体使用算法2去学习他们自己的DQN。

image-20230531162203905

**Computational complexity.**略

Experiments

在5.1定义了实验设置，在5.2分析了实验结果。

Experimental setting

Emulated data

模拟了在现实世界工厂里用63，50，35，34个机器实现四个有序操作的场景。他们的生产力范围从每小时2400到8400不等。有四种任务，每一种都有一个相等的关系，也就是这些拥有相同类型的任务是相等的，并且构成了相等的类。每种任务在每一个操作上有固定的机器集合，这些数据在表2中被展示。需要注意的是这些数据都是真实工厂中的数据。

image-20230531163034639

为了训练DQN，在每一个episode的开始，我们通过均匀分布得到机器U(16,64),任务的数量$|J|\sim U(10, 100)$来生成FJSS实例。每个人物和负载的数量$q \sim U(1,4) \times 10,000$。这些均匀分布是根据现实世界工厂的离散的值，请注意，机器 M 是从给定的常量机器集中为 J 中的每对作业类型和操作挑选的。 DQN 在 10,000 个实例上进行训练并在三个场景中进行测试。每个场景包含 100 个具有相同作业数量（即 20、60 和 100）的不同实例，并取这 100 个实例的平均性能。

Evaluated methods

我们将提出的DeepMAG同竞争的分发规则，因为其他的方法对于JSS或者FJSS来说没有可扩展性。大多数现有的方法只能解决少于20个机器或者任务。尽管RL方法可以处理大量的机器或者任务，但没有现有的工作用语FJSS。我们开发了四种复合调度方法。

  • $J_W M_{max}$：作业关联智能体选择剩余工作量最小的机器，机器关联智能体选择工作负载最大的作业。
  • $J_T M_{max}$：与作业相关的智能体选择剩余处理时间最少的机器，与机器相关的智能体选择工作量最大的作业。
  • $J_W M_{min}$：作业关联智能体选择剩余工作量最小的机器，机器关联智能体选择工作负载最小的作业。
  • $J_T M_{min}$：与作业相关的智能体选择剩余处理时间最少的机器，与机器相关的智能体选择工作量最小的作业。

四个复合调度规则始终将较高的优先级分配给负担较低的机器，即与作业相关的智能体的最小剩余工作量或处理时间。选择负担很重的机器显然是不合适的，这会成为制造时间的瓶颈。此外，这些规则总是根据作业的工作量为机器相关智能体选择作业，因为工作量与机器上的处理时间成正比，即工作量和处理时间都会导致相同的结果。

Performance metrics

为了比较 FJSS 上评估方法的性能，我们采用标准指标，即完成所有作业的时间步长总数。请注意，我们报告了每个场景中具有相同作业数量的 100 个测试实例的平均完工时间。

Implementation details

我们的实验平台是一个计算服务器，配备 Interl(R) Xeon (R) CPU E5-2699 v4 2.20 GHz 和 Nvidia V100 GPU (16 GB)。 OpenAI 的 Gym 和谷歌的 TensorFlow 是分别用于强化学习和深度学习的开源软件库。我们基于Gym 0.17.3 实现了FJSS 环境，通过指定环境与agent 交互的标准接口。我们基于 TensorFlow 1.14 使用 DQN 实现智能体。每个 DQN 都是一个多层感知器，其中隐藏层数设置为三层，三层神经元数设置为 64、32 和 16。折扣率设置为 γ = 0.9，ε-greedy探索从开始时的 ε = 1 衰减到结束时的 ε = 0.05。为了适应 FJSS 中具有不同机器和作业分布的各种环境，我们根据训练实例估计了预期的转换和步骤总数。然后，重放内存大小 |D|由与转换总数的比率（默认为 0.25）确定，而目标网络更新频率 N 是通过将总步数除以更新次数（默认为 10）来计算的。我们基于 Adam 优化器训练两个 DQN，批量大小为 64，学习率为 0.0001。

Experimental results

Method comparison

表 3 比较了三种不同场景下所有评估方法的完工时间。我们可以得出以下三个重要发现。 (1) 我们的 DeepMAG 始终在所有三种场景中实现最佳性能，包括小型、中型和大量作业。与第二好的相反，根据 JT Mmax 给出的性能，DeepMAG 平均将完工时间缩短了 3.6%。这些结果证明了 DeepMAG 对于具有大搜索空间的 FJSS 的有效性，因为它充分利用了 DRL 和 MARL 之间的集成以及智能体在根据机器和作业之间的操作关系构建的各种图中的合作。 (2) JT Mmax 优于其他评估的调度规则，因为在 JT Mmax 中，作业相关智能体根据其处理时间而不是工作量来选择机器，以考虑其生产力的影响。此外，在 JT Mmax 中，与机器相关的智能体通过选择具有最大工作负载而不是最小工作负载的作业来更加关注具有较大工作负载的作业以减少完工时间，其中具有大工作负载的作业主导完工时间。 (3) 相比之下，JW Mmin 在所有三种情况下始终记录最长的 makespan，因为它根据工作量选择机器而不考虑机器生产率，并通过更多地关注工作量小的工作来选择工作。

image-20230531171254007

Effect of replay memory ratios

图 4 描绘了不同重放内存比率对 DeepMAG 上预期转换总数的影响，其中该比率与重放内存大小 |D| 成正比。重放内存比率对完工时间的影响很小。由于这三种场景的预期转换总数很大，因此较小的比率会在回放内存中贡献足够的转换，以减轻观察序列中的相关性并平滑模拟数据中的变化，从而解决 DRL 中的不稳定性（甚至发散）和 MARL 在某种程度上。尽管较大的比率提供了更多的回放转换以进一步减少不稳定性，但更多的历史转换会降低学习效率并抵消对不稳定性的改进。在实践中，采用较小的比率来节省内存成本，例如，在我们的实验中默认为 0.25。

image-20230531171419329

Effect of target network update times

图 5 显示了 DeepMAG 中目标网络更新次数的影响，即目标网络在整个训练过程中更新了多少次。最好的结果是更新目标网络 10 次。当更新时间从 10 次减少到 5 次时，性能变差；原因是目标网络更新太慢，Eq.中的估计目标值。 (32) 经常过时。相反，随着更新时间从 10 次增加到 80 次，性能也变得更差；这个结果是由于状态-动作值和目标值之间的相关性导致的不稳定性增加造成的。因此，应该使用适当数量的目标网络更新次数来平衡不稳定性和过时的目标值。

image-20230531171452175

Effect of neuron numbers

图 6 描绘了关于改变 DQN 的第一个隐藏层中的神经元数量的影响，其中每个连续的隐藏层在前一个隐藏层中具有一半数量的神经元。具有 32 个神经元的设置产生最差的性能，因为神经元数量少导致 FJSS 学习模型的表达力非常有限。当神经元数量从 32 个增加到 64 个时，性能显着提高。原因是模型的表达能力增强了，有利于发现各种状态下更好的动作。随着神经元数量从 64 变为 128，makespan 变长了一点，因为学习的模型可能会出现过度拟合数据的问题。在实践中，应采用适度的神经元数来平衡模型的表达性、泛化性、专业化和计算成本，包括 CPU 时间和内存使用。

image-20230531171525518

Convergence analysis

图 7 分别说明了 DeepMAG 在具有 20、60 和 100 个作业的三个测试场景中的奖励曲线，其中 x 轴是训练集的数量，y 轴是 100 个测试实例的平均奖励，如前所述在第 5.1.1 节中。从图.图.从图7可以看出，一开始曲线波动较大，因为DeepMAG的模型参数更新很大。重要的是，在大约 7,000 次训练后，这些曲线收敛到与时间步数相反的接近最大的奖励。这种收敛特性使 DeepMAG 能够在真实的制造工厂中学习 FJSS 的可行解决方案。

image-20230531171559090

Conclusion and future work

在本文中，我们形式化了灵活的作业车间调度（FJSS）问题，包括基于作业排序和路由的基于马尔可夫决策过程的框架，并据此定义了 FJSS 中的环境、智能体、状态、动作和奖励五个重要概念。然后，我们提出了一种基于 DRL 的 FJSS 新模型 DeepMAG，该模型具有多智能体图，该图是根据机器和作业之间的操作关系构建的，即机器的操作顺序和可以处理的作业的可能操作。 DeepMAG 将 DRL 与 MARL 相结合，解决了 FJSS 在状态和动作上空间过大的问题。一方面，DeepMAG 利用两个 DQN 分别为机器相关智能体的作业排序和作业相关智能体的作业路由找到最佳操作。另一方面，DeepMAG 利用各种多智能体图使每个智能体能够与其相邻智能体合作并采取一个合作行动。最后，仿真实验结果表明，与其他最先进的方法相比，DeepMAG 在 FJSS 的三种场景下实现了最佳性能。

将来，我们将考虑更先进的方法作为基线，例如，通过升级基于启发式的方法以适应大量机器和作业。本文重点研究静态 FJSS 问题，而一些动态事件，如机器故障、新工作插入和工作取消，在现实世界的制造环境中是不可避免的。因此，在 FJSS 中结合动态事件的特征来设计方法是我们未来的研究方向之一。

Data availability

作者无权共享数据。