改进GWO算法求解柔性作业车间调度问题

马随东，艾尔肯·亥木都拉，郑威强

(新疆大学机械工程学院，新疆乌鲁木齐 830017)

0 前言

车间调度任务的基本目的是根据不同客户的订单在截止日期内完成指定生产任务的活动。柔性作业车间调度问题(Flexible Job Shop Scheduling Problem，FJSP)广泛存在于人类生产活动的各个领域，如纺织制造、半导体制造、汽车装配以及化学材料加工等。FJSP由机器分配和操作排序2个子问题组成，机器分配解决每个操作的候选集中机器选择问题，操作排序是调整每个机器上的所有操作，使得完成所有操作的最大完工时间最小。众所周知FJSP是NP难问题，求解该问题可以采用精确方法和近似方法，由于NP难问题的复杂性，精确方法在复杂FJSP上不适用，近似方法是目前研究FJSP的主流方法。

国内外学者利用近似算法对FJSP的应用进行了大量研究。在进化算法(Evolutionary Algorithms，EA)方面，学者们根据FJSP的特点对编码、初始种群、选择、交叉以及变异进行了大量研究，很多研究还将局部搜索算法嵌入EA，加强了EA算法的局部开发能力[1-2]。在群体智能算法(SI)方面。姜飞等人[3]以最大完工时间和客户满意度为目标，通过灰狼优化算法对多目标柔性作业车间动态调度问题进行了研究。姚远远、叶春明[4]以最小化最大完工时间为目标，通过改进混合灰狼算法对作业车间调度问题进行了研究，与布谷鸟搜索算法进行对比，验证了改进GWO求解作业车间调度问题的有效性。吴继浩、杨涛[5]结合改进GWO算法与模拟退火算法对FJSP进行了研究。姜天华[6]以最小制造时间为目标对JSP和FJSP设计了离散GWO算法。由于FJSP的本质是离散的，故对FJSP应用GWO之前要实现灰狼个体位置的离散性和多样性。

考虑到GWO与局部搜索算法集成的便利性，本文作者首先采用机器和工序的双层编码策略，并设计种群初始化方案；其次评估初始种群质量，并进行精英保留和锦标赛选择；接着为了寻找操作序列的最优顺序，对操作序列设计了GWO邻域搜索；然后对生成的最优序列执行TS搜索。此外，为了搜索种群中最优灰狼个体位置周围的搜索空间，对灰狼个体位置设计了变异操作。最后通过基准实例的仿真实验，评估改进GWO算法求解FJSP的性能。

1 模型建立

目前FJSP公认的数学模型是存在一组作业J={J1，…，Jn}和若干机器M={M1，…，Mm}，每个作业有若干操作，即Ji={Oi，j，…，Oi，ni}，其中ni是Ji的操作总数，每个操作都有对应的机器子集Mi，j⊆M，问题要求是将所有操作分配到对应机器上且要保证每台机器上的操作序列是最优的，即保证所有作业的最大完工时间最小min(Cmax)。

2 灰狼优化器原理

灰狼优化器原理如图1所示。α、β、δ狼称为领导者，ω狼称为进攻者，一个灰狼个体代表了一个可行的调度方案，位于金字塔顶端的α狼代表最优调度方案。当初始种群确定后，按照灰狼个体的最大制造跨度将所有灰狼个体进行排列，以确定最好的领导者和攻击者，GWO的搜索行为由领导者进行引导。灰狼算法搜索过程可分为围捕、狩猎和攻击3个阶段。

图1 灰狼领导层级

2.1 围捕

围捕阶段，由式(1)(2)完成对猎物的包围。

Dp=|C·Xp(t)-X(t)|

(1)

X(t+1)=Xp(t)-A·Dp

(2)

式中：t为迭代次数；Xp为猎物位置；X为ω狼的位置；Dp为猎物与ω狼之间的绝对距离；A和C是系数向量，由式(3)(4)确定。

A=2ar1-a

(3)

C=2r2

(4)

式中：r1、r2∈rand(0，1)是随机向量；a是收敛系数，从2逐渐下降到0，由式(5)确定。

(5)

式中：a1=2和a2=0为收敛系数的初始值和终止值；n为递减系数，n=1-t/tmax。

2.2 狩猎

在狩猎阶段，由于猎物位置(最优解)未知，故领导狼需预测猎物的潜在位置，而进攻狼根据领导狼的位置进行调整，以便攻击猎物。式(6)—(8)描述如下：

(6)

X1=Xα-A1·Dα

X2=Xβ-A2·Dβ

X3=Xδ-A3·Dδ

(7)

(8)

2.3 攻击

灰狼是否对猎物发动攻击由收敛系数A决定，当|A|≥1时，灰狼与猎物疏远进行全局搜索；当|A|<1时，灰狼接近猎物完成猎杀任务。

3 改进GWO算法的实现

由于GWO算法求解FJSP时会很快陷入局部最优，故将禁忌搜索算法(Tabu Search，TS)嵌入到GWO算法中，以辅助GWO算法跳出局部最优。所提GWO算法工作流程如图2所示。

图2 GWO算法的工作流程

3.1 编码与解码

由于编码策略不仅影响算法各部分的连接和解码效率，而且对GWO与局部搜素算法的集成至关重要。因此采用机器分配和操作排序双层编码策略，将作业、机器和加工时间一一对应。首先在区间[-n，n]内生成一个由实数组成的灰狼位置向量，向量中的元素符合均匀分布，且该向量与作业操作数量的长度相等，其中n表示作业数量，接着利用ROV规则将灰狼位置向量中的元素转换为对应的操作序列，图3所示为转换之后的操作序列：1→3→3→2→1→2→3→1→2。序列中相同数字出现的次数表示作业的第几次操作。如序列中第一个1代表第一个作业第一个操作O11，第二个1代表第一个作业第二个操作O12，其余作业操作依次类推。然后根据每个操作的可选机器集长度为每个操作随机分配一台机器。

图3 编码策略

3.2 种群初始化

根据第3.1节获得的机器序列和操作序列生成初始种群，方法如下：在机器分配阶段，首先依据操作Oi，j的加工条件，在可选机器集中为操作Oi，j选择加工时间最短的机器M1和可行时间最早的机器M2，分别计算操作Oi，j在机器M1和M2上的完成时间T1和T2，若T1

3.3 搜索猎物

应用GWO算法求解FJSP的关键是保证GWO算法的全局性和多样性。故针对操作序列设计了交叉邻域、插入邻域和路径重连邻域3种邻域函数，邻域函数表达式为式(9)，所设计GWO算法邻域搜索结构如图4所示。式(9)中Xk表示由邻域函数得到第k个灰狼的调度方案，Insertion函数定义了对Xβ进行插入邻域，Swapping函数定义了对Xα进行交叉邻域，PathRelinking函数定义了对Xδ进行路径重连邻域，r∈[0，1]是随机数。

(9)

图4 GWO算法邻域搜索结构

GWO算法邻域搜索步骤如下：

步骤1，设置迭代次数k=1和邻域数量Δ，令Δ=1，2，…，Δmax，选择较优的灰狼个体Xk(t)。

步骤2，随机生成一个随机数r≤[0,1]，执行以下程序：

(1)若r≤1/3，则执行Swapping邻域产生一个新的调度方案α。

(2)若1/3

(3)若r>2/3，则执行PathRelinking领域产生一个新的调度方案δ。

步骤3，判断k≤Δmax是否成立，若条件成立，令k=k+1，则转到步骤2，否则转到步骤4。

步骤4，根据式(6)—(8)更新α、β和δ狼的个体位置。

步骤5，按照α、β和δ狼的makespan进行排列。

步骤6，输出最优调度方案α。

3.3.1 交叉邻域

首先在OS序列中随机选择2个不同的位置k1和k2，然后将k1和k2位置上的序列交换，其余序列的位置不变。交叉邻域如图5所示。

图5 交叉邻域

3.3.2 插入邻域

首先在OS序列中随机选择2个不同的位置k1和k2，若k1

图6 插入邻域

3.3.3 路径重连邻域

PR邻域如图7所示。具体表述如下：首先从初始种群中随机确定起始解OS和导向解OS′，然后建立路径解，即比较OS与OS′中第i个位置上的序列是否相等，若相等，则保持OS中第i个位置上的序列不变，否则在OS中找到与OS′序列相等的第j个序列，将OS中第j个序列插入到第i-1个序列的后面，重复上述过程直到最后一个路径解与导向解完全一致，最后计算每个路径解的最大制造跨度，选择最大制造跨度最小的路径解作为新的个体。

图7 PR邻域

3.3.4 机器变异

根据操作序列OS的长度，变异位置个数取OS长度的一半并左取整，接着将所选位置的机器更改为对应操作的可选机器集中的其他机器。机器变异如图8所示。图8中OS长度为9，变异位置为4，选择操作O1，1、O2，2、O2，3和O3，2的机器序列进行变异，例如O1，1的可选机器为M1和M3，变异前为M3，变异后为M1。

图8 机器变异

3.4 TS搜索

TS算法[7]从一个可行解出发，通过关键加工路径的Nopt1邻域搜索最优解[8]。TS的初始调度方案为α，TS搜索流程如图9所示，执行步骤如下：

图9 TS搜索流程

步骤1，设置TS迭代次数k、s，置禁忌表为空，初始调度方案为α，禁忌迭代次数Tn，禁忌阈值Tu。

步骤2，判断k≥Tn是否成立，若条件成立，则执行步骤8，否则执行步骤3。

步骤3，获取α的关键加工路径上的操作和机器分配，改变关键操作的机器分配生成新邻域，估计每种邻域的最佳制造跨度。

步骤4，判断s≥Tu是否成立，若条件成立，则执行步骤5，否则执行步骤6。

步骤5，将满足藐视准则的候选解作为当前解，并执行步骤7。

步骤6，判断候选解的禁忌属性，选择邻域中非禁忌的最佳解作为当前解，并执行步骤7。

步骤7，更新禁忌列表，转到步骤2。

步骤8，输出最优调度方案。

在GWO邻域搜索阶段，首先通过Swapping、Inserting和PathRelinking邻域和机器变异得到操作分配的最优方案α，然后对α分配方案进行TS搜索，对于每个Nopt1邻域要先确定关键加工路径中的关键操作，调整这些操作可以有效优化makespan。在TS搜索过程中，TS迭代次数随着GWO迭代次数的增加而增加，TS禁忌阈值由关键加工路径上操作数量的倍数组成。

3.5 变异操作

由于当前个体的位置更新依赖于最佳狼α、β和δ的位置信息，这种更新机制往往缺失种群多样性，易使算法早熟收敛。故通过式(10)对最佳领导个体进行变异操作，以使领导个体从自身搜索空间周围探索新的最优解[9]。

(10)

4 实验

4.1 实验设置

改进GWO算法在Intel(R) Core(TM) i5-6300HQ CPU @2.30 GHz,4 GB RAM的PC上运行，运行系统为Windows10专业版，代码在MATLAB2021a上实现。实验中选择58个测试实例验证改进GWO算法的有效性。这些测试基准分别是Brandimate(1993)的10个实例(MK01-MK10)、Kacem(2002)的5个实例(K01-K05)、Hurink(1994)等的43个实例(mt06、mt10、mt20以及LA01-LA40)。表1为改进GWO算法的参数设置。

表1 改进GWO算法参数设置

4.1.1 实验一

表2为改进GWO算法与其他算法在Kacem测试实例上的结果对比。HA[1]、HGWO[6]、TS[7]、VNSGA[10]、Heuristic[11]、MA[12]、IWOA[13]、GLNSA[14]为对比算法，在以上算法中只有 GLNSA、Heuristic、HGWO以及IWOA算法获得了Kacem算例的完整解，其中仅有GLNSA算法达到目前已知的最优解，改进GWO算法获得的最优解优于HGWO，与GLNSA算法的最优解相当，此外改进GWO算法运行时间也优于HGWO算法。

表2 Kacem算例实验数据对比

4.1.2 实验二

表3为改进GWO算法与其他算法在Brandimate测试实例上的结果对比。HA[1]、GA-RRHC[2]、HGWO[6]、Heuristic[11]、MA[12]、IWOA[13]、GLNSA[14]、HLOA[15]、PSO+TS[16]为对比算法。在对比算法中HLOA和HA算法结果较好，Heuristic算法运行时间最短，但运行结果最差；改进GWO算法优于HGWO算法，取得了5个测试实例的最佳解，且改进算法具有更短的运行时间，与其他算法相比，改进算法具有一定的竞争性。

表4 对比算法在Brandimate算例上的RPD值对比

4.1.3 实验三

表5为改进GWO算法与其他算法在Hurink测试实例上的结果对比。HA[1]、GA-RRHC[2]、GLNSA[14]、IATS[15]为对比算法，其中GLNSA、GA-RRHC和HA算法获得的最优解相当，都获得了32个测试实例的最佳解，改进GWO算法获得了30个测试实例的最优解，高于IATS算法所获得测试实例最优解的个数。

表5 Hurink vdata实例实验结果对比

5 结论

文中以最大完工时间为目标，应用改进GWO求解了柔性作业车间的调度问题。首先改进了GWO的编码方案、种群初始化、灰狼变异以及种群更新机制，其次通过交叉邻域、插入邻域以及PR邻域得到GWO算法全局搜索邻域，接着提出禁忌搜索邻域以增强GWO算法局部开发能力。最后将所提算法在已知的著名算例上进行仿真实验，并与其他算法进行了对比。实验结果验证了改进GWO算法具有一定的优越性。