一种基于深度强化学习的作业车间自适应调度方法

1.本发明属于作业车间自适应调度技术领域，涉及一种基于深度强化学习的作业车间自适应调度方法。


背景技术：

2.随着信息技术在制造业中的发展，智能制造和可重构制造应运而生。作业车间调度问题由于能够最优地分配有限的资源，提高生产效率而备受关注。jssp本质上是一个组合优化问题，传统上区分精确算法(数学方法)和近视算法方法。解决jssp的精确算法主要基于运筹学产生，如数学规划法，拉格朗松弛法以及分支界限法等。这些方法从理论上可以得出最优解。然而因为该方法需要精准的建模和大量的计算，所有多数还停留在理论层面而不能应用于实际生产。
3.为了解决这一问题，许多学者将目光转移到了近似算法，如优先规则或元启发式算法。这些优先规则，如先进先出(first in first，fifo)、最长处理时间(longest processing time，lpt)、大部分剩余操作(most operation remaining，mopr)、大部分剩余处理时间(most work remaining，mwkr)等，计算速度更快，自然能够处理实践中的不确定性，但容易短视而陷入局部最优，难以获得全局最优解。当调度规模扩大时会导致调度解得质量下降。学者也提出了许多基于领域知识的复合规则，表现出了良好的调度性能。设计一个有效的复合调度规则需要大量的先验知识和大量的时间。在元启发式算法方面，有许多的群智能算法，如遗传算法、粒子群算法和蚁群算法等。这些算法通过不断的探索和迭代可以获得相对较优解。然而，元启发式和优先规则面临的相同问题是，一旦调度问题的规模发生变化，调度方案即不适用需要重新运算求解，在大规模生产下，难以想象将生产资源停工长时间甚至几个小时等调度方案。
4.为了寻求时间成本和算法质量之间的平衡，强化学习(reinforcement learning，rl)被提出来训练调度模型，并在实际调度案例中获得了许多成功的应用。还有两个问题需要关注。首先，由于人工指标的存在，车间状态的特征提取会受到人为的影响。其次，将调度规则作为动作空间，由于工作顺序的选择回到了规则的选择，必然会耗费更多的时间。
5.许多学者将强化学习(reinforcement learning，rl)应用于调度策略的研究，为作业车间调度的高效决策提供了新的途径和方向。强化学习(reinforcement learning，rl)是不需要预先准备标签数据的无监督学习。在标签数据难以收集和获取的情况下，具有独特的优势。作业车间可以看作是一个类似的场景，其中代理根据当前车间状态选择操作。车间调度过程可以转化为如图1所示的马尔可夫决策过程(markov decision process,mdp)，其关键要素为状态、行动和奖励。
6.rl在调度中的应用主要可以分为以下四类。首先，将强化学习(reinforcement learning，rl)与启发式算法相结合，通过优化算法参数来提高算法性能；其次，将强化学习(reinforcement learning，rl)与优先级规则相结合，将规则集合设计为动作空间；强化学习(reinforcement learning，rl)用于在每个调度点上寻找最优规则，以达到最优策略。第
三，将工件加工的工序直接设计为动作空间。强化学习(reinforcement learning，rl)直接选择每个调度点上的工序，即得到最优解。最后，将机器id或传输材料定义为智能体(agent)选择的动作空间。上述类别通常对应于强化学习(reinforcement learning，rl)的四种不同的动作空间类型，即优化参数、优化规则、加工工序和机器设备。
7.本发明提出了基于作业车间调度问题(job shop scheduling problem,jssp)的直接高效探索和异步更新的近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)，以最小化完工时间为优化目标。本文的主要工作如下:(1)通过设计一种动态优化谈索策略和异步更新机制，构建直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)算法，获得生产状态和动作概率分布的映射关系以获取最优工序序列。(2)针对不同的生产状态，特别是不同的算例规模，构建了一种自适应调度方案。(3)建立实时调度系统，实现离线训练和在线执行；该系统能够分配训练有素的模型来应对不确定的车间环境，以提高调度效率。(4)数值实验结果证明了所提出的直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)的有效性和通用性。


技术实现要素：

8.本发明要解决的技术问题是：提供一种基于深度强化学习的作业车间自适应调度方法，以解决现有技术中存在的技术问题。
9.本发明采取的技术方案为：一种基于深度强化学习的作业车间自适应调度方法，该方法包括以下步骤：
10.(1)构建作业车间调度问题的调度函数模型：设有以n个作业和m台机器，每个作业包括m个不同的工序，在作业车间调度中，n个作业j＝{j1，j2……
，jn}必须在m台机器m＝{m1，m2……
，mm}上按照预先知道的不同顺序进行处理，设o
k，b
表示为工件b第k个工序，每个工序o
k，b
都必须在特定的时间段内在特定的机器上执行，工件b在机器mk上的处理时间用t
b，k
标记，t
b，k
是预先确定的，工件b在mk机器上的实际完成时间用c
b，k
表示，它等于a
b，k
+t
b，k
,，其中a
b，k
表示工件b在mk机器上的开始处理时间，一个工件在它最后一个工序完成之后就全部完成，所有的调度目标都取决于所有工件的完成时间；最小化最大完工时间的目标函数对应调度的长度；作业车间调度问题(job shop scheduling problem,jssp)的调度函数模型定义为：
11.c
max
＝min max{c
b，k
}
ꢀꢀ
(1)
12.其中，b＝1,2
……
n；k＝1,2
……
，m；
13.c
bk-t
bk
+m(1-y
bhk
)≥c
bh
ꢀꢀ
(2)
14.其中，m是一个极大值，b＝1,2
……
n；h,k＝1,2
……
，m；c
bk
表示工件b在mk机器上的实际完成时间；t
b，k
表示工件b在机器mk上的处理时间；c
bh
表示工件b在mh机器上的实际完成时间；y
bhk
表示条件函数如(4),若工件b在机器h上加工先于机器k，y
bhk
等于1，否则等于0.
15.c
ak-c
bk
+m(1-x
bak
)≥t
ak
ꢀꢀ
(3)
16.其中，m是一个极大值，a,b＝1,2
……
n；k＝1,2
……
，m；c
ak
表示工件a在mk机器上的
实际完成时间,c
bk
表示工件b在mk机器上的实际完成时间；t
a，k
表示工件a在机器mk上的处理时间；x
bhk
表示条件函数如(5),若工件b先于工件a在机器k上加工,x
bhk
等于1，否则等于0；
[0017][0018][0019]
式(1)是使所有工件完成时间最小的总目标函数；公式(2)-(3)是调度过程的约束条件；公式(2)表示工件b在机器h上先于机器k处理，公式(3)表示工件b在机器k上加工先于工件a。
[0020]
(2)在近端策略优化算法引入优化策略和异步更新机制后形成直接高效探索和异步更新近端策略优化算法；
[0021]
(3)将图神经网络与原始状态信息的分层非线性细化相结合，并基于步骤(2)直接高效探索和异步更新近端策略优化算法，给出一种端到端的深度强化学习方法；
[0022]
(4)基于步骤(3)端到端的深度强化学习方法对步骤(1)作业车间进行自适应调度决策。
[0023]
动作策略采用新型探索策略
[0024][0025]
步骤(2.4)中采用如下损失函数
[0026][0027]
其中，
[0028]
其中xi，yi分别表示目标值与预测值，在误差接近0的区域使用目标值和预测值之差的平方的平均值，在误差远离0的区域使用目标值和预测值之差的绝对值的平均值。
[0029]
a网络和c网络均采用激活函数
[0030]
f(x)＝x.sigmoid(βx)
ꢀꢀ
(10)
[0031]
其中，x是网络的输入，f(x)是网络非线性变化后的输出，β是可训练参数。
[0032]
a网络和c网络更新采用异步更新机制：k＝2表示在c网络更细2次后a网络更新1次。
[0033]
本发明的有益效果：与现有技术相比，本发明的效果如下：
[0034]
1)本发明针对作业车间调度问题，在结合动作优化搜索策略和异步更新机制的近端策略优化算法基础上，提出了一种直接高效探索和异步更新近端策略优化算法；本发明的直接高效探索和异步更新近端策略优化算法具有高级鲁棒性，调度得分比近端策略优化算法提高5.6％，最小完成时间比传统深度q网络算法降低8.9％。实验结果证明了所提出的自适应调度策略的有效性和通用性；
[0035]
2)动作策略借鉴基于值确定性策略中的ε-greedy策略，选择动作概率高的动作作
为最佳动作，如式(8)所示。该方法减少了无意义的搜索，增强了搜索方向和小尺度遍历。该策略可以更快地学习最优调度策略，更适合车间的动态复杂性、可变性和不确定性；
[0036]
3)评估了优势函数，并引入了一个延迟策略，形成了c网络和a网络之间的异步更新机制。异步更新机制减少了a网络错误的更新，因为a网络的更新速度比批评网络慢。这样的优点可以避免不必要的重复更新，减少重复更新的累积误差。k为ac网络间的更新延迟系数；
[0037]
4)使用的光滑损失函数，而不是均方误差损失函数；该损失函数对异常值不敏感，并保证稳定性。在作业车间调度中，空间值的探索不可避免地会出现离群值。由光滑损耗函数生成的模型更适用于复杂制造，具有更好的鲁棒性，能够适应不同的调度情况。为了使模型性能最大化，神经网络采用的激活函数，它可以看作是介于线性函数和relu函数之间的平滑函数，结合了两者的优点。该激活函数比relu激活函数有更好的性能。
附图说明
[0038]
图1为生产调度的马尔科夫链示意图；
[0039]
图2为基于ppo2的算法流程图；
[0040]
图3为基于e2appo的实时调度系统图；
[0041]
图4为ε-greedy策略和softmax策略的收敛对比图；
[0042]
图5为不同ε参数的收敛对比图；
[0043]
图6为不同k系数下的收敛对比图；
[0044]
图7为e2appo和ga算法对比图；
[0045]
图8为e2appo和ga的性能得分图；
[0046]
图9为e2appo对大规模算法的泛化测试图；
[0047]
图10为e2appo和基础ppo的调度得分图；
[0048]
图11为e2appo和mdqn在训练稳定上的对比图。
具体实施方式
[0049]
下面结合具体的实施例对本发明进行进一步介绍。
[0050]
实施例1：如图1-11所示，一种基于深度强化学习的作业车间自适应调度方法，该方法包括以下步骤：
[0051]
正确的加工顺序和工序调度对车间最大化生产力而言至关重要。作业车间调度问题可以看作是一个序列决策问题。调度的目标是确定每台机器上各个工序的处理顺序和每个工序的开始时间，以最小化最大完工时间。
[0052]
为了便于建模，为这个问题约定了几个预定的约束。这些约束与现有技术中的方法相同，如下所示：(1)提前知道同一工件不同工序的顺序关系和加工时间；(2)每台机器一次最多只能进行一个操作；(3)每次操作只能在一台机器上进行；(4)任何已经开始的加工都应连续进行，不中断，直至完成；(5)不同工件的工序之间没有顺序约束；(6)所有工件在0时刻到达可用。
[0053]
(1)构建作业车间调度问题的调度函数模型：设有以n个作业和m台机器，每个作业包括m个不同的工序，在作业车间调度中，n个作业j＝{j1，j2……
，jn}必须在m台机器m＝
{m1，m2……
，mm}上按照预先知道的不同顺序进行处理，设o
k，b
表示为工件b第k个工序，每个工序o
k，b
都必须在特定的时间段内在特定的机器上执行，工件b在机器mk上的处理时间用t
b，k
标记，t
b，k
是预先确定的，工件b在mk机器上的实际完成时间用c
b，k
表示，它等于a
b，k
+t
b，k
,，其中a
b，k
表示工件b在mk机器上的开始处理时间，一个工件在它最后一个工序完成之后就全部完成，所有的调度目标都取决于所有工件的完成时间；最小化最大完工时间的目标函数对应调度的长度；作业车间调度问题(job shop schedulingproblem,jssp)的调度函数模型定义为：
[0054]cmax
＝min max{c
b，k
}
ꢀꢀ
(1)
[0055]
其中，b＝1,2
……
n；k＝1,2
……
，m；
[0056]cbk-t
bk
+m(1-y
bhk
)+c
bh
ꢀꢀ
(2)
[0057]
其中，m是一个极大值，b＝1,2
……
n；h,k＝1,2
……
，m；c
bk
表示工件b在mk机器上的实际完成时间；t
b，k
表示工件b在机器mk上的处理时间；c
bh
表示工件b在mh机器上的实际完成时间；y
bhk
表示条件函数如(4),若工件b在机器h上加工先于机器k，y
bhk
等于1，否则等于0.
[0058]cak-c
bk
+m(1-x
bak
)≥t
ak
ꢀꢀ
(3)
[0059]
其中，m是一个极大值，a,b＝1,2
……
n；k＝1,2
……
，m；c
ak
表示工件a在mk机器上的实际完成时间,c
bk
表示工件b在mk机器上的实际完成时间；t
a，k
表示工件a在机器mk上的处理时间；x
bhk
表示条件函数如(5),若工件b先于工件a在机器k上加工,x
bhk
等于1，否则等于0.
[0060][0061][0062]
式(1)是使所有工件完成时间最小的总目标函数；公式(2)-(3)是调度过程的约束条件；公式(2)表示工件b在机器h上先于机器k处理，公式(3)表示工件b在机器k上加工先于工件a。针对这种情况，本发明就是要找出解决调度问题的最佳策略；
[0063]
采用的算法是改进传统的近端策略优化算法(proximal policy optimization algorithm，ppo)来进行车间调度。结合图神经网络形成一种端到端强化学习方法，可以有效提取车间状态特征，帮助智能体(agent)学习更准确的策略。
[0064]
近端策略优化算法基于典型的ac网络框架，其中a网络用于动作选择，c网络用于评估状态价值函数v(s
t
)，以评估演员所做的决定。近端策略优化算法限制了新旧策略的更新范围，以保证其稳定性，使得策略梯度(policy gradient，pg)算法对较大的学习率不太敏感。它采用了裁剪函数(clip loss)，将更新程度限制在1-∈和1+∈之间，如式(6)，其中ε为超参数。
[0065][0066]
a(s
t
，a
t
)＝∑
t
′
＞t
γ
t
′‑
trt
′-v(s
t
)
ꢀꢀ
(7)
[0067]
优势函数公式(7)定义为状态价值函数v(s
t
)与折扣奖励的积分，表示采取行动a
t
的额外收益。状态价值函数v(s
t
)是负的，因此方差更小；通过应用优化器(adam)对网络进行训练。
[0068]
本发明利用智能体(agent)与生产车间交互生成调度数据，如加工时间、机器分配、调度当前流程等。这些数据被收集并存储在缓冲区中。在一个轨迹之后，参与者网络和评论网络使用存储的调度数据来学习经验。利用时间差分(temporal-difference，td)误差进行梯度下降更新批评网络，利用策略梯度进行梯度上升更新行动者网络，寻找应对生产状态变化的最佳行动者网络。调度的具体过程如图2所示。
[0069]
(2)直接高效探索和异步更新近端策略优化算法提出了车间调度环境的马尔可夫决策过程转换，如利用图神经网络提取车间特征、由可选操作组成的行动空间、模型训练过程的奖励设计等，基于近端策略优化算法在离散动作空间中的一致性性能，在近端策略优化算法引入贪婪策略和异步更新方法后形成直接高效探索和异步更新近端策略优化算法，该算法对步骤(1)作业车间进行自适应调度；
[0070]
直接高效探索和异步更新近端策略优化算法的步骤如下：
[0071]
(2.1)输入：带训练参数θ的a网络π
θ
；带训练参数ω的c网络v
ω
，裁剪系数∈，c网络相对于a网络的更新频率倍数k，折扣因子λ，贪婪因子ε；
[0072]
(2.2)生产环境的马尔科夫过程建模,设计环境状态(s
t
)，动作集合(a
t
)，奖励值(r
t
)；
[0073]
(2.3)对1-n轮调度训练；对该轮训练中的1-j步；感知状态s
t
,基于动作策略选择动作a
t
；获得即时奖励r
t
和下一状态s
t+1
；收集以上的参数{s
t
，r
t
，a
t
}到经验池,判断该轮调度是否完；
[0074]
(2.4)调度完成后，通过将经验池数据输入c网络，评估该轮训练的优势函数
[0075]
(2.5)反向传递更新c网络
[0076]
(2.6)当训练次数是k的整数倍时，按如下公式更新a网络的参数θ，体现ac网络的异步更新
[0077][0078]
(2.7)将更新后的参数赋值到a网络π
old
←
π
θ
。
[0079]
第2.2步的作用是利用马尔可夫设计强化学习过程中使用的关键元素{s
t
，r
t
，a
t
}，将在下面的部分中详细介绍。n是轨迹的数量，j是每条轨迹的训练步数。在每个轨迹中，步骤2.3中内容“对1-n轮调度训练；对该轮训练中的1-j步；感知状态s
t
,基于优化动作策略选择动作a
t
；获得即时奖励r
t
和下一状态s
t+1”表示代理与生产环境交互并收集数据。动作策略借鉴q学习(q-learning)中的ε-greedy策略，选择动作概率高的作为最佳动作，如式(8)所示。该方法减少了无意义的搜索，增强了搜索方向和小尺度遍历。该策略可以更快地学习最优调度策略，更适合车间的动态复杂性、可变性和不确定性。ε为探索和利用之间的平衡，一般调整在0.5～0.15之间。本发明仿真实验时采用0.1。
[0080][0081]
在一个轨迹的末端，第2.4步，将前三步智能体与环境交互而收集的参数输入c网
络，评估了优势函数并在2.6步引入了一个延迟策略，当更新步数是k的整数倍时，更新a网络，形成了a网络和c网络之间的异步更新机制。异步更新机制减少了错误的更新，因为参与者的更新速度比批评网络慢。这样的优点可以避免不必要的重复更新，减少重复更新的累积误差。k为行动者更新延迟系数，其最优值为训练实验中的2。与大多数算法不同，本发明使用的是光滑损失函数如式(9)，而不是均方误差损失函数。该损失函数对异常值不敏感，并保证稳定性。在作业车间调度中，空间值的探索不可避免地会出现离群值。由光滑损耗函数生成的模型更适用于复杂制造，具有更好的鲁棒性，能够适应不同的调度情况；采用的光滑损失函数：
[0082][0083]
其中,
[0084]
其中xi，yi分别表示目标值与预测值，在误差接近0的区域使用目标值和预测值之差的平方的平均值，在误差远离0的区域使用目标值和预测值之差的绝对值的平均值。
[0085]
为了使模型性能最大化，本发明的神经网络采用了如式(10)所示的激活函数，它可以看作是介于线性函数和relu函数之间的平滑函数，结合了两者的优点。该激活函数比relu激活函数有更好的性能。实验中使用了该激活函数，结果表明该方法具有较好的准确性。a网络和c网络的激活函数：
[0086]
f(x)＝x.sigmoid(βx)
ꢀꢀ
(10)
[0087]
where,βis a trainable parameter
[0088]
其中x是网络的输入，f(x)是网络非线性变化后的输出，β是可训练参数。
[0089]
(3)在近端策略优化算法引入优化策略和异步更新机制后形成直接高效探索和异步更新近端策略优化算法；
[0090]
(4)将图神经网络与原始状态信息的分层非线性细化相结合，并基于步骤(2)直接高效探索和异步更新近端策略优化算法，给出一种端到端的深度强化学习方法；
[0091]
(5)基于步骤(4)端到端的深度强化学习方法对步骤(1)作业车间进行自适应调度决策。
[0092]
作业车间的马尔可夫过程建模如下：
[0093]
强化学习应用智能体(agent)与环境进行连续的交互。智能体(agent)通过与环境的交互，获得状态和行为之间的映射，并学习最佳策略，使累积回报最大化。基本的强化学习任务通常转化为马尔可夫决策过程(markov decision process,mdp)。马尔可夫决策过程(markov decision process,mdp)框架用5元组《s,a,p,r(s,a)，γ来描述环境，s表示环境状态的集合，a表示智能体(agent)可以执行的行动集合，p是状态转换的概率，表示从先前状态转换到当前状态的概率。回报r(s
t
,a
t
)代表在状态s
t
∈s.下采取动作a
t
∈a的奖励。马尔科夫最重要的特性是，下一个状态与过去的状态无关，而只与当前的状态相关。
[0094]
作业车间调度很适合转化为马尔可夫决策过程。智能体(agent)观察车间调度状态，选择动作，操作完成后立即获得奖励，然后将累积奖励最大化，学习最优调度策略。作业车间调度的马尔可夫模型具有以下几个关键要素。
[0095]
(1)基于图神经网络(graph neural networks，gnn)方法的作业车间状态特征提
取
[0096]
车间调度状态可以用选取图表示，选取图提供了一个综合的视图，包括每台机器上的加工时间、预约束序列。国家在车间调度的决策点表示为一个析取图g＝(n,a,e),节点n描述全部工件所有工序的集合,包括开始和结束虚拟节点，n＝o∪{os，oe}＝{os，o
1，1
，...，o
1，v1
...，o
n，1
...o
n，vn
，oe}；连接弧集a表示同一工件的所有工序的集合，对于每个节点a包含有向边o(j,k)
→
o(j,k+1)；析取集合e反映了无向弧，每一弧连接一对需要同一台机器进行处理的工序。因此，为作业调度实例寻找解决方案与确定每个分离点的方向是一样的，从而产生有向无环图(dag)。在析取图中最小化最长路径恰好是最大完工时间最小化的最优解。
[0097]
基于图神经网络(graph neural networks，gnn)方法是提取析取图特征，并作为输入又更新析取图的有效方法。基于空间域的方法通过邻域采样、目标节点与邻域节点之间的相关性计算、接收到的消息聚合单个向量来表示车间状态获取特征。以g＝(n,a,e)为例，使用图神经网络(graph neural networks，gnn)对每个节点进行迭代以获得多维嵌入，第k次迭代的更新方程描述为公式(11)。单一启发式规则仅根据单个属性作为调度序列的基础。它只考虑了局部信息，在不同的情况下会产生不同的调度性能。相比之下，图神经网络(graph neural networks，gnn)方法提取的特征是基于原始数据的，可以更好地表达当前状态，避免了人为特征的不足。
[0098][0099]
式中，σ为非线性，w为权矩阵，h为节点特征，k为深度，邻域函数n。
[0100]
(2)作业车间中智能体的动作空间建模
[0101]
a表示在每个调度点上可以选择的动作集合。在车间调度领域中，动作空间一般是指可以执行的操作或启发式规则。此外，还有一些不同的形式，如设备设置和参数选择。在本发明中，将工序设计为动作空间。选择o
t
∈a
t
作为决策步骤t的动作，假设每个工件在t时刻只能有一个可加工工序，那么动作集的大小等于工件的数量，随着工件的完成而减小。
[0102]
(3)作业车间中智能体执行动作的奖励建模
[0103]
奖励函数本质上是为了引导智能体(agent)获得最大的累积奖励。我们的代理目标是在最优调度策略下最小化最大完工时间c
max
。c
max
是所有作业的最大完成时间，与整个进度表的范围相同。奖励函数定义为公式(12)，其中r(a
t
,s
t
)表示智能体在执行动作a
t
后得到的奖励值，也是状态s
t
与状态s
(t+1)
之间的值差，最大化即时奖励的累积与最小化完成时间的效果一致。奖励设计是生产调度成功的关键，本发明将完工时间作为生产调度中最关键的因素。
[0104]
r(a
t
，s
t
)＝t(s
t
)-t(s
t+1
)
ꢀꢀ
(12)
[0105]
其中，t(s
t
)表示s
t
状态下的完成时间，t(s
t+1
)表示下一状态的完成时间。
[0106]
实例仿真：建立了一个实时调度系统来验证算法的性能，并在系统下进行了算法测试和比较。首先建立了具有深度强化学习算法模型的实时调度系统，以增强生产车间的即时调度能力。训练和测试过程的参数优化和设置将在后面介绍。然后，将提出的直接高效探索和异步更新近端策略优化算法与经典启发式算法以及其他可信调度规则的性能进行了比较。为了进一步验证所提出的自适应调度策略的优势，还将直接高效探索和异步更新近端策略优化算法与其他两种采用强化学习训练的方法进行了比较。对比实验结果验证了所提出的自适应调度策略的有效性和通用性。
[0107]
基于该方法的作业车间实时调度系统：实时性是基于深度强化学习的车间生产调度系统与传统调度算法的显著区别。我们的目的不仅是开发一个适用于小型实例的高级解决方案，而且还需要找到一个解决方案，该解决方案可以快速地在大规模的最佳情况下获得近似的解决方案。本发明提出的系统如图3所示。一方面，系统可以利用历史数据或仿真数据来描述作业车间的状态，并提前对模型进行离线训练，然后将训练好的模型存储起来供以后使用。另一方面，系统可以通过车间实时传感技术或物联网技术来评估作业车间的当前状态，然后选择训练良好的模型进行实时调度。同时，训练后的模型对于调度不同大小的实例具有较强的泛化能力，避免了再训练的时间消耗，与传统方法相比，具有实时调度性能。
[0108]
实验参数：培训过程在上述调度系统下进行；在1-99范围内随机生成各种大小的训练实例的工序加工时间和机器任务分配。实验表明，10000次训练轨迹后可以达到收敛。提议的直接高效探索和异步更新近端策略优化算法运行在具有intel酷睿i7-6700@4.0ghz cpu、geforce rtx 2080ti gpu和8gb ram的计算机上。表1显示了训练过程的参数。在每一轮的训练中随机生成新的实例，提高了直接高效探索和异步更新近端策略优化算法在训练过程中的通用性，类似于复杂的制造环境。在每个训练阶段之后，在一个验证实例上测试训练过的直接高效探索和异步更新近端策略优化算法，以评估训练过的模型的有效性。
[0109]
表1算法在训练中的参数设置
[0110]
参数名称值训练次数10000记忆池容量1e6裁剪系数∈0.2创新探索策略参数ε0.05-0.15学习率lr2e-5延迟系数k2折扣因子γ1gae参数λ0.98优化器adam
[0111]
创新探索策略集中了随机策略和确定性策略的优点。与确定性策略相比，创新探索策略可以避免陷入局部最优；另一方面，与随机策略相比，创新探索策略具有更精确的勘探方向，防止无意义的勘探和消费。图4为创新探索策略和softmax策略在训练过程中的收敛情况。创新探索策略的奖励曲线基本高于其他策略，说明创新探索策略的累计奖励值大于softmax。创新探索策略的性能优于softmax策略在过程中寻找行动空间。
[0112]
参数ε为空间探索与开发的平衡，如图5所示。ε-贪婪参数ε为勘探概率，在0.05～0.15范围内得到优化，ε＝1为随机作用。实验结果表明，除ε＝1外，在ε＝1范围内，奖励曲线有逐渐增大的趋势。在大约3000回合后，ε＝0.1曲线已经到达顶部，而在后面的章节中，ε＝0.15的奖励值将会下降。其原因可能是ε的增加，导致开发不足。通过训练过程的比较，得出ε的最优值为0.1。
[0113]
在延迟更新机制中，参数k表示行动者网络相对于批评网络的延迟更新频率。从1-3中选取k倍数的最佳值。为了更好地显示在不同系数k下的收敛性，本实验的训练次数扩大
到16000次。如图6所示，k＝1和k＝2时的收敛曲线始终较高。k＝1在训练阶段开始时处于较高水平，但在后期，由于在批评家不确定的情况下，演员的更新频繁，导致k＝2曲线以下。可以得出，系数k＝2的异步更新策略相对于k＝1而言，使整个训练稳定下来，并在训练后期收敛到最高点。
[0114]
性能指标和测试数据集：对于本发明，目标是找到一个调度方案，使最大完工时间最小化。为了对各种调度方法进行综合评价，如式(13)所示，性能评分代表了不同方法得到的最小makespan与最优方案(or-tools)之间的差距。表现分数越高，说明该方法越有效。
[0115]
性能分数＝(1-(t
i-t
best
)/t
best
)*100％
ꢀꢀ
(13)
[0116]
式中ti为不同方法的完成时间，t
best
为or-tools解决方案的完成时间。本发明中使用的两个基准数据集是众所周知的公共作业车间调度问题(job shop scheduling problem,jssp)数据集和生成的实例；从公共基准中选取了近90个案例。其中，中小规模的例子来源于ft、la和orb。从dmu数据集中选取大规模的例子与文献“c.-c.lin,d.-j.deng,y.-l.chih,and h.-t.chiu(2019)smart manufacturing scheduling with edge computing using multiclass deep q network.ieee trans.ind.informatics 15(7):4276
–
4284”进行比较。采用文献“c.zhang,w.song,z.cao,j.zhang,p.s.tan,and c.xu(2020)learning to dispatch for job shop scheduling via deep reinforcement learning.neurips 1:1
–
17”中生成的相同实例，以便与其中的算法进行比较。
[0117]
结果与讨论：
[0118]
与启发式算法的比较：为了证明本发明提出的直接高效探索和异步更新近端策略优化算法相对于启发式算法的优越性，将其与文献“y.zhan and c.qiu(2008)genetic algorithm application to the hybrid flow shop scheduling problem.proc.ieee int.conf.mechatronics autom.icma2008”中的遗传算法(ga)进行了比较。选择了几个常用的高性能优先级规则来比较文献“v.sels,n.gheysen,and m.vanhoucke(2012)a comparison of priority rules for the job shop scheduling problem under different flow time-and tardiness-related objective functions.int.j.prod.res.50(5):4255
–
4270”。遗传算法对于解决jssp问题具有良好的性能；缺点是它需要在遇到不同的作业车间调度问题(job shop scheduling problem,jssp)实例时进行解决，并且再次花费大量时间。
[0119]
对于15*15的尺度，选择了25个例子与遗传算法(ga)进行比较。如图7所示，本发明方法在15种情况下优于遗传算法，在5种情况下等于遗传算法，在其余5种情况下略低于遗传算法。由以上结果并结合图8可以看出，直接高效探索和异步更新近端策略优化算法与遗传算法(ga)相比在质量上并没有绝对优势。直接高效探索和异步更新近端策略优化算法的主要优点是可以在不同大小的情况下获得近似优秀的结果，而无需重新训练，在大尺寸的实例中具有明显的优势。
[0120]
对比的优先规则如下所示。
[0121]
最短处理时间(spt)：选择处理时间最短的下一个操作；
[0122]
先进先出规则fifo(first in first out):选择最早到达的作业的下一个操作。
[0123]
最长处理时间(lpt):选择下一个处理时间最长的操作
[0124]
mopr(most operation remaining):剩余操作最多的作业先处理。
[0125]
大部分剩余工作(mwkr):最高优先级给予属于该工作的操作，该操作需要完成的总处理时间。
[0126]
流程截止日期与大部分剩余工作的最小比例(fdd):截止日期越早的任务优先级越高。
[0127]
表2优先规则与e2appo在不同算例下的求解
[0128][0129]
调度规则与直接高效探索和异步更新近端策略优化算法的比较如表2所示。在25个测试算例中，直接高效探索和异步更新近端策略优化算法在18个案例中优于规则的调度解，有72％的超过率，说明直接高效探索和异步更新近端策略优化算法优于规则调度。为了证明直接高效探索和异步更新近端策略优化算法在泛化能力方面的优势，从benchmark中选取70个大规模算例，对训练良好的30*20尺度模型进行泛化性测试，并将结果的平均值与已知的规则进行比较。如图9所示，直接高效探索和异步更新近端策略优化算法的曲线始终在左下角。与已知规则相比，30*20模型还可以快速求解相似尺度的最优值。直接高效探索和异步更新近端策略优化算法具有较强的泛化能力和自适应性能，更适合复杂和不确定的生产环境。
[0130]
与现有强化学习(reinforcement learning，rl)调度算法的比较：为了进一步确认直接高效探索和异步更新近端策略优化算法，e2appo)相对于传统强化学习算法的优势，选择基本近端策略优化算法(proximal policy optimization algorithm，ppo)和深度q网
络算法(deep q-network,dqn)算法进行比较。首先可以观察到，本发明提出的调度算法可以进一步提高基本近端策略优化算法(proximal policy optimization algorithm，ppo)的性能，在大多数情况下获得更高的调度得分，如图10所示。特别是对于30*20实例，调度分数提高了5.6％，体现了异步更新和策略的效果。同时，表3给出了几种知名规则、改进的深度q网络算法(modified deep q-network,mdqn)和e2appo算法在dmu数据集上的测试结果。最好的值用粗体表示；与改进的深度q网络算法(modified deep q-network,mdqn)相比，所有实例的完成时间均显著减少，平均减少8.9％。每个实例的结果及其平均值表明了直接高效探索和异步更新近端策略优化算法的优越性。由图11可以看出，直接高效探索和异步更新近端策略优化算法训练分布均匀，在考虑个体实例结果的稳定性方面具有明显的优势。
[0131]
表3 mdqn和e2appo在dmu算例上的对比
[0132][0133][0134]
仿真结论：针对作业车间调度问题，提出了一种直接高效探索和异步更新近端策略优化算法，该算法采用动态贪婪搜索策略和异步更新机制，以最小化总完成时间。提出的搜索策略提高了搜索效率，避免了不必要的搜索，异步更新机制使参与者网络更新更加稳定。行动者网络根据环境状态自适应地选择当前的操作。基于所提出的直接高效探索和异步更新近端策略优化算法，在实时调度系统中提出了一种自适应调度策略，包括离线训练和在线实现。自适应调度策略提高了对复杂车间环境的适应性。结果表明，训练良好的基于直接高效探索和异步更新近端策略优化算法的模型在不同尺度上具有比启发式算法更好的泛化性能，能够在调度质量和调度速度之间实现最优平衡。
[0135]
通过对大量的实例进行数值实验，包括众所周知的基准和随机生成的实例作为实际制造的真实再现，验证了所提出的直接高效探索和异步更新近端策略优化算法的优势。通过与启发式算法的比较，验证了直接高效探索和异步更新近端策略优化算法的优越性，特别是在不同尺度下的泛化性能。与现有的强化学习算法相比，直接高效探索和异步更新近端策略优化算法达到了我们的目的。
[0136]
综上所述，在现代多变复杂的制造业中，传统的调度方法由于响应时间的限制，已经不能满足高效率的要求。为此，在近端策略优化算法(proximal policy optimization algorithm，ppo)中设计优化的动作策略和异步更新机制，形成直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)，结合了探索方向更明确、训练过程更稳定的优点。基于
直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)，将图神经网络与原始状态信息的分层非线性细化相结合，设计了一种端到端的强化学习方法。在此基础上，我们实现了一个自适应调度系统，该系统由两个子系统组成:一是离线系统，对训练好的模型进行提前训练和存储；二是实时调用模型的在线系统。在该系统下，对训练后的直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)进行了广泛的测试，并与遗传算法等启发式算法和优先调度规则以及其他现有的基于强化学习的调度方法进行了比较。与遗传算法相比，有75％的算例得出的解优于或等同于遗传算法。在泛化性的测试中，所有大实例都优于已知的调度规则，体现了直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)的高级鲁棒性。调度得分比近端策略优化算法(proximal policy optimization algorithm，ppo)提高5.6％，最小完成时间比深度q网络算法(deep q-network,dqn)降低8.9％。实验结果证明了所提出的自适应调度策略的有效性和通用性。
[0137]
本发明具有如下优点：(1)通过设计一种动态优化探索策略和异步更新机制，开发了直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)算法，获得映射状态和动作概率分布的最优操作序列。(2)针对不同的实例状态，特别是不同的实例规模，构建了一种自适应调度方案。(3)建立实时调度系统，实现离线培训和在线执行；该系统能够分配训练有素的模型来应对不可预见的车间环境，以提高调度效率。(4)数值实验结果证明了所提出的直接高效探索和异步更新近端策略优化算法(explicit exploration and asynchronous update proximal policy optimization algorithm，e2appo)的有效性和通用性。
[0138]
以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内，因此，本发明的保护范围应以所述权利要求的保护范围为准。

技术特征：
1.一种基于深度强化学习的作业车间自适应调度方法，其特征在于：该方法包括以下步骤：(1)构建作业车间调度问题的调度函数模型：设有以n个作业和m台机器，每个作业包括m个不同的工序，在作业车间调度中，n个作业j＝{j1，j2......，j
n
}必须在m台机器m＝{m1，m2……
，m
m
}上按照预先知道的不同顺序进行处理，设o
k，b
表示为工件b第k个工序，每个工序o
k，b
都必须在特定的时间段内在特定的机器上执行，工件b在机器m
k
上的处理时间用t
b，k
标记，t
b，k
是预先确定的，工件b在m
k
机器上的实际完成时间用c
b，k
表示，它等于a
b，k
+t
b，k
，，其中a
b，k
表示工件b在m
k
机器上的开始处理时间，一个工件在它最后一个工序完成之后就全部完成，所有的调度目标都取决于所有工件的完成时间；最小化最大完工时间的目标函数对应调度的长度；作业车间调度问题的调度函数模型定义为：c
max
＝min max{c
b，k
}
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)其中，b＝1，2
……
n；k＝1，2
……
，m；c
bk-t
bk
+m(1-y
bhk
)≥c
bh
ꢀꢀꢀꢀꢀꢀꢀ
(2)其中，m是一个极大值，b＝1，2
……
n；h，k＝1，2
……
，m；c
bk
表示工件b在m
k
机器上的实际完成时间；t
b，k
表示工件b在机器m
k
上的处理时间；c
bh
表示工件b在m
h
机器上的实际完成时间；y
bhk
表示条件函数如(4)，若工件b在机器h上加工先于机器k，y
bhk
等于1，否则等于0.c
ak-c
bk
+m(1-x
bak
)≥t
ak
ꢀꢀꢀꢀꢀ
(3)其中，m是一个极大值，a，b＝1，2
……
n；k＝1，2
……
，m；c
ak
表示工件a在m
k
机器上的实际完成时间，c
bk
表示工件b在m
k
机器上的实际完成时间；t
a，k
表示工件a在机器m
k
上的处理时间；x
bhk
表示条件函数如(5)，若工件b先于工件a在机器k上加工，x
bhk
等于1，否则等于0.等于1，否则等于0.式(1)是使所有工件完成时间最小的总目标函数；公式(2)-(3)是调度过程的约束条件；公式(2)表示工件b在机器h上先于机器k处理，公式(3)表示工件b在机器k上加工先于工件a；(2)在近端策略优化算法引入优化策略和异步更新机制后形成直接高效探索和异步更新近端策略优化算法；(3)将图神经网络与原始状态信息的分层非线性细化相结合，并基于步骤(2)直接高效探索和异步更新近端策略优化算法，给出一种端到端的深度强化学习方法；(4)基于步骤(3)端到端的深度强化学习方法对步骤(1)作业车间进行自适应调度决策。2.根据权利要求1所述的一种基于深度强化学习的作业车间自适应调度方法，其特征在于：直接高效探索和异步更新近端策略优化算法的步骤如下：(2.1)输入：带训练参数θ的a网络π
θ
；带训练参数ω的c网络v
ω
，裁剪系数∈，c网络相对于a网络的更新频率倍数k，折扣因子λ，贪婪因子ε；(2.2)生产环境的马尔科夫过程建模，设计环境状态(s
t
)，动作集合(a
t
)，奖励值(r
t
)；
(2.3)对1-n轮调度训练；对该轮训练中的1-j步；感知状态s
t
，基于动作策略选择动作a
t
；获得即时奖励r
t
和下一状态s
t+1
；收集以上的参数{s
t
，r
t
，a
t
}到经验池，判断该轮调度是否完；(2.4)调度完成后，通过将经验池数据输入c网络，评估该轮训练的优势函数(2.5)反向传递更新c网络(2.6)当训练次数是k的整数倍时，按如下公式更新a网络的参数θ，(2.7)将更新后的参数赋值到a网络π
old
←
π
θ
。3.根据权利要求2所述的一种基于深度强化学习的作业车间自适应调度方法，其特征在于：动作策略采用新型探索策略4.根据权利要求2所述的一种基于深度强化学习的作业车间自适应调度方法，其特征在于：采用如下损失函数其中，其中x
i
，y
i
分别表示目标值与预测值，在误差接近0的区域使用目标值和预测值之差的平方的平均值，在误差远离0的区域使用目标值和预测值之差的绝对值的平均值。5.根据权利要求2所述的一种基于深度强化学习的作业车间自适应调度方法，其特征在于：a网络和c网络均采用激活函数f(x)＝x.sigmoid(βx)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(10)其中，x是网络的输入，f(x)是网络非线性变化后的输出，β是可训练参数。6.根据权利要求2所述的一种基于深度强化学习的作业车间自适应调度方法，其特征在于：a网络和c网络更新采用异步更新机制：k＝2表示在c网络更细2次后a网络更新1次。

技术总结
本发明公开了一种基于深度强化学习的作业车间自适应调度方法，在近端策略优化算法中设计优化的动作策略和异步更新机制，形成直接高效探索和异步更新近端策略优化算法，基于直接高效探索和异步更新近端策略优化算法，将图神经网络与原始状态信息的分层非线性细化相结合，设计了一种端到端的强化学习方法，基于此，获得一个自适应调度系统。本发明的直接高效探索和异步更新近端策略优化算法具有高级鲁棒性，调度得分比近端策略优化算法提高5.6％，最小完成时间比深度Q网络算法降低8.9％。实验结果证明了所提出的自适应调度策略的有效性和通用性。略的有效性和通用性。略的有效性和通用性。


技术研发人员：干雪梅 李少波 张钧星 张安思 左颖
受保护的技术使用者：贵州大学
技术研发日：2022.04.18
技术公布日：2022/7/5