柔性作业车间调度问题(FJSP)作为经典作业车间调度问题的一种延伸形式, 具有更强的应用背景和更大的求解难度, 已被证明是一种具有NP难特性的组合优化问题[1].与JSP问题相比, FJSP中工件柔性加工路径的特性在减小机器约束的同时, 又增加了调度的灵活性, 使其更能贴近于实际生产[2], 但是这也大大提升了其复杂程度.该问题的求解算法研究已成为车间调度领域的热点, 目前元启发式算法已成为最流行的方法, 它为FJSP问题提供了更多更新的求解思路和方法, 引起了国内外学者们的广泛关注.

Zhang等[1]针对不同性能指标下柔性作业车间调度问题进行了研究, 提出了一种具有双层子代产生模式的改进遗传算法; Zhang等[2]提出了一种改进遗传算法, 以优化FJSP问题中的3个指标:最大完工时间、机器总负载和瓶颈机器负荷; Liu等[3]提出了一种改进双链量子遗传算法求解具有模糊交货期的柔性作业车间调度问题, 以优化系统完工时间、总成本和提前/拖期惩罚; Karthikeyan等[4]提出了一种混合离散萤火虫算法求解有限资源约束下的多目标柔性作业车间调度问题; Yuan等[5]提出了一种混合差分进化算法, 以优化柔性作业车间工件的最大完工时间; Li等[6]将遗传算法和禁忌搜索相结合, 提出了一种混合算法以优化最大完工时间.尽管各种元启发式算法在FJSP问题中已得到了广泛的研究, 但目前仍没有任何一种算法能够获得所有问题的最优解, 因此学者们仍在不断积极探索, 以获得更丰富且更有效的方法.

灰狼优化算法是根据狼群捕食原理提出的一种新兴元启发式算法[7].该算法虽然出现的时间比较晚, 但目前已被成功运用于各类优化问题的求解中[8-11].然而, 该算法在生产调度领域的研究尚不多见, 且现有的几篇文献仅集中于简单流水车间调度问题的研究[12-14].因此, 本文将灰狼优化算法扩展应用于柔性作业车间调度问题, 并针对基本灰狼优化的算法进行一系列设计和改进, 提出一种混合型灰狼优化算法(HGWO).采用两段式个体编码方式实现离散调度解的连续编码, 设计一种种群初始化方法, 并利用变邻域搜索加强算法局部搜索能力, 使决策层个体更好地引导其他个体进行搜索.此外, 引入遗传算法的交叉和变异操作, 更好地避免算法出现早熟收敛.通过对大量基准和随机算例的仿真实验测试算法的计算性能, 并验证其有效性.

某车间内包含m台机器和n个待加工工件, 每个工件的加工需经过Ji(Ji≥1)道工序, 且工序间必须遵循一定的加工顺序.与JSP问题相比, FJSP问题中工序具有柔性加工路径, 每道工序可在多于一台的机器上处理, 其加工时间取决于所分配的机器的能力.本文FJSP问题的优化目标是为工序选择合适的机器, 并确定各机器上工序加工顺序, 使车间最大完工时间最小.对于该类问题, 存在以下假设: 1)所有工件和机器在零时刻均处于就绪状态; 2)同一时刻一台机器只可处理一个工件; 3)工件加工过程具有不可中断性; 4)仅考虑同工件工序间的先后约束关系, 而不同工件工序间相互独立; 5)各工件加工优先级相同; 6)忽略工序加工前机器所需的准备时间.

令Cmax表示工件最大完工时间, CiJi表示工件的完工时间, 则目标函数可表示为

灰狼优化算法是一种基于群智能的元启发式优化算法, 它是通过模拟狼群捕食的行为机制而提出的.根据基本灰狼优化算法的特点, 算法迭代过程中需按照适应度值从大到小的顺序将狼群个体划分为4类, 用于模拟狼群的社会等级, 狼群中适应度值排在前3位的个体分别依次定义为α、β和δ, 而其余个体均定义为ω.基本灰狼优化算法假设α、β和δ拥有获得潜在猎物所在位置的能力, 在算法每次迭代时均先找出目前为止算法最优的3个个体α、β和δ, 并保存好3者的个体位置, 然后以此更新下一代个体的位置, 通过不断迭代, 最终达到捕食猎物的目的.该过程可用以下公式表示:

其中:t表示当前迭代次数, A和C表示协同系数向量, X表示灰狼的个体位置向量, a中元素在迭代过程中由2线性递减到0, r1和r2均表示随机数向量.由式(2)和(3)计算出个体与α、β和δ的距离, 然后由式(4)确定个体向猎物移动的方向.由于篇幅限制, 基本GWO算法的步骤可参见文献[7].

FJSP问题包含机器分配和工序排序两个子问题, 因此每个个体可采用基于随机键的两段式编码, 其中各段长度相等, 且分别对应机器分配方案和工序排序方案.假设个体位置向量的长度为2l, 则可表示为X={x(1), x(2), ..., x(l), x(l+1), ..., x(2l)}, 各元素均在[-ε, ε]内任意取值.假设车间内包含3个工件, 每个工件包含两道工序, 则个体位置向量的总长度为12, 各元素在[-3, 3]中任意取值, 并按照一定的顺序存储, 如图 1所示, 其中OPij表示工件i的第j道工序.

由图 1可以看出, 灰狼优化算法中个体位置向量元素均为连续值, 而柔性作业车间调度解为离散值, 因此还需解决连续个体位置向量与离散调度解间的转换问题.为了实现算法解空间与问题空间之间的映射, 分别在前后两部分采用不同的转换方法.

1) 个体位置向调度方案的转换.

i) 机器分配:采用文献[15]中的转换方法, 按照式(7)将个体位置向量元素值转换成工序可选机器集中机器的序号, 由此可获得机器的编号

其中: z(h)表示元素h对应的工序的可选机器数; u(h)∈[1, z(h)]表示所选机器在工序可选机器集中的序号, 即工序可选机器集中第u(h)个元素就是为工序分配的机器.

ii)工序排序:采用文献[16]中的升序排列ROV (Ranked order value)规则, 首先按升序排列的顺序为每个位置元素赋予一个唯一的ROV值, 然后根据ROV值即可构造工序排序方案, 如图 2所示, 其中相同工序编号表示同工件不同工序.

2) 调度方案向个体位置的转换.

i) 机器分配:采用文献[15]中的转换方式, 即一般情况下, 可按照式(7)的逆操作执行, 如下式所示:

但存在一种特殊情况, 即若工序仅有一台可选机器, z(h)=1, 则x(h)在[-ε, ε]内任取数值.

ii)工序排序:首先在[-ε, ε]间随机产生l个随机数, 按升序顺序为每个位置元素赋予ROV值, 并与工序排序方案对应, 根据工序编号找到对应的ROV值, 然后根据重排ROV值确定个体位置向量中各元素的值, 转换过程如图 3所示.

根据个体位置向量的表达形式, 种群初始化将分别针对机器分配和工序排序进行.在机器分配部分采用文献[2]中基于启发式算法与随机生成法相结合的方式生成初始机器分配方案; 在工序排序部分采用文献[17]中基于搜索的方法, 即对于一个已生成的机器分配方案, 随机生成若干个工序排序方案, 将每一个排序方案与该机器分配方案结合, 选择最优的一组作为一个初始调度解, 重复上述过程, 直到生成初始种群为止.

在灰狼优化算法的搜索过程中, 种群个体根据决策层3个个体(α、β和δ)来更新自身的位置信息, 并最终达到捕食猎物的目的.因此, 决策层个体的好坏对算法的计算性能具有很大的影响.本文将变邻域搜索嵌入到灰狼优化算法中, 并在每次迭代中均作用于α、β和δ, 从而改善算法性能.变邻域搜索算法中, 针对个体位置向量采用以下3种邻域结构.

1) 邻域结构N1:在工序排序部分中任选两个元素, 所选元素需对应不同工件的工序, 然后对所选元素进行交换操作.

2) 邻域结构N2:在工序排序部分中任选两个元素, 然后将后一元素插入到前一元素之前的位置.

3) 邻域结构N3:在机器分配部分任选一个元素, 该元素对应工序的可选机器应多于一台, 然后将该工序分配至不同机器上, 并根据式(8)生成新元素值.

变邻域搜索算法的具体步骤如下.

Step 1:将决策层个体作为初始解X, 设置q←1,λmax←3及终止迭代次数qmax.

Step 2:设置λ←1.

Step 3:振动.若λ=1, 则X'← N1(X); 若λ=2, 则X'← N2(X); 若λ=3, 则X'← N3(X).

Step 4:局部搜索.将X'作为初始解, 获得局部最优解X''.

Step 5:若X''优于X, 则X←X'', 并设置λ← 1;否则设置λ←λ+1.

Step 6:判断λ>λmax是否满足.若满足, 则设置q← q+1, 转到Step 7;否则, 转到Step 3.

Step 7:判断q>qmax是否满足.若满足, 则转到Step 8;否则, 转到Step 2.

Step 8:算法结束.

变邻域搜索算法中局部搜索采用文献[18]中的阈值接受法, 具体步骤如下.

Step 1:获取初始解X', 并设置阈值ψ>0, ρ← 1, ϑ←1及终止迭代次数ρmax.

Step 2:若ϑ=1, 则X''← N1(X')∪N3(X'); 若ϑ=0, 则X''← N2(X')∪ N3(X').

Step 3:判断Cmax(X'')-Cmax(X')≤ψ是否满足.若满足, 则X'←X''; 否则, 设置ϑ←|ϑ-1|.

Step 4:令ρ←ρ+1, 并判断ρ>ρmax是否满足.若满足, 则X''←X', 转到Step 5;否则, 转到Step 2.

Step 5:算法结束.

灰狼优化算法进化时, 个体仅根据适应度最优的3个个体进行个体位置更新, 这使得该算法易陷入局部最优解, 对此本文引入变邻域搜索算法, 用于增强算法的局部开发能力.良好的算法能够在搜索过程中平衡全局探索与局部开发能力.考虑到遗传算法具有很强的全局搜索能力, 在灰狼优化算法中引入遗传算法的交叉和变异算子, 提高该算法的全局探索能力, 从而进一步增强该算法的计算性能.对于交叉操作, 在机器分配部分采用双点交叉法, 在工序排序部分采用部分匹配交叉法; 对于变异操作, 在机器分配部分采用单点变异法, 在工序排序部分采用逆序变异法, 即在个体位置向量中任选两个位置, 然后对所选位置间的元素进行逆序排序.

HGWO算法的具体步骤如下.

Step 1:设置算法参数并创建初始种群.

Step 2:评估种群中个体的适应度值, 并确定α、β和δ.

Step 3:对最优个体均执行变邻域搜索, 然后根据适应度值从大到小更新α、β和δ.

Step 4:根据式(2)~(6)更新个体位置信息.

Step 5:判断算法是否满足终止条件.若满足, 则转到Step 6;否则, 按一定概率对个体进行交叉和变异操作, 然后转到Step 2.

Step 6:算法结束并输出结果.

本节针对文献[19-20]中FJSP问题的15个基准算例(Kacem01~Kacem05, MK01~MK10)以及本文随机生成的15个算例(RM01~RM15)进行仿真.对于RM01~RM15, 机器数和工件数如表 1所示, 其他数据取值服从一定范围内的均匀分布, 其中工件的工序数在[1, 5]内取值, 工序加工时间在[1, 20]内取值.此外, 采用随机的方式确定各工序的可加工机器集, 即对于一台机器, 若产生的随机数大于0.5, 则该机器为对应工序的一台可加工机器.

采用Fortran程序设计语言, 在Win XP系统下内存2 G的Pentium CPU G2030 @3.00 GHz, 2.99 GHz计算机上运行.算法参数设置为:种群大小为100, 最大迭代次数为800, 变邻域搜索和局部搜索最大迭代次数qmax和ρmax均为10, 交叉率为0.8, 变异率为0.2.

首先对算法中几种改善机制的有效性进行验证, 其中包括种群初始化方法、变邻域搜索算法和交叉变异操作.各算法针对不同算例分别独立运行10次后进行比较, 对比结果如表 1所示.其中: BGWO表示不包含任何改善机制的基本灰狼优化算法; GWOin表示在BGWO中增加种群初始化方法而得到的算法; GWOin+vns表示在GWOin中嵌入变邻域搜索算法; HGWO表示本文所提出的算法, 即在GWOin+vns中又增加了交叉和变异算子; Time表示算法运行时间; Best表示算法运行10次获得的最佳结果; Avg表示算法10次运行结果的平均值; RPD表示相对百分比偏差, 计算公式为RPD=100×(Best-Min)/Min, Best表示各算法运行10次获得的最佳结果, Min表示各算法最佳结果中的最小值; Mean表示30个算例下各算法RPD的平均值.由表 1中的数据可知, 本文算法可以在较短时间内获得较满意的解, 但由于GWOin+vns和HGWO中包含变邻域搜索算法, 使其计算时间相对较长.从计算结果看, HGWO算法的计算结果最好, 能够在27个算例中获得最佳结果, 明显多于其他算法.此外, 与GWOin+vns算法相比, HGWO算法计算时间稍长, 但其Mean值更小, 且相同Best值的情况下, HGWO算法在10个算例中Avg值较好, 因此遗传算子的引入能够进一步改善算法的性能.

文献[19-26]中给出了不同算法求解15个FJSP问题基准算例下的工件最大完工时间.为了验证本文HGWO算法的有效性, 将其与上述文献中的各种算法进行比较, 算法对比结果如表 2和表 3所示.

在表 2和表 3中:粗体表示相同算例下各算法比较后的最佳结果, “-”表示文献中未给出相应结果. 表 2针对Kacem算例比较本文算法与其他算法的计算结果, 数据显示HGWO算法只在算例Kacem05下稍逊于其他3种算法, 但在算例Kacem01~Kacem04下均能获得最优解. 表 3通过对Brandimarte算例的计算进行进一步对比, 数据显示HGWO算法能够获得最优解的个数(5个)仅次于文献[26]中的算法(6个), 但若同时综合考虑表 2和表 3中13个基准算例, 本文HGWO算法能够获得最优解的个数(8个)多于文献[26]中算法(7个).

为了进一步测试本文算法的优越性, 将HGWO算法与文献[25-26]中算法的RPD值进行比较, 如表 4所示.

由表 4中的数据可以看出, HGWO算法获得的Mean值在3种算法中最小.因此, 综合表 2~表 4中的数据对比结果, 本文所提出的HGWO算法在求解FJSP问题中工件的最大完工时间方面具有一定的有效性.

本文针对柔性作业车间调度问题特点, 对新型灰狼优化算法进行一系列改进, 提出了一种混合灰狼优化算法: 1)采用两段式编码, 实现了连续个体位置与离散调度解间的转换; 设计了种群初始化方法, 确保种群的质量和多样性; 提出了一种变邻域搜索策略, 增强算法局部搜索能力; 引入了交叉和变异算子, 平衡算法全局探索与局部开发能力. 2)针对30个FJSP问题的算例进行了仿真, 验证了算法改善机制的有效性, 并进一步测试了算法解决柔性作业车间调度问题方面的有效性. 3)下一步将把灰狼优化算法扩展至更复杂的车间调度问题中, 并结合车间特点, 设计出更有效的算法.