基于AGV的管道加热器柔性作业车间调度方法研究

苗培仁，李晓东，胡 凯，刘 睿，刘 壮

(1.江阴市辉龙电热电器有限公司，江苏 江阴 214401；2.江苏省柔性电加热器工程技术研究中心，江苏 江阴 214401； 3.江苏省研究生工作站，江苏 江阴 214401)

0 引言

柔性作业车间调度问题(FJSP，flexible Job shop scheduling problem)是柔性制造系统的核心，合理的调度方案可以有效降低车间成本，提高车间效率，使生产线稳定运转，进而提高企业的效益[1]。自动导引车(AGV，automated guided vehicle)作为一种自动物流载具备智能、高效、安全性能好等优点，被广泛应用于制造领域[2]，其参与的集成调度逐渐成为生产调度优化领域的重点研究问题之一[3]。

在考虑运输时间的柔性作业车间调度中，机器与AGV紧密相连，在调度过程中需同时对这两个元素进行决策。群智能优化算法[4]具有较强的并行性和稳定性，它在解决优化问题时具有很好的搜索能力，因此被广泛应用于车间调度问题求解。文献[5]以绿色调度为重点，建立基于能耗阈值的机器、AGV联合调度模型，使用改进帝国竞争算法求解模型获得较优调度方案。文献[6]提出一种融合调度模型，同时实现AGV路径规划与车间生产调度，使用混合遗传鲸鱼优化算法对其进行求解。文献[7]以车辆装配车间为研究对象，引入多AGV搬运工件，使用加入工序约束矩阵的改进遗传算法对其进行求解。文献[8]构建AGV和机器双约束的多目标集成调度模型，综合考虑多种时间因素，设计了贪心解码策略和改进NSAG-II (Non-dominated Sorting Genetic Algorithm-II)算法求解模型。文献[9]提出一种包含AGV调度和无冲突路径规划的遗传算法用以解决 AGV约束下的FJSP。文献[10]建立基于AGV的柔性作业车间自动化制造系统，提出多目标改进遗传算法优化物流需求波动和生产周期。文献[11]采用加入跳跃基因的遗传算法求解AGV约束的FJSP，优化车间绩效指标和AGV使用时长。

文献[12]提出麻雀搜索算法SSA (Sparrow Search Algorithm)。该算法由于具有搜索精度高、收敛速度快等优点，一经提出便被广泛应用于深度学习、路径规划等领域，但在柔性作业车间调度方面应用较少，且存在着很大的优化空间。在文献[13-14]中，将麻雀搜索算法应用于FJSP，但都未深入讨论AGV在FJSP中所起到的约束作用，因此提出一种改进麻雀搜索算法求解AGV、机器双约束的柔性作业车间调度问题。

1 问题描述及模型建立

1.1 问题描述

管道加热器生产车间具有多约束性、多目标性、加工柔性和运输柔性等特点。其生产过程主要受到机器加工时间和物料运输时间的约束，且在生产过程中要兼顾生产效率、生产成本、交货期等指标。此外，管道加热器的每道工序都可以在不同的机器上加工，并且具备不同的加工时间，即加工柔性。工件在机器之间的运输依靠AGV实现，每个运输任务可以选择不同的AGV执行，因AGV所处位置的差异而具备不同的运输时间，即运输柔性。综上所述，生产调度即在多个约束条件的限制下寻找可以兼顾多个生产指标的较优调度方案，因其复杂性被划分为中的NP-hard (Non-deterministic Polynomial Hard)问题[15]。

为便于求解合适的调度方案，将柔性车间抽象为数学模型，即AGV和机器双约束下的多目标FJSP，其可以描述为：设有n个工件在m个机器上加工，有v个AGV承担运输任务。每个工件有多道加工工序，加工顺序固定，每道工序有多个可选的加工机器，且不同机器上的加工时间不同。对车间模型做出如下假设：

1)起始时刻所有工件与AGV均位于仓库中；

2)AGV执行完当前任务后立即执行下一任务；

3)机器在同一时刻只能加工一个工件；

4)工序的加工过程无法中断；

5)机器的缓冲区大小不限；

6)同一工件的相邻工序在同一机器上加工时，不需要AGV运输；

7)起始时刻所有AGV与机器均可用；

8)机器缓冲区中的工件加工顺序由解码方案确定；

1.2 模型建立

数学模型可直观表达抽象的调度问题，其符号定义如表1所示。

表1 调度模型参数定义

∑Xi，j，k≤1

(1)

∑αv，Wi，j≤1

(2)

Te ，v，pre≤TZb，v，Wi，j

(3)

Pei，j-1≤TZe，v，Wi，j

(4)

TZe，v，Wi，j≤Tb，v，Wi，j

(5)

Ei，j，k

(6)

Te，v，Wi，j-1≤Si，j，k

(7)

Pei，j-1≤Si，j，k

(8)

TZe，v，Wi，j+Te，v，Wi，j-TZs，v，Wi，j-Ts，v，Wi，j=Tv，Wi，j

(9)

Ci=Ei，n，k

(10)

其中：式(1)保证机器加工工序的时空唯一性；式(2)表示AGV运输工件的时空唯一性；式(3)和式(4)确保AGV空载开始时间不早于上一次运输结束时间而空载结束时间不早于工件的上一道工序的完工时间；式(5)和式(6)确保AGV负载开始时间不早于空载结束时间和Oi，j加工结束时间；式(7)和式(8)表示Oi，j的开工时间不早于负载结束时间和Oi，j-1加工结束时间；式(9)表示AGV完成任务Wi，j所需的时间等于空载时间加上负载时间；式(10)表示工件的完工时间等于最后一道工序结束的时间。

FJSP一般把某个调度指标作为评判调度方案是否合理的标准，常见的调度指标包括订单的完成时间、机器使用寿命、设备负载均衡等，其中最小化最大完工时间和最小化设备总负载是最常用的评价指标，如式(11)和式(12)所示：

f1=Cmax=min(maxCi)

(11)

(12)

2 改进麻雀搜索算法求解柔性作业车间调度问题

半导体管道加热器柔性作业车间的生产调度方案决定车间的生产效率及生产成本。不同于传统的FJSP，还需考虑工件的运输时间。随着产业的智能化升级，AGV被应用到车间的配送环节中，承担工件的运输任务，AGV成为求解车间生产调度方案的重要约束。

将管道加热器生产车间抽象为1.2所述数学模型，以最大完工时间代表生产效率，以设备总负载代表生产成本，并考虑实际生产过程中可能出现的撤单、设备故障、新订单等动态扰动。为求解车间的生产调度方案，可以采取启发式群智能优化算法[16]。其中麻雀搜索算法于2020 年提出，由于具有搜索稳定、精度高、收敛快等一系列优点，一经提出便被广泛应用于深度学习、路径规划等领域，但在柔性作业车间调度方面应用较少，且存在着很大的优化空间。麻雀搜索算法被广泛应用于FJSP，但都未能深入讨论AGV在FJSP中所起到的约束作用，因此提出一种改进麻雀搜索算法求解AGV、机器双约束的柔性作业车间调度问题，并使用开源数据集进行验证。

2.1 麻雀搜索算法

作为一种群智能优化算法，麻雀搜索算法受自然界动物种群启发，主要模拟麻雀种群的觅食及反捕食行为。麻雀种群在寻找食物的过程中具备明确的内部分工，觅食能力强的个体被称为发现者，其余麻雀作为跟随者共享发现者提供的食物信息。同时，种群中具有警戒者，它们在感知到危险后会发出警报信号，种群会飞行至其他安全区域觅食。在迭代中，发现者的位置更新公式为：

(13)

其中：t为迭代次数，Xi，j为麻雀i在j维的解，itermax为最大迭代次数，α为(0，1]内的一个随机数，ST为安全值，R2是预警值，L是元素为1的d维矩阵，Q是服从正态分布的随机数。对于跟随者，其位置更新公式如下：

(14)

其中：XP为最优发现者，Xworst则表示全局最差解，A为一个d维矩阵。当i>n/2 时，表明跟随者i没有食物，需要飞往其它地方觅食。对于警戒者，其位置更新公式为：

(15)

其中：Xbest则表示全局最优解，β为步长控制参数，K为一个随机数，fi则是当前个体的适应度值，fg和fw分别为当前全局最佳和最差的适应度值，ε为最小的常数。

2.2 编码与解码

机器和AGV双约束的FJSP包含3个子问题：工序分配子问题、机器分配子问题以及AGV调度子问题。其中机器分配子问题是为工序选择合适的加工机器；工序分配子问题是指确定机器上的工序加工顺序，以此确定工序加工起止时间；而AGV分配子问题是为各工序安排适合的AGV，进而确定运输任务的起点、终点以及运输时间。通过麻雀个体的编码去解决机器分配问题和工序排序问题，在解码过程中通过一种自适应贪心算法求解AGV调度子问题。

合理的编码规则和解码方式是求解FJSP的关键，模型采取基于工序的二维编码方式，包括工序向量OS(Operation Sequencing)和机器向量MS(Machine Sequencing)。OS由工件号组成，顺序读取OS，工件的工序数即工件号当前的出现次数，MS从左向右与OS逐一对应，如图1所示。

图1 编码方式

AGV在解码过程中进行调度，构建一种基于自适应贪心算法的AGV分配策略。解码过程是顺序解码，当编码靠后的工件先抵达指定机器时，其需要等待编码靠前的工件抵达并加工后才能进行加工，这种情况可能造成最大完工时间的整体后移，因此，需要在解码过程中加入前插判定，对于工序Oi，j和机器M，若满足以下条件则进行前插。

1)当Oi，j-1同样是在机器M上加工时，遍历机器M上已解码工件集OM，设Om.n和Ox，y是机器M上相邻的两道工序，且Ox，y先于Om，n加工，当满足式(16)时工序Oi，j可以前插置Ox，y和Om，n之间进行加工。

Si，j，M≥Ei，j-1，M&&Sm，n，M-Ex，y，M≥Pi，j，M

(16)

2)当Oi，j-1在其他机器上加工时，遍历机器M上已解码工件集OM，当满足式(17)时工序Oi，j可以前插置Ox，y和Om，n之间进行加工。

(Te，v，Wi，j≥Ex，y，M&&Sm，n，M-Te，v，Wi，j≥

Pi，j，M)||(Ex，y，M≥Te，v，Wi，j&&Sm，n，M-Ex，y，M≥Pi，j，M)

(17)

2.3 改进麻雀搜索算法

2.3.1 初始化种群

种群的初始解质量会直接影响算法的收敛速度和最终解的质量。综合考虑初始解的多样性和收敛性，选择随机生成和局部贪心选择两种方法相结合生成初始麻雀种群，两种初始化方式各占50%。

两种方法的工序码随机由随机数排序产生。对于机器码，随机初始化可以选择可用机器集中的任意机器，而局部贪心初始化左至右遍历工序码，选择加工耗时最短的机器，获得的解具有较小的初始设备总负载。

2.3.2 改进位置更新公式

由于SSA主要用来解决连续优化问题，而FJSP是典型的离散优化问题，直接将式(13)～(15)用于解的更新会产生大量非法解，极大地降低搜索效率，且麻雀搜索算法具有收敛过早、易陷入局部最优等缺陷。因此在SSA的位置更新公式中结合NSGA-II算法，将交叉变异算子和变邻域搜索应用于麻雀位置更新，提高算法寻优能力。

SSA的寻优能力主要取决于发现者，若发现者陷入局部最优，则算法性能也随之下降，因此发现者应当具备寻优方式多样和寻优能力强等特点。为扩大搜索域，将POX (Precedence Operation Crossover)算子和RPX (Random Precedence Crossover)算子[17]引入发现者位置更新，在使用式(13)对工序码进行更新后，使用式(18)对发现者的位置进行再次更新：

(18)

图2 POX交叉算子

对机器段使用RPX交叉算子，即遍历父代的机器段，以一定概率交换两个体中相同工序所选择的不同机器。Mut()是变异操作，以一定概率采用两点变异。为了防止出现无效解，在变异后需要对机器码做修复，若工序Oi，j无法在机器k上加工，则从工序Oi，j的机器集中随机选一个可用机器。

从式(14)和(15)可以看出警戒者和跟随者的位置更新均受最差个体的影响，这限制了种群多样性和种群的搜索范围，为加强发现者的引导作用，使用交叉变异算子使跟随者获取发现者的位置信息，跟随者的位置更新公式为：

(19)

同理，在警戒者进行位置更新后使用变邻域下降搜索算法对其进行再次更新，公式为：

(20)

警戒者可用来突破局部最优，邻域结构包括：两点交换邻域、单点插入邻域、变异邻域结构。前两者可能产生无效解，需要在变邻域搜索后遍历并做修复。

2.3.3 基于Patero等级排序

由于算法具备多个优化目标，适应度值是向量而非标量，单一指标无法判断解的优劣，因此引入Patero支配策略[18]来划分解的质量优劣。解之间的支配关系反映了两个解质量的好坏，假设x1，x2是解空间的两个可行解，解x1生成的方案要优于x2，则称解x1支配解x2，而x1支配x2的充要条件是任意x1的目标函数小于等于x2的目标函数且存在x1的目标函 数小于x2的目标函数。若x1，x2互不支配，则称x1与x2无差别。

结合NSGA-II算法的快速非支配排序，根据解的Patero等级和拥挤度进行排序，并依次划分发现者和跟随者。在快速非支配排序中，设每个解都有参数S(j)和N(j)，其中S(j)是麻雀j支配的解的集合，N(j)是种群中可以支配麻雀j的解的数量。N(j)越小解越优秀，若N(j)等于0，则解j的Patero等级是0，称解j是最优解。对于同一Patero等级的解，通过拥挤度进行排序，拥挤度的计算采用的Harmonic平均距离[19]，某个体的Harmonic平均距离Hdsi定义如式(21)，排序步骤如下：

1)计算所有麻雀的N(j)和S(j)，k= 1；

2)将所有N(j) = 0的个体存入集合F(k)；

3)遍历F(k)中个体的S(i)，将集合S(i)中每个个体的N(j)减1；

4)将F(k)中个体按照拥挤度进行排序，k=k+1；

5)重复步骤2)～4)直到所有麻雀都被排序。

(21)

其中：di，Nm表示与其他个体的几何距离，Nm表示优化目标数目，在式(19)中表示参与计算的与该个体集合距离最小的个体数量。

2.3.4 精英麻雀策略

改进麻雀搜索算法融合了传统麻雀算法和NSGA-II搜索算法的特征。在子代更新阶段，传统麻雀算法可能导致父代的优秀个体丢失。而NSGA-II算法在子代更新阶段使用二元锦标赛法筛选子代种群，随着迭代的进行，子代中存在大量近似解，算法陷入局部最优。为使算法在保持种群多样性的情况下保留父代的优秀个体，引入一个独立于迭代种群外的精英种群，初始精英种群由初始麻雀种群的最优解集组成，并随着迭代的不断更新种群成员。同时，为提高子代种群的搜索质量，选择精英解加入到发现者中参与迭代。精英种群的更新方法如下：

1)遍历子代种群，若精英种群中存在一个解支配子代个体，则跳过该个体；

2)若子代个体与精英种群中所有个体均互不支配，将其加入精英种群；

3)若子代个体支配精英种群中一个或多个个体，则子代个体替换精英种群中被其支配的个体；

4)在更新过程中，为防止精英种群中个体越来越多，需设置种群数目上限，并使用拥挤度排序去除所有顺序超出上限的解。

2.3.5 自适应种群比例因子

搜索广度与深度之间的协调对于SSA的性能至关重要。为此，提出自适应种群比例策略。在迭代的早期阶段，发现者占大多数，其数目随着迭代次数的增加而自适应减少，跟随者的数量自适应增加，从而提高方案的质量。具体公式表示为：

(22)

pNum=r*N

(23)

sNum=(1-r)*N

(24)

其中：pNum定义为发现者的数量，sNum表示跟随者的数量，b定义为一个比例因子，σ是一个[0，1]之间的偏差因子，N是总迭代次数，T是当前迭代次数。

3 算法流程

使用ISSA (improved sparrow search algorithm)求解柔性作业车间调度方案的流程如图3所示，具体步骤如下：

图3 改进麻雀搜索算法流程图

1)初始化麻雀种群数量、初始发现者、跟随者、警戒者比例、ST等，按照2.3.1节方法获取初始解。

2)按照2.3.3节方法划分种群的Patero等级，将最优解集加入到精英种群。

3)按照式(13)和(16)更新发现者位置。

4)按照式(14)和(17)更新跟随者位置。

5)按照式(15)和(18)更新警戒者位置。

6)划分子种群的Patero等级，按2.3.4节方法更新精英种群。

7)若满足终止条件，输出精英种群作为最终调度方案集合，否则返回步骤3)。

4 实验验证

4.1 仿真实验

仿真调度案例使用文献[20]和文献[21]中提出的考虑工件运输时间的FJSP基准实例(数据集下载地址：https：//fastmanufacturingproject.wordpress.com)。改进麻雀算法的主要参数包括迭代次数M=100，种群数量N=50，精英种群数量SN= 10，安全阈值ST=0.8，发现者、跟随者的比例按2.3.5节划分，警戒者占20%，设存在两个AGV进行物料运输。

为验证改进措施的有效性，分别对比ISSA、离散化SSA、SSA+初始化、SSA+精英策略、SSA+自适应因子5种算法，将5种算法分别命名为ISSA、ISSA-1、ISSA-2、ISSA-3，ISSA-4，其中离散化SSA由2.3.2和2.3.3节组成。为避免偶然性对实验结果的影响，分别进行20次仿真实验，对实验数据取平均值，对比5种算法取得的Cmax和L。

由表2可以看出，ISSA算法所求得的Cmax和L都是最优的，验证了所提出的4种改进策略的有效性。从ISSA-1、ISSA-2、ISSA-3、ISSA-4的对比数据中可以看出混合初始化机制、精英种群机制和自适应比例因子都对算法寻优有一定效果。其中ISSA-3的寻优效果提升更大，说明精英种群机制对算法的求解质量有较大的提升效果。这是由于SSA在迭代过程中会丢失父代的较优解，导致每轮迭代的最优解集互相之间没有联系，局部搜索能力下降。而在设置精英种群且精英种群加入子代选择后，精英解为种群提供导向，且随着精英种群动态更新，可有效防止算法陷入局部最优。

表2 案例结果对比表

为探究各优化策略对算法性能的影响，以算例JS1L1为例，5种算法求解算例JS1L1的收敛曲线如图4所示。采取了混合初始化方法的ISSA-2拥有质量较高的初始解。拥有自适应种群因子的ISSA-4在算法早期获得较大的发现者比例，提高全局搜索能力，随着迭代的进行扩大跟随者的比例，提升算法局部寻优能力，使得种群迅速收敛。而ISSA-3则通过精英种群策略保留并更新每代的最优解集，获取较强的突破局部最优的能力，其收敛曲线呈阶梯型下降。而ISSA算法综合以上特点，具备最佳的寻优能力。

图4 算例JS1L1的迭代曲线图

为进一步验证ISSA算法的有效性，分别与INSGA-II算法、SSA算法、MICA算法及IGA算法进行对比，结果如表3所示。

表3 管道加热器的工艺信息表

表3 最大完工时间对比结果

由表3可知，ISSA算法求解出的最优值均达到当前最佳。对于案例JS7L4，其最优值和平均值均远强于其它算法，表明了ISSA算法在求解较复杂案例时也有着较为突出的搜索性能。同时，ISSA算法的平均解值与最优解值的差距很小，可见算法搜索性能的稳定。图5为ISSA求解JS7L3算例所获得的甘特图。

图5 JS7L3调度甘特图

4.2 工厂实例

以某公司半导体管道加热器柔性作业车间为例，研究ISSA在实际生产中的应用。该车间是管道加热器组装及后处理车间，主要包括管道外观修饰、焊接控制器和封头等工序。车间布局如图6所示。

图6 改进后的车间布局图

对半导体管道加热器生产车间进行改造，按照功能将原车间划分为14个加工区域。引入AGV进行区域间的物料运输，使用改进蚁群算法求解 AGV 在不同区域间的物流时间。以一批包含4种8个工件的订单加工任务为研究对象，安排其在改造后的车间进行加工。组装车间主要的加工目标是多品种的半导体管道加热器，以小管加工为例，其工序以及可选择的加工区域如表3所示。每个工序可以选择多个不同机器进行加工，虽然工序相同，但 由于不同品种的加热器具有不同的尺寸、形状以及控制器数量，且在加工过程中受工人操作熟练度约束，同一工序在不同工位上加工时有不同的加工时间。

在车间的生产调度中，AGV数量会对调度结果产生较大影响。当AGV数量较少时，无法高效地完成物料运输，机器大多处在等待工件的状态，设备利用率较低。当AGV过多时，其相互之间的路径冲突增多，运输效率下降，造成生产效率下降，且过多的AGV会增加企业的运营成本，降低企业利润。

作业车间的现行调度方案为人工实时调度，其调度规则如下：1)在选择加工顺序时，按照工件的工序顺序和订单序号进行调度；2)在选择机器时，按照订单序号和机器序号依次安排可用机器；3)若存在多道相邻工序可在同一机器上加工，则由同一机器完成相邻工序的加工。调度方案如图7所示，其最大完工时间是289.9 min，设备总负荷是1 124.3 min。同时，使用改进麻雀搜索算法对同一调度问题进行求解，调度甘特图如图8所示，其最大完工时间是242.3 min，设备总负载是1 093.9 min。

图7 改进麻雀搜索算法调度甘特图

图8 人工调度甘特图

根据图8可知人工调度方案加工顺序并不合理，且各设备负载差距较大，总加工时间较长。虽然简单明了，但忽略了每个工件之间的加工时长差异。而在小批量、多品种柔性作业车间中，个体之间的加工顺序可能相同，但单步工序的加工时间差距较大，人工调度无法获得高效、低成本的加工方案。使用改进麻雀搜索算法求解的调度方案可先于人工方案47.6 min完成生产任务，效率提升了19.6%，同时其比人工方案减少了30.4 min的设备使用时长。

5 结束语

探究实际的柔性作业车间生产过程，将运输时间引入传统FJSP，将AGV作为物流系统的载体，同时提出多种柔性作业车间优化目标，建立更贴合实际的FJSP模型。设计一种二维编码方法表示调度方案。在解码过程中使用自适应贪心算法解决AGV分配问题，并提出一种改进麻雀搜索算法获取较优解。将ISSA算法与NSGA-II算法进行结合，使用交叉变异算子以及变邻域搜索算法突破局部最优，使用精英种群保存迭代过程中的较优解集。通过多个经典案例测试，结果表明算法在求解静态及动态调度问题上有很好的效果。

本文提出改进麻雀搜索算法和改进蚁群算法分别求解AGV约束下的多目标FJSP和AGV的路径规划问题，此外还对车间的动态扰动做了深入探讨，取得了一定成果。

结合某公司柔性生产车间，研究了上述算法的实际生产意义，对原生产车间进行改进以便引入AGV执行运输任务，使用上述算法生成调度方案，并与车间原生产方案进行对比，验证了算法的优越性。结合车间的实际扰动事件，验证了所提方法的可行性。