混合流水车间调度问题(hybrid flow shop scheduling problem，HFSP)是一类广泛存在于化工、冶金、纺织、钢铁、半导体等工业过程的典型调度问题，是对流水车间调度问题和并行机调度问题的综合[1]．随着经济全球化的不断深入发展和市场竞争的日益加剧，企业之间的并购、合作生产和协作生产越来越多，分布式生产成为一种常见的生产制造模式[2]．在分布式制造环境下，多个工厂的调度都包含混合流水车间调度问题，这类问题称为分布式混合流水车间调度问题(distributed hybrid flow shop scheduling problem，DHFSP)．分布式混合流水车间调度问题相关研究已取得了一些进展．对于以最小化最大完成时间为目标的分布式混合流水车间调度问题，研究者应用贪婪算法[3]、蛙跳算法[4]、头脑风暴算法[5]等智能优化算法求解[6-8]．对于多目标分布式混合流水车间调度问题，常用的算法有变邻域搜索[9]、改进的蛙跳算法(shuffled frog leaping algorithm，SFLA)[10]和改进的教学优化算法[11]等智能优化算法[12-13]．装配调度问题和分布式装配调度问题已受到一定关注[14]．然而，现有研究主要考虑加工和装配的两阶段装配调度问题，对于同时考虑加工、运输和装配的三阶段装配调度问题研究较少，更不涉及分布式装配调度问题．实际装配生产过程往往包含加工、运输和装配三个阶段，因此很有必要研究考虑运输的分布式装配混合流水车间调度问题(distributed assembly hybrid flow shop scheduling problem，DAHFSP)．改进的蛙跳算法是一种通过观察和模仿青蛙群体行为而形成的智能优化算法，该算法由Eusuff等[15]提出．因其概念简单、参数少、计算速度快且全局寻优能力强等特点，已广泛应用于各种优化问题[1]，并且已被验证可以很好地解决分布式混合流水车间调度问题．改进的蛙跳算法包含多种搜索策略，现有研究通过各种方法探索搜索策略的使用方式，但主要以经验为主，算法本身并不能智能选择最合适的搜索策略．Q-学习算法是一种最常用的无模型强化学习算法[16]，Q-学习算法通过强化信号或奖励与复杂的环境进行交互，从而选择最佳的动作．基于Q-学习的智能优化算法已成功应用于求解车间调度问题，并获得了成功[17]．因此，有必要研究如何将Q-学习算法与改进的蛙跳算法结合，以更好地解决分布式装配混合流水车间调度问题．基于以上分析，本研究分析分布式装配混合流水车间调度问题，并提出基于Q-学习的蛙跳算法(shuffled frog leaping algorithm with Q-learning，QSFLA)解决该问题．该算法设计了多种不同的邻域搜索结构、全局搜索方法和解的接收准则，并以此构成了动作集；给出了种群的评价方式，从而定义了种群的状态集．在模因组搜索过程中，根据种群的不同状态动态选择合适动作，从而实现搜索策略的选择；最后通过实验验证了算法的有效性．1 问题描述分布式装配混合流水车间调度问题描述如下：存在n个工件J1,J2,…,Jn，工件Ji的部件集合为Ψi．所有工件的总部件数h=∑i=1n|Ψi|．假设部件1,2,…,|Ψ1|属于工件1，工件Ji的部件为|Ψi-1|+1,|Ψi-1|+2,…,|Ψi-1|+|Ψi|，i1．存在F个同构工厂，每个工厂为一个装配混合流水车间，每个工厂包含加工、运输和装配三个过程．存在S个加工阶段，第l个加工阶段由ml台同速并行机组成．Mflk为工厂f第l个加工阶段的第k台机器．每个工厂f包含一台运输机器MfT和一台装配机器MfA．部件首先分配到工厂f完成加工，在属于同一工件的部件全部加工完成后，这些部件由运输机MfT收集并运送到装配机MfA处装配．pjl为部件j在第l阶段的加工时间，tit和tia分别为工件Ji的运输时间和装配时间，di为工件Ji的交货期．考虑运输和装配的分布式混合流水车间调度问题由工厂分配、机器分配和调度三个子问题组成，三个子问题之间存在强耦合关系．另外，调度子问题还包含工件调度和部件调度．工件调度决定工件的加工顺序，部件调度确定部件的加工顺序．子问题的数量和强耦合关系决定了获得精确解是极难的，因此，必须设计合理的方案简化处理子问题，并利用群智能算法获得近似解．在满足所有约束的条件下所有工件的总延迟时间T=∑i=1nmax{Ci-di,0}，(1)式中Ci为工件Ji的完成时间．2 基于Q-学习的蛙跳算法2.1　蛙跳算法蛙跳算法主要步骤包括种群初始化、种群划分、模因组搜索和种群重构．蛙跳算法的初始种群P由N个初始解构成，每个解表示一个青蛙的位置．种群划分是将整个种群划分为s个模因组，描述如下：a. 种群中的个体按照适应度值降序排序，假设fit(x1)≥fit(x2)≥…≥fit(xN)．b. 依次将所有解分配到s个模因组ℳ1,ℳ2,⋯,ℳs，解xk分配到模因组ℳ(k-1)(mods)+1，k(mods)为k/s的余数，fit(xk)为种群中第k个解的适应度值．有z=xw+α(xb-xw); (2)z=xw+α(xg-xw), (3)式中：xw,xb,xg分别为模因组的最差解、最好解及种群的最好解；α为[0，1]中服从均匀分布的随机数．模因组的搜索过程如下．a. 令i=1．b. 令j=1．c. 选择模因组ℳi中的最差解xw，利用式(1)产生新解z，若fit(z)fit(xw)，则使用z替换xw；否则，利用式(2)产生新解z，若fit(z)fit(xw)，则利用z代替xw，否则随机产生解z替换xw．d. j=j+1，若j≤μ，则转到步骤c．e. i=i+1，若i≤s，则转到步骤b，否则输出结果．模因组重构将所有进化后的模因组合在一起，得到新种群．2.2　Q-学习算法马尔科夫决策过程是基本的强化学习模型，可定义为四元组S,A,Re,Pr，其中：S为状态空间，包含agent可能感知到的所有环境状态；A为包含agent在每种状态下可执行的动作空间；Re为回报函数；Pr为状态转移概率．agent和环境的交互过程如图1所示．10.13245/j.hust.239412.F001图1强化学习的框架Q-学习算法是一种最常用的无模型强化学习算法，它的最简单的形式为        Q(st,at)←Q(st,at)+α(rt+1+γmaxaQ(st+1,a)-Q(st,at)), (4)式中：α为学习比例；γ为折扣因子；rt+1为在环境状态为st时执行动作at获得的回报；maxaQ(st+1,a)为Q-表中状态为st+1时最大的Q值．动作选择依赖于Q值．最初，所有Q值都是0，说明agent没有任何可供使用的学习经验．ε-greedy选择是一种常用的动作选择策略，其描述如下：如果随机数ε，随机选择一个动作；否则，选择当前状态下Q值最大的动作a，即a=maxa'Q(st,a')，其中随机数为[0，1]中服从均匀分布的随机数．2.3　编码和解码采用三串编码方式表达一个解．对于一个具有n个工件和F个工厂且考虑运输和装配的分布式混合流水车间调度问题，编码方案包括三个部分：工厂分配串[θ1,θ2,…,θn]，工件排列[π1,π2，…,πn]和部件排列[η1,…,η|Ψ1|,η|Ψ1|+1,…,ηH2,…,ηHP-1+1,…,ηh]，其中H0=0；Hg=∑i=1gΨi,g0；πi∈1,2,…,n；ηw为工件Ji的一个部件，Hi-1+1≤w≤Hi；θi∈{1,2,…,F}．工件Ji的部件为Hi-1+1,Hi-1+2,…,Hi，Hi为前i个产品的总部件数，ηHi-1+1,…,ηHi为这些部件的排列．解码过程如下：a. 根据工厂分配串将工件分配到各个工厂，由工件排列和部件排列确定每个工厂中工件和部件的排列；b. 根据工件和部件的排列，依次执行加工、运输和装配．当部件在第l个阶段加工时，选择ml台并行机中可利用时间最小的机器．2.4　种群初始化和邻域搜索初始种群P由随机产生的N个解组成，所有解都满足编码中要求，每个解都是可行解．动作at由全局搜索、邻域搜索和解的接收准则组成，首先介绍包含3种交叉操作的全局搜索和包含12种邻域结构的邻域搜索．应用12种邻域结构𝒩1～𝒩12．𝒩1的具体过程如下：随机选择工件Ji和Jg(θg=θi)，假设i=πv,g=πu,vu，将i插入到工件排列的位置u；𝒩2与𝒩1类似，区别为θg≠θi，令θi=θg，即将工件Ji从其当前工厂转移到工件Jg所在的工厂．𝒩3和𝒩1的区别在于交换工件Ji和Jg，而不是插入．𝒩4的具体步骤如下：随机选择工件Ji和Jg (θg≠θi)，交换工件排列中的Ji和Jg，交换工厂分配串中的θi和θg．𝒩5描述如下：随机选择一个工件Ji，随机选择工件Ji的部件ηv和ηu(vu)，将ηv插入到部件排列的位置u．𝒩6与𝒩5类似，区别在于交换ηv和ηu．图2给出了6个邻域结构的过程．10.13245/j.hust.239412.F002图26个邻域结构的过程假设工厂f是延迟时间最大的工厂，在邻域结构𝒩1中增加条件θg=θi=f可得到𝒩7．𝒩8的具体过程如下：随机选择工件Ji(θi=f)和工件Jg (θg≠f)，将工件Ji插入到工件Jg在工件排列中的位置，令θi=θg．𝒩9通过交换工件排列中属于同一工厂f的两个不同工件以产生新解．𝒩10和𝒩8类似，区别为交换工件排列中的工件Ji和Jg．当𝒩5中工件Ji的选择限制在工厂f时可得到𝒩11．𝒩12和𝒩6类似，不同之处为从工厂f选择Ji．当上述工厂f的最大延迟时间减少时，最大延迟时间很可能会降低．𝒩7～𝒩12与工件和部件的移动有关，如工厂f内的插入和互换操作，工厂f和其他工厂间的插入和互换操作．利用上述邻域结构，设计两种邻域搜索NS1和NS2．NS1描述如下：对于解x，令b=1，w=0，重复以下步骤直到b=7或w=1；产生新解y∈𝒩b(x)，若y优于x，则x=y，w=1，并利用y替换xg；否则，令b=b+1．NS2与NS1的步骤一样，只不过初始条件设为b=7，w=0，终止条件设为b=13或w=1．其中y替换xg的条件是y优于xg．对于NS1中的邻域结构，工厂选择是随机的．NS2的𝒩7～𝒩12中选择的工厂为延迟时间最大的工厂．2.5　全局搜索一个解由三个串组成，针对解x,z，设计三种交叉操作．解z的工件排列中位置k和l之间的工件的集合定义为Θklz，kl．工件排列的交叉操作描述如下：对于解x,z，随机产生k,l,1≤kl≤n，确定Θklz；使解x中属于Θklz的工件按照这些工件在解z中的顺序排列．部件排列的交叉过程如下：对于解x,z，随机确定k,l, 1≤kl≤n和Θklz，使解x中属于Θklz的工件的部件，按照这些部件在解z中的顺序排列．工厂分配串的交叉操作步骤如下：在Θklz确定以后，使解x中属于Θklz的工件对应的工厂分配串的值与z相同．解x,z之间的全局搜索描述如下：随机选择一个交叉操作，对x,z执行交叉操作产生一个新解．三个交叉操作的过程如图3所示．10.13245/j.hust.239412.F003图3三个交叉操作的过程2.6　Q-学习过程Q-学习算法主要包括状态st、动作at、回报rt和动作选择策略．为了实现Q-学习过程，环境状态由种群评估结果确定，根据全局搜索、邻域搜索和解的接受准则设计动作，并重新定义回报的计算方式．种群P的状态由种群最好解xg的变化情况和种群的离散程度Dg决定，Dg=∑i=1NCmaxi,g-C¯maxg2/N1/2/C¯maxg，(5)式中：Cmaxi,g为种群P在第g代的第i个解的总延迟时间；C¯maxg为P在第g代所有解的平均总延迟时间．Im用于描述xg的改进情况，若xg在当代得到了改进，则Im=1；否则，Im=0．ΔD=Dg-Dg-1，Dg通过对第g代的种群P利用式(5)计算得到．由于利用贪婪方式更新xg，种群P的xg不会变差，只存在Im=0和Im=1两种情况．随着种群P从第g-1代进化到第g代，ΔD可能会改善、恶化或保持不变，ΔD存在三种可能，这样由于两个指标的组合，因此存在6种状态，描述如下：状态1为Im=1且ΔD0；状态2为Im=1且ΔD=0；状态3为Im=1且ΔD0；状态4为Im=0且 ΔD0；状态5为Im=0且ΔD=0；状态6为Im=0且ΔD0；通常利用贪婪接收准则确定能否接收新解．动作集A包含4种动作，每种动作表示一种模因组搜索策略．A=[a(1),a(2),a(3),a(4)]，全局搜索过程采用贪婪接受准则或概率接收准则，NS1和NS2中始终使用贪婪接受准则．当模因组ℳl执行动作a(i)时，首先选择ℳl中的两个最好解xb1和xb2，假设xb2优于xb1．动作a(1)描述如下：由xb1和xb2的全局搜索产生新解z，应用贪婪接收准则确定z能否替代xb1，若不能则利用xb1和xg的全局搜索产生新解z；利用贪婪接收准则确定新解z能否替换xb1，若不能，对xb1执行NS1．动作a(2)与动作a(1)的步骤相同，只是利用NS2代替NS1．动作a(3)和a(4)与动作a(1)和a(2)的不同之处在于全局搜索采用概率接收准则．模因组搜索过程中，一旦选择一个动作，该动作作为模因组的搜索策略一直存在直到模因组搜索次数μ达到．6种状态的序号为1～6．显然，状态1最好，状态6最差．因为状态1中不仅xg得到了改善，而且种群P的离散程度也增加了，而状态6正好相反，状态的序号越小说明种群的状态越好．因此，当模因组搜索过程采用动作a(i)时，如果状态从l转移到w,wl，那么该动作就会获得奖励；如果状态从l转移到w，那么该动作就会得到惩罚．回报函数定义为：rt+1=l-w，其中st=l,st+1=w．动作选择采用ε-greedy选择策略．假设当前状态St=2，下一个状态St+1=3，当前动作at=2，α=0.1，γ=0.9，此时，回报函数rt+1=-1．在Q-表更新后，根据式(4)可知Q(2,2)=8.820．2.7　算法描述基于Q-学习的蛙跳算法是改进的蛙跳算法和Q-学习的集成．初始种群P随机产生，然后划分为s个模因组．模因组搜索过程利用Q-学习动态选择搜索策略．模因组搜索结束后，利用所有模因重新构建种群P．基于Q-学习的蛙跳算法描述如下：a. 随机产生包含N个解的种群P，Q-表的初始值设为0，g=1；b. 执行种群划分；c. 利用Q-学习动态选择一个动作，根据所选的动作确定使用的邻域搜索和全局搜索；d. 根据选择的动作，对每一个模因组执行模因组搜索；e. 进行种群重构，更新Q-表，g=g+1；f. 若不满足终止条件，则重复步骤b～e，否则输出结果．现有研究很少集成改进的蛙跳算法和Q-学习，本研究给出一种有效的方法集成改进的蛙跳算法与Q-学习，以动态地选择搜索策略，其主要特征如下：a. 构建了包含6个状态和4个动作的Q-学习算法，其中状态根据种群的评估结果确定，动作由不同的全局搜索、邻域搜索和解的接收准则组成；b. 该算法与通常只采用一种搜索策略的改进的蛙跳算法不同，应用了4种搜索策略，且运用Q-学习算法动态地选择搜索策略，可提高算法的搜索能力．3 计算实验所有实验利用Microsoft Visual C++ 2019编程实现并在8.0 GiB RAM 2.4 GHz CPU 个人电脑运行．3.1　测试实例和对比算法为了检验基于Q-学习的蛙跳算法在求解考虑运输和装配的分布式混合流水车间调度问题方面的性能，选用80个实例，其中pjl∈[1,100]，tit∈[1,100]，tia∈[1,100]，|Ψi|∈[2,5]，ml∈[2,5]．以上所有数据都是整数，实例表示为n×F×S．选择竞争文化基因算法(competitive memetic algorithm，CMA)[18]、混合粒子群优化(hybrid particle swarm optimization，HPSO)算法[19]、混合变邻域搜索(hybrid variable neighbourhood search，HVNS)算法[19]、改进的离散布谷鸟优化算法(improved discrete cuckoo optimization algorithm，IDCOA)[20]和基本的改进的蛙跳算法作为对比算法．3.2　参数设置基于Q-学习的蛙跳算法有7个主要参数：N， s，μ，α，γ，ε和终止条件．基于Q-学习的蛙跳算法、改进的蛙跳算法和四种对比算法都可以在CPU运行0.1×N×s后收敛，故终止条件设置为0.1×N×s．采用田口方法确定基于Q-学习的蛙跳算法其他参数的设定值，均值和信噪比的主效应图如图4所示．由图4可知参数最佳设定值为：N=60，s=6，μ=50，α=0.1，γ=0.9，ε=0.1．10.13245/j.hust.239412.F004图4均值和信噪比的主效应图四种对比算法除终止条件外，直接使用文献给出的参数设定值．改进的蛙跳算法包含N，s，μ三个参数，这些参数与基于Q-学习的蛙跳算法相同．通过实验可知，四种对比算法和改进的蛙跳算法使用这些设定值在大多数实例中获得了最好的实验结果，因此这些算法的参数设定合理．3.3　Q-学习的作用基于Q-学习的蛙跳算法和改进的蛙跳算法在每个实例独立运行10次，可以得到两种算法的计算结果，TMAX为10次运行所得到的最差精英解，TMIN为10次运行所得到的最好精英解，TAVG为10个精英解的平均值，图5为所有算法(包括基于Q-学习的蛙跳算法和改进的蛙跳算法)的箱线图．10.13245/j.hust.239412.F005图5六种算法计算结果的箱线图DMIN=[(TMIN-TMIN*)/TMIN*]×100%，式中TMIN*为所有算法获得的最小TMIN，当TMIN替换成TAVG或TMAX时，可得到DAVG或DMAX．基于Q-学习的蛙跳算法在所有例子中得到了比改进的蛙跳算法更小的TMIN，TAVG和TMAX，显然基于Q-学习的蛙跳算法的性能优于改进的蛙跳算法．这也表明基于Q-学习的蛙跳算法具有显著优势，说明Q-学习算法显著改善了基于Q-学习的蛙跳算法的搜索性能，Q-学习算法的引入合理有效．3.4　结果和分析四种对比算法用于所有实例独立运行10次，可以得到TMIN，TAVG和TMAX的计算结果，统计结果如图5所示．基于Q-学习的蛙跳算法在至少96个例子获得了比竞争文化基因算法更小的TMIN，TAVG和TMAX，且在所有实例所得到的TMIN和TAVG均优于竞争文化基因算法的相应结果；与混合粒子群优化算法相比，基于Q-学习的蛙跳算法在所有112个例子中都获得了更好的TMIN，在101个例子中得到了更小的TAVG，在98个例子中取得了更低的TMAX；与混合变邻域搜索算法相比，基于Q-学习的蛙跳算法的优势也比较明显，在超过99个例子中，基于Q-学习的蛙跳算法获得了比混合变邻域搜索算法更小的TMIN，TAVG和TMAX；基于Q-学习的蛙跳算法相比于改进的离散布谷鸟优化算法的优势更加明显，只在112个实例的5个实例中获得了比改进的离散布谷鸟优化算法更大的TAVG，在7个实例中得到了更高的TMAX．因此，基于Q-学习的蛙跳算法的性能明显优于四种对比算法．从图5中可以看出：基于Q-学习的蛙跳算法对于所有实例的DMIN均为0，所获得的DAVG和DMAX明显小于对比算法，这表明与对比算法相比，基于Q-学习的蛙跳算法得到的计算结果质量更高、稳定性更好且鲁棒性更优．基于Q-学习的蛙跳算法的优异性能主要来自于Q-学习过程，利用Q-学习算法为模因组动态选择搜索策略，提高了算法的探索能力．另外，每一种搜索策略结合了全局搜索和邻域搜索，使算法的全局搜索能力和局部搜索能力得到了平衡．因此，基于Q-学习的蛙跳算法是求解考虑运输和装配分布式混合流水车间调度问题的一种非常有竞争力的方法．4 结语分布式混合流水车间调度问题是混合流水车间调度问题在分布式制造环境下的扩展，近年来已受到广泛关注．然而，对分布式混合流水车间调度问题的研究未考虑运输和装配等在实际生产过程中常见的约束．本研究分析了考虑运输和装配的分布式混合流水车间调度问题，提出结合Q-学习的蛙跳算法解决该问题，给出了问题的一种三串表示方法．根据问题的特征，设计了基于全局搜索、邻域搜索和解的接收准则相结合组成的4种动作；基于种群的评价，给出了种群的6种状态，并给出一种新的回报函数．构建了Q-学习过程，根据种群的不同状态，动态选择模因组的搜索策略；将Q学习引入群智能优化算法中，以提高算法的性能．计算结果表明：Q-学习过程在基于Q-学习的蛙跳算法中起到了积极的效果，基于Q-学习的蛙跳算法为考虑运输和装配的分布式混合流水车间调度问题提供了很好的结果．强化学习与智能优化算法结合是提高算法搜索性能的一种新途径，未来将重点研究强化学习和智能优化算法的结合方式，并用于解决一些常见的车间调度问题．另外，其他分布式调度问题，如分布式并行机调度问题、分布式作业车间调度问题、分布式流水车间调度问题等，也是未来研究的重点方向．