基于DDQN算法的混流车间作业动态自适应调度的研究
2021-06-07陈晓航王美林吴耿枫梁凯晴
陈晓航 王美林 吴耿枫 梁凯晴
摘 要：大规模生产的混流车间制造系统存在资源规模大、约束多等问题，快速找到合适的调度策略是实现高效生产的关键。为解决传统数学规划算法和启发式算法存在的策略求解效率低、自适应性差等问题，文章提出一种基于DDQN的智能车间动态自适应调度方法，对车间作业的自适应调度做了研究。通过“一步一推理”的自适用动态调度，可以高效地匹配合适的调度策略动作。
关键词：深度强化学习;DDQN算法;动态自适应调度
中图分类号：TP18 文献标识码：A文章编号：2096-4706（2021）24-0133-06
Abstract： In view of the large scale of resources and many constraints of the hybrid flow workshop manufacturing system in mass production， how to quickly find a suitable scheduling strategy is the key to achieve efficient production. In order to solve the problems of low strategy solving efficiency and poor adaptive existing in traditional mathematical programming algorithms and heuristic algorithms， this paper proposes a dynamic adaptive scheduling method for intelligent workshop based on DDQN， research on adaptive scheduling of workshop operations. Through the self-adaptive dynamic scheduling of “one step， one reasoning”， the appropriate scheduling policy actions can be efficiently matched.
Keywords： deep reinforcement learning; DDQN algorithm; dynamic adaptive scheduling
0 引 言
在“中國制造2025”背景下，面向大批量定制生产的混流制造HFS（Hybrid Flow Shop， HFS）是一种主流生产组织模式。而HFS调度已被证明是一个NP-Hard（Non-deterministic Polynomial Hard）的问题，对于稍大规模的调度问题，在车间实际生产中往往会有各种复杂的干扰元素。因此，如何解决这些因素对车间作业调度的干扰问题，保证生产的顺利进行，就成为一个非常有意义的研究方向。
针对制造过程的动态自适应调度，在相当多的制造领域已经得到研究。车间现场的动态调度，传统的做法是采用反应式，预测反应式，前摄式，或滚动式等方式重调度或修补调度。文献[2]中针对在车间复杂动态环境下的制造企业生产过程执行系统MES，建立了自适应调度模型进行研究。文献[3]中针对Agent技术构建基于问题的功能模块，提出一种基于改进-学习算法（WSQ）的自适应调度机制。文献[4]中Sahman针对分布式作业车间调度问题，将贪婪启发式方法与DSHO算法相结合进行求解。文献[7]采用了多优先规则启发式的调度方式，文献[10]针对凸轮从动机构的优化设计，采用元启发式算法进行了研究。文献[14]采用反应式调度机制解决船舶流水线的模糊调度问题。文献[15]针对制造车间的信息物理融合系统CPS，提出了一个基于实时数据采集的自适应调度框架机制，但没有涉及具体问题应用与求解算法。
采用传统数学规划算法或启发式算法，能够解决车间调度的路径问题，但是在实际大规模定制生产现场中，其主要存在以下难点：一是面向大规模生产的HFS，系统规模大、资源约束多，会产生“维数灾难”导致求解困难;二是面向定制生产的HFS，会因订单、工艺、设备、人员和物料等各因素动态事件，导致APS（Advanced Planning and Scheduling）调度方案在生产执行中因执行偏差较大而不可行。因此，本论文针对大规模HFS系统的调度问题，采用MPN（Manufacturing Petri Net）对车间调度系统进行压缩建模，并提出一种基于DDQN算法的车间作业动态调度方法，将传统算法计算过程数据作为历史经验进行学习，得到蕴含调度知识的深度知识DQN。进一步，将深度知识中的Q值匹配车间生产中采集到的实时数据，形成工件流转的调度策略，调度过程中充分利用了深度知识DQN，从而在实时状态下能够高效地指导工业生产。
1 模型构建
1.1 MPN模型构建
混流制造车间运作过程可以描述为：一共n个待加工的工件经过s道工序进行加工，而每一道工序存在Mi台设备（Mi>1;i=1，2，…，s），每个工件需要经过每一道工序的加工，同一道工序的不同类型的设备对同一工件的加工时间不同。本文针对混流车间采用一种基于ROPN（Resource Oriented Petri Net）的制造系统MPN建模机制，将等价并行设备建模成为一个资源提供节点Place，将批次工件建模成Petri网中流转的Token，工序中工件可以建模为通过Transaction触发进行流转。这样的模型既缩小了混流制造车间调度模型规模，又具有良好的数学表达能力。
本论文用一个以某覆铜板厂案例进行说明，如图1所示，描述了一个基于MPN模型的车间制造系统。在MPN模型中，车间作业过程可以抽象为待加工的所有工件Token在目标函数的指导下全部从p0开始转运，在Transaction的触发下进入到合适的Place上完成加工等一系列操作，最终转运到p15并完成对所有工件加工的过程。各工位容量如图2所示。
该案例用到的加工時间矩阵为：
1.2 MPN数据状态建模
通过把MPN制造系统采集到的多源异构数据进行链接和集成的，对节点的多维数据进行准确表达，可以反映该节点上在制造过程中所蕴含的生产逻辑，从而实现MPN系统状态的建模。
定义1：工位状态由A=
定义2：制造系统状态S=
定义3：制造系统的MDP状态过程M={
针对研究的覆铜板厂MPN案例，如果工位只定义一个维度状态为Token数量，制造系统某个时刻系统的状态为：<4，1，1，2，2，0，0，0，0，0，0，0，0，0，0，0>，若p4一个工件token被转运到p5，其下一个时刻的状态为：<4，1，1，2，1，1，0，0，0，0，0，0，0，0，0，0>，前后状态有着时序上的演变逻辑。
2 算法设计与训练
为了充分利用制造数据中的价值，本文考虑强化学习中基于价值策略的思路来实现算法，通过模型训练，实现一个深度Q价值网络DQN作为深度知识来指导调度策略。进一步，为解决使用相同的value来进行选择动作和估计动作造成估计的价值过于乐观的问题，设计了将选择和评估分开成2个Q价值网络的Double DQN（DDQN）算法。本文基于DDQN算法，构建一个深度强化学习算法模块，把预备好的数据输入到算法模型中训练，充分利用数据中的生产逻辑蕴含的知识。模型训练的过程具体包括以下两个方面。
2.1 获取数据
从历史数据中随机获取最小批量数目的数据，每一条数据都按照
2.2 训练模型的过程
DDQN是由负责动作获取的现实网络Current_Net和负责动作价值计算的目标网络Target_Net组成，两者的网络结构完全相同。我们把MDP状态过程的各个系统状态S作为神经网络的输入值;神经网络的输出为各动作Q表，Q表的不同维度索引映射不同动作，Q表中某一索引存储的数值代表某一动作的Q值，Q值越大，动作的价值越大，表示该动作的合理性越高。整个模型的训练过程的如图3所示。
2.2.1 计算Batch样本集的Q值
具体步骤为：
（1）将样本i（i属于1，k）中的S+1数据分别输入Current_Net和Target_Net神经网络中，得到Cur_Q值表和Tar_Q值表;
（2）获取样本i（i属于1，k）Cur_Q值表中Q值最大的索引，即动作，再利用该索引检索Tar_Q表，得到对应动作的Tar_Q值;
（3）创建可存储k条样本Q值数据的列表Q_batch，每条样本数据根据：
Y=R+c*Qtarget（S_n，arg max′（Qcurrent（S_n，A′）））
分别计算对应的Q值并载入列表中，用于后续损失函数的计算。
2.2.2 损失函数的收敛过程
具体过程为：
（1）正向传播。将k条样本数据中的S输入Current_Net神经网络，得到的当前状态
（2）反向传播（收敛函数）。将损失函数Lost设定为：
Loss=Y-Qcurrent（S，A）
使用Tensorflow模块自带optimizer优化器，按照设定的固定步长e对Loss进行最小化收敛，通过训练次数的反复迭代得到适配的模型。
2.2.3 目标Q网络更新
本项研究中，设置更新目标网络的频率是f，即将Current_Net的参数每训练f步，就更新一次Target_Net的参数。它决定着DDQN算法训练的稳定性和快速性。相比DQN算法，引入目标网络可以增加算法的稳定性，考虑到车间制造的实际，如果车间的动态干扰性较弱，即车间的生产较少有加增订单或人员流动等情况，车间生产数据有相当的平稳性，那么可以考虑调小f，可以适当增加训练的算法的快速性;如果車间制造的动态性较强，时常有加增订单等突发事件，那么可以适当调大f，以使得训练算法具有更好的稳定性。
在每次车间作业之前，都会基于历史数据和当前状态数据训，按照以上的几个步骤训练R次，一般至少训练上万次，以确保模型的有效性。训练完成深度Q价值网络（DQN）作为自适应调度知识，用来指导调度。
3 实验与分析
3.1 实验条件与过程
为研究验证本文提出的基于DDQN的车间调度系统在调度动态自适应性方面的有效性。本文采用马尔可夫Petri网模型进行验证，实验平台采用Pycharm基于Python语言实现，实验环境为Intel（R） Core（TM） i5-5200U CPU @ 2.20 GHz、内存为12 GB、操作系统为Windows10。
实验参数：基于Python语言以及Tensorflow等神经网络算法库，搭建维度为10的输入层、9层隐含层、维度为220的输出层、每层隐含层的神经元个数不同的全连接深度神经网络，用作评估深度神经网络与目标深度神经网络，并初始化各个不同的权重和偏置参数，整个实验中所涉及的参数如表1所示。
根据图1的仿真模型验证DDQN算法，使用TensorFlow 2.1搭载多层感知机模型（Multilayer Perceptron， MLP）。输入层包含16个神经元，隐藏层层数为2，每层20个神经元，输出层包含220个神经元。随机生成220条消息样本，将每条消息从源节点开始执行某个动作前后状态转移情况及所获奖励存入经验池（经验池存满后最新获得的经验值覆盖最早经验值），待经验值存满后，随机抽取40个经验序列喂入神经网络进行训练，当前消息到达目的节点后视为当前轨迹到达终止状态，所有消息到达终止状态后完成训练并保存训练模型。
3.2 DDQN算法的有效性分析
为验证本文中DDQN算法对车间调度数据利用效率的有效性，优化模型的效果，通过加大训练次数，并针对不同的激励公式，根据训练的效果来分析车间调度的自适应性以及工作的效率。每训练1 000次就做一次调度时间Time的测试，用来研究训练次数和模型训练的效果之间的变化关系。
通过对设计激励公式的多次尝试和调参工作，本研究中设计的激励为：
经训练后，将得到的调度时间和训练次数的关系进行如图4所示。
根据结果可知，第一，损失在训练10万次后收敛，满足实验要求，证明了实验结果的有效性。第二，测试调度完工时间在训练10万次左右有明显下降，此后测试结果出现几次不错的调度时间结果，多次出现130，振荡幅度较为合理，模型训练较为理想。
实验得到收敛函数的图像，如图5所示，从图像可知，本次研究中学习模型的收敛函数是趋于平缓的，这说明模型训练的效果的科学性和合理性。
分析实验结果，由图4可知，首先，当训练次数在10万次以下的时候，经过训练得到的模型把调度时间稳定在190个时间单位左右;当训练次数当训练次数超过10万次，模型的调度时间明显降低到155个时间单位左右，并稳定在一定区间。这说明模型训练次数的增加可以在一定程度上优化模型。其次，经过30万次的训练，训练时长为43 min 56 s，平均训练一次的时长为0.008 786 67 s。这体现了模型具有良好的学习更新效率，满足动态自适应调度时效性的需求。最后，从完工时间和响应时间来看，测试出现的最长完工时间为237个时间单位;测试出现的最短完工时间为130个时间单位;训练30万次的模型最终测试调度时间为162个时间单位;响应时长为0.082 8 s，一共40步，则平均每步响应时长为0.002 07 s。这充分说明模型在每一步中可以快速做出响应，在极短时间内给出调度指导策略，能够有效解决车间自适应调度问题。
4 结 论
本文针对当前物联网智能制造的车间调度中存在的无法有效利用车间生产的各种数据，以及调度效率低下等问题，提出来一种基于积累奖励的双重Q网络算法，并以某覆铜板厂案例进行验证。本研究的调度系统可以通过“一步一调度”的策略响应系统的动态性，能够实时地根据环境的变化来不断选择策略。将实时状态与深度目标Q网络交互匹配，根据车间实时数据进行推演，每匹配一步则生成一次调度策略，用来指导下个一个作业，能够快速地响应车间的动态变化，体现了对动态事件的自适应性，这对指导车间生产调度有着重要的意义。
参考文献：
[1] MEILIN WANG，ZHONG R Y，DAI Q Y，et al. A MPN-based scheduling model for IoT-enabled hybrid flow shop manufacturing [J].Advanced Engineering Informatics，2016，30（4）：728-736.
[2] 贾万达，彭艳，石宝东.基于MES系统的动态环境自适应调度模型 [J].现代商贸工业，2021，42（2）：159-160.
[3] ABREU L R，TAVARES-NETO R F，NAGANO M S. A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization [J/OL].Engineering Applications of Artificial Intelligence，2021，104：[2021-11-02].https：//doi.org/10.1016/j.engappai.2021.104373.
[4] ?AHMAN M A. A discrete spotted hyena optimizer for solving distributed job shop scheduling problems [J/OL].Applied Soft Computing，2021，106：[2021-11.02].https：//doi.org/10.1016/j.asoc.2021.107349.
[5] 肖鹏飞，张超勇，孟磊磊，等.基于深度强化学习的非置换流水车间调度问题 [J].计算机集成制造系统，2021，27（1）：192-205.
[6] 李国梁，李峭，徐亚军，等.基于DDQN的片上網络混合关键性消息调度方法 [J/OL].北京航空航天大学学报，[2021-11-07].https：//www.cnki.net/KCMS/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=BJHK20210424001&v=MzEzMjJBUzZqaDRUQXpscTJBMGZMVDdSN3FkWmVac0Z5M2xWcjdCSlY0PUp5ZkRaYkc0SE5ETXE0MUJaT3NPWXdrN3ZC.
[7] 刘东宁，徐哲.基于多优先规则启发式的分布式多项目随机调度 [J].系统工程理论与实践，2021，41（12）：3294-3303.
[8] 秦浩翔，韩玉艳，陈庆达，等.求解阻塞混合流水车间调度的双层变异迭代贪婪算法 [J/OL].控制与决策，[2021-11-03].https：//www.cnki.net/KCMS/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=KZYC20210701014&v=MTc2NzNORE1xSTlFWk9vTFl3azd2QkFTNmpoNFRBemxxMkEwZkxUN1I3cWRaZVpzRnkzbFZyN0JKVjQ9TGpmU2JiRzRI.
[9] 秦媛媛.基于SVM与强化学习的启发式算法[J].长江工程职业技术学院学报，2021，38（2）：10-14.
[10] 李浩，刘志芳，严胜利.基于元启发式算法的凸轮从动机构优化设计研究 [J].机床与液压，2021，49（14）：105-109.
[11] ANGEL-BELLO F，VALLIKAVUNGAL J，Alvarez A. Fast and efficient algorithms to handle the dynamism in a single machine scheduling problem with sequence-dependent setup times [J/OL].Computers & Industrial Engineering，2021，152：[2021-10-29].https：//doi.org/10.1016/j.cie.2020.106984.
[12] 尹静，杨阿慧.考虑交货期约束的塔式起重机服务调度启发式算法 [J].中国工程机械学报，2021，19（1）：1-6.
[13] PENG K K，PAN Q K，GAO L，et al. An Improved Artificial Bee Colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process [J].Computers & Industrial Engineering，2018，122：235-250.
[14] 兰宏凯，杨志，柳存根，等.船舶平面分段单流水线反应式模糊调度研究 [J].舰船科学技术，2019，41（15）：7-11.
[15] ROSSIT D A，TOHM? F，Frutos M. A data-driven scheduling approach to smart manufacturing [J].Journal of Industrial Information Integration，2019，15：69–79.
[16] 钱斌，佘明哲，胡蓉，等.超启发式交叉熵算法求解模糊分布式流水线绿色调度问题 [J].控制与决策，2021，36（6）：1387-1396.
[17] 王建华，潘宇杰，孙瑞.考虑机床折旧的柔性作业车间绿色调度算法 [J].计算机应用，2020，40（1）：43-49.
[18] LIU C L，CHANG C C，TSENG C J. Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems [J].IEEE Access，2020，8：71752-71762.
[19] HU L，LIU Z Y，HU W F，et al. Petri-net-based dynamic scheduling of flexible manufacturing system via deep reinforcement learning with graph convolutional network [J].Journal of Manufacturing Systems.2020，55：1-14.
[20] HU H，JIA X L，HE Q X，et al. Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in industry 4.0 [J/OL].Computers & Industrial Engineering，2020， 149：[2021-10-29].106749.https：//doi.org/10.1016/j.cie.2020.106749.
[21] 马骋乾，谢伟，孙伟杰.强化学习研究综述 [J].指挥控制与仿真，2018，40（6）：68-72.
[22] 王维祺，叶春明，谭晓军.基于Q学习算法的作业车间动态调度 [J].计算机系统应用，2020，29（11）：218-226.
[23] YANG S L，XU Z G，WANG J Y. Intelligent Decision-Making of Scheduling for Dynamic Permutation Flowshop via Deep Reinforcement Learning [J/OL].Sensors，2021，21（3）：[2021-10-29].https：//doi.org/10.3390/s21031019.
[24] CLAUDIO A，FABRIZIO M，ANDREA P. Number of bins and maximum lateness minimization in two-dimensional bin packing [J].European Journal of Operational Research，2021，291（1）：101-113.
[25] SHIRVANI M H，TALOUKI REZA R. Bi-objective scheduling algorithm for scientific workflows on cloud computing platform with makespan and monetary cost minimization approach [J/OL].Complex & Intelligent Systems，[2021-10-29].https：//link.springer.com/article/10.1007/s40747-021-00528-1.
[26] PARK J，CHUN J，KIM S H，et al. Learning to schedule job-shop problems： representation and policy learning using graph neural network and reinforcement learning [J].International Journal of Production Research.2021，59（11）：3360-3377.
[27] LUO S. Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning [J/OL].Applied Soft Computing，2020，91：[2021-10-29].https：//doi.org/10.1016/j.asoc.2020.106208.
[28] PARK I B，HUH J，KIM J，et al. A Reinforcement Learning Approach to Robust Scheduling of Semiconductor Manufacturing Facilities [J].IEEE Transactions on Automation Science and Engineering，2020，17（3）：1420-1431.
[29] GEORGIADIS G P，ELEKIDIS A P，GEORGIADIS M C. Optimal production planning and scheduling in breweries [J/OL].Food and Bioproducts Processing，2021，125：[2021-10-29].https：//doi.org/10.1016/j.fbp.2020.11.008.
作者簡介：陈晓航（1995—），男，汉族，广东揭阳人，硕士研究生在读，研究方向：物联网车间调度和深度强化学习。王美林（1975-），男，汉族，湖南安化人，副教授，博士，研究方向：物联网技术、制造执行系统及应用、面向新工科教育的智慧学习工场技术;吴耿枫（1998-），男，汉族，广东揭阳人，硕士研究生在读，研究方向：物联网车间调度和深度强化学习;梁凯晴（1998-），女，汉族，广东江门人，硕士研究生在读，研究方向：物联网车间调度和深度强化学习。
