基于混合遗传算法的柔性作业车间机器和AGV规划

邓 希， 胡晓兵， 江代渝， 彭正超

(1.四川大学机械工程学院， 成都 610065; 2.四川大学宜宾园区， 宜宾 644000)

1 引 言

柔性制造系统(FMS)将加工设备与先进信息技术结合，实现了加工制造的柔性化和自动化加工[1].柔性作业车间中工件加工可有一种或多种机器可选，并有相应的加工时间，一道工序完成后由AGV运送到下一加工机器的位置加工下一道工序，不同的机器和路径选择则有不同的运输时间，因此机器、AGV选择和AGV路径规划都会影响整个生产调度周期，随着自动引导车辆(AGV)在柔性作业车间的广泛使用，考虑AGV运输的作业车间调度更能反映真实加工情况.解决柔性作业车间资源分配优化问题，最大化地利用生产资源，提高生产效率，对提高柔性制造企业的核心竞争力具有重大意义.

国内外学者对考虑AGV的作业车间调度问题做了许多研究.李岩等[2]建立了可变工艺路径、包含 AGV的FMS调度问题的模型，但其将返回成品区的时间包括在最后一道工序的时间内，忽略了AGV调度对时间的影响；柳赛男等[3]提出了基于遗传算法的机器/AGV的调度算法，Lacomme等[4]建立了一种基于析取图的机器/AGV联合调度模型框架；这部分学者[2-7]假定AGV的路径和行驶时间是确定的，但在调度中未考虑AGV行驶过程的碰撞冲突问题，以及不同路径对运输时长的影响.

Saidi-Mehrabad等[8]提出了一种二阶段蚁群算法求解问题，讨论了AGV的无冲突路径规划问题以及基本的车间作业调度(JSSP)问题，但所讨论的每道工序加工机器都是唯一的，未讨论柔性作业车间中零件的多台可选加工机器的情况.贺长征等[9]针对柔性作业车间机器/AGV的双资源调度设计了三链式编码结构，提出了基于时间窗和Dijkstra算法的混合遗传算法，但在AGV路径规划中未考虑小车静止时的占用冲突问题.

遗传算法在车间生产排产问题中有较为广泛的应用[10]，本文针对柔性作业车间机器/AGV的双资源集成调度问题，提出基于时间表和A*算法的混合遗传算法，以工件每一道工序为基础单元，以工件运回任务为特殊单元，设计了基于任务单元的染色体结构，分析解决了AGV小车在机器节点处等待的占用冲突问题，最终获得柔性作业车间的机器/AGV完整调度分配方案.

2 问题描述和模型建立

假设生产车间有k台可加工机器，v辆相同的AGV小车，当前总任务有n个待加工工件，每个工件有一道或多道工序，每道工序可在一台或多台机器上完成加工作业，并且有相应的加工时间.每台空闲的AGV小车都可以运送工件，最终加工完成的工件需要全部送回成品区.

本文引入表 1的符号定义，并假设条件如下.

1) 同一工件各工序的加工顺序固定，不同工件的工序加工顺序互不影响;2) 每个工件的每道工序只能在可选机器的一台上加工完成，加工时长确定，加工开始后不允许中断;3) 每台机器一次只加工一个工件.机器的工件存放空间足够大，待加工工件可提前送达，已加工工件可暂时存放.机器位置小车停靠会引起阻塞;4) 每台AGV小车一次只运送一个工件，行驶速度稳定不变;5) 所有AGV小车起始位置为毛坯库，结束任务后停留在成品库或机器旁;6) AGV小车结束当前运输任务后从当前位置立即开始下一运输任务，无空闲等待时间，运输任务全部完成后返回装卸点;7) 机器和AGV小车在零时刻都是可用的;8) 考虑AGV小车之间的碰撞冲突.

表1 符号定义

总调度任务为确定每一个任务单元的执行顺序，加工机器和AGV小车，规划AGV小车的最佳行驶路径，获得各工件工序的最佳开始加工时间和加工完成时间，以及最早运回成品区的时间.

目标函数：

(1)

约束条件：

(2)

(3)

Sijk+A×aiji′j′k≥Si′j′k+ti′j′k

(4)

Si′j′k+A(1-aiji′j′k)≥Sijk+tijk

(5)

(6)

式(1)表示模型以最大总运输时间最短为目标；式(2)表示工件的每道工序可也仅可在一台机器上加工完成；式(3)表示每个任务只能由一台AGV小车运送；式(4)和式(5)中A为一个特别大的数，公式表示在同一机器上后加工的工序必须等待前一工序加工完成才能开始加工；式(6)表示负载行程要等待小车到达且工件加工完成后才能开始，运输工件第一道工序任务时，无加工等待时间.

以每个工件的每道工序为一个任务单元，并考虑加工完成后将工件运回成品区的任务，每个工件有Pi+1个任务单元，其中，最后一个任务单元只含有运输任务，其余则包含运输任务和加工任务.任务及资源调度解析图如图1所示.

图1 柔性作业车间任务及资源调度解析

图1中，TAiu表示一个作业任务，Oij，Mk，Vv表示该任务所处理的工件工序，以及需要的机器和AGV资源，如任务TA11表示由V2运输工件N1到机器M1，在机器M1上加工O11，TA14表示由V2运输加工完成的工件N1到成品区.

3 路径规划冲突类型及解决策略

使用栅格地图[11]表示柔性作业车间布局环境，如图2所示 ，LU1表示毛坯仓库上货点，LU2表示成品仓库卸货点，标有Mk的栅格为机器Mk所在的节点位置.

图2 栅格地图Fig.2 Raster map

在小车的一次运输任务周期内，包含空载行程，等待负载，负载行程三个状态，如图3所示，负载行程结束后立即进入下一任务等待状态，当前一任务结束时小车所在位置和下一任务起始位置相同时，AGV小车无空载行程.

图3 AGV小车作业周期示意图Fig.3 Operation cycle of AGV

3.1 A*算法

A*算法是一种启发式的搜索算法，通常采用f(n)=g(n)+h(n)作为启发式评估函数[12].本文采用曼哈顿距离作为启发函数，曼哈顿距离的启发式函数为

h(n)=abs(n.x-goal.x)+abs(n.y-goal.y)

(7)

A*能快速搜索出起点和终点之间的全局最优路径，具有结构简单、搜索精度高等优点[13].但是在多小车运输的路径规划中，由于存在交通冲突，A*算法并不完全适用，因此需要使用改进的基于时间表的A*算法进行路径规划.

3.2 AGV行走状态冲突及解决策略

在AGV路径规划的问题中，常见的交通阻塞有相向阻塞，交叉阻塞和节点占用3种.假设起始时间t，每拓展一个节点时间增加Δt，在A*算法中拓展节点N时，根据时间表查询待拓展节点的占用情况，并判断阻塞类型.

若为交叉阻塞，小车以当前点当作一个临时目标点，查询节点N占用结束时间为t1，以当前节点C为新的起始点，起始时间t=t1进行路径规划，更新时间表.

若为相向阻塞和节点占用，则将被占用节点N设为不可行点，并继续拓展新的节点，若无可拓展节点，则起始时间t=t+Δt，重新进行路径规划.

由于AGV小车完成单个任务后停靠于机器旁，而其他任务优先级的小车若要访问此机器则不允许其长时间占用，因而产生的机器节点位置占用冲突.

图4 AGV等待状态冲突示意图Fig.4 Conflict of AGV waiting state

在任务TAiu中，如图4所示，小车Vv取件(空载)时，根据路径规划获得到达机器Mk的时间VET′iuv，根据式(6)计算小车Vv运输Oij(负载)开始时间VSTiuv.

(8)

4 基于遗传算法的车间作业规划

采用一个实例来描述遗传操作的过程.工件加工信息如表2所示.

表2 柔性作业车间工件加工及运输信息

4.1 编 码

采用扩展的基于工序的编码[7]，编码由三部分组成，第一部分为任务编码，表示工件的工序加工任务顺序，和工件加工完成后运回成品区任务的顺序，基因串长度为

(9)

第二部分为机器编码，表示各工件各工序的加工机器，基因串长度为总工序数为

(10)

第三部分为AGV编码，表示执行各工件各工序运输任务的AGV小车，顺序对应任务编码中的各任务运输所需AGV号，基因串长度为L1.

根据表1实例信息编码的染色体编码方式如图5所示.

图5 染色体编码方式

按从左到右的顺序计数，任务编码基因串中的数字表示工件号，出现的次数n表示执行工件的第n道工序的任务，最后一次出现的数字表示运回该工件的任务.如第一个1表示执行工件1的第一道工序任务，第二个1表示执行工件1的第二道工序任务，第四个1即最后一次出现的1表示运回工件1的任务，以此类推；AGV编码中第三个的数字为2，表示任务编码中第三个任务即加工工件3的第一道工序使用的AGV小车号为3，以此类推；机器编码中工件1的范围内表示工件1的三道工序依次由机器1、2、2加工，以此类推.此编码方式可得到柔性作业车间一个完整加工和运输作业中多机器和多AGV调度问题的可行解.

4.2 初始化

初始种群的质量对遗传算法求解FJSP问题有较大影响，由于本文以最短完工时间为目标函数，在机器编码中按0.2的概率选择加工工序Oij时长最短的机器，在AGV编码中按0.2的概率将AGV小车较为均匀的分配，减少部分小车的闲置.在保持初始种群多样性的同时提高初始化种群个体质量.

4.3 选择操作

使用随机遍历选择法，根据随机生成的序号选择选择种群中相应位置的个体进行交叉和变异操作，保证种群的多样性.

4.4 交叉操作

根据染色体编码的不同，针对任务基因串使用OX交叉算子，随机取两条P1,P2父代染色体和随机的两个点，分别将P1,P2两点之间的基因段G1，G2提取到子代两条染色体C1,C2的相同位置，将P1按顺序删除G2中存在的基因，按顺序填入C2的基因空位中，将P2按顺序删除G1中存在的基因，按顺序填入C1的基因空位中.任务编码基因串交叉过程见图6(a).

针对机器基因串和AGV基因串使用MPX交叉算子.随机生成一条与机器基因串长度相同的0、1序列M，将父代染色体P1,P2中数字1位置的基因互相交换，即交换所使用的机器或AGV小车.AGV基因串交叉过程见图6(b)，机器基因串交叉过程见图6(c).

图6 染色体交叉示意图Fig.6 The crossing process of chromosome

4.5 变异操作

针对任务基因串，从染色体P1中随机选择两个位置的基因，然后将它们的位置互换.任务基因串变异过程见图7(a).

针对机器基因串，随机选择机器编码的基因串上的一个基因，在该工序的加工机器集中随机选取另外一个不同的机器替换掉当前机器，并按0.2的概率选择加工时间最短的机器.机器基因串变异过程见图7(b).

针对AGV基因串的变异采用和任务基因串相同的变异方式，在其基础上按0.2的概率随机选择AGV编码基因串上的一个基因，选择出现次数最少的AGV小车号替换当前基因，以平均AGV小车的利用率，且较为均匀的小车数量分配能减少总运输时间.AGV基因串变异过程见图7(c).

图7 染色体变异示意图

4.6 精英保留策略

父代种群通过交叉变异产生子代种群，将种群合并后得到规模大于P的临时种群，为保证进化过程中种群规模一致，需对种群内个体进行筛选.首先保存父代种群中的最优解，当存在多个最优个体相等时，以AGV行走时间最短为第二目标，计算AGV小车的总运行时间T，根据下式.

F=F+0.0001×T

(11)

对个体进行排序，保留AGV小车的总运行时间最小的个体为最优解.

通过轮盘赌法根据适应度占比在临时种群中随机选择个体，生成规模为P的新种群，最后采用精英保留策略，用保存的父代种群最优解替换新种群中的最差解，得到下一代的父代种群.

既保证种群的多样性又保留种群中最优的个体，加快全局收敛性和计算效率.

4.7 解码和适应度计算

根据染色体的编码可以获得任务信息，包括加工工件工序Oij，所使用机器Mk和运输的AGV小车Vv.将信息作为基于时间窗的A*路径算法的初始条件，结合冲突检测和解决方案，得到一条无冲突无阻塞的路径和相应的运输时间，将已加工完成的工件最后运送到达成品库的最晚时间max(VETv)，为完成所有任务的最大时长，即染色体适应度值F.路径规划具体步骤如下.

步骤1读取信息.从左到右依次读取任务染色体中的一个基因，判断任务类型.若为加工任务，对应工序为Oij，加工机器为Mk，加工时间为tijk，前一道工序Oi(j-1)的完工时间Ci(j-1)，小车可用时间VRTijv；若为运回任务，则无加工机器和加工时长信息.对应工件为Ni，工件最后一道工序OiPi的完工时间CiPi，小车执行运输任务TAi(Pi+1)可用时间VRTi(Pi+1)v.

根据相应信息和运输起始位置SP，终点位置EP，选用的AGV小车Vv，小车当前位置Pv，执行步骤2.

步骤2空载路径规划.根据地图和时间表，小车Vv的可使用时间VRTijv，起点小车位置Pv，空载任务终点SP，进行空载路径规划，执行步骤5，获得最短路径和相应的时间表，执行步骤3.

步骤3等待状态冲突判断.根据时间表查询是否存在机器节点占用冲突，若有，执行AGV等待状态冲突解决方案，返回步骤2，若无，执行步骤4.

步骤4负载路径规划.根据负载开始运输时间VSTijv，起点SP，终点EP， 由基于时间表的A*算法求解出最短可行路径，执行步骤5；获得最短路径和相应的时间表，执行步骤10.

步骤5基于时间表的A*算法搜索路径，根据输入的起始时间t，起始节点S，目标节点G进行路径搜索，当前节点为C，拓展节点N，每拓展一个节点时间增加Δt.

步骤6冲突检测.通过时间表查询t+Δt时刻节点N占用情况，若未被占用，更新时间表，执行步骤7，若占用，执行步骤8.

步骤7判断节点N是否为目标节点G，若是，输出最短路径和相应的时间表，返回相应调用步骤2或步骤4.若不是，则继续拓展下一节点，执行步骤6.

步骤8判断阻塞类型.执行AGV行走状态冲突解决方案，拓展新的节点，执行步骤6，若无可拓展节点，则起始时间t=t+Δt，重新进行路径规划，执行步骤5.

步骤9根据空载和负载行程的最优路径和时间表计算此任务中工序Oij的开始运送时间VSTijv，运送结束时间VETijv，当任务为加工任务时，计算开始加工时间Sijk和加工完成时间Cijk，当任务为运回任务时，得到小车运回工件到成品库的时间.

步骤10重复步骤1～步骤9，直至所有任务都解码完成，得到各工件的加工方案，小车的调度方案和适应度值F.

算法的具体流程如图8.

图8 算法流程图Fig.8 The flow chart of algorithm

5 算法对比分析

采用文献[8]中的算例(1～8)在MATLAB 2016a 对本文算法进行对比验证.算例中布局环境信息，工件、小车及机器信息见文献[8],将该文献中的算法命名为GAMS，ACA，一般遗传算法记为GA，本文改进的混合遗传算法算法命名为HGA.以总任务完成时间最小为目标进行计算，程序运行5次结果平均值见表3.一般遗传算法与本文改进遗传算法的基本参数设置分别为：初始化种群popsize=30,最大进化代数mgen=30交叉概率pc=0.6，变异概率pm=0.2.

表3 不同算法求解结果对比表

表中“-”表示求解时间较长，无法求得结果，对比结果可以看出本算法在解决中小规模JSP问题时相较于文献[8]中的算法有较优的结果，使用本文算法获得的最大完工时间比ACA算法平均减少了20%左右，相较于一般的遗传算法，在求解规模增大后也逐渐产生优势，因此可以证明本算法的可行性和优越性.

应用本文算法求解柔性作业车间的算例，以下是通过对离散制造企业进行调研处理后获得的柔性作业车间中多加工机器选择的算例数据.车间待加工工件为5个，机器6台，AGV小车3辆，具体工序和加工机器时间如表4所示.车间布局如图2栅格地图所示，假设AGV小车行走每一栅格的时间为1 min.

设置基本参数分别为：初始化种群popsize=60,最大进化代数mgen=50,交叉概率pc=0.6，变异概率pm=0.2.计算5次获得的最优调度方案甘特图见图9，该生产调度最佳调度周期为144，三辆AGV小车行走时长依次为99、111、117.小车每一时刻所在节点位置情况如图10 所示，数字1、2、3分别表示三台AGV小车，从图中可以看出AGV小车在行走和等待的状态下都没有节点占用冲突，符合算法设计要求.

表4 工件加工时间表(min)

图9 调度方案的甘特图Fig.9 The Gantt graph of scheduling scheme

图10 AGV位置节点时间表Fig.10 Time table of AGV location

图11 HGA算法搜索过程曲线Fig.11 The process curve of HGA algorithm

图12 一般遗传算法搜索过程曲线Fig.12 The process curve of simple genetic algorithm

改进的混合遗传算法和一般遗传算法的搜索过程曲线分别如图11和图12所示.从图中可以看出适应度值逐渐减小并收敛，改进的混合遗传算法在20代开始收敛，比一般遗传算法收敛速度更快，且获得的最优解更好.仿真结果表明，本文使用的基于时间表和A*算法的混合遗传算法在处理柔性作业车间机器/AGV双资源调度问题是有效的，算法收敛速度较快，能够得到完整柔性车间工艺和物流集成规划方案.

6 结 论

本文针对柔性作业车间机器/AGV双资源调度问题，使用栅格地图模拟车间机器布局和AGV运行环境，分析了AGV小车在运动和静止两种状态时的冲突情况并提出解决方案.提出基于时间表和A*算法的混合遗传算法，设计了以任务为单元的染色体结构，提出相应的交叉变异操作和精英保留策略.以AGV行走时间最短为第二目标，在适应度值相等的个体中优先选择AGV行走时间最短的个体，减少资源浪费.最后实验证明本文算法在解决中小规模柔性作业车间机器/AGV双资源调度问题的有效性和优越性.