并行机调度问题(parallel machine scheduling problem，PMSP)是将n个工件分配在m台机器上并确定工件在机器上的加工顺序，以使得追求的绩效指标最优的问题，是实际生产制造过程中广泛存在的一类典型调度问题[1]．并行机调度问题中的并行机一般分为等效(identical)机、匀速(uniform)机与无关(unrelated)机三类．传统有关并行机调度问题的研究主要围绕静态问题(如假设机器一直可用，工件到达时间确定等)展开，提出的求解方法有精确法(如动态规划法、数学规划法)[2]，启发式规则(如列表调度(LS)、最短处理时间(SPT)、加权最短处理时间(WSPT)、最长处理时间(LPT)、迭代贪婪(IG))[2-3]，随机邻域搜索算法(如模拟退火(SA))以及群体智能算法(如粒子群优化(PSO)，布谷鸟搜索(CS)算法)[3]等．由于现实生产中存在各种动态因素(如机器故障或维护、工件随机到达、紧急订单等)，研究集成动态因素的并行机调度问题非常必要．文献[4-5]研究了考虑机器维护活动的并行机调度问题，分别提出了动态规划方法与启发式算法；文献[6]研究了考虑工件到达与处理时间随机的并行机调度问题，提出了一种两阶段随机规划方法；文献[7]研究了考虑工件动态到达的并行机调度问题，提出了一种基于AD-SWPT规则的在线调度方法．然而，动态因素影响下的调度目标和约束一直处于动态变化和进化过程中，是典型的序列动态决策问题．基于启发式与智能算法的调度方法，其效果极大地依赖搜索规则与算子以及算法参数的设计，很难满足智能制造背景下的实时自适应调度需求．随着强化学习技术的发展，将调度过程作为马尔可夫决策过程，根据调度问题的实时环境状态选择最合适的调度决策以最大化系统绩效成为动态调度问题的研究趋势[8]．早期基于强化学习的动态调度主要运用 SARSA，Q-learning和Q-Ⅲ learning等算法[9-11]，须要建立状态-行为-奖励之间的函数关系，更适用于小规模简单问题的求解．对于中大规模复杂问题，须要采用结合神经网络的深度强化学习(deep reinforcement learning，DRL)算法求解．例如文献[12]提出了基于近端策略优化(PPO)算法的作业车间动态调度方法；文献[13]提出了基于DQN算法的动态柔性作业车间调度方法；文献[14]提出了基于DRL与迭代贪婪算法融合的流水车间调度方法；文献[15]建立了一种基于时序差分法的DRL算法求解非置换流水车间调度问题模型；文献[16]提出了基于Petri网与DQN算法的柔性制造系统动态调度方法；文献[17]提出了一种基于长短期记忆近端策略优化(LSTM-PPO)强化学习的等效并行机在线调度方法．然而，DRL算法一般采取基于固定神经网络结构的智能体学习，自适应能力较差，将强化学习与进化算法混合可望成为新的研究热点[18]．增强拓扑神经进化(NEAT)算法是一种基于遗传算法优化神经网络的拓扑结构和神经网络的节点权重参数的DRL算法[19]．其不须要设计奖励函数，具有从最小神经网络结构逐渐增长、使用物种形成保护结构创新、不同拓扑交叉等特点，已在函数优化、动态机器人控制等领域得到应用．目前基于NEAT的动态调度研究非常少，文献[19]提出了针对具有与排序相关安装时间的两阶段混合流水车间调度问题的基于NEAT算法的动态调度方法，但是尚未发现针对工件动态到达、处理时间不确定且机器需要弹性预防维护的等效并行机调度问题的相关研究．因此，本研究基于NEAT算法的等效并行机动态调度方法，并通过实例研究与DQN算法，SPT和FIFO等调度规则进行比较分析．1 等效并行机动态调度问题描述本研究的等效并行机动态调度问题可以描述为：将n类动态到达的工件Jj(j=1,2,…,n)安排在m台机器Mi(i=1,2,…,m)上，每类工件的数量为nj，到达时间为rj，加工时间为pj．n类工件的总数量N=n1+n2+…+nn，每个工件Jk(k=1,2,⋯,N)可以在等效并行机中的任何一台机器上加工，加工过程不可中断，一台机器不能同时加工多个工件．考虑生产实际，机器须要弹性预防维护，即机器连续加工的时间不能超过维护门槛值TU，维护时间为t，工件加工时间pj小于门槛值TU．为了最小化在制品库存，目标为最小化平均流程时间．本研究的问题用三域法可以表示为Pm|dynamic,fpm|F，其中：Pm表示等效并行机；dynamic表示动态环境；fpm表示弹性预防维护；F为平均流程时间．假设rk和ck分别为工件Jk的到达时间和完工时间，则该工件的流程时间为fk=ck-rk，平均流程时间F=∑k=1Nfk/N．2 等效并行机动态调度方法在基于强化学习的等效并行机动态调度系统中，强化学习智能体通过与并行机生产车间环境进行交互，在每一个决策时刻根据观察到的当前状态St尝试从行为空间中选择一种行为at，并获取奖励值rtR作为当前调度决策的评价．通过反复与环境交互，尝试各种调度行为，以获取更高的奖励值，实现最优的调度策略．2.1　状态空间状态空间(state)S的界定与智能体寻找的最优调度策略密切相关，是智能体选择调度行为和评估决策奖励的依据[17]．状态空间S应能实时反映调度环境的主要状态特征以及状态的变化，经过强化学习后的智能体能根据当前状态St，选择调度行为at，实现最优的调度策略．等效并行机调度问题的状态包括工件、机器及物流等要素在内的多个特征，实际操作中选取有限个重要特征组合近似描述系统环境．针对等效并行机调度问题的特点，定义状态空间向量S=[qj,Tjr,Ti,Tia,Uir]，从工件、机器、暂存区三个维度描述环境．其中：qj为等待队列中各类工件的数量；Tjr为当前时刻与工件Jj到达时间的时间间隔；Ti为机器Mi正在加工工件的加工时间，若须要维护则增加维护时间t，若机器Mi处于空闲状态，则Ti=0；Tia为机器Mi正在加工工件的已加工时间；Uir为机器Mi在当前时刻剩余的维护门槛值．整个并行机环境状态空间S的维度大小为n+n+m+m+m．2.2　行为空间行为空间(action)即智能体在任何状态下所能选择的行为集合，其设计应该以优化目标为导向，保证最优解所在区域的搜索可达性．根据考虑弹性预防维护的等效并行机动态调度问题的特征和目标，设计了以下的三种行为．行为1 基于SPT规则的最小批浪费机器规则 (modified shortest processing time，MSPT)．步骤1 根据SPT规则从等待队列中选择加工时间最短的工件Jk，若存在多个同类工件，则随机选择其中的一个工件Jk．步骤2 将工件Jk分别尝试安排在空闲机器Ml上，根据机器Ml上的剩余维护门槛值Ulr计算每种安排的批浪费Bwl=Ulr-pk，将工件Jk安排在批浪费最小的机器Mk上，即Mk=min {Bwl}    (Bwl≥0,Bwl≤0);　min {Bwl,Bwl≥0}    (Bwl≥0,Bwl≤0). (1)行为2 基于FIFO规则的最小批浪费机器规则(modified first in first out，MFIFO)．步骤1 根据FIFO规则从等待队列中选择最先到达的工件Jk，若存在多个同时到达的工件，则选择加工时间最短的一个工件Jk．步骤2 按照与行为1步骤2相同的方法，将工件Jk安排在批浪费最小的机器Mk上．行为3 等待，不选择任何工件进行加工．当工件加工完成或新类型工件到达触发调度决策时，强化学习智能体根据环境状态选择三种调度行为中的一种．针对三种特殊情况的调度行为选择说明如下：a. 当等待队列中没有工件时，智能体只能选择行为3；b. 当有新类型工件到达而没有空闲机器时，智能体只能选择行为3；c. 当所有机器都处于空闲状态而等待队列中有工件时，智能体不允许选择行为3．2.3　奖励函数与适应度函数DQN算法须要设计奖励函数(reward)．对于工件Jk的流程时间fk=ck-rk=rk+pk+wk-rk=pk+wk，其中wk表示工件Jk的等待时间．由于加工时间pk在工件到达时已经确定，因此最小化F等同于最小化平均等待时间．针对动态决策的特点，提出在加工时序上按决策时刻分段计算工件的等待时间，如图1所示．10.13245/j.hust.220614.F001图1等待时间分段计算示意图由图1可知：当三元组（St,at,St+1）确定时，St和St+1所对应的两个决策时刻之间的间隔时间Δtt就确定．在间隔时间Δtt中，所有等待加工工件的等待时间和为γt=Δttntw，ntw表示所有等待加工工件的数量．由于智能体以奖励R最大化为目标，而调度目标为最小化F，因此将智能体的即时奖励rtR设置为γt的相反数．整个决策期间总的等待时间TW=γ1+γ2+⋯+γT-1，总奖励R=-(γ1+γ2+⋯+γT-1)，平均等待时间T¯W=TW/N．智能体寻找R最大化的策略等于最小化T¯W的策略，等同于最小化F．NEAT算法通过适应度函数的优化寻找最优调度策略，因此设计NEAT的适应度函数为G=1/F，最大化适应度函数等于最小化平均流程时间．不同于DQN基于状态St选择任一行为at所获得的奖励rtR评估学习在状态St下各行为的优劣，NEAT基于与目标值相关的适应度值，评价当前策略对模型所要优化方向的适应性．2.4　调度方法NEAT是一种遗传算法(GA)与DRL的集成算法，将强化学习的学习能力与遗传算法的搜索能力结合，实现了学习与搜索的平衡．NEAT从一群只有输入层和输出层而无隐藏层节点的种子神经网络开始，通过遗传进化逐步添加隐藏层，优化神经网络结构和参数，最终构造生成最优调度策略的神经网络[19]．基于NEAT强化学习的等效并行机动态调度方法分为三个模块：一是NEAT智能体与并行机环境交互强化学习模块；二是NEAT神经网络进化模块；三是实例测试模块．在模块1中，每一个NEAT智能体分别与等效并行机环境交互，感知实时状态，在每一个决策时刻选择一种调度行为，通过一系列的动态决策，生成调度策略，得到适应度值．在模块2中，神经网络种群采用基于物种相容性阈值的种群分化、五种方式变异（添加连接、添加节点、删除连接、删除节点、变异节点权重率）、交叉以及停滞物种淘汰等方式实现遗传进化，得到适应度值最高的神经网络．模块3使用训练好的神经网络进行实例测试．模块1和模块2的伪代码如下．模块1 智能体与等效并行机环境交互学习输入神经网络 P dot=0 #决策时刻初始化任务序列，状态S0ts=0 #仿真时钟记录时刻While 所有工件加工完毕 or 达到最大决策次数 doIf 新工件到达等待区(t=rj) or工件生产完成(Tia=pj) doIf 工件生产完成 do更新生产序列与工件完工时间End if触发决策时刻，t=t+1更新瞬时状态St输入神经网络P神经网络P输出三种调度行为的值Q1，Q2，Q3按照a=argmax Q选择行为at执行行为atEnd ifEnd whileIf t最大决策次数 do计算神经网络P的适应度值GEnd ifIf t=最大决策次数 do将适应度值G设置为一个无穷小的值End if输出神经网络P的适应度值G模块2　NEAT的神经网络种群进化For 每一代神经网络种群 g doFor 每一个个体神经网络 P do计算神经网络P与种群其他神经网络个体的距离End for按照物种相容性阈值TcP把种群分化成ScP个物种选择复制Ne个直接进入下一代的个体随机选择五种变异方式，生成新的神经网络PnewFor 每一个个体神经网络 Pnew do调用“模块1：智能体与等效并行机环境交互学习”，得到新神经网络Pnew的适应度值End for选择NcP个个体交叉操作，生成子代神经网络PosFor 每一个个体神经网络 Pos do调用“模块1：智能体与等效并行机环境交互学习”，得到子代神经网络Pos的适应度值End for物种内竞争，淘汰物种内适应度值低的个体根据物种停滞进化的代数删除与更新物种End for输出最优个体神经网络Pbest3 实验设计与结果分析使用Spyder软件进行编程，环境为Python3.7，在操作系统Win10，CPU频率为2.9 GHz，内存16 GiB的计算机上运行．分别搭建了等效并行机仿真环境、DQN智能体和NEAT智能体模型．3.1　测试与仿真结果分析实验中的工件加工时间pj和到达时间rj都基于均匀分布生成．按照m，n取值将问题分成小、中和大三种规模，每一种规模随机生成10组实例进行实验(见表1)．NEAT和DQN算法的实验参数见表2．10.13245/j.hust.220614.T002表1并行机问题的仿真实验数据问题mnpjrjnjTUt小规模210U[1，5]U[1，5]U[1，5]102中规模450U[1，5]U[1，5]U[1，5]102大规模8100U[1，10]U[1，10]U[1，10]12410.13245/j.hust.220614.T001表2NEAT与DQN的实验参数问题NEATDQN进化代数种群规模训练回合数小规模10100300中规模10200500大规模103001 000利用实例数据训练NEAT和DQN模型并进行测试，重复5次得到的平均流程时间均值(F¯)、标准差(s)及求解一个完整实例问题所需运行时间的平均值(T¯tR)见表3．10.13245/j.hust.220614.T003表3不同调度方法的实验结果问题SPTFIFODQNNEATF¯±sT¯tR/msF¯±sT¯tR/msF¯±sT¯tR/sF¯±sT¯tR/s小规模25.20±0.000.4033.97±4.090.4044.58±9.8953.8025.48±0.4714.7034.22±0.640.4034.83±3.160.4033.4±5.9744.8025.59±6.2413.7028.38±0.000.4037.75±2.030.4036.64±15.8859.9033.04±9.1116.1024.59±0.720.4028.02±2.810.6027.46±5.8347.4022.59±0.5414.4018.48±0.000.4034.93±6.970.4029.33±13.3249.7021.84±6.3413.4026.62±0.410.6030.72±1.490.4028.43±1.1547.1026.41±0.0015.0050.30±0.000.8049.28±5.910.6053.69±1.8962.0047.95±1.419.9032.16±0.470.6050.53±3.080.4041.35±8.5157.0031.39±0.3517.1039.38±0.570.4045.12±1.200.6040.65±1.8061.2038.76±1.4920.1028.40±0.410.4038.48±5.310.4035.58±7.4050.5027.69±1.2115.30中规模115.43±0.876.77164.47±11.986.57173.74±29.20453.00111.98±3.02346.00174.51±0.938.19216.68±5.487.78212.1±20.30509.00167.50±0.00390.00152.21±0.908.19193.49±4.046.59169.47±19.87461.00146.43±1.46357.00166.63±0.457.78218.78±10.998.19180.34±24.50493.00157.53±0.00395.00151.53±0.936.55199.92±12.698.20162.69±26.25494.00146.87±0.00383.00168.04±1.117.78217.05±17.096.15213.4±38.33511.00155.42±0.00399.00165.96±1.335.98220.48±3.585.99188.91±24.97425.00161.72±1.72315.00165.27±1.116.58213.20±4.838.22208.41±37.13506.00155.97±0.00390.00166.74±2.058.20213.96±16.397.76188.56±27.76526.00158.92±0.00406.00155.40±1.438.17201.75±5.166.15191.27±31.26465.00144.44±1.39369.00大规模982.51±3.8494.401 517.63±21.8698.801 065.37±150.984 530.00901.10±14.784 040.001 215.85±2.32103.001 867.86±43.29100.001 306.36±208.045 550.001 091.74±29.754 570.001 163.38±5.08103.001 731.52±22.7796.801 300.88±199.495 580.001 097.36±4.694 440.001 310.60±3.98103.001 906.75±39.55105.001 427.56±173.505 780.001 255.32±14.554 770.001 291.72±3.51103.001 945.63±30.82102.001 550.83±208.935 380.001 212.59±21.334 510.001 225.69±4.68101.001 640.97±58.76101.001 283.97±112.985 220.001 149.22±7.874 290.001 297.48±4.3695.401 737.56±89.4096.201 341.59±151.095 200.001 237.38±27.424 400.001 283.22±5.46102.001 780.24±159.3596.601 498.72±255.724 890.001 144.57±26.274 900.001 355.37±7.87106.002 040.64±37.68111.001 551.66±216.795 780.001 280.23±13.814 930.001 273.27±2.51117.001 916.00±119.14107.001 246.35±4.866 040.001 188.37±30.254 160.00由表3可知：对于小规模等效并行机调度问题，基于NEAT的方法获得的平均流程时间明显优于基于DQN的方法，以及基于SPT和FIFO规则；随着问题规模变大(即n和m都增加)，基于NEAT的方法的优势更明显．在本研究中，无论是何种规模的问题，基于DQN方法获得的平均流程时间均优于基于FIFO调度规则，但是劣于基于SPT规则，原因是本研究的问题存在稀疏奖励，DQN采取的单步奖励方式易导致解空间搜索不完整，影响解质量．从平均流程时间的标准差来看，基于SPT规则的最小，基于NEAT的次之，基于FIFO规则和基于DQN算法的较大，这表明基于NEAT的方法有足够的稳健性．从运行时间来看，基于FIFO规则和基于SPT规则很小，而基于DQN和NEAT需要更多的运行时间，这是因为强化学习方法须要与等效并行机环境进行多个周期的交互学习之后才进行决策制定．相比于基于DQN的方法，基于NEAT的方法训练时间更短，获得调度解的目标值和稳健性更好．3.2　泛化能力分析泛化能力是基于NEAT算法的动态调度方法的核心能力，只有具备了一定的泛化能力，才具有自适应动态环境的能力．为验证基于NEAT算法的泛化能力，随机生成表1大规模问题的10组实例，对每一组实例分别使用SPT和FIFO规则与训练好的NEAT算法求解10次，求得的平均流程时间如图2所示，针对动态事件的响应时间TsR见表4．10.13245/j.hust.220614.F002图2不同方法的平均流程时间10.13245/j.hust.220614.T004表4不同方法动态事件的响应时间(TsR)对比组数SPTFIFONEAT10.120.1241020.140.1443030.130.1342040.120.1341050.130.1441060.130.1341070.110.1340080.130.1443090.130.14430100.120.13410ms由图2和表4可知：任何一组对比实验中，NEAT找到的目标值都优于SPT和FIFO规则，响应时间也相对较短，表明NEAT调度方法具备较强的泛化能力，训练完毕后的模型不须要再次训练就能对随机变化的动态环境做出自适应反应．4 结语针对考虑弹性预防维护及随机到达和处理时间的等效并行机动态调度问题，提出了基于NEAT算法的调度方法．尽管NEAT算法的采样效率不高，针对本研究的问题，实验结果表明相比传统的DQN方法，NEAT方法能够以更短训练时间获得更优更稳健的调度方案．此外，实验表明经过训练的NEAT模型能够快速高质量求解随机生成的大规模问题实例，具备较好的泛化能力．基于NEAT算法的并行机动态调度方法能够为智能制造背景下的实时自适应调度提供方法参考．本研究提出的等效并行机动态调度问题，优化目标为最小化平均流程时间，设备维护为弹性预防维护，而现实生产环境中的并行机调度问题优化目标和动态约束更多样，且机器设备的故障服从一定的随机分布．因此，在未来的研究中将尝试采用NEAT算法求解更加现实的等效并行机，甚至不相关并行机的动态调度问题．