一种求解柔性作业车间调度问题的改进灰狼优化算法

张其文,王 超

(兰州理工大学 计算机与通信学院,甘肃 兰州 730050)

柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)是作业车间调度问题(job-shop scheduling problem,JSP)的一个延伸问题.在JSP中加工机器及加工时间是确定的，而FJSP的每道加工工序的加工机器是不确定的，每个工件的每道工序可在多个不同的机器之间进行选择加工，且不同加工机器所对应的加工时间不同.由于它的这一特性，FJSP已经被证实是一个NP难度的问题[1].

近年来，元启发式算法已成为车间调度领域广泛研究的解决办法，它的出现也为更有效地求解FJSP提供了新的思路.姜天华[2]提出了一种改进猫群优化算法来求解柔性车间调度问题，算法在猫群的跟踪模式阶段引入莱维飞行，来增强算法跳出局部最优的能力.屈迟文等[3]针对柔性作业车间调度问题，将黑洞搜索策略及关键工序的邻域搜索引入鸟群算法提出了一种改进鸟群算法，提高了算法的种群多样性及求解精度.Gaham等[4]针对柔性作业车间调度问题，将一种智能突变算子引入离散和声搜索算法提出了一种基于有效置换工序的离散和声搜索算法，有效地提高了算法的全局搜索能力.Lei等[5]针对考虑能耗的多目标柔性作业车间调度问题，提出了一种两阶段的启发式算法，将帝国主义竞争算法与变邻域搜索算法相结合，在兼顾能耗约束下得到了更好的总完工时间和总延时.Luo等[6]针对多目标柔性作业车间调度问题，提出了一种多目标灰狼算法，通过同时参考种群最差解及最优解的信息，提出了新的个体位置更新方法，提高了算法的全局搜索能力.Sun等[7]针对模糊柔性作业车间调度问题，将粒子群优化算法与遗传算法相结合，提出一种混合协同进化算法.栾飞等[8]将鲸鱼群算法应用于柔性作业车间调度问题，并用算例证明了算法在求解FJSP上的有效性.由于FJSP的NP难度特性，当问题的规模变大时，使用现有算法求解则无法避免地会出现优化效率降低、解的质量差等问题.

灰狼算法(grey wolf optimization，GWO)是一种根据模仿狼群捕食行为产生的新兴元启发式算法，算法将狼群的等级制度引入到个体的位置更新上，种群中适应度值最优的三只狼为狼群的决策层，灰狼个体在决策层个体的指引下不断地探索解空间最终寻找到最优解，在函数优化问题上相比粒子群优化算法、遗传算法精度高，收敛速度快[9].该算法的缺陷在于算法依赖于种群三个最优个体的引导，若最优个体与全局最优点相距过远，算法就会容易陷入局部最优，求解高维度问题时会导致算法无法收敛到全局最优值.因此本文针对GWO的不足进行改进，提出一种改进灰狼优化算法(improved gray wolf optimization,IGWO)，并将其应用于求解FJSP.

1 柔性作业车间调度问题

1.1 问题描述

假设一个车间有m台加工机器和n个工件，每个工件有若干不等个工序待加工，工序的加工按照一定的顺序进行，每个工序的加工过程都可以在许多不同的机器上进行，且所需加工时间不同.FJSP问题的优化目标是为每个工序分配适当的机器，并对每台机器上的工序加工顺序进行排序，以期实现给定目标最优.

对于FJSP问题，存在以下前提：

1) 零时刻，所有工件和机器都处于可用状态；

2) 加工前的机器准备时间被忽略；

3) 工序加工一旦开始，便无法中断;

4) 一台机器一次只能够处理一个工件；

5) 不同工件的工序之间相互独立，同一工件的工序之间具有先后加工的确定关系；

6) 各工件加工的优先级相同.

1.2 数学建模

本文以车间的最大完工时间最小化为目标所建立的数学模型如下：

其中:n表示工件数；m表示机器数,k∈{1,2,…,m}；假设Oij为工件i的第j道工序；Cmax表示最大完工时间；Cij表示工序Oij的完工时间；Sij表示工序Oij的开始加工时间；xijk是一个变量，当它为1时表示工序Oij在机器k上加工，否则便为0；tijk表示机器k上工序Oij的加工时间；yiji′j′k是一个变量，当它为1时表示工序Oij在机器k上的加工顺序先于工序Oi′j′，否则便为0；c为一个无穷大的数.

式(1)表示本文的优化目标为最大完工时间最小化；式(2)表示工件的加工过程不能中断；式(3)与式(4)表示一台机器同一时刻只能处理一个工件；式(5)表示同一工件不同工序加工顺序具有约束.

2 改进灰狼优化算法

2.1 编码与解码

灰狼优化算法起初是为了解决连续问题而提出的，但FJSP是一个离散问题，如何使用适当的编码与解码机制来建立离散量与连续量之间的联系是使用GWO解决FJSP问题的关键之一.根据FJSP问题的特点，每个个体的编码被分为两个部分：一部分是机器分配，另一部分是工序排序.这两部分组成一个染色体，作为一个可行的柔性作业调度车间解决方案.

假设某车间包含3个工件，每个工件有2个加工工序，则个体位置向量的总长度为12，位置向量的各元素值在[-3,3]取值.表1为有3个工件，每个工件有2道工序的个体位置向量，其中工序编号Oij表示工件i的第j道工序.

表1 个体位置向量Tab.1 Individual position vector

在个体位置向量向调度方案转换时，机器分配部分采用了文献[10]中所用的方法，使用下式将个体位置向量值转换为工序可选分配机器集的编号：

(6)

其中:u(j)表示个体j所分配机器在对应的工序可选分配机器集的序号(1≤j≤l)；x(j)表示个体j的位置向量值；s(j)表示个体j对应的工序可选分配机器数；λ表示工件数；l表示总工序数.

在调度方案向个体位置向量转换时，使用式(6)的逆运算进行.

在个体位置向量向调度方案转换时，工序排序部分采用文献[11]中的排列顺序规则ROV(ranked order value).首先，将每个个体的位置向量值按照升序进行排序，排序的次序便是ROV值，按照ROV值所对应的次序对向量值的初始工序编号进行排序，得到工序排序.表2为个体位置信息与工序排序之间的对应关系.

表2 位置信息与对应工序排序的关系Tab.2 The relationship between location information and corresponding operation sequencing

在调度方案向个体位置向量转换时，则是首先在[-λ,λ]生成随机值，对随机值用升序排列的方式生成ROV值，并与工序排序相对应.将ROV值按照表2初始工序编号的次序进行重排来得到对应的新的随机值排列，进而完成对个体位置向量值的确定.

2.2 种群初始化

对于FJSP问题，初始种群的质量对于问题的有效解决有至关重要的作用.本文采用了文献[12]中的启发式规则，即全局搜索方法对每个工序进行机器分配.

全局搜索：设置一个与机器数等长的数组，数组的每一位值对应相应机器的加工时间.随机选择一个工件，从第一道工序开始，将当前工序可选机器的加工时间与数组对应位置相加，选择加工时间最短的作为加工机器，并将时间保留在数组对应位置.以此类推，直到所有工序的机器选择完毕.

这样可以在考虑最大完工时间最小的同时减小机器负荷.对于工序排序部分则采用随机化方法进行初始化.

2.3 个体位置更新方法

由文献[13]可知，基本灰狼算法的全局搜索及局部搜索主要依靠收敛因子a进行调节，在基本灰狼优化算法中，a的值从2到0线性递减，如下式所示：

a=(amax-amin)-(amax-amin)x/xmax

(7)

其中：amax和amin分别为收敛因子的最大值及最小值，本文分别为2和0；xmax为算法最大迭代次数；x为当前迭代次数.

当a∈[1,2]，算法处于全局搜索阶段，全局搜索能力强，有利于跳出局部最优；当a∈[0,1)时，算法处于局部搜索阶段，局部搜索能力强，有利于快速收敛.若这两个过程协调不佳，算法便容易趋于局部最优，由于具体的优化过程通常是比较复杂、非线性的，因此基本灰狼算法中所使用的线性收敛因子是不适应复杂的优化过程的.

双曲正切函数在神经网络领域作为激活函数有着很好的应用[14]，为了更好地平衡算法的全局搜索与局部搜索，本文将双曲正切函数引入灰狼算法的非线性收敛因子公式，如下式所示：

a=-(amax-amin)tanh((4/xmax)x-4)

(8)

图1给出了改进后的非线性收敛因子与基本灰狼算法中线性收敛因子的对比.由图1可以看出，在迭代初期,相比基本灰狼算法中的线性收敛因子，非线性的收敛因子曲线的斜率是较小的，收敛因子值较大，即在初期算法处于全局搜索阶段，在大范围内搜索最优解，并尽可能保持这种状态;在迭代后期,非线性的收敛因子曲线斜率大，收敛因子值小，即在后期算法处于局部搜索阶段，在小范围内进行开发过程，并加快收敛过程.线性收敛因子的曲线则从始至终一直保持相同的斜率，并没有有效地平衡算法的全局搜索与局部搜索过程.

基本灰狼算法中的普通灰狼个体位置是根据三个最优灰狼位置信息的均值计算出来的.若最优个体并不是全局最优，算法便容易在最优个体的指引下趋于局部最优.为了改善算法容易趋于局部最优的问题，并更好地体现出灰狼优势群体的指导作用，本文在个体位置更新阶段提出了一种基于适应度值的加权距离更新方法.如下式所示：

其中:fα、fβ、fδ分别表示灰狼领导者α、β、δ的适应度值.

由式(9,10)可以看出，随着算法优化过程的进行，适应度值会逐渐减小，权重值也会随之减小;在最优的三个个体中，α所占权重值最小，β、δ次之.通过这种方法在优化过程中减少对当前最优个体的依赖，并适当增加次优解个体在优化过程中参与的比重来改善算法在进行至后期时，由于过分依赖于最优个体而致使个体局部聚集，种群多样性减少，陷入局部最优的问题.相比较基本灰狼算法中的个体位置更新方法，本文通过增加优势群体的适应度值作为权重，而不是仅仅依靠位置信息来进行位置更新;在迭代中，基于适应度值权重的动态变化可以更好地平衡全局搜索和局部搜索，加快算法的收敛速度.

2.4 变邻域搜索算法

变邻域搜索算法是一种有效的局部搜索算法，对于求解车辆路径规划问题[15]、装配线平衡问题[16]这样的组合优化问题具有很好的效果.它的基本思想是系统地改变搜索过程中当前解的邻域结构集，扩大搜索范围，然后通过局部搜索算法得到局部最优解，然后再基于局部最优解重复搜索，最终得到较优解[17].

关键路径是指甘特图中无空闲时间的最长路径，它的存在决定了调度方案的最大完工时间[18].通过对关键路径上的工序进行移动或者改变加工机器，能够最大可能地减小最大完工时间.图2为某调度方案中的关键路径，同一个调度方案可能有多条关键路径，在变邻域搜索时若有多条关键路径则对所有关键路径均执行邻域搜索.通过对关键路径上工序O33进行重新分配机器，得到如图3所示的新的调度解，最大完工时间缩短了两个单位.

图2 关键路径示意图Fig.2 Critical path schematic

图3 变邻域搜索结果示意图Fig.3 Variable neighborhood search results diagram

由于灰狼算法的迭代寻优过程主要依赖于种群最优的三个个体α、β、δ的指导，若最优个体并不是全局最优，算法便容易趋于局部最优.本文使用基于关键路径的变邻域搜索算法对种群最优个体进行局部搜索，通过对最优个体的迭代寻优，进而使得算法找到全局最优值的可能性更大.

本文针对FJSP的特点设计了三种基于关键路径的邻域结构.

1) 邻域结构N1：随机选择2道不同工件的工序，互换两工序所在的位置，重复多次改变工序位置.

2) 邻域结构N2：在工序排序部分中随机选择2个元素，将排后的元素插入在排前的元素之前.

3) 邻域结构N3：在机器分配部分随机选择一个元素，将该元素所对应工序分配至不同的可用机器上.如果只有一个机器能处理该工序，则不变.

变邻域搜索算法的主要流程如图4所示.

图4 变邻域搜索算法流程图Fig.4 Flow chart of variable neighborhood search algorithm

3 仿真实验及分析

为了验证本文所提算法在解决FJSP问题上的有效性，选取了文献[3]中某制造业工厂的加工车间实例及文献[1]、文献[19]的部分Kacem和Brandimarte基准算例进行仿真，算例中工件数从4到20不等，机器数从5到15不等.

实验环境：Windows10系统，MatlabR2016a编程平台，处理器为Intel(R)Core(TM)i5-8300H，内存为16 GB.

3.1 实际案例测试

某制造厂实际加工车间有待加工工件6个，加工机器数量为6，具体机器加工时间见文献[3].为客观起见，将算法参数设置与文献[3]相同，即种群大小为100，最大迭代次数50次，变邻域搜索最大迭代次数qmax为3，每个实例独立运行20次.

为便于对比，将算法运行结果与文献[3]中所列改进鸟群算法(improved bird swarm algorithm,IBSA)以及经典算法如粒子群算法(particle swarm optimization,PSO)和布谷鸟搜索算法(cuckoo search algorithm)结果进行比较，并对本文算法中改进机制的有效性进行验证.表3为IBSA、GWO等五种算法在求解某制造厂实际柔性作业车间调度问题的结果统计.其中GWO表示基本灰狼优化算法，GWO+IM表示增加了种群初始化方法的GWO，GWO+IM+IU表示在GWO+IM中使用了本文所提个体更新方法，IGWO即本文所提出的改进灰狼优化算法.

表3 实例求解结果统计Tab.3 Statistical results of the example solution

由表3可以看出，在最优值方面，IBSA、GWO+IM、GWO+IM+IU、IGWO都取得了七种算法中的最好结果，而GWO、PSO、CS并没有能够求得最优值.在均值方面，IGWO在七种算法中的结果最好，其次是GWO+IM+IU、GWO+IM与IBSA，GWO、PSO及CS则相差较多.在方差方面，IGWO最小，说明IGWO在求解FJSP问题上稳定性比IBSA、GWO等算法都要好.由表3也可以看出，IGWO相比GWO所采取的改进方法是有效的.图5为实际案例的最优调度甘特图.

图5 IGWO求解实际案例的最优调度甘特图Fig.5 IGWO solving practical example of the optimal scheduling Gantt chart

3.2 算例测试

为了更好地验证算法在解决FJSP问题上的有效性，实验选取了部分Kacem与Brandimarte算例，将实验所得结果分别与多目标进化算法(multi-objective evolutionary optimization，MEO)[1]、改进猫群算法(improved cat swarm optimization，ICSO)[2]、鲸鱼群算法(whale swarm algorithm，WSA)[8]、启发式算法(heuristic algorithm，HA)[20]、改进鲸鱼算法(improved whale optimization algorithm，IWOA)[21]、分布粒子群算法(distributed particle swarm optimization，DPSO)[22]的实验结果作对比，对比结果见表4和表5.其中，n表示工件个数，m表示机器数量，粗体表示同算例中算法结果的最优值.

表4 Kacem算例对比结果Tab.4 Comparison results of Kacem example

表5 Brandimarte算例对比结果Tab.5 Comparison results of Brandimarte example

在算例测试中，为了更好地发挥IGWO的性能，经实验验证后参数设置为以下条件：种群数为100，最大迭代次数800次，变邻域搜索最大迭代次数qmax为3，每个算例独立运行10次.

由表4及表5数据可以看出，IGWO在小规模Kacem算例测试下，均能取得当前对比文献中的最优值，在Brandimarte这样的中大型算例测试中，MK01、MK04、MK07及MK08算例测试均获得了当前的最优值，在面对MK10这样的大规模算例时效果不太理想，但结果与当前最优值相差不大，GWO则在最优值方面与IGWO结果相差甚远，由此也可以看出IGWO相比GWO的改进是有效的.从表4及表5总体的结果来看，IGWO算法目前应用于中小规模FJSP时，效果良好，在面对较大规模FJSP时会出现效果不理想的情况.因此本文所提算法在解决FJSP问题上有一定的有效性.

4 结语

本文以柔性作业调度车间最大完工时间最小化为目标，对灰狼算法进行了一系列改进.在编码阶段，采用两段式的编码方法，建立了离散问题与连续空间的映射；其次，采用一种启发式的规则对种群进行初始化，提高了种群质量；在算法个体更新阶段，提出一种基于双曲正切函数的非线性收敛因子公式，并提出基于适应度值的加权距离更新方法，改善了算法容易趋于局部最优的问题；引入变邻域搜索对算法的决策群体进行迭代寻优，加强了算法的局部搜索能力.最后，使用实际柔性作业车间案例与8个FJSP问题的基准算例对算法的有效性进行验证，证明了所提算法在解决FJSP问题上的有效性.

同时，IGWO在算例测试时也暴露出在面对大规模算例时效果不理想的情况，算法还是有一定几率会陷入局部最优.下一步的研究会考虑将灰狼算法与其他有效算法相结合，应用于流水车间调度问题中，使算法能更有效地解决该问题.