考虑运输时间的分布式置换流水车间调度灰狼优化算法

夏霖辉，吴瑶，周学良，王海林

（湖北汽车工业学院机械工程学院，湖北十堰 442002）

网络环境下协同制造能最大限度调动社会优质资源，发挥制造优势，高效、快速、低成本地完成客户个性化订单的生产制造任务。传统单工厂订单制造模式将逐渐被多工厂协同制造模式取代［1］，分布式多工厂生产制造是发展趋势。流水车间是车间加工设备的主要组织形式，分布式置换流水车间调度问题是企业协同制造过程中需要解决的关键问题［2］，成为调度领域新的研究热点。文献［3-10］通过设计不同的优化算法对分布式置换流水车间调度问题进行研究，文献［11-16］研究了考虑运输时间的生产调度优化问题，但主要针对单工厂内工序间的加工转运以及单工序工件在多工厂间的运输。多工序工件在并行工厂加工完成后的交付转运对工件的加工分配和完工交付有重要影响，文中以最小化最大工件交付时间为目标，建立考虑运输时间的分布式置换流水车间调度问题的数学规划模型，采用灰狼优化算法的计算框架，结合问题的结构特点，设计基于工件加工位置的随机键编码方式和局部搜索策略以提高算法的性能。

1 问题描述与模型建立

考虑运输时间的分布式置换流水车间调度问题描述如下：有n个待加工工件需要在分布于不同地区的F间工厂进行加工，各工厂拥有1条相同的由m台机器串行构成的流水生产线，分配至各工厂的待加工工件需按照相同加工路径在m台机器上依次加工，同工厂的所有工件加工完毕后由运输车辆统一运至客户。已知工件在每台机器上的加工时间和各工厂至客户的运输时间。调度决策需要研究如何联合多工厂协同完成工件加工任务，降低工件交付时间，优化目标为最小化最大工件交付时间，即工件完工时间与工件运输时间之和。调度决策内容如下：1）待加工工件如何在各工厂分配；2）分配至各工厂的工件的加工排序。

为方便建立模型，作如下假设：1）不同流水车间的加工工艺相同，相应工序的机器性能相同；2）任一待加工工件可在任意流水车间内加工，同车间内的所有工件都完工后经同批次运输至客户；3）同车间内各台机器上的工件加工排序相同，任一机器同时刻只能加工1个工件，任一工件同时刻只能在1台机器上加工。目标函数为

约束条件为

变量说明如表1所示。

表1 变量说明

2 改进灰狼算法

灰狼算法（grey wolf optimization，GWO）是受灰狼捕食行为启发所提出的新型群体智能优化算法［17］，采用实数编码机制，应用于求解连续优化问题。有学者通过尝试改进灰狼算法将其应用于车间调度等典型的离散型优化问题，并取得良好的效果。文中基于GWO 的计算框架，提出改进灰狼算法（improved grey wolf optimization，IGWO）求解考虑运输时间的分布式置换流水车间调度问题。鉴于算法在表达离散变量时存在编码表示和迭代更新困难，设计随机键编码机制，将连续编码映射为离散码值，同时引入局部搜索策略以改进算法最优解，提高算法的收敛速度。

2.1 GWO基本原理

GWO通过模拟灰狼群的严格等级制度和灰狼追踪、包围、攻击猎物的行为过程，构建解的更新机制。算法将第1～3 阶级灰狼分别表示为α、β、δ，群体中其他个体为第4阶级，用ω表示。不失一般性，前3阶级各有1只灰狼，依次对应灰狼群中适应度好的前3 个解。灰狼群中占比最大的ω必须完全服从α、β和δ，因而灰狼群的解更新过程主要由α, β和δ进行引导和指示。在支配性灰狼引导下灰狼位置更新数学模型表示如下：

式中：X(t)为当前灰狼的位置向量；t为当前迭代次数；Xp为支配性灰狼（猎物）的位置向量；D为距离向量；A和C为协同系数向量；a为参数，随迭代次数的增加从2 逐渐降低到0；r1和r2为0～1 随机向量。模拟灰狼攻击猎物行为，在α、β、δ的同时引导下，X(t)更新数学模型表示如下：

2.2 IGWO设计

基于GWO 基本原理设计IGWO，如图1 所示，主要包括编码与解码、生成初始灰狼群、解评价与更新机制以及局部搜索等算子。

图1 改进灰狼算法流程图

2.2.1 编码与解码

采用基于随机键编码的最大顺序值规则（larg‑est order value,LOV）［17］，将灰狼位置坐标的连续数值映射为离散数值。

编码过程如下：根据车间数量，生成含F个片段且长度为n的随机向量，如编码串{π1,π2,…,πθ1,|,…,|,πθF-1+1,…,πn}，“ |”为分配到不同车间工件之间的分隔符，工厂f分配的工件数为

解码过程如下：对编码数组

中的数值作降序排列，然后将相应数值转换为排列顺序的离散值，得到中间数组：

再根据式（14）将中间数组映射为加工排序向量。

为清晰说明解码过程，以含有5个工件的单个车间调度问题为例。随机生成灰狼个体向量Xi为［0.62,0.46,0.81,0.31,0.13］，如图2 所示。依编码序列的数值大小对不同编码位置依次分配2、3、1、4和5，得到中间序列φi为［2,3,1,4,5］，通过式（14）可得：当k为1 时，φi,1为2，πi,2为1；当k为2 时，φi,2为3，πi,3为2；当k为3时，φi,3为1，πi,1为3；当k为4时，φi,4为4，πi,4为4；当k为5时，φi,5为5，πi,5为5。进而获得解码后的工件加工序列：

图2 随机向量解码过程示例

以2个工厂、10个具有2道工序的工件加工调度为例，设灰狼编码向量为［0.12,0.94,0.64,0.56,0.91|0.78,0.71,0.32,0.51,0.19］。第1个编码向量片段［0.12,0.94,0.64,0.56,0.91］，解码后获得的加工顺序为［2,5,6,7,3］；另一工厂编码向量片段为［0.78,0.71,0.32,0.51,0.19］，解码后获得的加工顺序为［4,9,8,10,1］，2个工厂对应的加工调度方案的甘特图如图3所示。

图3 实例甘特图

2.2.2 灰狼群初始化

随机生成N个灰狼个体，构造初始灰狼群。任意灰狼位置编码Xi为[xi,1,xi,2,…,xi,n]，其中xi,j为向量的第j维取值，得：

式中：ju和jl分别为第j元素的上界和下界；n为工件总数；R为0～1随机数。

2.2.3 评价和更新机制

基于问题目标，将灰狼个体适应度函数定义为

计算每个灰狼的适应度，并按照适应度从大到小的顺序排列，进而确定α、β和δ。

在灰狼群迭代更新过程中，为了避免种群退化，采用精英保留策略，将适应度最好的3 个个体α、β和δ直接保留至下一代，其他灰狼个体的位置按照式（9）的更新机制进行，即以α、β和δ的位置指引其他灰狼向猎物方向搜索。

2.2.4 局部搜索

工件交付时间为加工工厂的完工时间与运输时间之和，而后者为固定值，因而目标函数值取决于工件交付时间最长的工厂l的完工时间。为缩短工厂l的工件交付时间，改变工件数量、类型和加工顺序，提出3种基于工件分配方案和加工顺序变动的局部搜索策略，具体操作如下：

1）工厂间工件交换。将交付时间最长的工厂l与其他任意工厂l′的1个工件交换，若交换后最大交付时间减小，则更新最优解。

2）工厂间工件插入。任选交付时间最长的工厂l的1个工件插入交付时间最短工厂l′的加工序列，若变换后的最大交付时间减小，则更新最优解。

3）工厂内工件移位。任选交付时间最长的工厂l的1个工件，将其插入加工序列的其他位置，若工件移位后的最大交付时间减小，则更新最优解。

3 实验结果与分析

考虑运输时间对分布式置换流水车间调度问题的影响，对文献［6］中32 组算例进行改进，增加各工厂至客户的运输时间。对于含2 个工厂的算例，假设各工厂到客户的运输时间分别为120 min和180 min；对于含3个工厂的算例，假设各工厂到客户的运输时间分别为120 min、150 min和180 min。基于上述算例，采用MATLAB2016a，Windows10，Intel i5 2.5GHz，RAM 8GB 的运算测试环境，使用IGWO GWO 和GA（遗传算法）求解，算法参数设置参考文献［17］。将3 种算法的种群规模均设置为100，最大迭代次数设置为200。GA 的交叉概率为0.4，变异概率为0.08。

3种算法对各测试算例分别运行40次，求解每次运算的C。基于运算结果的最小值Cmin、平均值Cave、平均相对误差Eare来比较3 种算法的求解质量［18］。Eare表示为

式中：C∗为目前已知的下界值。

3 种算法对算例的计算结果如表2～4 所示，可以看出，采用IGWO求得的Cmin、Cave均不低于GWO和GA，Eare也优于GWO 和GA。这是因为GWO 在求解离散流水车间调度收敛速度慢，后期容易陷入局部收敛；GA因为随机生成初始种群，生成的个体适应度较低，影响种群的收敛速度和最终解的质量。由此可见，IGWO对求解文中问题有更好的效果，提出的局部搜索算子能有效提升求解质量。

表2 IGWO仿真结果

表3 GWO仿真结果

表4 GA仿真结果

4 结论

针对考虑运输时间的分布式置换流水车间调度问题，建立以最小化最大交付时间为目标的数学模型，采用改进的灰狼算法对问题进行求解，并在优化过程中加入局部搜索算子，更好地平衡算法的全局探索与局部开发最优解的能力，通过MATLAB对大量算例进行仿真计算，与传统遗传算法和灰狼算法进行比较，证明改进的灰狼算法对研究问题的求解具有优越性。文中针对分布式置换流水车间环境，仅考虑了交付时间对订单分配和加工排序的影响，未考虑订单交付期约束以及工件装配调度过程，后续可在考虑这些因素情况下进行扩展研究。