基于GWO的多目标柔性作业车间动态调度研究

姜 飞，李国昊，陶斯安

(江苏大学管理学院，江苏 镇江 212013)

制造业在我国国民经济中占有较高的比重，其发展水平彰显了国家的生产力水平。在“智能制造2025”、“工业4.0”等一系列背景驱动下，面对经济全球化发展趋势，愈发激烈的全球化市场竞争给国内制造业带来了新的机遇与挑战。生产者既要提升产品的品质，也要保证更优质的服务，才能使得企业保持活力、延续生命力。以往企业产品种类单一、生产批量大，随着产品革新换代速度的加快，顾客对产品的个性化需求越来越高，这就要求企业提高产品、技术创新效率，企业生产朝着多品类、小批量方向改变[1]。

在生产调度中随时都会有随机干扰事件发生，因此动态性普遍存在于车间调度问题中[2]。实际的调度管理系统是开放的，可能被任何事件影响，如设备突发故障、作业人员操作熟练度不够、调度环境改变等，加工时间和交货期也会随之改变，因此这两者往往是不确定的，这个不确定的时间就是模糊加工时间与模糊交货期[3]。

考虑到模糊交货期，本文首先依照字典序方法将最终目标分级，一级目标为最大完工时间，二级目标为客户满意度，建立柔性作业车间动态调度模型；然后对灰狼优化(grey wolf optimizer,GWO)算法进行改进，将收敛因子由线性改为非线性，提升算法扩大搜索范围的能力，使局部最优解与全局优化能力达到平衡，同时将不同的决策权重赋予不同位置的灰狼领导层，以动态权重的方式提高算法的精度；最后结合现场生产实例，对不同机器出现故障的情况进行对比分析，筛选出影响生产效率与稳定性的关键设备，验证模型和算法的可行性。

1 柔性作业车间动态调度模型

柔性作业车间调度(flexible job-shop scheduling problem,FJSP)在设备选择和工艺处理方面体现了柔性化，而且还能减少生产过程中动态干扰因素的影响[4]。另外，在实际的FJSP中产品的交货期是模糊的，由生产者和客户共同决定。因此，本文在交货期模糊以及设备故障的情况下，建立柔性作业车间动态调度模型，以期将所有设备与工序最优化匹配，合理安排加工顺序，以满足整个车间的调度性能要求。

本文模型涉及到的符号及变量见表1。

表1 符号与变量含义

1.1 模型建立

在柔性作业车间的生产加工过程中，往往要权衡多个优化目标，尽可能满足各方的要求，只有这样企业才能在竞争中保持优势[5]。本文基于最大完工时间最小，根据实际市场情况考虑模糊交货期以及产品提前/拖期完成的惩罚策略，求得客户的满意度，以最大完工时间最小和客户满意度总和最大为目标建立多目标优化模型。

1.1.1最大完工时间

从加工开始时刻算起至全部工件加工完成，所有工件加工时间中的最大值就是最大完工时间，它能最直接地反映生产效率，函数表达如下：

Cmax=max(Ci)i=1,2,…,n

(1)

式中：Cmax为最大完工时间。

1.1.2考虑模糊交货期的多目标优化模型

在企业中，各部门均有其不同的生产目标，因此现实的生产调度问题必须对多个优化目标综合考量。在考量常见调度目标的同时，本文还将加工环境干扰和模糊交易期的影响加入模型，从客户满意度、时间消耗两个方面进行调度优化，针对最大完工时间最小和客户满意度总和最大两个目标，采用字典序方法构建多目标模型。

本文采用考虑提前/拖期惩罚的梯形模糊交易期，如图1所示，表示方法如下：

图1 模糊交货期的梯形客户满意度

(2)

以最大完工时间最小为一级目标P1、客户满意度总和最大为二级目标P2，构建动态调度模型：

minCmax=min[max(Ci)]i=1,…,n

(3)

(4)

s.t.P1>P2

(5)

Sijk+Xijk×Pijk≤Tijk

(6)

Tijk≤Si(j+1)l

(7)

Ci≤Cmax

(8)

Sijk+Pijk≤Sabk+L×(1-Rijabk)

(9)

(10)

Tijk>0,Sijk>0

(11)

(12)

式(3)表示最大完工时间最小；式(4)表示客户满意度总和最大；式(5)约束了目标满足字典序表达顺序；式(6)和(7)表示对工件紧前工序的约束，完成紧前工序后才能进入下一步加工，每个工件在同一时刻只能在一台机器上加工；式(8)表示所有工件的完工时刻不大于最大完工时刻；式(9)约束单一设备同一时刻只能进行一道工序加工，Sabk为Oab在k机器上的开始加工时间；式(10)表示一道工序不能多次加工；式(11)约束变量的正负；式(12)处理了再调度时刻正在加工的工序，Tabl为Oab在l机器上完成加工的时间，Xijk=1时，Oij可在机器k上加工，否则不可用；tD时刻机器不可用，且该时刻Xijl=1。

2 GWO算法的改进

GWO算法只有A,C,a3个参数，具有参数少、算法简单的特点。参数C是[0,2]区间上的随机数，很难改进，参数A的值取决于收敛因子a。在整个运算过程中，最关键的步骤是根据α、β、δ狼的位置进行ω狼位置的更新，三头领导狼对ω狼的影响是等同的[6]，但这不符合实际情况。因此，本文将从改变参数a和位置信息所占权重两个方面改进GWO算法，以使算法在避免局部最优、扩大全局搜索能力以及加快收敛速度等方面有所改善。

2.1 基于非线性收敛因子的改进

基于对GWO算法参数的分析可知，参数A是决定狼群狩猎是否成功的关键。参数A的大小主要取决于收敛因子a，a是线性递减的。然而在收敛的过程中任何群体智能优化算法都不可能始终是线性的。因此，本文利用一种指数型非线性收敛方式进行算法收敛，具体数学描述如下：

(13)

式中：t为迭代次数；tmax为最大迭代次数。

如图2所示，改进后随着迭代次数的增加收敛因子a虽然依然从2逐步递减到0，但递减速度和方式都已经发生了变化。改进后收敛因子递减以凸函数形式存在，初期衰减速度降低，这说明本算法拥有更加广泛的全局搜索范围，便于更多候选解的选择；后期收敛速度加快，使局部最解更优。因此，改进的收敛因子在扩大算法搜索范围的同时，优化了全局和局部搜索能力，使算法全局寻优的能力进一步加强，更符合收敛的实际过程。

图2 收敛因子对比图

2.2 基于动态权重的改进

GWO算法是在严格等级划分的基础上搭建的优化算法。在优化过程中，使α、β、δ狼指导狼群中其他狼的权力完全一样，其缺点是会影响算法的收敛，且容易陷入局部最优，使算法最终输出的最优解不是真正的最优解。为弥补算法的这一不足，基于动态分配指导权重思想，每次迭代时通过α、β、δ狼与猎物的动态距离指导ω狼更新位置。狼群在α、β、δ狼指导下更新位置的方式如下：

(14)

式中：X1,X2,X3分别为更新后的α、β、δ狼的位置；Xα,Xβ,Xδ分别为当前的α、β、δ狼的位置；Dα,Dβ,Dδ为ω狼与α、β、δ狼之间的距离；A1，A2，A3为α、β、δ狼对应的算法参数。

基于每次迭代产生的α、β、δ狼的新位置，动态权重下ω狼的更新位置X(t+1)如下：

X(t+1)=w1X1+w2X2+w3X3

(15)

(16)

式中：w1，w2，w3分别为ω狼对α、β、δ狼的学习权重。

由权重公式(16)可知，w1，w2，w3在迭代过程中不断地更新。因此，根据每次迭代过程中的实际收敛情况，本文使用的权重分配方式会及时地调整动态权重，使得算法的环境适应性提高。

3 改进灰狼算法实例分析

为了验证本文改进算法的可行性，本节对该算法进行实例分析。

3.1 算例数据

截取DS亚克力板材厂生产现场某一时段的6×10(6道加工工序与10个加工设备)加工数据，进行FJSP字典序多目标优化分析，优化目标为最大完工时间最小P1和客户满意度总和最大P2。加工数据见表2，模糊交货期见表3。表2中上下两部分分别对应，如工件O1对应的工序1上部分(3,6,10)表示该工序可由机器3、6、10加工，相应机器对应加工时间为下部分中的(3,9,5)。

表2 加工机器与加工时间

表3 模糊交货期

3.2 参数设置

灰狼优化算法的初始化设置为：灰狼群体大小为50，迭代次数为600，不同等级狼α、β、δ、ω的初始位置为零矩阵，适应度函数为正无穷。在PC环境下，使用MATLAB2016b，处理器为Inter(R) Core(TM) i5-4210H CPU@2.90 GHz，运行内存为8 GB。

3.3 收敛性分析

为检测本仿真算法的可用性，进行收敛性仿真测试，结果如图3所示，改进GWO算法与传统GWO算法的运算性能对比见表4。由表中数据可知，改进GWO算法在168代完成收敛，相较传统的GWO算法收敛速度更快，且精度较高，最大完工时间为37 s，客户满意度之和为6.00。此外，改进GWO算法在开始阶段快速收敛，并在之后减缓收敛速度，说明其拥有较高质量的初始解集，全局搜索性能较好，并且改进GWO算法的收敛是分阶段的，证明了它能很好地避免陷入局部最优的困境，对全局进行寻优。

表4 算法运行结果对比

图3 收敛性能和种群数量仿真

3.4 实例结果对比分析

无设备损坏时的调度方案如图4所示。

本文运用改进GWO算法对图4所示的10台机器分别发生故障的情况下进行10次仿真，并对调度目标的平均结果进行比较，结果见表5。

图4 无设备损坏调度方案

表5 设备故障仿真结果对比

对最大完工时间和客户满意度总和进行综合考量，当第2、3、9、10台设备发生故障时，最大完工时间较长、客户满意度总和较小，总体目标结果表现较差，即这些机器加工效率较高，发生故障时会影响生产的稳定性，从而影响加工效率和客户满意度。因此，第2、3、9、10台设备是关键设备，企业应对这4台设备进行重点维护和保养。

4 结束语

本文对GWO算法进行优化，改进了收敛因子，并确立了灰狼领导层的动态性权重分配，促进算法局部最优与全局搜索之间的平衡，提高了算法的精确性，改进后的GWO算法收敛速度更快，且精度较高。针对模糊交货期和动态干扰事件为设备故障的情况，建立FJSP模型，分析DS亚克力板材厂中不同设备损坏情况下的最大完工时间与客户满意度，找出关键设备，提醒企业重点维护保养。后续还可以考虑结合模糊加工时间、其他动态干扰事件进行相关研究。