本发明针对单件作业车间调度问题约束复杂、解空间种类多，传统的数学规划算法和元启发算法无法满足大规模作业车间调度问题的快速求解的特点，提出了基于多Agent深度强化学习的单件作业车间调度方法。本发明首先设计多Agent间的通信机制，采用多Agent方法对单件作业车间调度问题的强化学习建模；其次构建深层神经网络对车间状态进行提取，并在此基础上设计作业车间动作选择机制，实现了车间加工工件与车间环境之间的交互；再次，设计奖励函数对整个调度决策进行评估，并使用PolicyGradient算法对调度决策进行更新，以得到更优秀的调度结果；最后使用标准数据集对算法性能进行了性能评估与验证。本发明能够解决作业车间调度问题，丰富了作业车间调度问题的方法体系。
1.一种多Agent深度强化学习的单件作业车间调度方法，其特征在于，包括以下步骤：步骤1、采用多Agent方法对作业车间调度环境进行分布式建模；
在多Agent强化学习作业车间调度过程中，将全局状态S因式分解为m个Agi的局部状态Si依次输入多Agent强化学习系统，输出Agi当前执行的动作ai，改变全局状态S，获得奖励R，重复该过程直到所有Agi完成加工任务，其中，Agi对应第i个机床，i＝1,...,m，m为机床的总个数，Si为Agi的局部状态，S＝{S1，…,Si,…,Sm}，Ai为Agi的局部动作集合，其中，局部状态Si由Agi对应机床上等待加工的工件的局部动作集合Ai及其对应的加工时间δ(Ai)表示，即Si＝Ai∪δ(Ai)；
步骤2、首先，构建神经网络模型，对车间状态进行提取，输出每个工件被加工的概率；
其次，根据概率对加工工件进行选择；最后，设计作业车间多Agent交互机制，根据所加工工件，改变车间状态，实现车间加工工件与全局状态之间的交互，全局状态即为车间环境；
(1)构建神经网络模型，对车间状态进行提取：对应每个Agi分别构建m个神经网络模型Ni，i＝1,...,m，将全局状态S依次输入神经网络模型Ni，神经网络模型Ni输出机床i上所有工件被加工的概率Pi，在神经网络模型输出概i
率时，采用面向作业车间调度过程的概率函数Pi＝f(ai,Si|θ)表示在作业车间状态Si下执i
行动作ai的概率Pi，θ表示状态Si下每个动作所对应的权重，使当前不可加工的工件及已加工完成的工件被选择的概率为零，有：式中， 表示状态Si下动作ai所对应的权重， 状态Si下动作x所对应的权重，x∈Si表示x为状态Si所有可能执行的动作；
在根据概率P进行动作选择时，为了避免决策结果陷入局部较优值，将选择最大概率动作α＝max(P)和按照概率分布进行动作选择α＝random(P)进行结合，在当前最优决策中加入不确定性来设计动作选择机制，使得强化学习模型在得到局部较优值之后，依然会去探索其他解决方案，从而跳出局部较优解，寻找更好的解；动作选择机制中存在人为设定的超参数c和随即生成的自然数d，d∈(0,1)，当d大于超参数c时，选择概率最大的工件进行加工，当d小于超参数c时，按照概率分布选择加工工件，即有：(3)设计作业车间多Agent交互机制，实现车间加工工件与全局状态之间的交互：当Agi正在加工工序 ai∈Ai，那么在完成工序 后，Agi的局部动作集合Ai变为Ai:＝Ai‑ai，定义动作转移函数σi，通过定义动作转移函数σi建立Agent之间的通信机制：式中，α表示加工工序 对应的工件，b表示加工工序 对应的机床， 表示加工工序 对应的加工时间，k表示作业车间调度问题中所有的机床；
步骤3、在完成整个调度决策之后，设计奖励函数对整个调度决策进行评估，并使用PolicyGradient算法通过更新神经网络权重参数，实现调度决策的更新，所述PolicyGradient算法在根据策略完成后的回报函数J(θ)对策略进行更新，有：f t
函数J(θ)表示当T个步长结束达到最终状态S所获得的加权奖励，加权因子γ取决于时间步长与折扣因子γ，Gt表示T个步长所求得的加权奖励， 表示对其奖励进行加权平均；针对作业车间调度问题中奖励时序性的特点，在调度过程中r(t)始终为0，直到调度过程完成时由作业车间调度问题目标函数min(Cmax)，将奖励值赋为‑Cmax，并设γ＝1，则：对函数J(θ)对策略进行更新，将回报函数J(θ)对于动作概率参数 微分，求得函数梯度有：
式中， 表示对动作ai的概率 求偏导，求得函数梯度 后，对Agi动作概率参数 进行更新，有：
对概率参数 完成更新后，利用反向传播原理调用Adadelta优化器对神经网络权重W进行参数更新，完成整个策略更新。
2.如权利要求1所述的一种多Agent深度强化学习的单件作业车间调度方法，其特征在于，步骤1中，所述奖励R表示为R(S,ai,S′)，表示在状态S下执行动作ai得到状态S′所获得的奖励值。
3.如权利要求1所述的一种多Agent深度强化学习的单件作业车间调度方法，其特征在于，步骤1中，所述局部状态Si由Agi对应机床上等待加工的工件的局部动作集合Ai及其对应的加工时间δ(Ai)表示，即Si＝Ai∪δ(Ai)。
4.如权利要求1所述的一种多Agent深度强化学习的单件作业车间调度方法，其特征在于，步骤2中，所述神经网络模型由输入层、隐藏层、输出层三部分组成，其中：输入层：将作业车间状态Si转换为向量模式输出Si至第一个隐藏层h1，输入层到隐藏层h1之间采用tanhx激活函数， W1和b1分别表示第一个隐藏层h1的权重和阈值，则有：
隐藏层：隐藏层节点数设置为20，隐藏层到输出层之间不使用激活函数，有：hN＝tanh(WNhN‑1+bN)式中，hN表示第N个隐藏层，WN和bN分别表示第N个隐藏层hN的权重和阈值；
输出层：输出层的每个节点 对应Ag的动作ai被选择的概率，故将输出层节点设置为工件个数n。
一种多Agent深度强化学习的单件作业车间调度方法
技术领域
[0001] 本发明涉及车间调度领域，所研究问题为生产中最常见的单件作业车间调度问题。
背景技术
[0002] 制造业是我国的支柱产业，现代制造企业生产环节多、协作关系复杂，合理的生产调度对提高企业生产效率、降低成本和缩短生产周期有着重要意义。单件作业车间调度问
题(job‑shop scheduling problem，JSP)是最常见的作业车间调度问题，反映了在车间物
料、工艺等约束下，调配制造任务与资源间的映射关系，该问题的研究对提升制造企业的生
产效率有着重要意义，是学术界和工程界的广泛研究的课题。
[0003] JSP问题求解复杂，是典型的NP‑Hard问题。目前求解JSP问题的常用方法有最优化方法和元启发式算法。最优化方法通过数学规划法对作业车间调度问题进行建模求解，根
据不同的作业车间调度问题，可以分别用整数规划法、混合整数规划法和动态规划法来描
述。元启发式算法通过不断地迭代优化，可以在较短的时间内获得问题的近优解，元启发式
算法根据其优化策略的不同可分为局部搜索算法、禁忌搜索算法、模拟退火算法、遗传算
法、粒子群搜索算法和人工神经网络算法等。
[0004] 近年来，深度强化学习的兴起为解决JSP问题提供了新的思路。2017年，Irwan使用深度强化学习训练出一个具有决策能力的模型，成功解决了同属NP‑Hard问题的TSP问题。
Hanjun Dai使用深度强化学习方法解决了组合优化问题。2019年，Xiao等人使用深度强化
学习方法解决了流水车间调度问题。目前国内仍缺乏对于深度强化学习在JSP问题上的研
究。
发明内容
[0005] 本发明的目的是：实现对单件作业车间调度问题的分布式强化学习建模、基于神经网络的调度决策以及基于PolicyGradient算法的调度决策优化。
[0006] 为了达到上述目的，本发明的技术方案是提供了一种多Agent深度强化学习的单件作业车间调度方法，其特征在于，包括以下步骤：
[0007] 步骤1、采用多Agent方法对作业车间调度环境进行分布式建模，在多Agent强化学习作业车间调度过程中，将全局状态S因式分解为m个Agi的局部状态Si依次输入多Agent强
化学习系统，输出Agi当前执行的动作ai，改变全局状态S，获得奖励R，重复该过程直到所有
Agi完成加工任务，其中，Agi对应第i个机床，i＝1,...,m，m为机床的总个数，Si为Agi的局部
状态，S＝{S1，L,Si,L,Sm}，Ai为Agi的局部动作集合；
[0008] 步骤2、构建神经网络模型，对车间状态进行提取；
[0009] 将全局状态S输入神经网络模型，神经网络模型输出每个工件被加工的概率P，在i
神经网络模型输出概率时，采用面向作业车间调度过程的概率函数P＝f(a,Si|θ)表示在作
i
业车间状态Si下执行动作a的概率P，θ表示状态Si下每个动作所对应的权重，使当前不可加
工的工件及已加工完成的工件被选择的概率为零，有：
[0010]
[0011] 式中， 表示状态Si下动作a所对应的权重， 状态Si下动作x所对应的权重，x∈Si表示x为状态Si所有可能执行的动作；
[0012] 步骤3、根据神经模型所提取车间状态，对加工工件进行选择：
[0013] 在根据概率P进行动作选择时，将选择最大概率动作α＝max(P)和按照概率分布进行动作选择α＝random(P)进行结合，在当前最优决策中加入不确定性来设计动作选择机
制，动作选择机制中存在人为设定的超参数c和随即生成的自然数d，d∈(0,1)，当d大于超
参数c时，选择概率最大的工件进行加工，当d小于超参数c时，按照概率分布选择加工工件，
即有：
[0014]
[0015] 步骤4、设计作业车间多Agent交互机制，实现车间加工工件与车间环境之间的交互：
[0016] 当Agi正在加工工序Oa,b，a∈Ai，那么在完成工序Oa,b后，Agi的局部动作集合Ai变为Ai:＝Ai‑a，而Agi′(i′＝γ(Oa,b+1))被拓展为Ai′:＝Ai+a，定义动作转移函数σi：
[0017]
[0018] 式中，a表示加工工序Oa,b对应的工件，b表示加工工序Oa,b对应的机床，γ(oa,b)表示加工工序Oa,b对应的加工时间，k表示作业车间调度问题中所有的机床；
[0019] 步骤5、设计奖励函数对整个调度决策进行评估，并使用PolicyGradient算法通过更新神经网络权重参数，实现调度决策的更新。
[0020] 优选地，步骤1中，所述奖励R表示为R(S,a,S′)，表示在状态S下执行动作a得到状态S′所获得的奖励值。
[0021] 优选地，步骤1中，所述局部状态Si由Agi对应机床上等待加工的工件的局部动作集合Ai及其对应的加工时间δ(Ai)表示，即Si＝Ai∪δ(Ai)。
[0022] 优选地，步骤2中，所述神经网络模型由输入层、隐藏层、输出层三部分组成，其中：
[0023] 输入层：将作业车间状态Si转换为向量模式输出Si至第一个隐藏层h1，输入层到隐藏层h1之间采用tanhx激活函数， W1和b1分别表示第一个隐藏层h1的权重
和偏置，则有：
[0024] h1＝tanh(W1Si+b1)
[0025] 隐藏层：隐藏层节点数设置为20，隐藏层到输出层之间不使用激活函数，有：
[0026] hN＝tanh(WNhN‑1+bN)
[0027] 式中，hN表示第N个隐藏层，WN和bN分别表示第N个隐藏层hN的权重和偏置；
[0028] 输出层：输出层的每个节点θa对应Ag的动作a被选择的概率，故将输出层节点设置为工件个数n。
[0029] 优选地，步骤5中，所述PolicyGradient算法在根据策略完成后的回报函数J(θ)对策略进行更新，有：
[0030]
[0031] 函数J(θ)表示当T个步长结束达到最终状态Sf所获得的加权奖励，加权因子γt取决于时间步长与折扣因子γ，Gt表示T个步长所求得的加权奖励， 表示对其奖励进行加
权平均，针对JSP问题中奖励时序性的特点，在调度过程中r(t)始终为0，直到调度过程完成
时由JSP问题目标函数min(Cmax)，将奖励值赋为‑Cmax，并设本式中有γ＝1，则：
[0032]
[0033]
[0034] 将回报函数J(θ)对于动作概率参数θa微分，求得函数梯度ga，有：
[0035]
[0036] 式中， 表示对动作a的概率θa求偏导；
[0037] 求得函数梯度ga后，对Agi动作概率参数θa进行更新，有：
[0038] θa:＝θa+μNga
[0039] 其中μN∈R表示更新速率，N表示更新次数；
[0040] 对概率参数θa完成更新后，利用反向传播原理调用Adadelta优化器对神经网络权重W进行参数更新，完成整个策略更新。
[0041] 本发明针对单件作业车间调度问题约束复杂、解空间种类多，传统的数学规划算法和元启发算法无法满足大规模作业车间调度问题的快速求解的特点，提出了基于多
Agent深度强化学习的单件作业车间调度方法。本发明首先设计多Agent间的通信机制，采
用多Agent方法对作业车间调度问题的强化学习建模；其次构建深层神经网络对车间状态
进行提取，并在此基础上设计作业车间动作选择机制，实现了车间加工工件与车间环境之
间的交互；再次，设计奖励函数对整个调度决策进行评估，并使用PolicyGradient算法对调
度决策进行更新，以得到更优秀的调度结果；最后使用标准数据集对算法性能进行了性能
评估与验证。本发明能够解决单件作业车间调度问题，丰富了作业车间调度问题的方法体
系。
附图说明
[0042] 图1为多Agent强化学习模型；
[0043] 图2为深度神经网络模型结构；
[0044] 图3为Policy Gradient流程图；
[0045] 图4为FT06目标函数曲线图；
[0046] 图5为FT06问题最优解；
[0047] 图6为本发明的流程图。
具体实施方式
[0048] 下面结合具体实施例，进一步阐述本发明。应理解，这些实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人
员可以对本发明作各种改动或修改，这些等价形式同样落于本申请所附权利要求书所限定
的范围。
[0049] 本发明提供的一种多Agent深度强化学习的单件作业车间调度方法，包括以下步骤：
[0050] 步骤1、采用多Agent方法对单件作业车间调度环境进行分布式建模。
[0051] 如图1所示，是本发明的多Agent强化学习模型，包括以下内容：
[0052] Ag＝{Ag1,L,Agi,L,Agm}，其中，Agi对应第i个机床，i＝1,...,m。
[0053] S＝{S1，L,Si,L,Sm}，为所有Agi的局部状态Si组成的全局状态。
[0054] A＝{A1,L,Ai,L,Am}，为所有Agi的局部动作集合Ai构成的全局动作集合，ai表示Agi当前时刻执行的动作。
[0055] P为状态S下的概率转移矩阵，转换函数P(S′|S，a)表示在状态S下执行动作a得到状态S′的概率。
[0056] R为奖励函数，R(S,a,S′)表示在状态S下执行动作a得到状态S′所获得的奖励值。
[0057] γ为折扣因子，γ∈[0,1]。
[0058] 在多Agent强化学习作业车间调度过程中，将全局状态S因式分解为m个Agi的局部状态Si依次输入多Agent强化学习系统，输出Agi当前执行的动作ai，改变全局状态S，获得奖
励R，重复该过程直到所有Agi完成加工任务。其中，局部状态Si由Agi对应机床上等待加工的
工件的局部动作集合Ai及其对应的加工时间δ(Ai)表示，即Si＝Ai∪δ(Ai)。
[0059] 步骤2、构建神经网络模型，对车间状态进行提取。
[0060] 本实施例中，该神经网络模型由输入层、隐藏层、输出层三部分组成。
[0061] 输入层：输入层节点数设置为10，将作业车间状态Si转换为向量模式输出Si至第一个隐藏层h1，输入层到隐藏层h1之间采用tanhx激活函数， W1和b1分别表示
第一个隐藏层h1的权重和偏置，则有：
[0062] h1＝tanh(W1Si+b1)
[0063] 隐藏层：隐藏层节点数设置为20，隐藏层到输出层之间不使用激活函数，有：
[0064] hN＝tanh(WNhN‑1+bN)
[0065] 式中，hN表示第N个隐藏层，WN和bN分别表示第N个隐藏层hN的权重和偏置
[0066] 输出层：输出层的每个节点θa对应Ag的动作a被选择的概率，故将输出层节点设置为工件个数n。
[0067] 表示状态Si下动作a所对应的权重， 状态Si下动作x所对应的权重，x∈Si表示x为状态Si所有可能执行的动作.
[0068] 本实施例中，将全局状态S输入神经网络模型，神经网络模型输出每个工件被加工的概率P，在输入层与隐藏层之间使用tanhx激活函数， 在神经网络模型输
出概率时，为避免在作业车间调度过程中选择已完成工件和当前不可加加工工件，并保证
概率之和 本发明基于Softmax函数设计了面向作业车间调度过程的概率函数P＝f
i i
(a,Si|θ)表示在作业车间状态Si下执行动作a的概率P，θ表示表示状态Si下每个动作所对
应的权重，使当前不可加工的工件及已加工完成的工件被选择的概率为零。
[0069]
[0070] 式中， 表示状态Si下动作a所对应的权重， 状态Si下动作x所对应的权重，x∈Si表示x为状态Si所有可能执行的动作。
[0071] 步骤3、根据神经模型所提取车间状态，对加工工件进行选择。
[0072] 在根据概率P进行动作选择时，为了确保调度策略能够收敛并且具有跳出局部最优解的能力，将选择最大概率动作α＝max(P)和按照概率分布进行动作选择α＝random(P)
进行结合，在当前最优决策中加入不确定性来设计动作选择机制。该动作选择机制中存在
人为设定的超参数c和随即生成的自然数d，d∈(0,1)，当d大于超参数c时，选择概率最大的
工件进行加工，当d小于超参数c时，按照概率分布选择加工工件，即有：
[0073]
[0074] 步骤4、设计作业车间多Agent交互机制，实现车间加工工件与车间环境之间的交互。
[0075] 作业车间调度中，状态Si随局部动作集合Ai变化，由此可见局部状态Si随局部动作集合Ai变化，因此本发明通过定义动作转移函数建立Agent之间的通信机制。当Agi正在加工
工序Oa,b，a∈Ai，那么在完成工序Oa,b后，Agi的局部动作集合Ai变为Ai:＝Ai‑a，而Agi′(i′＝
γ(Oa,b+1))被拓展为Ai′:＝Ai+a。由此发明定义动作转移函数σi：
[0076]
[0077] 式中，a表示加工工序Oa,b对应的工件，b表示加工工序Oa,b对应的机床，γ(oa,b)表示加工工序Oa,b对应的加工时间，k表示作业车间调度问题中所有的机床；
[0078] 步骤5、设计奖励函数对整个调度决策进行评估，并使用PolicyGradient算法通过更新神经网络权重参数，实现调度决策的更新。如图3所示，PolicyGradi算法的核心是在根
据策略完成后的回报函数J(θ)对策略进行更新，有：
[0079]
[0080] 函数J(θ)表示当T个步长结束达到最终状态Sf所获得的加权奖励，加权因子γt取决于时间步长与折扣因子γ，Gt表示T个步长所求得的加权奖励， 表示对其奖励进行加权
平均。针对JSP问题中奖励时序性的特点，在调度过程中r(t)始终为0，直到调度过程完成时
由JSP问题目标函数min(Cmax)，将奖励值赋为‑Cmax，并有γ＝1，则：
[0081]
[0082]
[0083] 在策略更新时遵循预期收益下降最快准则，因此将回报函数J(θ)对于动作概率参数θa微分，求得函数梯度ga，有：
[0084]
[0085] 式中， 表示对动作a的概率θa求偏导，求得函数梯度ga后，对Agi动作概率参数θa进行更新，有：
[0086] θa:＝θa+μNga
[0087] 其中μN∈R表示更新速率，N表示更新次数。
[0088] 对概率参数θa完成更新后，利用反向传播原理调用Adadelta优化器对神经网络权重W进行参数更新，完成整个策略更新。
