求解带AGV柔性作业车间调度问题的改进灰狼算法

徐逸凡，张利平，唐秋华，黄雨晨

(武汉科技大学 1.冶金装备及其控制教育部重点实验室；2.机械传动与制造工程湖北省重点实验室，湖北 武汉 430081)

柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)是传统作业车间调度问题(jobshop scheduling problem, JSP)的拓展。传统作业车间调度问题中，每个工件的加工工序是预先确定的，意味着每道工序的加工机器和加工时间是预先确定的。而在柔性作业车间调度问题中，每道工序的加工机器不用预先确定，可以在多种加工机器上选择一种进行加工，通常不同的加工机器伴随着不同的加工时间。FJSP具有生产灵活性，更贴近实际，是企业迫切需要解决的问题。

车间实际生产中，有效的调度方式可以提高生产效率，降低生产成本。在相关的柔性作业车间调度研究中，陈瑾标等[1]针对具有自动装卸搬运机器人的制造单元，着重考虑其双重资源约束的特点，提出了该系统的有限缓冲排队网的建模方法。张超勇等[2]用改进的两级遗传算法有效提高了FJSP的求解效率。为了更贴近实际生产，很多学者将工件的移动时间作为一道重要工序融进柔性作业车间调度问题中。张国辉等[3]设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。有关研究表明，考虑运输时间的柔性作业车间调度可进一步提升车间系统生产效率。

同时，随着自动化技术和车间智能化技术的不断发展，自动导引小车(automated guided vehicle，AGV)作为一种灵活高效的输送设备在制造系统中得到广泛应用。据相关资料统计，制造业中不足5%的时间用于加工装配，而超过95%的时间用于物料配送，因此物料的及时准确供应直接关系到生产线的流畅性。已有研究表明，合理的AGV分配与路径规划可有效提高物料配送效率和准确率。国内外对带AGV柔性作业车间调度问题的研究主要集中在生产调度、机器分配、AGV调度分配、AGV路径选择4个方面，通常文献选择1个或2个方面进行求解。徐云琴等[4]研究AGV最优调度方案和最佳AGV数量，建立使用AGV搬运的柔性作业车间调度模型。杨锋英等[5]认为AGV作业调度主要是对已有任务加工序列进行AGV的分配和路径优化。何之洲等[6]提出了一种并行禁忌搜索算法，但是仅针对一台搬运机器人的job-shop调度问题。Babu等[7]使用差分进化算法解决了在柔性制造系统中同时调度机器和2个相同的AGV的问题，但是没有将工件加工完成后搬运至卸载站的时间考虑在内。Lacomme[8]引入了一个基于析取图的框架来对有AGV的联合调度问题进行建模，并使用模因算法求得了新的下界值。综上所述，含AGV的柔性作业车间调度研究较少，研究者往往集中在把运输时间这个因素作为一道工序放进生产调度中，而忽略了物料设备选择以及路径的规划，集成AGV调度与生产调度的柔性作业车间问题还有待进一步研究。

灰狼算法(grey wolf optimization，GWO)自提出以来，就因具有良好的性能而引起了众多学者的广泛关注。GWO参数较少，易于实现，具备良好的收敛性，这些优点使得GWO被大量应用于各种实际问题的求解。GWO广泛应用于聚类分析、特征子集选择、经济调度指派、直流电机最优控制等诸多领域[9]。然而，灰狼算法多用于解决连续函数问题的研究，在车间调度这类非常复杂的离散组合优化问题中的应用还较少。姜天华[10]使用混合灰狼算法解决柔性作业车间调度问题，证明了算法的有效性。姚远远等[11]在重入混合流水车间调度问题中利用灰狼算法进行双目标优化求解，验证了算法的有效性。因此，本文将灰狼优化算法扩展应用于带AGV柔性作业车间调度问题，设计和改进编码方式、参数设定方式、邻域搜索策略等来改进灰狼算法，通过大量基准的仿真实验测试算法的计算性能，并验证其有效性。

1 问题描述

带AGV柔性作业车间调度问题可以描述为：一个加工任务中有n个工件，每个工件有若干道工序需要在m台机器上加工，每道工序在其可选加工机器集合中选取一台机器进行加工，工件在不同加工机器之间的转移由r台AGV搬运机器人进行搬运操作。在调度初始时刻，AGV和工件均位于装载站；调度结束时刻，AGV和工件均位于卸载站。调度过程中，AGV存在负载和空载2种状态。该问题同时考虑了工件在装载站与机器、卸载站与机器、不同机器之间被AGV搬运的时间，需要合理安排工件在不同机器的加工顺序和AGV分配，以优化加工车间的某些性能指标。参数定义如表1所示。

表1 参数定义Table1 Parameter definition

以最小化最大完工时间为优化目标，目标函数为

约束条件如下。

首道加工工序时间约束：工件需从装载站M0搬至其首道工序的加工机器。

AGV相邻两道搬运任务时间约束：一台AGV完成其上道搬运任务，空载到其下一道搬运任务的初始机器，再将工件搬运至其加工机器。

工件前后工序搬运时间约束：工件前道工序加工完成后才能搬运至下道工序。

同一机器加工顺序规则约束：机器按先到先服务的规则加工。

工件在机器上的加工过程约束：工件被搬运到机器输入缓冲区需等待机器空闲再对其进行加工。

2 改进的灰狼算法(improved grey wolf optimization, IGWO)

灰狼算法是由Mirjalili等[12]提出的一种受灰狼寻找猎物行为所启发的优化算法。该算法利用灰狼种群严格的社群机制来搜索最优解。灰狼种群被划分为α、β、δ和ω 4种等级，其中，种群中最好个体定义为α狼，次优和第三优个体分别定义为β和δ狼，其余为ω狼。灰狼算法中α、β和δ起领导作用，引导种群中余下低等级的ω狼平衡种群关系和发掘猎物，达到搜寻最优解的目的。这种行为的更新方式为

式中，t为当前迭代代数；A和E为协同系数向量；D为灰狼个体与猎物间的距离；Xp和X分别是猎物位置和灰狼位置；r1、r2是[0, 1]之间的随机数；a是收敛因子，随着迭代代数从2线性递减到0。

在α、β和δ引导ω搜索猎物时，由于猎物的位置是未知的，该算法假设猎物位于α、β和δ之间。所以在α、β和δ引导下，种群中灰狼ω位置更新采取如下方式。

Xα、Xβ和Xδ分别为灰狼α、β和δ的位置；Dα、Dβ和Dδ分别为α、β和δ与被引导的个体X之间的距离。

2.1 编码和解码

带AGV柔性作业车间调度问题由加工机器选择、工序排序和AGV搬运序列排序3个子问题构成。首先，根据机器集合中存在的约束关系合理为每道工序选择合适加工机器；然后，对工件的工序进行排序；最后，均匀分配产生AGV搬运序列，编码结构如图1所示。

图1 三段编码Figure1 Three-segment encoding

解码时，加工机器选择的Ms序列中的数字表示对应工序可选加工机器集合中的第几台机器；工序排序Os序列中工件号表示工件的每道工序，工件号的第n次出现表示该工件的第n道工序；AGV搬运序列Ts中数字表示与第2层工序排序编码对应位置的工序被分配到不同型号的AGV。

如图2所示，Ms、Os、Ts编码从左往右读取。在对应的第1列中，Ts中的1代表AGV1；Os中的2的第1次出现表示工件2的第1道工序；Ms中3表示加工机器m3。完整表述为AGV1将工件2搬运至机器m3进行第1道工序加工。以此类推，得到一个可行的调度方案。

图2 解码方式Figure2 Decoding method

2.2 种群初始化

种群初始化产生的解对算法求解的质量和收敛速度有较大的影响。本文采用两种初始化方式，一是机器负载平衡的方式，二是随机初始化的方式。根据上文的编码方式，工件的总加工工序数目在调度任务开始前是已知的，对于随机生成的加工序列编码Os，需要将每道工序安排在可选的唯一加工机器上。机器负载平衡的方式确保每台机器上加工工序的数目尽可能一致，即在初始化选择加工机器时，所有工件的总工序数目被平均分配到每台加工机器上。机器负载平衡的方式与随机初始化的方式比例为1∶1。

2.3 狼群位置更新

在算法迭代进化中，直接利用灰狼ω位置更新公式对灰狼ω中的每个个体的机器选择Ms和工序排序Os进行更新，AGV搬运序列不进行更新。

1) 灰狼ω中个体加工机器选择Ms的更新如下。分别取出灰狼α、β和δ的Ms序列和灰狼ω中的一个个体的Ms序列，根据式(13)的引导方式，取整后产生一个与Ms序列维度相同的数组。对于该数组中的每个元素，若元素值为该工序可选加工机器集中的编号，则选择对应机器编号；若元素值不存在于该工序可选加工机器集中，则随机选择一个加工机器编号。

2) 灰狼ω中个体工序排序Os的更新如下。如图3所示。首先，存在一个工序数组存放该调度任务的所有工序，按照自然数顺序从1开始将所有工序依次编号，工序与工序号用数字一一对应。然后，分别取出灰狼α、β和δ的Os序列和灰狼ω中的一个个体工序排序Os序列，根据式(13)的引导方式，产生一个与Os序列维度相同的元素值数组，将数组中的元素按照升序的方式编号产生一个升序位置号的数组，根据该数组中的数值返回到图3的工序数组，匹配相同元素编号下对应的工序和工序号，该操作如图4所示。此时，灰狼ω中个体工序排序Os完成更新操作。

图3 工序数组Figure3 Operation array

图4 个体位置转化为工序排序Figure4 Transformation of individual positions into process sequencing

2.4 参数a和E的优化策略

本文采用文献[13]提出的改进非线性收敛因子a计算公式。该文献说明了原始灰狼优化算法的收敛因子a从2随着算法迭代次数线性递减到0，但在算法的求解过程中并不是一个线性过程。改进的非线性收敛因子能更好地平衡算法在全局搜索和局部搜索的能力。改进收敛因子a为

其中，e是自然对数的底数；t为当前迭代的次数；tmax为最大迭代次数。

此外，本文采用文献[14]提出的优化参数E的方式。该文献通过实验验证了参数E对灰狼算法的影响规律，并明确指出，在算法迭代的初期，当E＞1时，算法的搜索能力不强导致进化缓慢；同时在算法迭代的后期，当E＜1时，算法容易早熟收敛导致陷入局部最优。优化参数E的方法，能够实现在算法迭代初期E以较大概率小于1和算法迭代后期E以较大概率大于1，具备平衡算法勘探能力和局部搜索能力。优化参数E为

其中，r3是[0, 1]之间的随机数，E(1)=2r2。

2.5 基于POX的扰动机制

关于灰狼算法的寻优策略，在进化后期，种群中灰狼个体均向最优个体位置靠近，导致种群多样性降低，如果最优个体为局部最优解，则灰狼算法会早熟收敛陷入局部最优。基于工序编码的交叉算子POX[15]能够继承父代的优良特征，且产生的子代均为可行解，这种方式以一定概率保证算法跳出局部最优，探索其他解空间的最优解。

对于灰狼算法Os编码采用POX的扰动机制。考虑到在原始灰狼算法中，种群个体主要依赖α、β和δ这3个头狼的引导来更新，而彼此间的相互作用较弱，因此，在每次迭代时，以一定概率将POX扰动机制应用于灰狼种群中的所有个体，强化种群内部信息交流，丰富种群多样性。

首先，随机确定2个父代灰狼个体P1和P2，进行POX扰动操作后产生2个子代个体C1和C2。具体操作步骤如下。

Step1随机将工件集合{1, 2, 3, ···,n}划分为2个非空子集J1和J2。

Step2复制P1包含在J1的工件到C1，P2包含在J1的工件到C2，保留它们的位置。

Step3复制P2包含在J2的工件到C1，P1包含在J2的工件到C2，保留它们的顺序。

图5所示为J1={1, 2}，J2={3, 4}，工件数n=4，每个工件有2道工序时，进行POX扰动操作。

图5 POX扰动操作Figure5 POX disturbance operation

2.6 邻域结构

灰狼算法在寻优过程中，关键在于α、β和δ这3只头狼在全局中的引领作用，决策层个体的优劣对算法性能有决定性影响，因此优化决策层个体能强化算法的计算性能。而邻域搜索算法是求解组合优化问题的有效局部算法，通过不断计算初始解邻域中解集的适应度值，选择更优结果的个体替代当前个体，能够帮助算法跳出局部最优。邻域搜索方法的嵌入能帮助这3个决策层个体进化，从而改善算法性能。针对α、β和δ的工序排序Os，本文设计了3种邻域结构，记为N1、N2和N3。这3种邻域结构如下。每代种群的进化过程中，以一定概率同时对α使用N1，对β使用N2，对δ使用N3进行邻域搜索。

1) 邻域结构N1：任选2个位置元素，将后一元素插入到前一元素之前。

2) 邻域结构N2：任选2个不同工件的工序交换。

3) 邻域结构N3：交换首尾2个元素位置。

2.7 改进的灰狼算法流程

改进灰狼算法的流程如图6所示。

图6 改进灰狼算法流程图Figure6 Flow chart of improved gray wolf algorithm

Step1设置算法参数a和E并按2.2节所描述方式创建初始种群。

Step2评估种群每个个体的适应度值，进行等级划分，确定α、β、δ和ω，判断是否达到算法终止条件。若达到，执行Step6；否则执行Step3。

Step3以一定概率同时分别对α使用N1邻域搜索方式，对β使用N2邻域搜索方式，对δ使用N3邻域结构进行优化。

Step4灰狼算法引导机制更新种群中的ω个体。

Step5以一定概率将POX交叉算子应用于灰狼种群中的所有个体，两两随机选择个体匹配。

Step6算法终止输出最优解。

3 实验设计与结果分析

上述改进的灰狼算法利用Matlab编程，程序运行环境为Windows 10系统下内存8G的AMD Ryzen 3 2200G @3.50 GHz计算机。

3.1 实验设计

AGV运输时间矩阵和测试工件的工序加工是由Kumar等[16]提出的关于柔性制造系统标准算例。车间加工机器有4种布局方式，有4种不同AGV运输时间矩阵，测试工件的工序加工集合有10种不同工件集合，两两组合一共40个测试案例。制造系统有4台加工机器和2台AGV。这4台机器有4种不同组合布局方式，导致AGV在装载站与机器、卸载站与机器，以及不同机器之间的搬运时间不同。

3.2 算法性能分析

算法最大迭代次数为100；初始种群规模为200；收敛因子a按照式(14)设置，参数E按照式(15)设置；POX扰动概率为0.8；邻域搜索概率为0.5；算法的优化目标为最小化最大完工时间，每个算例连续运行20次。

所选对比组实验与本文算法均考虑AGV在装载站、机器、卸载站三者之间的有效负载时间和空载时间，MAS(multi-agent system)[17]算法与本文提出的IGWO算法作为一组对比，该组中AGV数量均为2台，但是没有考虑工序加工机器的选择，系统柔性降低。在另一组FMAS(flexible multi-agent system)[18]、IGWO(n=2)和IGWO(n=3)则考虑了工序加工机器的选择。

由表2可知，本文提出的IGWO算法产生解的质量普遍更高。在被测试案例中，AGV数量为2时，75%的结果优于MAS算法的结果。FMAS算法测试案例对比本文IGWO(n=2)，本文所求解的结果32.5%优于FMAS的结果，提供了有竞争力的解，验证了IGWO算法的有效性。当AGV数量为3台时，IGWO(n=3)中解的质量比IGWO(n=2)中的解有了明显提升，时间显著减少。这充分体现了该类问题特征，AGV数量的变化会对系统加工效率产生明显影响。

表2 IGWO与其他算法测试结果对比Table2 Comparison between IGWO and other algorithm test results

目前，关于带AGV柔性作业车间调度问题的研究尚未取得有说服力的下界值。Ulusoy等[19]提出了一种特殊的下界值LBU，在EX11 ～ 104这组案例中，假设AGV在调度的任意时刻均是可以使用的状态，即生产系统中AGV数量总是够用，且每道工序加工前后立刻有AGV搬运，不会造成等待滞留的情况。在这样一种特殊假设下，LBU的结果通过精确数学公式得到，此方法耗费大量计算时间，如表3所示。LBU、GATS+HM(genetic algorithm with tabu search based on clustered holonic multiagent model)[20]

算法与本文IGWO算法结果对比，其中CPU Time1和CPU time2分别为GATS+HM和IGWO的计算时间。

由表3可知，2种算法的计算时间均较小，且都处于同一数量级，但是IGWO所求的解有52.5%的结果同时优于和LBU和GATS+HM，充分证明了该算法的有效性。

表3 特殊下界值测试结果对比Table3 Comparison of test results for special lower bound values

3.3 算法收敛性分析

以EX33案例为例，改进灰狼算法(IGWO)和原始灰狼算法(GWO)的收敛曲线如图7所示。IGWO在迭代前期以较大的搜索步幅在全局范围内探索较优解，后期收敛速度变缓，以较小步幅在局部范围内搜寻最优解。因此，IGWO具备较强的全局搜索能力和较快的收敛速度。

图7 算法收敛曲线Figure7 Algorithm convergence curve

3.4 案例结果展示

以EX32案例作为结果展示。其中，包含2台AGV、4台加工机器和5个工件，如图8所示。甘特图中折线表示AGV的搬运路径，与横坐标轴平行的直线表示AGV在对应机器位置的等待过程，此调度方案的最大完工时间为86 s。

如图8所示，在该实验案例EX32中，寻找到的最优解存在2种不同的调度方案，理论上这两种方案均有效。

图8 EX32最优解Figure8 EX32 optimal solution

AGV运行状态如表4所示，机器加工时长如表5所示。

表4 AGV运行状态Table4 AGV running status h

表5 机器加工时长Table5 Machine processing time s

对于AGV的运行状态，负载时间是值得关注的。在EX32(a)中，AGV1负载时间在总时间中的占比为27.9%，AGV2的负载时间在总时间中占比为56.4%；在EX32(b)中，AGV1负载时间在总时间中占比为55.8%，AGV2的负载时间在总时间中占比为29.9%。在这2种方案中，2台AGV执行不同搬运任务，路径和时间均有所差别，总优化目标为最小化最大完工时间，AGV之间并不存在优化负载时间使得每台AGV负载均衡。

此外，可以观察到在EX32(a)和EX32(b)中，机器加工时长有差异。由于4台不同机器处理不同工序的时间不相等，而且此时以最小化最大完工时间为优化目标，难以同时保证机器加工时长相对均衡。

4 结论

本文主要针对2台和3台AGV参与柔性车间作业调度的问题，提出了改进灰狼算法解决的方法，结果与标准测试案例进行对比，较好解决了带AGV柔性作业车间调度问题，验证了算法的有效性。此外，本文实验结果说明了算法具备较好的收敛性，在案例分析的结果中对AGV运行状态和机器加工时长进行统计说明。

该类问题还有许多值得深入研究的地方，未来可以更加智能化分配AGV数量和搬运任务安排，进一步提高生产效率。而且不少传统柔性作业车间的调度规则不能很好地适用于当前的调度环境。如何通过数据和结果总结出更加考虑问题属性的调度规则是非常值得探索的。