求解混合流水车间调度问题的改进灰狼算法

时维国，宋存利

(1.大连交通大学 电气信息工程学院，辽宁 大连 116028;2.大连交通大学 软件学院，辽宁 大连 116052)

0 引言

带有相同并行机的混合流水车间调度问题(Hybrid Flow shop Scheduling Problem, HFSP)是典型流水车间调度问题的扩展，其所有加工任务均以相同的顺序经过各个加工阶段，而每个加工阶段均配置有一台或多台相同的加工设备，且至少有一个加工阶段配置有多台相同的加工设备。HFSP的研究目标是如何安排加工任务的加工顺序，以满足企业生产追求的目标，如每个加工阶段的设备负载均衡、总流水时间最小、最小化最大完工时间等。典型的生产案例有食品生产、化工生产、钢铁生产等，因此对该类问题进行研究具有重要的意义。

HOOGEVEEN等[1]对具有两阶段HFSP的复杂性进行了研究，证明该问题属于NP难题。对于小规模的HFSP问题常用精确方法，例如BRAH等[2]针对带有多处理的流水车间调度问题，提出一种分枝定界算法；HIDRI等[3]对带有运输时间的两阶段HFSP以最小化最大完工时间为目标，提出一种分枝定界法；FATTAHI等[4]对带有批操作和设置时间的HFSP提出一种分枝定界算法。这些精确算法虽然能求出问题的最优解，但是当问题规模变大时，求解效率将大大降低，因此学者们提出各类启发式算法和智能优化算法：例如宋存利等[5]提出求解无等待流水车间调度问题的贪婪迭代搜索算法；屈国强[6]提出一种瓶颈聚焦的启发式方法；MOCCELLIN等[7]针对考虑阻塞和设置时间的HFSP，提出一种基于优先级的启发式规则算法。实验证明，启发式方法的优点是求解速度快，缺点是寻优效果往往受启发式规则影响较大；智能优化算法受问题特点影响较小，且求解结果较好，因此受到广大学者的青睐，例如针对HFSP，ALAYKYRAN等[8]提出蚂蚁算法；LOW[9]提出模拟退火算法；SHIAU等[10]提出粒子群算法；FIGIELSKA[11]提出遗传算法和模拟退火算法的混合算法；RABIEE等[12]提出基于帝国竞争算法的混合算法；宋存利[13]提出贪婪遗传算法；KOMAKI等[14]提出人工免疫算法；LI等[15]提出人工蜂群算法；SUN等[16]和王芳等[17]针对带有不相关并行机的HFSP提出分布估算算法；SIQUEIRA等[18]和ESKANDARI等[19]提出变邻域搜索算法解决该问题。

灰狼优化(Grey Wolf Optimization, GWO)算法是2014年由澳大利亚学者MIRJALILI等[20]提出的一种群体智能优化算法，该算法是一种受灰狼捕食猎物活动启发而开发的一种优化搜索方法，因具有较强的搜索能力，且控制参数少、易实现，受到学者们的广泛关注，其在参数优化[21]、图像分类[22-23]、旅行商问题[24]等方面得到成功应用。

近年来，GWO算法开始应用在生产调度领域。孟荣华等[25]提出基于十进制GWO算法的金属板材切割调度，该算法重新设计了灰狼的游走和奔袭等智能行为，改进后的GWO算法以一种全新的机制进化，不再受参数A和C的影响；KOMAKI等[26]将GWO算法应用于两阶段装配流水车间调度问题，在GWO算法找到较好的解后再对其实施一种邻域寻优操作，以便最大限度提高解的质量；YANG等[27]将GWO算法应用于带有阻塞的流水车间调度问题，通过将一种变邻域搜索算法应用于GWO算法来提高算法的局部搜索能力；LU等[28]提出一种多目标细胞GWO算法，该算法将细胞自动机的优点融于算法，以提高灰狼种群的多样性，同时将变邻域搜索算法运用于头狼，以提高算法的局部搜索能力。然而目前对HFSP，GWO算法的应用研究极少。

针对HFSP以求解最小化最大完工时间为目标，本文对GWO算法的应用展开了研究。同其他群体智能优化算法一样，GWO算法同样存在早熟收敛、易陷入局部最优等问题，很多学者对其提出了改进。例如，文献[26-28]将其他算法算子混入GWO算法，以提高其局部搜索能力；文献[29-30]对GWO算法的距离控制参数a进行改进，较好地控制灰狼的全局搜索和局部探索能力；文献[25,30]对GWO算法的位置更新公式进行了改进；文献[31-32]分析了控制参数C对GWO算法的影响，分别提出改进控制参数C的策略来提高算法探索能力。本文对GWO算法的改进体现在以下方面：

(1)鉴于GWO算法的控制参数C对狼群全局探索和局部搜索能力有重要影响，提出一种新的控制参数C的设置策略，以平衡狼群的全局探索和局部搜索能力。

(2)在算法后期提出一种平面镜成像学习策略应用于灰狼种群，以提高狼群的多样性。

(3)考虑到基于工件加工顺序的编码在解码时的效果受设备配置影响较大，采用正序解码和逆序解码相补充的策略。

1 混合流水车间调度问题

1.1 问题描述

HFSP可描述为N个工件以相同的加工顺序经过S个加工阶段进行加工，M台不同的加工设备分布在S个加工阶段，每个加工阶段的加工设备数量大于等于1台，且相同阶段的加工设备完全一样，不同加工阶段的加工工艺不同。问题的目标是如何安排N个工件在每个阶段加工设备上的加工顺序，使最大总完成时间最小。问题的假设条件如下：

(1)一个工件同一时间只能在一台设备上加工，而且在加工过程中不能被其他工件抢占。

(2)每台设备同一时间只能加工一个工件。

(3)每个工件均需按照相同的顺序经过各个加工阶段，且在每个加工阶段都有一道工序需要加工，但加工时间因工件不同而不同。

(4)同一阶段的加工设备完全相同。

(5)不同阶段之间有无限缓冲区间。

(6)忽略设备故障和到达延迟等问题。

1.2 问题建模

为了方便问题建模，定义数学符号如下：

N为待加工的工件数量；

S为加工阶段数量；

i为工件编号，i=1,2,…,N；

j为加工阶段编号，j=1,2,…,S；

Mj为第j阶段的加工设备数量；

k为某阶段的设备编号，k=1,2,…,Mj；

mj,k为第j加工阶段的第k台加工设备；

Ei,j为工件Ji在第j个加工阶段的完工时间；

Bi,j为工件Ji在第j个加工阶段的加工开始时间；

pi,j为工件Ji在第j个加工阶段的加工时间；

Xi,j,k表示工件Ji在第j个加工阶段是否在设备mj,k上加工，Xi,j,k=1则在该设备上加工，Xi,j,k=0则不在该设备上加工；

Cmax为所有工件的最大完工时间；

Ri,j为工件Ji在第j阶段之后的剩余加工时间。

HFSP问题的目标函数为

Cmax=min{max{Ei,j|

i=1,2,…,N;j=1,2,…,S}}。

(1)

s.t.

Ei,j=Bi,j+pi,j≤Bi,j+1；

(2)

Bi,1≥0；

(3)

(4)

(5)

(6)

其中：式(2)约定每个工件在相应加工阶段的完工时间为其在该阶段的开始加工时间加上其工序对应的加工时间，而且下一阶段的开始加工时间大于等于前一阶段工件的完工时间；式(3)表示每个工件第一道工序的开始加工时间大于等于0；式(4)表示每个工件在第j阶段只能在其中一台设备上加工；式(5)表示每个工件在每个阶段必须选择一台且只能在其中一台设备上加工；式(6)为工件在阶段j之后的剩余加工时间。

2 灰狼优化算法

GWO算法是受自然界狼群捕猎行为启发而提出的一种智能群体优化算法，是将狼群的捕猎行为归结为追踪、围猎和攻击3种行为而构建的一种优化算法，适用于求解组合优化问题。该算法将每只狼抽象为问题的一个解，适应度最好的解为头狼，称为α狼，适应度次好的解为β狼，适应度第3的解为δ狼，其他解为ω狼。ω狼在α狼、β狼和δ狼的引领下进行追踪、围猎和攻击，不断接近猎物，最终抓住猎物。对于N维组合优化问题，每只狼为一个N维向量，一般表示为Xi(xi,1,xi,2,…,xi,N)，狼群围猎的数学模型为：

X(t+1)=Xp(t)+A·|C·Xp(t)-X(t)|；

(7)

A=2a·r1-a；

(8)

C=2·r2；

(9)

(10)

式中：X为灰狼个体；Xp为猎物位置；A和C为系数向量；t为当前迭代的代数；MaxIter为最大迭代次数；r1和r2为[0,1]之间的随机变量；a为距离控制参数，其值随迭代次数的增加而逐渐减小为0。

狼群攻击猎物的模型为：

X1=Xα+A1·|C1·Xα-X|；

(11)

X2=Xβ+A2·|C2·Xβ-X|；

(12)

X3=Xδ+A3·|C3·Xδ-X|；

(13)

(14)

式中：参数A1，A2，A3根据式(8)计算；C1，C2，C3根据式(9)计算。

3 改进的灰狼优化算法

3.1 控制参数C的确定

文献[32]通过实验验证了控制参数C对GWO算法的影响规律，即在算法的早期阶段，若C>1则算法的勘探能力不足，算法进化较慢；在算法中后期，若C<1，则算法容易出现早熟收敛的情况。鉴于此，本文提出一种新的控制参数C的方法，控制C在算法早期以较大概率小于1而在中后期以较大概率大于1，从而平衡算法的勘探能力和后期的局部搜索能力，具体公式为

(15)

式中r3为一个[0，1]之间的随机数。

3.2 灰狼编码

HFSP需要确定N个工件在每个加工阶段的加工顺序，其结果是由S个1～N的整数排列构成，本文编码只表示工件在第一阶段的加工顺序，其他阶段的加工顺序采用3.4节的解码规则确定，从而将问题的解空间减小为N!。该编码是N维空间中的一些离散点，而GWO算法更适合解决连续解空间中的问题。为了便于用GWO算法解决HFSP，这里将离散的解空间连续化，方法是将N维空间的每一位用一个(0,2)之间的实型数据表示，而该实数对应的工件编号是按照实数在向量中的数值大小确定，其中最小的实数对应工件号1，次小的实数对应工件号2，依次类推，最大的实数对应工件号N。例如5个工件对应的5维向量编码为(1.24,0.28,1.37,0.82,0.56)，其由小到大的排序结果为(0.28,0.56,0.82,1.24,1.37)，可确定5个工件的加工顺序为(4,1,5,3,2)，该顺序为工件在第一阶段的加工顺序。

3.3 镜面成像学习策略

平面镜成像是指将一个物体放置在平面镜前，则在平面镜中将呈现一个和物体大小相同、与镜面距离相同，且物与像的连线垂直于镜面的像，如图1所示。

若考虑三维空间，物O对应的点坐标为(x,y,z)，将平面镜放置在y轴和z轴确定的平面上，且x轴坐标为0的位置，则像O′的坐标为(-x,y,z)。为简化问题，不考虑镜子的其他不规则放置。利用该原理，对于N维空间的物O，假设其所在的位置为(x1,x2,…,xN)，随机产生两个1～N之间的随机数i和j，从而确定镜子的放置位置为(1,…,xi,…,xj,…,1)，则像O′的坐标分量为

k=1,2,…,N,k≠i,k≠j；

(16)

(17)

利用平面镜成像原理，在狼群围猎后，对每只灰狼进行镜面学习，若像的适应值优于其自身的适应值，则用像替换它，这种操作既有利于增加种群多样性，又可避免早熟收敛。

以3.2节的5个工件编码(1.24,0.28,1.37,0.82,0.56)为例，其确定的工件加工顺序为(4,1,5,3,2)。对其进行镜面学习，假如随机确定1～5之间两个不相等的整数为3和5，根据式(16)和式(17)，该编码的像为(0.76,1.72,1.37,1.18,0.56)，确定工件加工顺序为(2,5,4,3,1)。

3.4 解码算法

(1)先到先加工解码算法(First arrive First process, FF) 该算法的思想是对于第一个加工阶段，工件完全按照编码顺序安排加工，其他加工阶段则按照工件到达该阶段的顺序安排加工设备。因为每个加工阶段的加工设备可能不止一台，所以选择最早可加工该工件的设备进行加工，直到安排完每个工件。

(2)基于剩余未加工时间优先的解码算法(Remaining unprocessed Time first process, RT) 该算法的思想是对于第一个加工阶段，每个工件完全按照其编码顺序安排加工。对于其他加工阶段，首先将工件按其到达时间的先后顺序排序，选择可最早开工的设备，并确定该设备的最早开工时间，然后对剩余未调度的工件进行调度。若在设备的最早开工时间没有工件到来，则将最早到来的工件安排在该设备加工；若有多个工件同时到来，则选择剩余未加工时间最长的工件优先加工；若在设备可开工时间之前已有多个工件到来且未加工，则在这些工件中选择剩余未加工时间最长的工件优先加工。

(3)FF联合RT解码策略(简称FFRT) 该算法的思想是瓶颈阶段及瓶颈阶段之前的加工阶段均采用FF策略解码，瓶颈阶段的后续阶段采用RT策略。因此当瓶颈阶段在第一阶段时，该策略退化为RT策略；若瓶颈阶段在最后一个阶段，则该策略退化为FF策略。

3.5 逆序解码策略

鉴于瓶颈加工阶段对调度结果影响较大，为增加寻找最优解的机率，将文献[21]的逆序调度方法用于本文解码，具体为将工件原有加工工艺的逆序工艺作为其加工工艺，对同一个编码按照逆序工艺进行解码调度，即对于有S道工序的加工任务，其正常工序的第1道工艺对应逆序调度中的第S道工艺，第2道工艺对应逆序调度中的第S-1道工艺，依次类推。采用逆序解码的案例，需对最后最优解的调度结果进行正序化。具体方法是保持每个加工设备上分配的加工任务不变，加工顺序为与逆序解码结果相反的顺序，相应设备上每个任务的开始加工时间和完工时间如下：

(18)

(19)

3.6 改进的灰狼优化算法步骤

改进的灰狼优化(Improved Grey Wolf Optimization, IGWO)算法的具体步骤如下：

步骤1初始化狼群规模为size，初始化算法的最大迭代次数为MaxIter，令当前迭代次数t=0，采用随机算法初始化狼群。

步骤2对每只狼解码并计算适应度，找出适应度最好的3只狼，依次为α狼、β狼和δ狼。

步骤3当t≥MaxIter时，转步骤4；否则，对每只狼依次进行如下操作：

(1)用式(11)～式(14)更新狼的位置，其中控制参数C用式(15)计算，控制参数A用式(8)计算。根据3.3节的镜面学习策略找到狼的像，分别计算狼和狼的像的适应度，比较其适应度的值，若像的适应值小于狼的适应值，则用像替换狼进行下一轮捕猎行动。

(2)更新新狼群α，β，δ狼的位置及其对应的适应度值，返回步骤3。

步骤4输出α的解码结果。

4 仿真实验

为了验证本文所提算法的有效性，在PC机(i7-8550U/2 GHzCPU，16 G内存空间，WIN10)采用VC++2006实现了算法。HFSP实验案例选自Carlier and Néron(2000年)[33]提出的benchmark案例，包括47个a类和b类简单案例与30个c类和d类复杂案例。a类和b类案例的特点是只有一个瓶颈阶段，且瓶颈阶段只有一台加工设备，而其他加工阶段均有3台加工设备，其中a类的瓶颈阶段在中间阶段，b类的瓶颈阶段在开始阶段或结束阶段；c类案例瓶颈阶段在中间阶段，且有2台加工设备，其他阶段有3台加工设备；d类案例没有明显的瓶颈阶段，每个阶段均有3台加工设备。案例名称中的j表示待加工工件，c表示加工阶段，a表示a类案例。

通过正交实验确定灰狼种群为40，算法的最大迭代代数为1 000，并设置了100代内最优解无更新算法则自动结束算法。实验中，每个案例最多运行20次，10次采用正序解码，10次采用逆序解码。在表1～表3中：LB为最大完工时间的下界；BD为该案例的瓶颈度，

(20)

Cmax为最大完工时间；times为IGWO算法取得最优解的最小迭代代数；PD为最优解Cmax相对下界LB的偏离度，用百分比表示为

(21)

4.1 a类和b类案例的实验

在实验过程中，IGWO算法采用3.3节设计的3种解码算法，分别记为FF-IGWO, RT-IGWO和FFRT-IGWO，鉴于a类和b类问题较为简单，实验只使用正序解码，每个算法运行10次，实验结果如表1所示。

表1 a类案例和b类案例的实验结果

续表1

从表1可见，47个案例瓶颈阶段的加工负载是其他阶段加工负载的2倍以上，说明其他阶段的加工顺序对整个加工任务的完成时间影响不大，而瓶颈阶段工件的加工顺序对调度结果影响较大；FF-IGWO和RT-IGWO对47个案例均找到了下界，而FFRT-IGWO找到了46个案例的下界；本文算法对大部分案例在迭代代数为0时找到了最优解，说明算法在初始化阶段就能找到大多数案例的最优解，从而说明本文所提解码算法的有效性；FFRT-IGWO在47个案例上运行的平均迭代次数最小，在一定程度上说明FFRT解码方法对此类问题的有效性。

4.2 c类和d类案例的实验

由于c类和d类问题的复杂度较高，每个案例采用3种不同解码策略的IGWO算法求解，每个算法最多计算20次，前10次采用正序解码，若正序解码没有找到问题的下界或目前最优解，再采用逆序解码运行后10次，记录最优值。表2中加粗的数据为采用逆序解码求得，表明采用正序解码无法求得相应最优解。将本文IGWO算法与目前其他较好算法，如分布估计算法[34](Estimation of Distribution Algorithm, EDA)、变邻域改进遗传算法[35](Improved Genetic Algorithm Variable Neighborhood Search, IGA-VNS)和改进的灰狼优化算法LIL-GWO[31](lens imaging learning grey wolf optimizer algorithm)进行实验对比。其中：EDA和IGA-VNS采用原有文献的实验结果；LIL-GWO是目前对参数C进行改进的较好的GWO算法，其解码算法采用本文提出的较好的解码方法FFRT，种群规模、迭代代数、运行次数也采用本文IGWO算法的设置。实验结果如表2所示。

表2 c类和d类案例的实验结果

续表2

从表2可见，c类和d类案例的平均瓶颈度为1.4，相对于a类和b类问题的瓶颈度大大减小，说明瓶颈阶段对调度结果的影响变小，其他阶段加工顺序对调度结果的影响增加，问题的复杂性增加。

对前5种算法进行分析。从30个案例的求解平均偏差PD值看，前5种算法中FFRT-IGWO最好，平均PD值为3%；RT-IGWO次之，平均PD值为3.02%；第3为FF-IGWO，平均PD值为3.04%；第4为EDA，平均PD值为3.06%；最差的是IGA-VNS，平均PD为3.26%。从30个案例的实验结果看，前5种算法中，FFRT-IGWO和RT-IGWO找到了28个案例的目前最优解，FF-IGWO找到了27个，EDA找到了26个，而IGA-VNS算法只找到23个，说明FFRT-IGWO和RT-IGWO最好。在FFRT-IGWO找到的28个最优解中有4个案例采用逆序解码找到，在RT-IGWO找到的28个最优解中有3个案例采用逆序解码找到，在FF-IGWO找到的27个案例的最优解中有7个案例采用逆序解码获得，说明了逆序解码策略的必要性，也一定程度说明了逆序解码对FF解码策略有较大影响。案例j10c10c1的实验结果114是目前找到的最优结果，这一结果用本文所提的3种解码方案采用逆序解码均能找到，进一步验证了逆序解码的必要性。综上所述，本文提出的FFRT-IGWO算法效果最好。

将本文FFRT-IGWO算法与同样对控制参数C进行改进并具有学习策略的LIL-GWO算法，对c类和d类案例的实验结果进行比对。实验发现，在j10c5c4和j10c10c6案例上，FFRT-IGWO算法的寻优结果较LIL-GWO算法好，而在剩余其他28个案例上两个算法的最优解完全一样，说明本文对GWO算法改进的有效性。

4.3 算法有效性验证

为了说明本文所提策略的有效性，将标准灰狼优化算法记为GWO，改进控制参数C的GWO算法记为ICGWO，采用镜面学习策略的GWO记为IMGWO，综合改进后的GWO记为IGWO，所有算法的解码方法均采用逆序RT方法，实验案例选择规模较大、复杂度较高的6个案例j10c10c1～j10c10c6，每个算法在每个案例上运行10次，统计10次取得的最优解Cmax，以及10次最优解的平均值AV和偏差值PD，实验结果如表3所示。

表3 算法有效性验证

从表3可见6个案例中，本文RT-IGWO算法取得的最优解均较好。与RT-IGWO算法的实验结果相比，RT-ICGWO算法和RT-GWO算法在案例j10c10C6上取得的最优解与其相同，其他5个案例均较差，RT-IMGWO算法有4个案例取得的最优解与其相同，2个较差，从而说明RT-IGWO算法的有效性。比较RT-ICGWO算法与RT-GWO算法发现，RT-ICGWO算法有3个案例的最优解优于RT-GWO算法，有3个案例的最优解与RT-GWO算法相同，但从6个案例的AV值发现，RT-ICGWO算法有5个案例的AV优于RT-GWO算法，1个与之相同，说明改进控制参数C的策略有效平衡了算法的局部搜索和局部搜索性能，提高了算法找到最优解的概率。比较RT-IMGWO算法与RT-GWO算法发现，RT-IMGWO算法有4个案例的最优解优于RT-GWO算法，有2个案例的最优解与RT-GWO算法相同，但从6个案例的AV发现，RT-ICGWO算法有5个案例的AV优于RT-GWO算法，1个较差，从而说明了平面镜学习策略的有效性，最大限度避免了算法陷入局部最优。

图3所示为IGWO算法与GWO算法在较复杂案例 j10c10c1上进行实验对比的收敛曲线。设每个算法的最大迭代代数均为1 000次，且均采用逆序解码，分别采用3种不同的解码算法形成6种算法，记为RT-IGWO，FF-IGWO，FFRT-IGWO，RT-GWO，FF-GWO，FFRT-GWO。可见，在采用相同解码算法时，IGWO算法比GWO算法的收敛速度快，而且很容易找到较好的最优解，进一步证明了相关改进策略的有效性。图4所示为案例j10c10c1的调度甘特图，其中横坐标为时间轴，纵坐标为工件的10个加工阶段以及每个阶段的设备信息。

4.4 实际案例仿真结果

某汽车发动机缸体生产线生产1.8 L和2.4 L两款自然吸气发动机以及1.5 T和2.0 T两款涡轮增压发动机。生产线包括定位基准、粗加工、中间清洗、压检、压装、精加工、清洗、终检8道工序，每个缸体加工工件时均以相同的顺序经过以上8道工序，8道工序配备相同的并行机，数量依次为(2,3,1,1,1,3,1,1)，缸体的生产时间如表4所示。

表4 缸体生产时间

车间所加工产品相应的数量如表4所示，车间原有的调度甘特图如图5所示，其中最大完工时间为3 740 s。采用本文FF-IGWO算法进行调度的甘特图如图6所示，其中最大完工时间为3 570 s，总工时减少170 s，比原来减少约4%，因此提高了企业生产效率。

5 结束语

带有相同并行机的HFSP是典型的NP难题，针对该问题，本文提出一种IGWO算法。该算法给出控制参数C新的计算公式，从而提高了早期算法的勘探能力和后期算法的局部搜索能力。鉴于算法后期狼群急剧聚集，种群多样性不足，将镜面成像学习策略应用其中，增加了种群多样性。同时考虑混合流水车间各加工阶段设备配置不均衡会影响瓶颈加工阶段的解码结果，提出正序解码与逆序互补解码策略，提高了找到问题最优解的概率，并通过实验验证了算法的有效性和可靠性。

下一步的研究工作为：

(1)针对复杂环境的生产调度问题进一步展开研究，如基于物联网的实时调度研究、考虑多约束条件的调度问题研究等。

(2)GWO算法的发展历史比较短，还有很多待解决的问题，对GWO算法进一步展开理论和应用研究将是未来的一个研究方向。