基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度

陈飞跃, 徐震浩, 顾幸生

(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237)



基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度

陈飞跃, 徐震浩, 顾幸生

(华东理工大学化工过程先进控制和优化技术教育部重点实验室,上海 200237)

基于以最小完工时间为目标的带阻塞有差速混合流水车间调度问题,提出了一种改进的离散布谷鸟搜索算法。在基本布谷鸟搜索算法的莱维飞行和巢寄生性的基础结构上,提出了一种基于交叉策略的莱维飞行机制,以便算法能够解决离散问题;同时,通过非余弦递减策略的动态发现概率去发现劣质鸟巢,并利用排列差分进化算法的变异思想将劣质鸟巢重建;在搜索过程中设定全局最优极值保持代数为阈值去重新发现劣质鸟巢,以防止算法陷入局部最优;最后利用邻域搜索方法进一步提高算法的搜索精度。通过仿真实验验证了该算法在求解混合流水车间调度类离散问题上的有效性与优越性。

布谷鸟搜索算法; 差分进化; 阻塞; 差速; 最小完成时间

混合流水车间调度[1](Hybrid Flow-shop Scheduling Problem,HFSP)在现代复杂制造业普遍存在,很多学者对其进行了深入的研究并取得了丰厚的成果。由于生产工艺要求、设备性能差异等客观原因,带阻塞有差速的混合流水车间调度问题应运而生。带阻塞有差速的混合流水车间调度问题可以拆分为混合流水车间调度问题、带阻塞流水车间调度问题以及有差速并行机流水车间调度问题。HFSP是一般流水车间调度问题的推广,其最主要的特征是工件加工工序中至少有一道工序存在并行机,并且在存在此工序,工件可以选择任意一个并行机进行加工;带阻塞流水车间调度问题(Blocking Flow-shop Scheduling Problem,BFSP)[2]是对普通流水车间调度问题的进一步约束,即工序之间不存在缓冲区;有差速并行机流水车间调度(Unrelated Parallel Flow-shop Scheduling Problem,UPFSP)[3]是对一般带并行机流水车间调度问题的拓展,即在每道工序的并行机可能由于设备型号、性能等客观原因导致即使生产相同工件,生产效率也不尽相同。带阻塞有差速的混合流水车间调度(Blocking and Unrelated Hybrid Flow-shop Scheduling Problem,BUHFSP)是以上3种调度模型的扩展融合。由于BUHFSP具有更高的柔性,而更适用于现代制造业,对其研究有助于提高生产效率,且混合流水车间调度问题以及阻塞流水车间调度问题都属于NP[4-5]完全问题,所以本文对带阻塞有差速的混合流水车间调度问题的研究具有重要的学术价值和现实意义。

由于BHFSP问题的普遍存在性与求解复杂性,学者一直对其进行着研究。Sawik[6]首次提出运用整数规划求解带阻塞及中间存储有限的混合流水车间调度问题,但整数规划只适合求解小规模问题;Tavakkoli等[7]针对该问题提出了一种带邻域搜索的文化基因算法,并证明了该算法效果明显优于经典的遗传算法。然而,以上两个算法都只是针对相同的并行加工设备。Yaurima等[8]利用改进GA求解不相关并行机的缓冲区有限的混合流水车间调度问题,但其求解最多包含6个加工阶段。在现实生产中,包含多阶段不相关并行设备的情况普遍存在,而以往研究大多只针对无差速或者少阶段、有差速、带阻塞混合流水车间。因此本文对带阻塞约束的有差速混合流水车间调度问题进行了研究,以最小完工时间为目标提出了一种基于每道工序完工时间最优的启发式规则的最小完工时间求解方法。

布谷鸟搜索算法作为一种新型现代元启发式算法[9],由于其控制参数少、能有效平衡全局最优与局部最优及其结构简单易实现的优点,一经提出就受到学者的推崇,并成功用于工程优化等实际问题中。Burnwal等[10]采用改进的布谷鸟算法解决以最小化延期惩罚成本和最大化机器利用率为目标的混合流水车间调度问题,并通过算例验证了该算法性能优于已有的GA、PSO算法;刘长平等[11]采用布谷鸟算法求解以最小完工时间为目标的置换流水车间调度问题,并通过Benchmark算例证明了该算法的优越性与有效性。布谷鸟搜索算法仅适用于求解连续问题,已有文献针对调度类离散问题大多是利用一定的排序映射规则将布谷鸟算法应用到离散问题,但是用该方法求解大规模问题就会陷入解震荡的局面。

通过研究分析,针对BUHFSP问题,本文设计了5种改进策略,分别是采用反向学习机制初始化布谷鸟鸟巢位置、改进莱维飞行方式将算法离散化、改进劣质鸟巢发现概率、基于最优阈值防止陷入局部最优以及融入邻域搜索。将以上改进DCS算法用于求解带阻塞的有差速混合流水车间调度问题,仿真实验验证了改进DCS算法求解BUHFSP问题的有效性。

1 问题描述

一般的流水车间调度都会假设工序间缓冲区无限大,而本文研究的带阻塞混合流水车间调度问题则假设工序之间不存在缓冲区,即若某工件的某一工序完成该工序操作后,下一工序机器仍处于被占用状态,则该工件会在该机器上等待,并且阻塞该工序以后工件的加工直至下一个工序机器被释放。针对一般流水调度车间模型,假设某车间要加工6件不同的工件,每个工件要经历3道工序,则不同的工序间存储策略的对比如图1所示。

图1 不同存储策略的3道工序流水车间最大完工时间的对比Fig.1 Comparison of the make-span of 3 procedures with different storage strategies

一般对带阻塞有差速混合流水车间调度生产过程作如下假设:

(1) 所有工件加工工序相同;

(2) 有并行机存在的工序,工件可以选择任意空闲机器进行加工;

(3) 工件间没有优先级;

(4) 一台机器不能同时加工多个工件,一个工件不能在同一时间被多台机器加工;

(5) 工序间的缓冲区为零;

(6) 工件在各工序、各机器上的加工时间已知,并且各工序的并行机加工同一工件的时间可能不同;

(7) 原料不限,完工工件存储空间不限。

根据以上假设,带阻塞有差速的混合流水车间可以描述为:n个待加工的工件要依次经过S道工序的加工,每道工序至少有一台加工设备并且至少有一道工序存在并行加工设备(设第j道工序的设备数为mj,j=1,2,…,S),要求确定所有工件的加工顺序及其在并行机上的分配情况,以使得最大完工时间(makespan)最小。有差速混合流水车间调度模型如图2所示,其中mi表示不同工序并行机的数量,矩形的大小表示工件在该机器上加工时间。

图2 带阻塞有差速混合流水车间调度模型Fig.2 Model of BUHFSP

假设工件数为n,机器数为m,工序数为λ,第k道工序的并行机数量为πk(k=1,2,…,λ),Ti,j表示工件Ji(i=1,2,…,n)在机器Mj(j=1,2,…,m)上的加工时间,Si,k表示工件Ji在工序k上的开始加工时间,Ci,k表示工件Ji在工序k上的完工时间,cmax为最大完工时间,Rj表示Mj被释放的时间,可以得出BUHFSP的数学模型为

minCmax

(1)

s.t.

i=1,2,…,n;k=1,2,…,λ

(2)

(3)

其中:式(1)为问题的目标函数;式(2)表示某一工件的某一工序只能由一台机器进行加工;式(3)表示某一时刻某一机器只能加工某一工件;式(4)、式(5)表示有差速并行机并且带阻塞限制的开工时间以及完工时间的约束关系。

2 改进的离散布谷鸟算法

2.1 概述

布谷鸟搜索算法(Cuckoo Search Algorithm,CS)是由Yang等[9]基于布谷鸟的繁殖寄生行为提出的一种新型元启发式群智能算法,其主要思想基于巢寄生特性以及莱维飞行机制两个策略。巢寄生特性:布谷鸟等寄生鸟类在繁殖产卵季节选择适宜的鸟巢并将鸟蛋产在宿主鸟巢,由宿主鸟孵育下一代;莱维飞行机制:莱维飞行是动物最有效的一种觅食方式[12],在智能算法中采取莱维飞行机制,大步长、小步长交替出现,可以有效地平衡局部最优与全局最优。本文利用基本布谷鸟搜索算法的优势,提出了改进的离散布谷鸟搜索算法(Discrete Cuckoo Search Algorithm,DCS)。

2.2 算法思路

2.2.1 编码与解码 采用整数编码,即只针对工件的加工顺序排序。编码序列为

X=(x1,x2,…,xi,…,xn),

1≤i≤n,1≤xi≤n

(6)

其中xi为正整数,表示所有工件加工的次序。

解码可分为3步:

(1) 第1个工件分别选择在各工序加工时间最短的机器上加工;

(2) 后续工件则占用最早完成本道工序加工的启发式规则,依次加工剩余工件;

(3) 若有工序存在本工序完工时间相同的情况,则随机选择一台机器进行该工序的加工。

2.2.2 基于反向学习的初始化 随机产生的初始鸟巢可能会在整个解空间中分布不均匀,为了提高初始鸟巢的质量,同时保证初始鸟巢的均匀性,引入基于反向学习的机制[13],即对初始序列作xi=1+n-xi变换,然后分别计算其适应度值,选取较优的个体作为初始鸟巢,从而保证初始化种群的优越性及提高收敛速度。

2.2.3 基于最早完工启发式规则的适应度值计算 编码解码方法初步解决了机器的分配问题。本文主要用到的启发式思想为:从第1件工件开始加工,针对存在并行机的加工阶段都选择能够使本阶段最早完工的机器进行加工。若并行机空闲,则直接选择最优的机器进行加工;若有并行机被占用,则待其被释放后比较该阶段的完工时间,依旧选择能够使本阶段最早完工的机器。算法处理过程如下:

Step1 针对前min(πk)件工件,只选择能使工件在各阶段最早完工的机器进行加工;

Step2 针对min(πk)到max(πk)的工件,有空闲并行机存在的则选择最优的机器,瓶颈阶段则选择最早空闲或者能够最早完工的机器进行加工;

Step3 针对max(πk)以后的工件,则按照工件加工次序,依次进行加工,对第1工序被释放的机器按照最先释放、最早优先的规则安排工件加工,后序工序则采用使本阶段最早完工、最早优先的规则进行加工,直至所有工序完毕为止。

根据以上3个步骤,对所有工件完成加工,求得最大完工时间。

2.3 算法流程

基本布谷鸟算法只适用于求解连续型优化问题,而生产调度属于组合优化问题,因此借鉴遗传算法的交叉思想以及基于排列的差分进化变异思想对CS算法进行离散化。

(1) 基于交叉的莱维飞行。莱维飞行是一种随机游走机制,代表一类非高斯随机过程。其随机游走的公式为

(7)

(8)

从而新鸟巢的位置为

⊗L(β)

(9)

本文借鉴遗传算法的交叉思想提出基于交叉的莱维飞行将莱维飞行离散化,即将种群的每个鸟巢位置分量与当前最优鸟巢位置分量以Pcross的概率进行交叉操作。交叉操作可以部分或全部地继承父代的优秀基因,因此,所有鸟巢与最优鸟巢的交叉可以使得各鸟巢位置向最优位置快速靠拢。交叉概率Pcross借鉴搜索向量L(β)产生的思想,取Pcross=max(α⊕L(β)),即若当前鸟巢位置分量与最优鸟巢位置相对分量最大差异值较小时,则该鸟巢位置与最优鸟巢位置交叉概率较小;反之则较大。这样根据与最优鸟巢位置差异来控制交叉概率,从而能够更好地利用“大小交叉概率”控制鸟巢种群的优化方向。其中交叉采用整数修正的交叉方法。

(2) 余弦递减策略的发现概率。一般的CS算法都是采用固定的发现概率Pa,Pa的大小会影响最优解的搜索速度,Pa过大则较难收敛到最优解,Pa过小则会使得收敛速度变慢。为了增加算法的自适应性,本文引入了基于余弦递减策略的动态发现概率

(10)

其中:Pmax、Pmin表示最大、最小发现概率;i表示当前迭代代数;maxgen表示最大迭代代数。

引入该策略,可以使得算法在计算前期能够在保证全局搜索能力的前提下快速收敛到非劣解,随着迭代代数的增加,种群个体的质量逐渐提高;到寻优后期,Pa随着代数的增加而减小,有利于算法进行更精确的局部搜索。通过测试验证表明,动态发现概率有效地提高了算法的收敛速度并改善了搜索能力。

(3) 剔除劣质鸟巢,新增优质鸟巢。用一个随机数r作为衡量宿主鸟发现鸟巢异常的概率,并与Pa进行比较,若r>Pa,则通过对劣质鸟巢位置进行变异操作,产生新的鸟巢位置。本文采用排序差分进化算法[14]的变异操作,其基本原理为将差分向量加到要变异的基向量上去。选择DE/target-to-best/1的变异策略。即

(11)

(12)

其中:r1、r2为[1,N]内与i不相等的随机整数,且两两不相等;F为缩放因子,为了增加增强算法的自适应能力,本文取非线性递增的取值策略,从而保证算法在运算初期劣解与当前最优解差异较大时适当地控制扰动,在算法后期适当地增大扰动,动态调节缩放因子F,从而可以有效平衡全局搜索与局部搜索。F的取值如式(12)所示,其中Fl=0.1,Fh=0.9,从而可以保证F在[0.1,0.9]之间随着迭代代数的变化而变化。通过DE变异操作,可以有效地补充丢失的有效“基因”而维持鸟巢种群的多样性。

(4) 基于最优代数阈值的变异操作。在算法迭代开始前,定义全局最优保持代数dir为零;当对鸟巢位置迭代更新时,在每一代的进化过程中,记录并更新当前全局最优值保持的代数dir,当其全局最优值保持代数超过设定的阈值stage时,对当前鸟巢种群进行步骤(3)的操作,然后对dir置零。设置最优代数阈值,可以有效地加快算法收敛速度,当算法陷入局部最优,会通过变异来增加种群的多样性,从而使算法能够快速跳出局部最优。而针对阈值的选择,通过取不同等级的stage实验验证了随着stage的增大,优化性能会逐渐降低,但是若stage选取过小,则会增大算法的时间复杂度。综合相关实验以及文献[15]分析,取阈值stage=5。当达到预设stage时,则重复步骤(3)的操作,增加种群的多样性,在一定程度上避免算法陷入局部最优。

(5) 邻域搜索。为了提高算法的搜索精度,引入邻域搜索方法[16]。目前,针对调度等组合优化类问题通常采用Insert、Swap以及Interchange 3种方法。Schiavinotto等[17]的研究表明,Insert和Interchange的直径都是n-1,而Swap的直径是n(n-1)/2,这表明局部搜索过程中,Insert和Interchange方法要比Swap方法更有效。本文采用基于Insert和Interchange方法的局部搜索(Local Search,IILS),在每代进化的最后,对每个鸟巢的个体最优值进行局部搜索,从而提高算法精度。

离散的布谷鸟算法流程伪代码如下:

设置参数,Pmax、Pmin,最大迭代代数maxgen,鸟巢个数,dir=0;

根据反向学习机制对鸟巢位置进行初始化,并获取当前最优鸟巢位置;

For index

获取当前最优鸟巢,并替换最差鸟巢位置;

利用基于交叉的莱维飞行产生新的鸟巢位置,获取当前最优鸟巢;

采用余弦递减策略的动态发现概率,产生各代的发现概率Pa;

IfPa>rand

对劣质鸟巢进行DE变异操作,产生新的鸟巢位置;

End

计算鸟巢种群适应度值fit;

If rand<0.05

随机选择鸟巢变异位置,然后对两个位置“基因”交换位置;

计算突变后鸟巢的适应度值fit_temp,

If fit_temp

更新鸟巢位置为突变后的鸟巢位置

End

End

If 当前最优等于全局最优

dir = dir+1;

End

If dir==5

重复Empty_Nest操作;

End

End

对鸟巢种群个体极值进行局部搜索(ILS)操作;

计算当前最优鸟巢位置,并替换最差鸟巢位置;

End

2.4 算法复杂度分析

假设算法的最大迭代次数为maxgen,由2.1节可得计算该类问题的目标函数的时间复杂度为O(sn2),莱维飞行的时间复杂度为O(NEST lgn);基于DE变异操作的淘汰劣质鸟巢的时间复杂度为O(NESTsn);突变产生新鸟巢位置的时间复杂度为O(NESTsn);阈值变异操作的时间复杂度为O(NESTsn);邻域搜索的时间复杂度为O(sn2(n+1))。由于突变操作、阈值变异操作以及邻域搜索都是概率发生的,对时间复杂度的增加影响不大,因此算法的时间复杂度为O(maxgen (NEST lgn+ NESTsn+sn2))。可以看出算法计算量主要与迭代次数maxgen、鸟巢种群NEST以及算例规模(工序数s、工件数n)有关。

3 仿真实验

3.1 实验设置

为了验证算法、模型的可行性和优越性,选取文献[18]的算例以及在一定规则下生成的随机算例进行计算分析。引用解决调度问题较为成熟且效果较好的算法APSO[19]、SAGA[20]进行算法性能比较。所有实验均在处理器为Intel(R) Core(TM) i3-2310M @ 2.10 GHz,6 G内存的PC机上采用Matlab R2014a对算法进行编程计算。

3.2 参数分析

智能优化算法中参数的设置对于算法的寻优性能以及收敛速度具有很大的影响,为了选取能够达到综合性能最优的参数,本文引入了因子设计方法(Factorial Design,FD)[21]来选取DCS的参数。

DCS算法包含4个参数:n,pmax,pmin,β,将这4个参数设置为4个因素,每个因素含有3个水平,如表1 所示。为了减少计算量,提高参数设计效率,本文采用正交设计的方法,即只需要32=9组试验即可取得最优参数值。

表1 正交设计因素和水平表

正交试验取9组不同规模随机算例独立运算10次统计其运算结果。表2给出了所取9个算例的STD值,并列出了这4个参数在9个不同规模的随机算例计算结果中的Mij值,如表3～6所示。其中Mij(i=1,2,3;j=1,2,3,4)表示第j个参数的第i个Level的平均值;STD表示Mij的标准差。对于每个参数,若第j列的某个Mij最小,则说明参数j取i水平所对应的参数值最佳。

表2 随机算例的正交计算结果方差

表3 DCS算法选取不同n值的仿真结果

表4 DCS算法选取不同Pmax值的仿真结果

表5 DCS算法选取不同Pmin值的仿真结果

表6 DCS算法选取不同β值的仿真结果

STD值反应了参数j对算法的影响程度,STD越大,说明参数j的设置对算法的寻优性能影响越大。根据表2可以看出,无论算例规模大小,在大多数情况下,n、β对算法影响程度最大。在表3～6中,黑体数字表示该算例的最小值,对于大多数算例,当n=30、Pmax=0.8、Pmin=0.2、β=1.5时,算法能够取得较好的结果。因此,算法性能分析中,DCS的参数设置为n=30、Pmax=0.8、Pmin=0.2、β=1.5。

3.3 性能分析

DCS算法采用基于反向学习机制的初始化方法,使得该算法初始解较优;利用基于交叉的莱维飞行机制产生新的鸟巢以及基于PDE的变异策略重构鸟巢位置解决连续问题的布谷鸟搜索算法应用到离散问题领域,使得该算法能够既保持布谷鸟搜索算法的平衡全局搜索与局部搜索的优势,又能够极好地适用于解决离散型优化问题;采用余弦递减的发现概率策略,使得该算法能够在整个算法进程中既保持了前期的快速收敛性,又具有后期强劲的局部搜索能力;添加的突变操作以及代数阈值操作保证了种群“基因”的完整性以及防止算法陷入局部最优;而局部搜索策略则保证了算法的搜索精度。

(1) 邻域搜索策略分析。针对DCS可能存在的搜索精度不高以及收敛速度慢的缺陷,添加邻域搜索的改进策略,即在DCS迭代过程中针对每代的最优鸟巢位置进行邻域搜索。选择效率较高的Insert和Interchange局部搜索策略,可以使得DCS具有较强的能力跳出局部最优。为了验证以上理论,分别对采用邻域搜索策略和不采用邻域搜索策略的DCS进行算例测试分析,实验结果如表7所示,其中Best表示独立运算20代的最优值,Worse表示独立运算20代的最劣值,Avg表示20代寻优的平均值,STD表示20代最优值的标准差,avg_dir表示20代最优寻优代数的平均值,std_dir表示20代最优寻优代数的标准差。

表7示出的10个算例为随机生成的规模为10道工序10件工件的算例,其中DCS_ IILS表示带邻域搜索策略的DCS。由表7可以看出,DCS_ IILS与DCS独立运算20次求得的最优下界都相同,但是从Worse列可以看出,DCS_IILS要明显优于DCS,并且Avg列与STD也都明显优于DCS,这表明添加邻域搜索策略使得DCS算法的搜索精度有了明显的改善;从avg_dir列可以看出,DCS_IILS要明显优于DCS,可以证明添加了添加邻域搜索策略的DCS的收敛速度也同样得到了明显的改善。图3示出了随机选择的Obj02与Obj07的收敛曲线对比图,可以更清晰地看出添加了邻域搜索策略的DCS在收敛速度与精度上的优越性。从表7中数据以及图3收敛曲线的对比可以看出,带邻域搜索策略的DCS算法在鸟巢种群处于优秀区域时采用邻域搜索可以进一步提高算法搜索精度,同时可以能够在一定程度上跳出局部最优加快算法的收敛速度。

图3 收敛曲线对比Fig.3 Comparison of convergence curves

(2) 综合性能分析。针对BUHFSP选取文献[18]的测试实例,两个算例的已知最优下界为301、26。采用本文DCS算法以及基于各工序最小完工时间的启发式规则的求解方法对文献[18]的两个实例进行运算。为了便于分析算法的结果,此处取最优相对误差(ORE)、最差相对误差(WRE)和平均相对误差(ARE)作为评价指标。

(13)

(14)

(15)

其中:Cmin和Cmax分别表示20次计算结果中得到的最优解和最劣解;STDEV表示20次运算结果标准差;Cave表示20次结果的平均值;C*表示文献最优下界。运算结果如表8、9所示。

表7 变邻域搜索策略的影响

表8 算例1计算结果

表9 算例2计算结果

由表8、9中的数据可以清晰地看出,用DCS算法求解带阻塞的混合流水车间调度问题有一定的优势,该方法求得的最优下界都明显优于文献[18]的结果。同时,DCS算法无论是最优下界还是Cave都优于SAGA、APSO、CS等算法,并且DCS的ORE始终不大于其他算法的ORE,DCS算法在寻优能力上具有绝对的优势;通过比较分析STDEV可以看出,DCS算法保持最小,说明该算法在求解稳定性上具有一定的优势。

为了更清晰显示DCS算法在收敛性和寻优能力的优越性,绘制算例1、2的收敛曲线如图4所示。从图4可以看出,由于DCS算法采用了基于反向学习机制的初始化方法,所以其算法初始解明显要优于另外几种算法;在算法迭代前期,比如针对所有算法的前10代,可以明显看出DCS算法下降速度明显要优于另外几种算法;而在接下来的迭代过程中,DCS算法还能继续寻优而不是陷入局部最优之中,可见本文改进的DCS算法保留了基本CS算法既能保持全局最优又能局部寻优的优势。而针对算法的最终寻优结果,DCS算法在后期始终保持最优的状态,并且综合表8、9,可以得出DCS算法在寻优能力方面具有绝对的优势。

3.4 算法性能比较

为了验证本文提出的DCS的优越性,选择随机生成不同规模的算例进行算法性能测试,同时与APSO和SAGA两种算法进行比较。算例生成机制如下:

(1) 限定生产工序数,在某个范围内随机产生每道工序并行机数量;

(2) 在每道工序随机产生一个比工序的基准加工时间BaseTime,然后随机生成每台并行机的差异加工时间RandTime,BaseTime+RandTime即为该工序并行机的加工时间。

图 4 收敛曲线对比Fig.4 Comparison of convergence curves

利用以上算例生成规则,分别生成5道工序*10件工件、5道工序*20件工件、10道工序*10件工件、10道工序*20件工件的各10个算例。采用各算例独立20次运算结果的最劣下界(Max)、最优下界(Min)、平均值(Mean)、标准差(STD)作为评价指标,由于篇幅有限仅选取几组不同规模算例如表10所示。

表10 DCS与其他算法结果比较

表10中黑体表示3种算法的最优结果。可以明显看出,本文提出的DCS算法无论是最优下界还是最优下界平均值都要优于SAGA、APSO算法,可见该算法的寻优性能要明显优于SAGA、APSO算法;分别分析当工件数相同以及工序数相同的两种情况下的最优下界的平均值Mean可以看出:当工件数量增加时,DCS的寻优能力明显增强;当工件相同工序增加,DCS的寻优能力增加,但没有工件增加时寻优能力增强得那么明显;从STD列可以看出DCS算法针对不同规模的算例,总体上也明显优于两位两种算法。综合分析表中不同规模算例,可以看出随着算例规模的增大,DCS算法在寻优能力上始终保持绝对的优越性并且随着模型规模的增大,最优下界的优越性也随之增加。

为了从统计学的角度验证本文提出的DCS算法的性能优越性,采用方差分析法对随机算例的计算结果进行进一步分析。针对4组不同规模的40个算例独立运算20次的结果,计算不同规模的最优平均相对误差

ARE=(Mean-Min)/Mean

(16)

然后对同一规模的不同算例取平均值均方差,结果见表11。

表11 不同算法ARE均值统计比较

表11中ARE表示该算法求得的解与所有算法求得的最优解相比较的平均相对误差。很明显,ARE越小,说明算法的寻优性能就越好。STD表示ARE的标准差,STD越小则说明算法的稳定性越高。从表11黑体字可以看出,针对不同规模的算例,本文提出的DCS算法的最优平均相对误差的平均值始终最小,且其方差也总是最小,可以判定该算法的寻优能力以及寻优稳定性要优于另外两种经典算法。在LSD区间均值图中,若两个区间完全没有重叠,则可以说明这两个区间代表的元素在统计学上有显著的差异。从图5可以看出DCS算法的置信区间均值与另外两种经典求解调度问题的改进算法大体上不重叠,说明本文提出的DCS算法在统计意义上有明显的优势;同时,从图5中可以看出DCS算法的区间相比于另外两种算法最窄,说明该算法相比于两种算法具有良好的稳定性。

图5 不同规模不同算法具有95%置信区间的LSD区间均值图

综合以上分析,本文提出的DCS算法在求解基于各工序最早完工的差值平移模型的带阻塞有差速混合流水车间调度问题时无论是收敛速度还是寻优能力都具有明显的优势。

4 结 论

本文研究了以最小化最大完工时间为目标的带阻塞有差速混合流水车间调度问题。该问题基于经典流水车间调度模型考虑了并行机约束、阻塞约束以及设备效率差异,建立了基于各工序最早完工的启发式规则的调度模型。调度问题作为经典的离散组合优化问题,而原始CS算法只适用于求解连续问题。为了使将该算法用于求解调度类组合优化问题,本文提出了一种改进的离散布谷鸟搜索算法,采用基于交叉的莱维飞行机制以及基于排列差分进化思想的变异操作将布谷鸟算法离散化,进而适用于求解离散排序问题。采用反向学习的初始化方法以及动态的发现概率改善了初始种群的优越性及算法的搜索能力,引入最优代数阈值使的算法能够在一定程度上避免陷入局部最优,最后通过邻域搜索,进一步提高了算法的搜索精度。通过仿真实验以及对算法的分析对比,验证了所提算法在求解调度类组合优化问题上的有效性与优越性。

[1] 王凌,周刚,许烨,等.混合流水线调度研究进展[J].化工自动化及仪表,2011 (1):1-8.

[2] GRABOWSKI J,PEMPERA J.Sequencing of jobs in some production system[J].European Journal of Operational Research,2000,125(3):535-550.

[3] FIGIELSKA E.A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources[J].Computers & Industrial Engineering,2009,56(1):142-151.

[4] GUPTA J N D.Two stage hybrid flow shop scheduling problem[J].Asia-Pacific Journal of Operational Research,1988,39(4):359-364.

[5] DENG G,CUI Z,GU X.A discrete artificial bee colony algorithm for the blocking flow shop scheduling problem[C]// 2012 10th World Congress on Intelligent Control and Automation (WCICA).USA:IEEE,2012:518-522.

[6] SAWIK T J.A scheduling algorithm for flexible flow lines with limited intermediate buffers[J].Applied Stochastic Models and Data Analysis,1993,9(2):127-138.

[7] TAVAKKOLI-MOGHADDAM R,SAFAEI N,SASSANI F.A memetic algorithm for the flexible flow line scheduling problem with processor blocking[J].Computers & Operations Research,2009,36(2):402-414.

[8] YAURIMA V,BURTSEVA L,TCHERNYKH A.Hybrid flowshop with unrelated machines,sequence-dependent setup time,availability constraints and limited buffers[J].Computers & Industrial Engineering,2009,56(4):1452-1463.

[9] YANG X S,DEB S.Cuckoo search via Lévy flights[C]// World Congress on Nature & Biologically Inspired Computing,2009.USA:IEEE,2009:210-214.

[10] BURNWAL S,DEB S.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach[J].The International Journal of Advanced Manufacturing Technology,2013,64(5/8):951-959.

[11] 刘长平,叶春明.求解置换流水车间调度问题的布谷鸟算法[J].上海理工大学学报,2013,35(1):17-20.

[12] REYNOLDS A M,SMITH A D,MENZEL R,etal.Displaced honey bees perform optimal scale-free search flights[J].Ecology,2007,88(8):1955-1961.

[13] 吴昱,李元香,徐星.基于群智能的新型反向混合差分进化算法[J].小型微型计算机系统,2009,30(5):903-907.

[14] DAS S,ABRAHAM A,CHAKRABORTY U K,etal.Differential evolution using a neighborhood-based mutation operator[J].IEEE Transactions on Evolutionary Computation,2009,13(3):526-553.

[15] 徐震浩,李青青,顾幸生.基于 DEPSO 的模糊时间 ZW 多产品厂间歇调度[J].控制与决策,2015,30(12):2275-2279.

[16] QIAN B,WANG L,HU R,etal.A DE-based approach to no-wait flow-shop scheduling[J].Computers & Industrial Engineering,2009,57(3):787-805.

[17] SCHIAVINOTTO T,STÜTZLE T.A review of metrics on permutations for search landscape analysis[J].Computers & Operations Research,2007,34(10):3143-3153.

[18] 张其亮,陈永生.带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法[J].信息与控制,2013,42(2):252-257.

[19] 张顶学,关治洪,刘新芝.一种动态改变惯性权重的自适应粒子群算法[J].控制与决策,2008,23(11):1253-1257.

[20] JIA Hongyan,HONG H.Research on job-shop scheduling problem based on self-adaptation genetic algorithm[C]// 2010 International Conference on Logistics Systems and Intelligent Management.USA:IEEE,2010: 940-943.

[21] MONTGOMERY D C.Design and Analysis of Experiments[M].USA:John Wiley & Sons,2008.

欢迎订阅

《华东理工大学学报(自然科学版)》

地址：上海市梅陇路130号436信箱 邮编：200237

邮发代号：4-382

Discrete Cuckoo Search Algorithm for Blocking and Unrelated Hybrid Flow Shop Scheduling Problem

CHEN Fei-yue, XU Zhen-hao, GU Xing-sheng

(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

For the hybrid flow shop scheduling problem of minimizing the total flow time subject to blocking and differential speed,this paper proposes a discrete cuckoo search algorithm (DCS).By means of the Levy flight and the brood parasite of the cuckoo search algorithm,this paper proposes a crossover strategy based Levy flight mechanism so that the DCS can solve the discrete optimization problems.And then,the dynamic detection probability method is utilized to search for the inferior nest that is further reconstructed by adopting the mutation technique of the permutation-based differential evolution.In order to prevent the DCS from falling into local extremism,this paper introduces the global optimum extreme value algebra as the threshold to rediscover the inferior nests.Finally,the neighborhood search algorithm is used to further improve the search accuracy.The simulation results verify the effectiveness of the proposed algorithm for solving the hybrid flow shop scheduling problems subject to blocking.

cuckoo search algorithm; differential evolution; block; unrelated; minimizing flow time

1006-3080(2017)03-0425-11

10.14135/j.cnki.1006-3080.2017.03.020

2016-09-28

国家自然科学基金(61104178, 61174040)

陈飞跃(1990-)，男，河南开封人，硕士生，研究方向为生产调度、智能算法。

徐震浩，E-mail: xuzhenhao@ecust.edu.cn

TP301

A