可重入混合流水车间问题(RHFSP)是一种考虑可重入约束的混合流水车间调度问题(HFSP)，广泛存在于电子制造行业，如印刷电路板生产、半导体晶片制造[1]、半导体组装、薄膜晶体管和液晶显示器制造等．目前，RHFSP研究取得了较大进展，产生了大量研究成果，研究者应用分支定界算法[2]、启发式算法[2]、遗传算法[3]、迭代帕累托贪婪(IPG)算法[4]、教学优化算法(TLBO)[5]、二级递阶过程[6]、多元宇宙优化算法[7]、基于拉格朗日松弛算法的调度方法[8]和改进的离散鲸鱼群算法[9]，对不同RHFSP进行求解．以上这些精确算法、启发式算法和智能优化算法已成功应用于RHFSP的求解．其中，由于对大规模复杂优化问题具有较强的搜索优势，因此智能优化算法能有效解决RHFSP，并取得满意的计算结果．目前，智能算法的应用还不充分，仅应用IPG，TLBO和遗传算法等对问题求解．其他算法如蛙跳算法(SFLA)则很少用来求解RHFSP．SFLA是一种通过观察和模仿青蛙群体行为而形成的智能优化算法[10]，具有收敛速度快及包含局部搜索和全局信息交换的有效算法结构等特点，已广泛应用于各种调度问题优化[11-13]，其中基于SFLA的HFSP研究进展较大，研究者应用SFLA解决了包括低碳HFSP在内的多种HFSP，显示出该算法在求解HFSP方面的显著优势[14-18]．RHFSP和HFSP之间存在较大的相似性，如两个问题都包括调度子问题和机器分配子问题，只是RHFSP的机器分配更复杂．SFLA在HFSP方面的成功应用表明，它是解决RHFSP具有潜在优势的优化方法．针对多目标RHFSP，本研究提出一种协作蛙跳算法(CSFLA)，以最小化最大完成时间和总延迟时间．该算法评价模因组的解质量和进化质量，根据进化质量确定最多两对模因组，在每对的两个模因组之间执行交换搜索次数和搜索能力的动态协作，并运用动态多邻域搜索(DMNS)和自学习过程改善算法性能．通过进行大量仿真实验，实验结果表明：CSFLA的新策略有效，在解决RHFSP方面具有较强的搜索优势．1 问题描述RHFSP描述如下：混合流水车间存在n个工件Ji(i∈{1,2,⋯,n})，具有m个阶段Sj(j∈{1,2,⋯，m})，阶段Sj有jk台同速并行机Mj1,Mj2,⋯,Mjk，至少有一个阶段jk1．工件可以在每个阶段的任一台机器上加工．每个工件按照阶段1，阶段2，⋯，阶段m的顺序依次加工．考虑循环可重入，工件按同样的顺序访问混合流水车间的m个阶段L(L1)次，即重入次数为L-1，且工件须在完成第l次所有m个阶段的加工后才能开始第l+1次的加工．存在如下约束：每一台机器同一时刻最多只能加工一个工件；一个工件同一时间最多也只能由一台机器加工；工件加工不能被中断；所有机器和工件零时刻可用等．在满足所有约束条件的情况下，问题的目标为f1=maxi=1,2,⋯,n{Ci}；(1)f2=∑i=1nmax{Ci-di,0，(2)式中：Ci和di为工件Ji的完成时间和交货期；f1和f2分别为最大完成时间和总延迟时间．帕累托支配是多目标优化问题的基本概念，假设优化问题的目标总数为R，且都是最小化目标，如果解x和y满足∀i∈1,2,⋯,R,fi(x)≤fi(y)且∃i∈1,2,⋯,R,fi(x)fi(y)，那么解x支配y或y被x所支配，计作x≻y．对于一个集合Φ和解x∈Φ，如果x不被Φ中任意其他解所支配，那么x为关于Φ的一个非支配解．2 基于CSFLA的RHFSP通常SFLA的各模因组搜索彼此独立，现有研究很少实现模因组之间的协作[15]．本研究在模因组质量评价基础上，确定最多两对模因组，在每对的两个模因组之间进行协作，进而提出CSFLA．2.1　种群初始化和种群划分文献[3]提出一种编码方法和解码过程．对于具有n个工件、m个阶段和L-1次重入的RHFSP，其解表示为[π1,π2,⋯,πn](πi∈{1,2,⋯,n})．本研究直接采用文献[3]的解码方法和编码过程．随机产生N个初始解，构成初始种群P．种群划分的具体过程描述如下．令集合Θ=P，g=1，重复以下步骤直到Θ为空：a．随机选取两个解x,y∈Θ，若x≻y(y≻x)，则将x(y)放入模因组ℳg，其中ℳg为第g个模因组，且g=1,2,⋯,s；b．若x与y互不支配，则任选其中一个放入ℳg；c．Θ=Θ\选中的解，g=g+1，若gs，则令g=1．2.2　基于协作的模因组搜索模因组搜索是SFLA产生新解的主要步骤，其具体过程如下．确定模因组ℳg内的最优解xb，最差解xw和全局最优解xg，首先利用如下公式产生一个新解xw'，即xw'=xw+rand(xb-xw)，(3)式中rand为区间[0，1]服从均匀分布的随机数．若xw'优于xw，则用新解进行替换xw'；否则利用如下公式产生新解xw'，即xw'=xw+rand(xg-xw)．(4)若xw'优于xw'，则进行替换，否则随机生成一个新解直接替换xw．重复上述步骤直到达到给定的迭代次数μ为止．由于RHFSP的离散特性，直接利用上述公式产生新解无法保证解的合法性，因此采用离散化方法应用SFLA对RHFSP求解．以下详细描述模因组搜索和模因组之间的协作．首先，对模因组ℳg的解质量Sqg和进化质量Eqg定义为Sqg=∑x∈ℳg|{y∈P|y⊁x}|；(5)Eqg=θλ¯/λ+(1-θ)λ˜/λ¯，(6)式中：y⊁x表示解y 不支配解x；λ¯，λ和λ˜分别为模因组ℳg在搜索过程中生成的改进解的数量、所使用的迭代次数和进入外部档案Ψ的改进解的数量，其中λ等于μ或μ/2；θ为实数．若解x在搜索过程中得到改进，即被新解替代，则x为改进解．基于协作的模因组搜索过程描述如下．a．计算每个模因组的解质量，s个模因组根据Sqg进行升序排序，假设Sq1≤Sq2≤⋯≤Sqs．b．令u=v=0，Φ和φ为空集，其中Φ和φ为用来存储模因组序号的集合．c．对于每个模因组ℳg(g=1,2,⋯,s)，令l=1，重复执行如下过程，直到lμ．c1．对ℳg中所有解进行非支配排序[19]，随机选择一个非支配解x∈ℳg和另外一个解y∈ℳg，x≠y，对两个解执行线性顺序交叉(LOX)，产生新解z，若z不受x支配，则z替换x并用z更新Ψ；否则执行DMNS(x)，生成新解z'，若z'不受x支配，则z'替换x并用z'更新Ψ，l=l+1．c2．当l=μ/2时，计算Eqg，若EqgQ且u2，其中Q为进化质量阈值，则Φ=Φ⋃g，u=u+1，且令l=μ+1．d．从模因组ℳ1开始，依次针对每个模因组ℳg，计算其Eqg，并判定条件Eqg≥Q且v2是否成立，若成立，则φ=φ⋃g和v=v+1．e．若u0,v0，则首先针对每个ℳg(g∈φ)，令l=1，重复执行如下过程uμ/(2v)次，即执行步骤c1，并更新解集ζ；然后利用解集ζ更新Φ中的模因组．在以上过程中，Ψ和ζ都用来保留算法搜索过程中产生的非劣解集，当产生的新解z或z'可替换x却不能进入Ψ时，用z或z'更新ζ．Ψ和ζ的更新过程一样：以使用z更新为例，将其加入到Ψ和ζ中，然后进行所有解之间基于帕累托支配的比较，剔除受支配解．提出三种邻域结构𝒩1，𝒩2和𝒩3，分别为调度研究常用的插入、互换和逆序．设置r1,r2,r3用于记录每个邻域结构的有效搜索次数，初始令r1=r2=r3=0．DMNS(x)步骤如下．首先根据三个rδi的降序排序结果，确定邻域结构的使用顺序δ1,δ2,δ3；然后从第1个邻域结构𝒩δ1开始，依次针对每个邻域结构𝒩δi(δi∈1,2,3)，执行如下过程：产生解z∈𝒩δix，若z不受x支配，则z替换x，用z更新Ψ，rδi=rδi+1，同时DMNS的搜索停止．假设rδi的降序排序结果为r1≥r2≥r3，则邻域结构使用顺序为1,2,3．利用解集ζ更新Φ中模因组的过程如下．a．若ζ/u≥τ，则τ¯=τ，其中τ为整数，经过大量实验后确定取值为5；否则τ¯=ζ/u．b．计算Φ中每个模因组的进化质量．c．从进化质量较差的模因组开始，依次对每个模因组ℳg，令w=0，重复执行如下过程直到wτ¯：随机选择解z∈ζ，确定ℳg中rank值最大的解，若z不受该解支配，则用z替代该解，同时将z从集合ζ中剔除，w=w+1．上述模因组搜索过程从解质量最差的模因组开始，集合Φ中的模因组进化质量较差，而集合φ中的模因组进化质量较高．当这个两个集合都非空时，执行模因组间的协作：φ中模因组利用Φ中的模因组未使用的迭代次数进行搜索，中间数据保留在集合ζ中，并利用ζ更新Φ中的模因组．上述协作可有效避免计算资源在进化质量较差的模因组上的浪费，充分利用φ中的模因组的进化优势，从而有助于CSFLA陷入局部最优解并提升搜索效率，协作的劣势在于须额外增加一些计算量来确定参与协作的模因组．2.3　算法描述CSFLA详细步骤描述如下：a．随机生成一个初始种群P；b．将种群划分为s个模因组；c．执行带协作的模因组搜索；d．种群重构；e．运行自学习过程；f．若终止条件得到满足，则输出外部档案；否则转到步骤b．当前运行时间ttmax/2时，执行自学习过程，其描述如下．重复执行以下过程W次：对种群P进行非支配排序，选择其中W个rank值最小的解，然后从这W个解中随机选择一个解x，应用ri值最大的邻域𝒩i，产生新解z，若z不受x支配，则z替换x，用z更新外部档案Ψ，ri=ri+1，其中tmax为最大运行时间．算法的计算复杂度为Ο((1+W)Nn2+NμΤn2)，其中T为步骤b和c中的重复执行次数．文献[15]实现了最好模因组和最差模因组之间的协作，本研究在CSFLA中完成了一种新的协作过程，其最多在两对模因组，即最多2个进化质量较高的模因组和最多2个进化质量较低的模因组之间进行协作，参与协作的模因组数根据进化质量而定．此外，还增加了DMNS和自学习过程．这些策略有助于CSFLA保持较高的种群多样性，减少了陷入局部最优的可能性．3 计算实验为验证CSFLA在求解多目标RHFSP方面的搜索优势，进行了大量实验，这些实验运用Xcode C++编程实现，程序运行环境为16.0 G RAM 2.00 GHz的计算机．3.1　测试实例和对比算法利用文献[3]提供的方法生成实例，其中(α,β)表示交货期宽松度．给出6个实例集，每个实例集由随机生成的20个实例组成，总共120个实例．选用IPG[4]，TLBO[5]和殖民竞争算法(CCA)[20]作为对比算法．IPG和TLBO本身用来求解多目标RHFSP，CCA用来解决HFSP，也可直接优化RHFSP．文献[3-4]给出了三种性能评价指标，即收敛性指标ϒ、分布性指标Δ及支配性指标Ω．本研究使用这些指标评价算法的计算结果．当计算指标时，由于所测试问题的最优帕累托前沿未知，因此本研究将所有算法的全部运行结果放在一起，生成非支配解集作为最优帕累托前沿．3.2　参数设置CSFLA有6个参数：种群规模N，模因组个数s，权值θ，模因组内搜索次数μ，W，终止条件tmax．采用田口实验确定CSFLA的参数，参数水平如表1所示，表中：m为阶段数；n为工件数．10.13245/j.hust.229313.T001表1参数及水平参数因子水平123N6090120s5610tmax0.1mn0.2mn0.3mnμ100120140θ0.250.300.35W456选取一个实例，根据正交表L27(36)，具有每个参数组合的CSFLA随机运行10次，信噪比为-10lg Ω2，由表2可知：当参数设置为N=90，W=5，s=6，μ=120，θ=0.3，tmax=0.2mn时，CSFLA可获得最好的结果，因此直接选择这组参数值．三种对比算法除了终止条件之外，其他参数设置来自文献[4-5，20]，计算实验表明这些算法的参数设置依然有效．10.13245/j.hust.229313.T002表2Ω均值和信噪比主效应排序表参数均值/%信噪比123123N5.005.100.90-19.0-20.8-17.7s3.504.303.50-17.7-21.9-19.8tmax2.504.304.30-20.8-19.2-19.2μ2.505.103.30-20.8-20.8-17.7θ0.906.004.20-17.7-20.0-19.2W1.605.004.30-23.8-19.0-19.33.3　计算结果及分析针对CSFLA，TLBO，IPG，SFLA和CCA，每个算法关于每个实例随机运行20次，算法对比结果如表3~5所示，表中EI表示评价指标．具有同一交货期宽松度的实例有20个，指标min，avg和max[3]分别表示关于20个实例得到的最好解、平均解和最差解．表6描述了所有算法关于各指标95%置信区间的下界值和上界值．10.13245/j.hust.229313.T003表3五种算法对比结果一EI(α，β)=(0.0，0.5)(α，β)=(0.00，0.33)CSFLATLBOIPGCCASFLACSFLATLBOIPGCCASFLAϒavg174.21 548.5228.68 419.2211.4123.01 572.9229.5802.4440.9min0.0241.03.51 061.60.00.0203.619.673.75.3max1 065.23 835.3912.422 579.2922.7789.49 281.01 754.36 547.04 622.1Δavg1.00.90.91.00.90.90.90.90.91.0min0.80.70.60.90.60.60.70.70.80.5max1.31.01.21.01.41.31.01.31.11.4Ω/%avg50.10.032.10.017.850.10.035.80.413.7min10.00.00.00.00.021.10.00.00.00.0max91.30.073.30.060.0100.00.078.97.139.310.13245/j.hust.229313.T004表4五种算法对比结果二EI(α，β)=(0.5，1.0)(α，β)=(0.33，0.67)CSFLATLBOIPGCCASFLACSFLATLBOIPGCCASFLAϒavg83.93 267.3461.355 317.9247.9101.02 106.5273.716 506.6261.6min0.0534.50.010 434.45.30.0266.90.05 798.47.8max316.113 014.63 283.8124 062.02 229.0586.06 783.9890.439 015.81 758.8Δavg0.90.90.91.01.01.00.90.91.01.0min0.60.80.61.00.60.60.80.41.00.8max1.41.01.21.01.21.31.01.11.01.3Ω/%avg55.90.017.00.027.159.70.020.50.019.8min7.70.00.00.00.023.50.00.00.00.0max100.00.084.60.066.7100.00.044.00.055.610.13245/j.hust.229313.T005表5五种算法对比结果三EI(α，β)=(0.0，1.0)(α，β)=(0.67，1.00)CSFLATLBOIPGCCASFLACSFLATLBOIPGCCASFLAϒavg65.43 319.9524.533 943.8161.6109.62 034.9160.458 704.1132.9min0.0774.927.36 528.23.80.0279.10.09 972.20.0max210.015 764.03 038.886 533.6746.5532.27 355.4625.9135 557.0816.1Δavg0.90.91.01.01.00.90.90.81.00.9min0.00.80.71.00.60.30.80.21.00.7max1.31.11.21.01.31.21.11.11.01.4Ω/%avg65.00.012.50.022.554.80.027.80.017.4min25.00.00.00.00.00.00.00.00.00.0max100.00.043.80.066.7100.00.0100.00.060.010.13245/j.hust.229313.T006表6五种算法关于三个指标95%置信区间均值表EICSFLATLBOIPGCCASFLAϒ下界0.00.20.12.5×1040.1上界0.10.30.23.9×1040.2Δ下界0.910.880.850.960.92上界0.980.910.920.980.98Ω/%下界5000015上界600100224如表3~5所示，CSFLA关于指标ϒ和Ω的结果优于SFLA．对于ϒ，CSFLA关于所有实例集所得到的avg至少比SFLA的相应结果小30，max至少小140，CSFLA的收敛性明显优于SFLA．对于Ω，CSFLA关于所有实例集得到的min，avg和max均优于SFLA，且关于6个实例集中的5个，CSFLA的max等于100%，即非支配解集的所有解均由CSFLA产生．对于指标Δ，CSFLA与SFLA的结果相近．通过表6也可以得到同样结论．以上分析表明，协作和自学习等新策略显著改善了CSFLA的收敛性．对比CSFLA和三种对比算法，可以发现CSFLA关于指标ϒ和Ω的计算结果优于其他三种对比算法．对于ϒ，CSFLA关于所有实例集得到的min，avg和max均优于TLBO相应值，且结果相差较大；CSFLA关于所有实例集得到的avg和max都小于IPG和CCA的相应值．对于Ω，CSFLA关于所有实例集得到的min，avg和max均优于其他三种算法．因此，CSFLA的收敛性优于其三种对比算法．对于指标Δ，CSFLA与TLBO，IPG和CCA关于所有实例集得到的结果相似，表明CSFLA与对比算法具有相似的多样性表现．因此，CSFLA在求解多目标RHFSP方面具有较强的搜索优势，通过表6也可得到上述同样结论．模因组间协作、DMNS和自学习过程是CSFLA的新策略，这些策略有助于CSFLA具有更高的种群多样性、减少陷入局部最优的可能性和更强的搜索能力，从而导致CSFLA产生更优的计算结果．因此，CSFLA是一种在求解多目标RHFSP方面具有较强竞争力的算法．4 结语本研究针对RHFSP，提出一种CSFLA，以最小化最大完成时间和总延迟时间，给出了模因组的解质量和进化质量评价方法，根据进化质量确定最多两对模因组，在每对的两个模因组之间执行交换搜索次数和搜索能力的动态协作，并运用DMNS和自学习过程改善算法性能．进行了大量仿真实验，计算结果验证了CSFLA的有效性和搜索优势．