基于改进多种群候鸟迁徙算法的混合流水车间调度

张素君, 杨文强, 顾幸生

(1. 河南科技学院 机电学院, 河南 新乡 453003; 2. 华东理工大学 能源化工过程智能制造教育部重点实验室, 上海 200237)

带顺序依赖准备时间的混合流水车间调度[1](HFS-SDST)问题是混合流水车间调度[2](HFS)问题的一个重要分支.HFS-SDST广泛存在于钢铁、电子、化工、流程工业及离散智能制造等调度问题中[2],70%的实际工业过程需要考虑SDST,若不能正确处理该问题,将使用超过20%的机器容量[1],而且考虑SDST时,92%的订单会达到交货期[3].因此,虽然在HFS问题中考虑SDST更贴近生产实际,但建模难度会增加,设计调度算法时考虑的约束更多,寻找全局最优解更加困难[4].

HFS-SDST问题的调度涉及工件的排序和机器分配,是典型的组合优化问题,已经证明HFS-SDST是非确定性多项式难(NP-hard)的问题[5].因此,利用精确算法理论上可以求解,但随着问题规模的增大出现组合爆炸问题,几乎不可能在合理的时间内找到最优调度解,难以满足实际生产需要.启发式算法依据某些规则对调度解进行构造,大大缩短了寻找调度解的时间,Moccellin等[6]提出基于最短处理时间(SPT)和最长处理时间(LPT)规则的启发式算法,求解针对机器阻塞、顺序依赖、顺序独立准备时间的HFS问题,结果证明了对于HFS-SDST问题,最长处理和准备时间(LPS)规则优于其他规则.然而,对于较大规模的复杂调度问题,启发式规则构造的调度解质量不高,因此,采用智能优化算法为快速求解组合优化问题提供了可能;文献[7]中提出基于超启发式学习增强的迭代贪心算法求解HFS-SDST问题,采用该算法对一个实际生产实例的设备数据进行求解可以达到较好的效果;周炳海等[8]提出蚁群算法求解双目标HFS问题,但该算法仅限于求解较小规模的问题;文献[9]中提出基于代理的改进遗传算法,融合了多智能体和遗传算法的优点求解HFS-SDST问题,并通过实验得到一些算例的下限值;Pan等[10]列出6个局部搜索算法和3个群智能优化算法,其中3个群智能算法为改进的果蝇优化算法(FOA)、改进的候鸟迁徙优化(IMBO)和离散人工蜂群(DABC)算法,并给出一种协同优化策略,通过仿真测试对比可知,对于大部分算例,DABC优于其他8个算法;Tian等[11]提出基于pareto的自适应变邻域搜索算法,证明了变邻域搜索求解HFS-SDST问题的有效性;Khare等[12]提出了混合松鼠搜索、反向鲸鱼及离散灰狼3个群智能算法,并且为了提高算法的性能,在松鼠算法中引入变邻域搜索和混合局部搜索,在鲸鱼算法中引入反向学习策略,优化目标为总提早和拖期.文献[10,12]中为群智能算法求解HFS-SDST问题的有效性提供了依据.虽然针对HFS-SDST问题已有一些研究,但算法方面还未形成系统理论成果,因此,研究更高性能的调度算法具有深刻的理论和实际应用意义.

Duman等[13]在2012年提出的候鸟迁徙优化(MBO)算法,因调整参数少、结构简单等优点,得到了广泛应用,但该算法容易早熟收敛且不能直接应用于组合优化问题,因此,Pan等[14]和Han等[15]分别提出改进的离散MBO算法求解HFS问题,且在此基础上,Pan等[10]对文献[14]中提出的IMBO进行了改进.Sioud等[3]针对带SDST的置换流水车间调度(PFSP)问题提出增强的候鸟迁徙优化(EMBO)算法,利用禁忌表控制混合邻域策略产生邻域解的多样性;Meng等[16]和汤洪涛等[17]分别提出采用和声搜索(HS)策略以及变邻域搜索策略产生邻域解的离散MBO,求解批量流车间调度问题.然而,MBO算法是一种邻域搜索算法,因此邻域的选择对算法的优化效果影响较大,而变邻域搜索是一种可以系统地利用邻域变化思想的算法;Bez等[18]提出结合贪心随机自适应力(GRASP)和变邻域搜索的混合算法求解带SDST的平行机调度问题.为了改善MBO的早熟收敛问题,文献[3]中采用重置机制提高算法的全局搜索能力,此外,采用多种群智能优化算法为提高该能力提供了另一种思路;Han等[19]提出改进的多种群离散差分进化算法,求解多用途批处理设备调度问题;Gao等[20]提出一种动态洗牌的多微种群候鸟迁徙优化(SM2-MBO)算法,利用多微子种群并行搜索,求解多资源约束柔性作业车间调度问题,但该算法不能在子种群信息交互时产生更好新个体;Tongur等[21]提出了基于粒子群优化(PSO)算法的改进多种群MBO(IMFMBO)算法,在多种群MBO框架下,通过另一种算法促进子种群之间的信息交互,提高算法的全局搜索能力.因此,本文结合候鸟迁徙优化、子种群交互策略和多种群并行搜索思想,提出IMMBO算法求解HFS-SDST问题.

1 HFS-SDST问题

HFS-SDST问题描述如下:n个工件在m个阶段的流水线上加工,每个工件j(j=1, 2, …,n)依次按相同的顺序通过阶段k(k=1, 2, …,m),m个阶段至少有一个阶段的机器数量Mk>1,每个工件可以在阶段k的任意一台机器上加工.加工过程满足假设:①任意时刻每个工件只能在一台机器上加工;②每台机器同一时间只能加工一个工件;③工件在某阶段机器上一旦开始加工不允许中断.优化目标为通过确定工件的加工顺序以及每阶段工件在机器上的分配情况,使工件的最大加工完成时间(makespan)即Cmax最小.

考虑SDST,n个工件在第1阶段机器上的加工顺序一旦确定,依据工件在可用机器上的加工完成时间最短的标准,工件在后续阶段机器上的加工顺序会相应确定.若工件在第1阶段的加工顺序为π,π=(π1,π2, …,πn),则给出如下HFS-SDST问题的数学模型.

若第1阶段和阶段k(k=2, 3, …,m)的第i(i=1, 2, …,Mk)台机器没有加工过其他工件,则工件πj的完成时间Ck, πj, i分别由下式给出:

Ck, πj, i=Sk, πj, πj+pk, πj,k=1

(1)

Ck, πj, i=max{Sk, πj, πj,Ck-1, πj}+pk, πj,

k=2,…,m

(2)

式中:Ck, πj, i和pk, πj分别为工件πj在阶段k的第i台机器上的作业完成时间和作业时间;Sk, πj, πj为工件πj在k阶段的准备时间.

如果阶段k的第i台机器加工πj前已经加工过其他工件,则工件πj的加工完成时间为

Ck, πj, i=

max{Ck,πτk, i+Sk,πτk, i, πj,Ck-1, πj}+pk, πj

(3)

式中:Ck,πτk, i为阶段k的第i台机器在加工πj的前1个工件πτk, i的加工完成时间;Sk,πτk, i, πj为πj在阶段k的准备时间.工件πj在阶段k的机器选择依据πj在该阶段的作业完成时间最短的原则,即πj在阶段k加工完成时间最短的机器为

其作业完成时间为

Ck, πj=minCk, πj, i

(4)

最后一个工件在最后阶段机器上的加工完成时间的最大值为

(5)

2 IMMBO

IMMBO算法把初始化种群分成多个子种群,各个子种群利用MBO机制平行搜索,子种群之间利用离散鲸鱼优化策略对各子种群的领飞鸟优化完成信息交互;同时设计局部搜索增强和种群多样化控制机制提高算法的探索和开发能力,IMMBO算法框架如下.

步骤1设置算法相关参数.利用MNEH算法初始化种群,并把最好的1/3 分到每个子种群作为其领飞鸟,剩下2/3个体随机分配到各子种群,每个子种群包括两个跟飞鸟.

步骤2保存本代最优个体.

步骤3子种群领飞鸟利用串行变邻域搜索策略产生邻域个体,若邻域个体中最好的优于领飞鸟,替换领飞鸟.

步骤4子种群跟飞鸟利用并行变邻域搜索策略产生邻域个体,若邻域个体中最好的优于该跟飞鸟,替换跟飞鸟,若跟飞鸟优于本群的领飞鸟,二者交换.

步骤5检查是否达到巡回次数,若未达到,转到步骤3,否则转到步骤6.

步骤6各子种群领飞鸟利用离散鲸鱼优化策略进行交叉,完成子种群之间的信息交互.

步骤7对种群中的最优个体执行局部搜索(LS).

步骤8更新各子种群领飞鸟的年龄变量,若某子种群的领飞鸟年龄达到设定年龄限制,启动多样化控制机制,重新产生一个个体放入种群.

步骤9判断算法迭代是否达到最大迭代次数,若未达到,转到步骤2,否则,算法结束,输出最优个体及其Cmax值.

2.1 编码和解码

连续的优化算法不能直接应用于组合优化问题HFS-SDST,故需要设计离散形式的优化算法,而设计离散优化算法需要对算法中个体进行离散编码和解码.针对HFS问题,常用的编码和解码方法有矩阵和向量两种,本文在考虑SDST的同时采用向量编码,即基于所有工件的一个调度顺序对个体编码[12],然后,将工件按照排列的顺序分配到第1阶段的空闲机器上加工.解码方法为:考虑准备时间,工件在第1阶段按照编码顺序加工,第k(k=2, …,m)阶段的工件加工顺序则依据在该阶段加工完成时间最短的原则,重新排列得到工件在阶段k的加工顺序.

2.2 初始化种群

(1) 计算每个工件的ψj,对ψj升序排列,得到工件在第1阶段的排序π=(π1,π2, …,πn).

(2) 依据第1阶段的机器数M1,把π分成两个子序列π1=(π1,π2, …,πM1)和π2=(πM1+1,πM1+2, …,πn),π=π1∪π2.

(3) 随机调换π2中工件的顺序得到π2′,与π1合并得到一个新的第1阶段工件的排序π′=π1∪π2′.

(4) 重复(3), 得到与种群规模相同的工件在第 1 阶段机器上的加工顺序,并分别求出其Cmax.

针对初始种群,按种群中个体的Cmax值升序排列,其中前1/3分配到各个子种群,作为领飞鸟;其余2/3随机分配到各子种群,作为跟飞鸟.子种群的规模为3,即1个领飞鸟和2个跟飞鸟.

2.3 子种群领飞鸟进化

领飞鸟是一个子种群中最好的个体,领飞鸟的质量决定子种群的搜索方向.各子种群中的领飞鸟通过其邻域个体更新.文献[22]中已经证明插入、交换及迭代贪婪(IG)算法中的破坏重建(DC)操作在流水车间调度问题中是较好的邻域解产生策略,因此,领飞鸟的邻域个体由插入、交换以及DC串联起来的串行变邻域搜索策略产生,即依次执行插入、交换和DC,只要采用某一策略能够产生更好的邻域个体就继续使用,反之,则执行下一个策略,直到结束.

串行变邻域策略伪代码如下:

输入π; 输出π

k=1

whilek<=3

switchk

case 1 随机选择位置r1上的工件,1≤r1≤n,插入到π的所有可能位置,并依据指标Cmax,找到最好的π′

如果Cmax(π′)

π=π′,k=1

否则

k=k+1

case 2 随机选择位置r1上的工件,1≤r1≤n,与π的其他所有位置上工件交换,并依据指标Cmax,找到最好的π′

如果Cmax(π′)

π=π′,k=2

否则

k=k+1

case 3 对π执行破坏重建(DC),得到π′

如果Cmax(π′)

π=π′,k=3

否则

k=k+1

End switch

End while

2.4 子种群跟飞鸟进化

产生跟飞鸟邻域个体的策略,要兼具邻域个体的质量和多样性,因此子种群中的跟飞鸟领域个体采用并行变邻域搜索产生,即按照一定概率选择插入或交换两种邻域之一产生跟飞鸟邻域个体.在生产调度问题中,插入更易产生较好的邻域个体,因此,设置选择插入邻域结构的概率设为Pm=0.6,即产生一个随机数r,r∈[0, 1],如果r

2.5 巡回

多个子种群领飞鸟和跟飞鸟依据2.3节和2.4节循环G次,利用其邻域解,完成领飞鸟和跟飞鸟的充分开发.

2.6 子种群信息交互

IMMBO算法采用多种群并行搜索,但随着算法的执行,子种群内部个体失去多样性,因此需要通过子种群之间的信息交互,产生更好的个体.鲸鱼优化算法(WOA)[23]是最优个体引领搜索方向的算法,这是利用鲸鱼可以通过螺旋上升过程中泡泡网围攻以及随机搜索猎物完成捕食过程.因此,设计离散鲸鱼优化算法(DWOA)完成子种群之间的信息交互.最优个体存在于各子种群的领飞鸟中,因此,DWOA只对它们优化,同时利用3种交叉策略模拟鲸鱼的捕食过程.鲸鱼围攻和螺旋上升过程分别利用当前个体和最优个体进行次序交叉和两段交叉模拟,分别以50%的概率完成局部搜索,产生一个随机数p,p∈[0, 1],若p<0.5,执行次序交叉,否则执行两段交叉;随机搜索猎物过程则利用当前个体和种群中随机个体进行随机交叉模拟完成全局搜索.3种交叉的具体操作如图1～3所示,其中P1和P2为两个父代个体,C1和C2为两个子代交叉个体.

图1 次序交叉操作

图2 随机交叉操作

图3 两段交叉操作

(1) 次序交叉(OX).

步骤1随机选择两个交叉点r1和r2,且 1≤r1

步骤2把P1和P2中r1～r2的工件分别复制到C1和C2中的r1～r2位置.

步骤3把P1不包含在C2中的工件依次复制到C2; 把P2不包含在C1中的工件依次复制到C1.

步骤4将C1和C2中Cmax值较小的作为交叉结果.

(2) 随机交叉(JBX).

步骤1构造两个子序列S1,S2.

步骤2把P1中对应S1的元素复制到C1;把P2中对应S2的元素复制到P2.

步骤3把P2中对应S2的元素复制到C1;把P1中对应的S1的元素复制到C2.

步骤4将C1和C2中Cmax值较小的作为交叉结果.

(3) 两段交叉(TSX).

步骤1随机选择两个交叉点r1和r2,且1≤r1

步骤2把P1中r1～r2的工件复制到子序列sub1;从P2中去除sub1中工件,剩余的工件作为子序列sub2.

步骤3把子序列sub1和sub2复制到C1,把子序列sub2和sub1复制到C2.

步骤4如果r<0.5,C1作为交叉结束,否则C2作为交叉结果.

在DWOA中,LS和全局搜索平衡至关重要.为达到更好的优化效果,通过一个选择概率Pb完成算法探索和开发的切换,Pb采用非线性的正弦函数替代WOA[23]中的线性函数,由下式给出:

(6)

For 每个个体

如果p<0.5

如果r>Pb

种群最优个体与当前个体执行次序交叉(OX)

否则

当前个体与随机选择个体进行随机交叉(JBX)

End if

否则

种群最优个体与当前个体执行两段交叉(TSX)

End if

End for

2.7 LS能力增强

为了进一步提高全局最优个体的质量,对其进行LS.但最优个体是经过多次进化所得,直接进行LS可能进入循环搜索,因此,首先对最优个体进行干扰,然后再执行LS.LS算法流程图如图4所示.

图4 局部搜索算法流程图

2.8 种群多样化控制

随着IMMBO算法进化,种群中个体失去多样性,因此,为各子种群的领飞鸟设置一个年龄变量,可记录其更新程度,年龄越大,说明更新能力越差.年龄变量初始值为0,如果个体更新,年龄变量清0,否则增加1,并与设置的最大年龄限制,即alimit比较,当某个体年龄大于该值时,可能在它的邻域循环搜索,此时,启动种群多样化控制机制,产生一个新的个体替换该个体.但随机产生的个体质量可能更差,导致算法收敛速度下降,而且被放弃的个体进化了多代,必然携带较好个体信息,其邻域可能就是更好的可行区域.为兼顾随机性和质量,对被放弃的个体执行3次插入干扰,产生一个领域个体,但该邻域个体很难保证质量.为了找到较好的邻域个体,使算法朝着期望的区域搜索,重复上述操作τ次,产生τ个邻域个体,将其中最好的一个个体放入种群替换原个体.考虑新个体的质量和算法效率,将τ设置为10.

3 仿真研究

3.1 仿真环境和算例

算法采用MATLAB R2016b 编写,并在Intel(R) Core(TM) i5-9600KF/3.7 GHz/ 16.0 GB,系统为Windows 10的平台运行.

为了验证实验效果,选择适用于带SDST的流水或HFS问题的算例,即基于Ta的自适应算例[24],通过测试该算例进行参数调整及算法的有效性验证.

3.2 参数调整

参数设置对于智能优化算法性能影响较大,为了使IMMBO算法在最佳状态下对HFS-SDST问题求解,需要对其参数进行调整.参数调整通过测试中等规模的Ta42衍生的8个自适应算例进行,Ta42算例的工件数n为50,阶段数m为10,每个阶段的机器数有2种情况:3台(P3)或者服从1～3台(P13)之间的统一分布,同时准备时间考虑4种情况,分别为平均加工时间的10%(SSD10)、50%(SSD50)、100%(SSD100)、125%(SSD125).根据上述每个阶段机器数和准备时间情况产生的8个自适应算例记作:SSD10_P13_50、SSD50_P13_50、SSD100_P13_50、SSD125_P13_50、SSD10_P3_50、SSD50_P3_50、SSD100_P3_50和SSD125_P3_50.IMMBO算法中涉及参数较多,通过前期测试,可知对算法优化效果影响较大的5个参数及其大致范围.为了确定参数的值,采用正交实验法对算法中的5个参数的4个水平进行测试.5个参数分别为子种群个数Np、巡回次数G、 最大年龄alimit、破坏重建中的破坏程度d和最大进化代数tmax.正交表如表1所示.

表1 正交实验参数/水平表

如果对IMMBO算法的5个参数的4个水平全部组合进行测试,需要进行45=1 024 组实验,但采用正交实验法只需测试42=16组,即可为算法选出合适的参数值,显然,用正交实验法可以使参数选择效率大幅度提高.16种参数组合及测试上述8个算例的结果如表2所示.

表2 L16(45)正交表和实验结果

表2最后一列测试结果为每种参数组合测试8个算例,对每个算例算法独立测试5次,共40次实验测得的Cmax平均值.表3为5个参数,4种水平的平均值以及标准偏差(SD),据此选择参数的水平.4行中每一列的最小值所对应的水平值,表示较好的参数水平值.SD为该参数各个水平的标准偏差, SD值越大,对算法的优化效果影响越大, 表中最后一行为5个参数按照SD值降序排列.5个参数在不同水平的平均Cmax(AVG)的变化曲线如图5所示,其中AVG最小的水平即为该参数的最佳设置值.

表3 参数等级及均值响应

图5 IMMBO算法中的5个参数在4个水平变化趋势图

由图5和表3可以看出,alimit对算法的优化效果影响最大,子种群个数Np的影响最小.因此,设置参数Np=15,d=5,alimit=20,G和tmax分别设为3和600.

3.3 算法各部分有效性测试

通过测试IMMBO的4个变体分别说明算法各部分的有效性.选择32个自适应算例进行测试,即Ta算例(Ta32,Ta34, …, Ta46),自适应考虑4种准备时间且每个阶段3台机器情况.IMMBO的4个变体分别为:去掉领飞鸟邻域搜索策略中的DC(IMMBO_NDC)、 去掉子种群交互机制的DWOA算法(IMMBO_NDWOA)、 去掉LS的算法(IMMBO_NLS)和去掉种群多样化控制机制(IMMBO_NR).表4中所列出的值表示选择不同准备时间时,每个变体独立运行5次测试8个算例(8×5=40)的Cmax平均值,表达式为

表4 IMMBO算法4个变体测试P3情况均值响应表

(7)

表4的同一组算例中,CAVG越大,说明去掉的对应算子对优化结果影响越大.可知,邻域搜索中的DC和种群多样化控制机制对算法优化效果影响最大,子种群交互机制对算法的影响次之,LS对算法的影响最小.

3.4 算法性能测试

为了验证IMMBO算法求解HFS-SDST问题的效果,将IMMBO和文献[10]中求解同一问题的ILSMRLS、IMBO和DABC算法通过测试Ta32～Ta60的自适应算例进行比较,准备时间和机器数同3.2节算例设计,总算例数目为15×4×2=120,每个算法独立运行5次测试所有算例,结果如表5所示.表5中所列出的值表示每个算法独立运行5次测试15个算例(15×5=75)的Cmax平均值,表达式为

表5 IMMBO/IMBO/DABC/ILSMRLS算法针对P13和P3算例的测试结果对比

(8)

表5中4个算法相比,可知, IMMBO算法对各种机器配置和准备时间算例都有较好的优化效果.表6为上述4个算法分别测试8个自适应Ta算例的运行时间.可以看出,测试相同算例时,4个算法的运行时间由小到大依次是DABC、IMBO、ILSMRLS、IMMBO,虽然IMMBO所用时间稍长于IMBO 和ILSMRLS,但可以得到更好的优化效果.图6和图7分别为4个算法测试算例Ta56的SSD125_P3_50和Ta60的SSD50_P13_50的收敛曲线.由图可知,IMMBO算法与其他3个算法相比,无论是进化前期的收敛速度还是后期的收敛精度都是较优的.

表6 4个算法测试8个自适应算例的运行时间对比

图7 算例Ta60中SSD50_P13_50的4个算法收敛曲线图

4 结语

针对有较强工业背景的HFS-SDST问题,提出IMMBO算法,优化调度目标是找到使最大完成时间最短的工件在第1阶段机器上的加工顺序,即使Cmax最小的调度解.首先,采用MNEH初始化种群,并将其随机分配到各子种群,子种群规模为3,由1个领飞鸟和2个跟飞鸟组成.然后采用多种群候鸟迁徙算法的各子种群独立并行搜索和 DWOA算法实现子种群信息交互,同时加入LS和种群多样化控制策略平衡算法的探索和开发能力.为了使算法在最佳状态下求解HFS-SDST问题,针对IMMBO算法进行参数调整和算法各部分的性能测试,为了验证算法的有效性,与ILSMRLS、IMBO和DABC算法进行比较.结果表明,IMMBO的优化效果优于其他算法,且在进化前期所提算法有较快的收敛速度,后期能够跳出局部最优.