考虑充电的多AGV的作业车间调度问题

李峥峰，刘阳阳

(中原工学院 机电学院，河南 郑州 450007)

0 引言

随着车间调度理论研究的深入和实际应用，运输时间是车间调度实际应用中不可忽视的部分，近年来得到了越来越多的重视和研究。文献[1-4]研究了考虑运输时间的作业车间和柔性作业车间调度问题;DAI等[5]研究了运输约束的柔性作业车间的多目标优化问题;HUANG等[6]研究了考虑运输约束的柔性作业车间多目标混合遗传算法;LIU等[7]研究了考虑吊车运输的能耗的集成绿色柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP);KARIMI等[8]对运输时间柔性作业车间调度问题进行了研究。

近年来，自动导引车(Automatic Guided Vehicle, AGV)在生产车间逐渐得到推广。特别是AGV在物料搬运、工件搬运等方面的应用，可以有效地减少企业的劳动力成本，减轻工人劳动强度，提高生产效率。AGV在生产车间的应用为研究运输时间提供了更准确信息，同时也带来了AGV任务分配、AGV电量约束、AGV数量及成本等新的实际问题。在车间工件加工调度的同时，还增加了AGV的调度、AGV的充电的电量约束问题以及AGV数量约束问题，这些都极大地增加了问题的规模、维度以及求解难度，使得考虑AGV运输的车间调度问题成为具有很大实际价值的热点问题，引起了科研和生产管理人员的高度重视和兴趣。贺长征等[9]研究了柔性作业车间多AGV和机器的集成调度问题;魏永来等[10]采用混合禁忌蝙蝠算法研究了AGV物料配送调度问题;刘二辉等[11]采用改进花粉算法研究了共融AGV作业车间调度问题;付建林等[11]对自动导引车调度优化问题进行了综述;HEGER等[13-14]采用排序和路由规则研究了含AGV的柔性作业车间平均拖期问题，以及柔性作业车间的AGV动态优先分配规则;Xu等[15]采用分段编码的进化算法研究了带AGV的柔性制造系统(Flexible Manufacture System, FMS)多目标多维绿色调度方法;ZHANG等[16]考虑了AGV载重量,研究了混流装配线AGV分配问题。

通过文献分析，目前对车间调度问题中的AGV充电问题研究的还比较少。DEHNAVI等[17]通过GAMS软件仿真研究了在作业车间中AGV充电站位置优化问题;WANG等[18]考虑了AGV能耗和车间复杂度来研究AGV调度方法，但研究的AGV执行一次任务后就返回，不连续执行任务。

实际生产车间中,AGV充电问题是不可回避的重要问题，直接影响运输工件的AGV工作效率、AGV的数量，反应了生产的运行成本。作业车间是典型的车间生产模式，其理论研究具有重要的实践意义。因此，本文针对AGV运输的作业车间调度问题特点，综合考虑工件调度、AGV运输任务调度、AGV充电约束以及AGV数量等因素，对考虑AGV充电的作业车间调度优化问题展开研究，设计了求解算法，并进行了仿真验证。

1 问题描述与模型

1.1 问题模式

作业车间调度问题简单描述为：n个工件在m台机器上同时并行进行加工，并有K台AGV将工件在机器之间进行工件运输，每个工件有d道不同的工序，d不大于m，每台工序只能在一台机器上进行加工。

目前，制造企业生产车间的AGV充电方式一般有两种：①在充电站直接更换电池;②在充电站停留直接进行充电。一般情形下，直接更换电池方式需要的时间较短，但电池成本更高，而直接充电方式需要AGV较长的停留时间。不论哪种方式，都需要一定的时间，本文研究将这两种方式统一用充电时长来表示。

考虑AGV充电的作业车间调度问题有以下假设：

(1)AGV运行速度固定，能耗固定，运输时间只与距离有关，运输距离和运输时间是一致的。

(2)AGV运行负载为单负载。

(3)AGV装卸时间包含在运输时间内。

(4)AGV装卸点位置在支线上，装卸或停留等待的时候不影响AGV主线通行。

(5)AGV送达地点后立即卸载，即机器工件缓冲区无限大，不考虑工件拥堵。

(6)AGV完成一个运输任务后，若电量小于阈值，则返回充电站充电，否则待在原地;若有新的任务分配，立刻前往任务起始点等待。

(7)AGV阈值电量能完成一个最远距离任务并返回充电站，不存在中途没电的情况。

(8)AGV充电过程不中断，充满为止。

(9)AGV运输任务完成过程不中断

(10)AGV运行路线不考虑路径冲突。

(11)准备就绪状态，工件、设备和AGV可用时间为0，不需要额外准备时间。

(12)设有工件物料区、成品区和充电站区域。

(13)所有AGV有调度中心进行任务分配，AGV之间无通信协调。

1.2 参数符号定义

M表示设备，Ml表示第l个设备，m表示设备数量；

A表示AGV，Ak表示第k个AGV，K表示AGV数量；

J表示工件，Ji表示第i个工件，n表示工件数量;

O表示工序，Oij表示第i个工件的第j道工序，d表示工件最大工序数;

A表示AGV，Ak-bat表示第k个AGV的电池实际电量;

Ak-max表示最大电量;

Ak-able表示AGV可用时刻;

Ak-threshold表示AGV电量阈值;

Ak-pos表示AGV当前位置;

Ak-start表示AGV开始运输时刻;

Ak-end表示AGV运输完成时刻;

Ak-total表示AGV每次任务总运行时间;

Ak-power表示AGV单位时间能耗;

Ak-chargeRate表示AGV充电速率;

Ak-charge表示充电时长;

Mij表示工件i工序j的加工设备;

Tk-pos-mij表示AGV从当前位置到Mij的时间;

TijAk表示工件i的j工序用AGVk运输的时间;

Sij表示工件i工序j的加工开始时间;

Cij表示工件i工序j的完工时间;

pij表示工件i工序j的工艺加工时间。

1.3 优化模型

优化目标为工件最大完工时间最小化：

f=minMax(Ci)。

(1)

考虑AGV充电的作业车间调度的约束有：

Ci=Sid+Pid;

(2)

Sij=Ci(j-1)+TijAk;

(3)

Cij=sij+pij;

(4)

Tk-start=max{Ak-able+Tk-pos-mi(j-1)，C(ij-1)};

(5)

Tk-end=Tk-start+Tk-mi(j-1)-mij;

(6)

TijAk=Tagv×(Ak-able+Tk-pos-mi(j-1)-C(ij-1))+

Tk-mi(j-1)-mij;

(7)

Ak-total=Tk-pos-mi(j-1)+Tk-mi(j-1)-mij;

(8)

Ak-bat=Ak-total×Ak-power;

(9)

Ak-charge=(Ak-max-Ak-bat)/Ak-chargerate。

(10)

式(2)表示工件最后一道工序加工结束就是完工时间;式(3)表示工件工序的开始加工时间受上一道工序加工时间和运输时间约束;式(4)表示工件工序完工时间受开始加工时间与加工工艺时间约束;式(5)表示AGV开始运输时间受AGV可用时间、AGV到上道工序加工设备的时间以及工件上道工序完工时间的约束;式(6)表示AGV运输完成时间;式(7)表示实际运输时间受AGV可用时间、AGV当前位置、运输任务起止位置以及上道工序完工时间约束;式(8)表示完成运输任务AGV总运输时间，即AGV从原来位置移动到工件起始位置再把工件运输到下一工序加工位置的实际移动时间;式(9)表示AGV消耗电量;式(10)表示AGV充电时长约束。

2 改进遗传算法求解

含有多AGV的作业车间调度问题可以分解为工件在设备上的调度问题和运输任务AGV的分配问题两个子问题。针对考虑充电的多AGV车间调度的特点，设计如图1所示的改进遗传算法(improved Genetic Algorithm, iGA)。

(1)编码 针对两个子问题，采用工序和AGV两段染色体编码，如图2所示。考虑到AGV运输问题，由于工件需要在原料库、设备和成品库之间进行运输，每个工件的运输任务比工序数多1，为了便于统一两段编码，将成品库假设为一个虚拟设备，其加工时间为0。

工序编码采用整数编码，基因为工件编号，长度为总工序数+总工件数n。AGV编码采用整数编码，基因为AGV编号，该段染色体长度为总工序数+总工件数n。

以图2染色体编码为例，工序编码部分表示3个工件的工序编码，编码数字表示工件代号，数字出现的次序表示工序，每一个工件有3道工序，其中前两道工序为机器上的实际加工工序，第3道工序为虚拟设备M3上的虚拟工序Oi3，M3对应的位置表示成品库。从工序编码可以得到运输任务序列，运输任务中的下标表示运输的起始位置和终止位置，其中0表示原料库，3表示成品库，其他数字表示相应设备的位置；AGV编码即AGV代号，表示对应相同工序编码的运输任务。

如工序编码第一个3表示工件3的第一道工序O31，相应的加工设备为M1，其对应的运输任务T01表示从原料库运输到设备1，相应的AGV编码为1，表示运输任务T01分配给代号为1的AGV；工序编码第二个3表示工件3的第二道工序O32，其加工设备为M2，对应的运输任务为T12,表示从设备M1运输到设备M2处，相应的AGV编码为2，表示运输任务为T12分配给代号为2的AGV；工序编码第三个3表示工件3在虚拟设备M3上的虚拟工序O33，运输任务T23表示从设备M2到成品库，相应AGV编码为3，表示运输任务T23分配给代号为3的AGV。

种群初始化，对于工序编码部分可以采用随机初始化，AGV任务编码按均匀分配编码进行初始化。

(2)交叉 父代的两个染色体通过相互交换基因生产新的子代染色体。交叉方法采用POX(precedence operation crossover)方法，通过对染色体中的多个工件进行操作，很好地保持父代个体的优良特征[9]。工件集{J1,J2,…,Jn}采用随机方式分为两个工件子集Jobset1和Jobset2；再分别对两个工件子集生成其子代C1/C2。

其过程如图3所示，对工件子集Jobset1生成子代C1，依次按父代染色体基因位进行顺序复制。如果父代染色体P1的基因位是set1的所包含工件，则保持位置和顺序不变化，复制到子代C1；然后根据C1空白位置，按顺序依次复制父代染色体P2中的非set1工件的基因位到C1。同样地，对工件子集对工件子集set2生成子代C2。

(3)变异 采用随机互换两点基因进行变异的方法，在染色体中随机选择两个基因位置，然后将这两个基因交换位置，在实现变异的同时保证了编码的合法性。

(4)局部搜索 经过变异后的个体，按照一定概率进行局部搜索。在个体中选择3个不同随机的位置，对这3个基因进行排列产生另外5个候选解。

(5)选择 选择方法采用锦标赛方法，其具有更小的复杂度、易并行处理等优点

(6)解码 对工序部分进行解码，生成工件工序的加工顺序。

1)依次读取一位染色体基因，转换为相应的工序Oij。

2)获得该工序的加工设备序号和工艺加工时间。

3)获得该工序的运输任务序列R，获得运输起点和目的地;然后根据工序部分解码，得到运输任务序列R，对AGV编码部分进行解码。

4)依次读取AGV编码的一位染色体基因，获得相应AGV状态信息。

5)根据其运输任务，获得该运输任务的起始点、目的点和运输时间。

6)根据目前AGV所在的原始位置，计算AGV到运输任务起始点的时间，根据式(5)计算Tk-start，根据式(7)更新TijAk，计算式(8)Ak-total，根据式(9)计算AGV电量Ak-bat，更新AGV可用时间Ak-able，完成该运输任务，更新AGV状态信息。

7)判断AGV是否需要充电，如不需充电，转骤8)；否则，回充电站充电，计算AGV回充电站的时间，更新AGV电量，更新充电开始时间，进行充电，计算充电时长Ak-charge，更新AGV的可用时间Ak-able，更新AGV状态信息。

8)判断是否全面解码结束，结束则跳转9)；否则转1)。

9)结束。

3 仿真测试与分析

3.1 算法有效性验证

为验证算法的有效性，仿真程序采用VC6++实现，初始种群数量为200，交叉概率0.8，变异率为0.01，迭代200，并采取保优策略，运行10次取运算结果的平均值作为参考值。

为验证算法的有效性，从以下两个方面进行对比验证：①与经典遗传算法(Genetic Algorithm, GA)对比算法的寻优能力和收敛速度，从而验证算法的质量；②与不考虑运输时间优化的调度方案的完工时间对比，从而说明该问题研究的必要性及算法的效果。算法有效性验证采用经典的FT06和LA01算例进行比较，FT06是6×6问题，而LA01则是10×5问题，具有一定的代表性。在测试过程中，运输时间相对加工时间长短不同，对优化结果的影响也有所不同，运输时间越长，优化结果越明显，反之优化结果越不明显。为了更严格地验证算法的有效性，本文选择运输时间最小的情况来进行验证算法有效性，即单位距离运输时间为1。

如表1所示，算例为验证算法的FT06和LA01算例；不考虑运输时间最优解表示没有运输时间，只有加工时间优化的最优完工时间；加工时间范围表示工件所有工序的工艺加工时间区间范围；加入运输时间的最优解表示在之前最优解的基础上，直接增加相应工件的运输时间后得到的实际完工时间；tGA算法Cmax表示考虑运输时间采用经典GA进行优化的完工时间结果；iGA算法Cmax表示考虑运输时间采用改进GA算法进行优化的完工时间结果；Im%表示相对加入考虑运输时间的最优解，iGA算法对完工时间的改进程度；itGA%表示考虑运输时间，iGA算法相对经典tGA优化结果的改进程度。从表中可以看到，是否考虑运输时间优化对完工时间的影响很大，具有明显的改进效果。即使在最小单位的运输时间情况下，运输时间对完工时间的影响也不可忽视，因此考虑运输时间进行优化是十分必要的。同时，在运输时间最小、优化结果最不明显的情况下，iGA算法相对经典tGA算法具有一定的改进作用。

表1 算法的有效性验证结果对比表

为了更好地观察本文算法的收敛性，图4给出了FT06和LA01算例下iGA算法和经典tGA算法的有效性比较曲线，可以发现不论是收敛速度还是寻优能力，iGA算法相对经典tGA都有所提高。

在验证了改进算法iGA的有效性后，以下分析研究影响AGV充电的主要因素。通过对考虑AGV充电因素的问题分析，影响优化目标的因素主要有运输时间、AGV数量、AGV电量等几个方面。下面选择经典的FT06测试用例对这几个因素进行仿真测试研究。

3.2 运输时间影响分析

简化情况下，不考虑其他约束，在AGV速度固定不变，运输时间指工件在设备间移动的时间，与设备间的距离成正比关系。设备间运输时间相对工件工序工艺加工时间的比例是更准确地反应运输时间对优化目标的影响。不失一般性，假设相邻设备距离为单位距离，选择单位距离的运输时间与单个工序平均加工时间的比值来分析其影响。在算例FT06中，工序工艺加工时间范围为1～10，平均工艺加工时间为5.7，本文测试单位距离运输时间在1～8之间对优化目标的影响。此时，AGV数量为6，AGV电量为100，即AGV数量和电量都足够完成所有运输任务。结果如表2和图5所示，随着单位距离运输时间的增加，完工时间也相应增加，优化效果逐渐增加。在单位距离运输时间达到工艺时间的80%左右，优化效果减少，是优化曲线的拐点，并且之后优化效果快速下降。这是因为随着单位运输时间相对工艺时间比值的增加，加工时间对工件完工时间的作用在降低，而运输时间的作用在增加，并逐步改变着问题的性质。此外，从仿真结果可以看出，随着单位距离运输时间的增加，不考虑运输时间的优化结果逐渐偏离了实际生产情况，这也是其结果不能应用于实践调度的原因。

表2 单位距离时间的仿真结果表

3.3 AGV数量影响分析

在考虑采用AGV运输工件的车间优化中，AGV作为运输的载体，是否能够及时将工件送达设备，成为影响完工时间的关键因素。AGV数量的多少直接影响运输的任务分配，对优化目标亦有明显的影响。最理想情况下，每一个工件都有一个专职AGV运输该工件，这样AGV就完全不会成为运输的制约。在FT06算例中，工件工序的加工时间数值在1～10之间，假设单位运输时间为1。为了避免AGV电量和AGV数量相互影响，假设AGV电量充足不需要充电，研究AGV数量对完工时间的影响。仿真结果如表3和图6所示，随着AGV数量的增加，完工时间逐渐减少。当AGV数量为工件数量的30%，优化效果显著增加，是优化效果的拐点，说明AGV数量小于工件数量的30%时，优化性能会急速减少，AGV运输成为制约完工时间的瓶颈，严重影响生产效率。当AGV数量大于工件数量的80%时，AGV数量对完工时间的优化基本停滞，此时达到较优解，再通过增加AGV数量来提高优化效果作用不太明显，而且还会增加经济成本。

表3 AGV数量的仿真结果表

3.4 AGV电量

在不考虑AGV负载轻重影响能耗的情况下，AGV固定速度，电量就代表着其可用工作时间，也代表运输距离。AGV的可用工作时间的长短直接影响其到充电站充电的次数，也影响工件等待AGV的时间，从而影响完工时间。在FT06仿真实验中，工件工序的平均加工时间为5.7，AGV数量为6，单位距离时间为1。仿真结果如表4和图7所示，随着AGV可用时间越长，AGV的优化效果越好。由此可知， AGV可用时间与工序工艺时间的比值更直接体现其对优化目标的影响，当AGV可用时间相对工序加工时间的比值在2左右，是优化效果的拐点。这是因为当AGV可用时间太短时，AGV频繁回到充电站充电，将导致运输效率急剧恶化;随着AGV可用时间的增加，当比值达到2左右，AGV可以进行运输从而实现运输的优化，随后优化效果提升明显;继续增加，当比值达到5时候，AGV的充电基本可以不影响工件的正常运输，达到最优值。

表4 AGV电量的仿真结果表

4 结束语

本文针对考虑多AGV充电的作业车间调度问题进行研究，建立了考虑充电的AGV运输工件的作业车间调度模型，设计了集成工件加工机器分配和运输任务AGV分配的集成遗传编码方式，设计了相应的改进遗传算法进行求解，最后分析了单位运输时间相对长短、AGV数量、AGV电量(单次充电可用时间)对优化作业车间工件完工时间的影响，并进行了仿真测试和验证。在未来工作中，将针对运输时间相对时长、AGV数量、AGV电量及AGV充电站位置之间的相互影响，AGV轻载和重载对耗电量的影响，AGV路径冲突以及相关多目标优化展开进一步研究，同时改进求解算法的收敛性和寻优能力。