源码获取请点击此处
更多强化学习内容可点击此处?
《Learning to Dispatch for Job Shop scheduling via Deep Reinforcemnet Learning》
NeurIPS 2020
1 摘要
优先调度规则(Priority dispatching rule,PDR)广泛用于求解JSSP问题,这篇文章通过端到端的深度强化学习代理来自动学习PDR。利用JSSP的析取图表示,提出了一种基于图神经网络(Graph Neural Network,GNN)的方案来嵌入求解过程中遇到的状态。由此产生的策略网络与大小无关,有效地实现了大规模实例的泛化。实验表明,该代理能够以基本的原始特征从头开始学习高质量的PDR,并且与现有最好的PDR相比表现出很强的性能。
2 文章解读
? ? ? ? 这篇文章研究的问题为静态的JSP问题。出发点是通过研究析取图,通过图神经网络来挖掘析取图中蕴含的信息,以此来达到端到端的实现。

2.1 相关状态、动作、状态转移、奖励、策略的定义
2.1.1 状态(state)
? ? ? ? 状态即为解的当前析取图状态
2.1.2 动作(action)
? ? ? ? 动作集为当前可进行加工的工序集,从中选择一个最为合适的工作作为当前阶段的动作。
2.1.3 状态转移
????????一旦确定下一步要调度的操作,我们首先要找到在所需机器上分配的最早可行时间段。然后,我们根据当前的时间关系更新该机器的析取弧的方向,并生成一个新的析取图作为新的state。
?2.1.4 奖励
????????我们的目标是学会一步一步地进行调度,以便最大限度地减少完工时间。为此,我们将奖励函数R(st,at)设计为两个状态s(t+1)、s(t)对应的部分解之间的质量差,即R(at,st)=H(St)?H(st+1),其中H(·)是质量度量。这里我们将其定义为最大完工时间的下界,即:

?2.1.5 策略
????????对于状态st,随机策略π(at|st)输出动作为动作集At上的分布。如果采用传统的PDR作为策略,则分布为one-hot,并且具有最高优先级的动作的概率为1。
?2.2 将策略参数化
????????将随机策略π(at|st)参数化为具有可训练参数θ的图神经网络,即πθ(at|st),它可以学习强调度规则并泛化。
?2.2.1 Graph embedding
? ? ? ? 这篇文章采用的是图同构网络(Graph Isomorphism Network,GIN),对给定图G=(V,E),GIN执行多次更新以计算每个节点v∈V的一维嵌入,并且迭代时的更新如下所示:

? ? ? ? ?GIN最初是针对无向图提出的,然而对JSP,析取图是一个即带有向弧的混合图,用于描述机器上的优先约束和操作序列等关键特征,这里有两种解决方法:
法一:
? ? ? ? 将无向弧换为两条有向弧,这样的话在状态转移的过程中就需要去掉其余的无向图。
法二:
? ? ? ? 忽略未定向的析取弧,通过添加弧的方式来表达状态转移,这样的一个缺点就是得到的状态表示更加稀疏。

?3 实验

?
?
? ? ? ??
|