基于电量和负载均衡约束的多AGV生产车间调度研究

陈 晨，张绪美，梁晓磊，鄢 威

（1.武汉科技大学 汽车与交通工程学院，武汉 430081；2.武汉科技大学 机械传动与制造工程湖北省重点实验室，武汉 430081）

0 引言

制造业的不断发展，对企业生产加工过程的优化提出了更高的要求，如何提高生产效率，成为企业亟需解决的问题。通过使用自动引导小车（aotomated guided vehicle，AGV）对生产进行调度优化，可以大大提高企业生产效率，但是同时又会产生一些新的问题，如：负载不均造成的拥堵问题，或者因为AGV电量约束产生的充电问题等。因此对生产车间，进行含有AGV的多目标调度优化，成为了目前的一个研究热点。

在传统的生产车间调度研究中，最直接的提高生产效率的方式就是减少调度的时间，因此有学者对AGV调度时间进行了优化研究，如：Mahalakshmi等[1]将最小化AGV的总提前以及延误的总时间作为目标时间，采用人工免疫算法，对调度进行优化，李西兴等[2]将调度最短时间作为优化目标，采用鲸鱼算法引入遗传算法的操作，提高算法全局搜索策略，进行优化。而实际调度中除了考虑系统的整体调度时间，还需要考虑AGV在运行中的路径冲突问题对调度的影响，邓希等[3]通过与A*算法结合的混合遗传算法解决路径冲突以及AGV调度问题，对不同小车进行优先级分配，结合是否空载对路径进行再次规划。W等[4]通过调整不同AGV小车在搬运中的运行速度，优化AGV在路径上的重叠问题，利用一种高效的MapReduce框架提高系统的决策效率，解决AGV路径冲突问题。郭昆仑等[5]考虑AGV作业时间，冲突距离等因素，建立了多AGV的无冲突路径规划模型。Umar等[6]提出了一种多目标自适应权重方法，利用混合模糊逻辑以及启发式局部搜索算法对多目标遗传算法进行改进。通过优化策略以及改进算法，对AGV调度中的时间及路径进行优化，可以提高系统的整体调度效率，而在加工车间中，除了AGV调度时间和路径外还有很多其他因素会影响调度效率。

受AGV电池容量限制，在AGV运行过程中，需要考虑AGV续航及充电等问题对调度的影响，针对带有电池电量以及充电时间约束的AGV调度问题进行研究，李铮峰等[7]建立了考虑充电的AGV搬运模型，试验结果表明：搬运时间越长对AGV充电的影响越大，AGV数量越多对AGV充电的影响反而会逐渐减小。Moussa等[8]以最小化完工时间为目标，研究了不同的充电策略下，机器、AGV以及充电站的最佳安排方式，运用基于GVNS的启发式算法，优化了AGV调度。同时随着AGV数量的增加，系统还按照时间最优的策略来进行调度，就会产生负载不均的问题，这些问题主要分为三类：1）机器负载不均，即某工序的加工机器持续工作，而其他的机器负荷较少，会造成加工工件在某一机器前排队；2）路网负载不均，如路网中有些节点经过的AGV较少，另外一些节点则比较繁忙，可能会产生局部拥堵；3）AGV负载不均，即由于搬运任务分配不均，导致一些AGV持续性工作，另外一些AGV间歇性工作，使得AGV间产生冲突的可能性增加，同时降低了AGV利用率。因此，在机器负载优化中，Yuan等[9]将最大完工时间、总延误、机器总负荷和总能耗最小作为目标，建立了智能制造车间资源调度模型以及基于排序水平和拥挤度的评价函数，减轻了机器在生产中的负荷。邹裕吉等[10]在时间和路径的基础上将机器总负荷也作为优化目标，通过优化算法对车间集成调度问题进行了研究。在路网负载优化中，张得志等[11]在对AGV分拣系统的研究中发现AGV在某个时间的某个节点负载量不均衡是造成拥堵的主要原因，利用整数规划优化模型，对分拣系统负载量均衡做了优化。在AGV负载优化中，Udhayakumar等[12]根据平衡的工作负荷，利用遗传算法来寻找两台自动导引车的最优的调度，平衡任务，提高了自动导引车的利用率。

综上所述，对于AGV车辆影响因素可以从这几方面进行考虑。现阶段的研究多偏向于机器以及路网负载不均两方面，而在AGV负载均衡方面的研究，大多是通过对比AGV间不同的工作负荷，来重新分配调度任务，使每个AGV达到负载均衡，提高调度的整体效率。但在实际中，AGV负载不均对调度产生的影响不是孤立的，AGV续航时间不够长或充电频率太高都会对调度产生较大的影响，因此现阶段将电池续航、充电问题与负载均衡问题结合，是十分有意义的。针对此问题，本文将在AGV续航有限且需要考虑充电，这两个约束的基础上，通过均衡性这一目标，对调度进行优化，其中均衡性是指系统在调度分配过程中，平衡每辆AGV的分配任务数，使得每辆AGV执行的任务量都基本相当，其中每辆AGV任务量与所有AGV平均任务量的差值叫做均衡性偏差，偏差越小说明系统中每辆AGV间的任务量调度越优。设计了AGV最小化最大运行时间及最小化最大均衡偏差的双目标优化模型，利用改进的自适应遗传算法，提出了三段式的编码方式，通过MFC（Minimum time selection for charged volume constraint）初始化策略，生成染色体后通过自适应的交叉变异方式，对生产车间多AGV与机器进行集成调度，根据不同的AGV数量对作业的影响[13]，研究了不同数量、不同电量的AGV在不同均衡性下的表现。

1 问题描述与建模

1.1 问题描述

生产车间调度问题一般为n件带有加工工序约束的工件，在m台机器上进行加工，机器必须完成紧前工序才能进行下一工件的加工，工件在机器之间的搬运由多个AGV来完成，AGV的调度优化是通过最大加工完成时间的最小值来实现。然而在AGV搬运中每运行单位距离都会消耗单位电量，因此AGV在调度前必须考虑有余电可以返回充电，同时充电中的AGV不能进行搬运。另外，在多个AGV调度时，会出现各AGV之间负载不均的情况，以此会造成出入口拥堵，以及部分AGV持续运行，而另一部分AGV间歇性运行，工况不均的问题。因此AGV的电量约束和负载均衡性是必须要考虑的两个方面。参考了AGV在融合调度中的运行方式[2]，使用两段搬运的方式，进行搬运。第一段搬运为AGV先从当前位置运行至工件所在位置，第二段搬运则再从工件所在位置运行至目标位置，按照最短路的原则进行调度安排，设置了AGV任务均衡性的目标函数，通过最小化均衡偏差值进行优化。

为了简化问题，存在以下假设：

1）AGV空载与负载搬运速度相同且恒定，充电时间恒定。

2）机器之间的搬运路线确定，不同机器只能加工对应工件的对应工序。

3）AGV一次只能搬运一个工件，机器一次只能加工一个工件。

4）不考虑AGV之间产生的路径冲突问题。

5）AGV和机器在零时刻都是可以用的。

6）AGV和工件都是从初始仓库出发，且在初始位置充电。

7）AGV可用电量可等价为AGV剩余可用时间。

1.2 数学模型

1.2.1 变量定义

索引及参数：

n工件总数。

m工序总数。

GAGV总数。

SAGV搬运任务总数。

K加工机器数。

i工件索引号；i∈{1,2,…,n}。

j工序索引号；j∈{1,2,…,m}。

gAGV索引号；g∈{1,2,…,G}。

sAGV搬运数索引号；s∈{1,2,…,S}。

k加工机器索引号；k∈{1,2,…,K}。

ω加工时间与均衡偏差之间的权重。

λAGV完成最短搬运时间任务并返回后剩余电量。

Oi,j工件i的第j道工序。

Ci,j加工工序Oij加工完成时间。

Di,j加工工序Oij加工开始时间。

Bk,k’工件从机器K搬运到机器K’的时间。

TBi,jAGV每次搬运时间。

HgN(AGV)g的第N次搬运结束时间。

Pi,jAGV第二段搬运开始时间。

Q一个很大的正整数。

Ng,s每个(AGV)g搬运的总次数。

ENg(AGV)g在工序Oij结束后的第N次搬运时的可用电量。

Gk,k’(AGV)g搬运工序Oij开始搬运时间。

TC充一次电的时间。

RAGV平均充电次数。

TAGV平均运行时间。

决策变量：

1.2.2 模型建立

本文的总调度任务为确定各工件工序的加工顺序，加工机器及搬运AGV，平衡每辆AGV的负载，获得各工件工序在机器上的最短加工完成时间。

优化目标1：选择最小化最大加工完成时间。

优化目标2：最小化AGV的负载均衡偏差，使得每台AGV分配的任务大致相当。通过最小化每台AGV实际任务量与AGV平均任务量间差的绝对值，来进行计算。

优化总目标即为加工时间和AGV的均衡偏差最小。

工序加工完成时间等于工件的开始加工时间加上工件在机器上的加工时间。

工序加工开始时间等于工件的加工完成时间加上工件搬运的时间，其中工件第一次加工完成时间等于其搬运时间。

AGV的搬运时间由AGV从当前位置运行至工件位置的时间以及从工件位置运行至目标机器位置的时间，以及AGV等待工件加工完成时间，三部分组成。

AGV在从工件所在位置运行至目标位置时的开始搬运时间，即第二段搬运开始时间，将AGV上一道搬运的结束时间加上第一道搬运时间与工件上一道加工结束时间作比较，得到二者中的较大值，作为第二段搬运的开始时间，确保工件加工完成后再继续搬运。

AGV的搬运结束时间。

工序Oi,j在搬运完成后才能加工。

当AGV要搬运两个不同的工件时，紧前工序能被先AGV搬运，即保证在同一时刻，每个AGV只能搬运一个工件。

一道工序只能且必须选择一台机器进行加工。

同一道工序在紧前工序完成后才能进行下一道工序的加工。

同一机器，在面对不同工序时遵循先进先出原则，同时每个机器每次都只能加工一个工件。

机器只有在搬运完成后才能加工。

每一个AGV的总搬运次数。

AGV执行完当前搬运任务后的电量。

判断AGV剩余电量能否完成当前最短时间的搬运任务（minTBi,j）并能够返回(Bk,1)。

AGV执行完任务后，剩余电量可用时间大于返回充电桩所需时间。

AGV在充电时不能执行任务。

AGV平均运行时间

AGV平均充电次数。

2 算法设计

2.1 算法编码

该问题分为工件工序分配，工序机器调度，AGV搬运任务分配三个方面，因此利用了三层编码的结构，使用实数编码的方式对染色体进行设计：

如图1所示，O表示的是工件的索引号，该索引号第几次出现，就代表此时为该工件的第几道工序，如O21代表工件2的第一道工序。M为对应工序所选择的机器，在可加工该工序的机器中的序号，K是其该序号代表的机器索引号。G对应AGV小车的索引号，该索引号出现次数即为AGV执行任务数。工序O21-O31-O11-O2-O22-O32-O33-O13-O23对应的加工机器是K4-K2-K3-K5-K2-K4-K4-K2-K1，对应搬运的AGV为G1-G2-G3-G2-G1-G2-G1-G3-G2。O-M-AGV三段编码的组合即为染色体的编码方式。

图1 染色体编码

2.2 种群初始化

种群初始化的算子，将直接影响算法的收敛效率及搜索结果，本文在三层编码结构上，提出了一种基于AGV带电量约束的最短时间选择（Minimum time selection for charged volume constraint，MFC）的初始化方案，对工序O采用随机生成策略，根据工序可加工机器M，选择对应AGV采用MFC策略。

MFC初始化步骤如下：

步骤1：定义工件对应工序加工机器，机器加工时间，机器之间的搬运路线，AGV电量，初始化当前机器运行时间，AGV运行时间。

步骤2：随机生成工件加工工序。

步骤3：按顺序选取工序，根据工序选择可加工序的机器，搬运AGV。

步骤4：根据机器加工时间和AGV搬运时间判断电量是否满足搬运条件。如果不满足则进行判断，若AGV余电小于阈值AGV需要返回充电，若AGV余电大于阈值，则等待下一次分配，如果多次电量超过阈值但无法分配，AGV需要返回充电，如果AGV要充电，本次搬运时间需要加上充电时间，满足则不需要充电。

步骤5：更新此机器及AGV的全局运行时间，全局运行时间由机器当前运行时间和此工序加工时间，AGV当前运行时间和AGV此工序搬运时间组成。

步骤6：根据全局时间选择最短时间，根据最短时间生成对应的机器索引号和AGV索引号。

步骤7：更新机器时间表，AGV时间表，AGV剩余电量。跳至第二步继续循环，直至所有工序被分配完成。

图2使用MFC选择策略根通过初始工序算子1122，以上步骤，得到的对应机器编码为1231，AGV编码为2121，所以此基因编码为112212312121。

图2 初始化策略

2.3 适应度函数

为了研究AGV工作的平衡性与调度时间之间的冲突关系，需要在两个目标之间分配不同的权重来进行比较，再通过最小化调度时间与均衡偏差，来得到优化结果。但是时间与均衡偏差不是同一个量纲，所以需要将其进行标准化的处理，才能进行计算，结合不同的数据标准化方法[14]，因比重法具有不改变评价对象内部以及评价对象互相之间的差异性，缩放无关性等优点，因此作为本文标准化的方法。适应度函数将两目标分配权重后求最小值，i代表基于基因序号，n为总基因数。

2.4 交叉变异

算法采用自适应交叉和变异的方法[15]，在种群适应度值相对分散时，降低交叉和变异的概率，保护优势个体的生存。当种群的个体适应度值趋于相同或局部最优时，增加交叉和变异的概率，避免产生局部最优解。交叉概率和变异概率的公式为：

Pc,Pm是交叉与变异的概率，Pc1,Pc2,Pm1,Pm2是设定的参数，Fmin和-F分别是适应度的最小值与平均值，F,F’是分别是交叉染色体中适应度值较大的个体适应值及突变个体的适应值。

种群采用单点交叉的方式，针对交叉产生的子代染色体不能保证工件号i有且仅出现ni次的问题进行改进，同时根据调整后的工序再调整机器和AGV。若需要调度的工件总数为n，工件ni对应mj道工序，首先从种群中根据交叉概率选取两条染色体，在染色体的前位中随机选择交叉点进行单点交叉，交叉后某些工件的工序多余，某些工件的工序缺失，因此把工件工序多余的操作变为工件工序缺失的操作，并按照交叉前个体的操作机器和AGV，来调整位的加工机器，以及位的搬运AGV。其操作如图3所示。

图3 交叉及修复

2.5 算法流程

本文整体的算法流程框架图如图4所示。算法在遗传算法的基础上，针对本模型提出了一种新的MFC初始化策略，使用随机遍历的方法进行选择，交叉变异概率进行自适应调整，进行求解。

图4 算法流程图

3 实验分析

为了验证算法的有效性，实验使用下表所示实例进行仿真实验。实例设置6个工件，每个工件对应6道工序，在9台机器上由分别由4、5、6台AGV进行搬运，AGV电量分别设置为30、40、50、60，充电时间为10。表1表示的是机器编号，由工件与工序来确定，如(1,4)表示工件1的第4道工序可以在机器2上加工，也可以在机器9上加工。表2表示的是工件加工时间，由工序与机器来确定，如(1,4)表示工件1的第4道工序在机器2上加工时间为5，在机器9上的加工时间为4。AGV在不同机器间的搬运时间如表3所示，其中0表示原材料仓库，X表示成品仓库，所有工件都将从0处出发，在工序结束后在X处卸载，如(1,2)表示AGV从0出发到1号机器需要时间为2。

表1 机器编号

表2 工件加工时间

表3 搬运时间

3.1 算法有效性验证

实验首先与没有改进的遗传算法行对比，从而验证算法的质量。算法参数设置为种群规模N=50,迭代次数iteration=100，代沟GGAP=0.9，交叉率Pc1=0.7，Pc2=0.3，变异率Pm1=0.25，Pm2=0.18，AGV数量为6，电池容量为50，调度时间与均衡偏差权重比为1:1。

tGA算法表示采用传统遗传算法后的优化结果，iGA算法表示改进算法的优化结果。图5给出了在带有充电约束的AGV调度中不同算法种群均值的变化情况。从图中可以看出，iGA算法初始解就优于tGA算法，收敛速度更快，同时iGA算法的完工时间是远远小于tGA算法的，即iGA算法具有更强的寻优能力。

图5 算法有效性对比

3.2 参数分析

在带有AGV的车间调度问题中，AGV作为搬运的主体，在AGV电量一定时，不同数量的AGV会影响搬运任务的分配，同时当AGV数量一定时，不同电量的AGV运行时间不同，进而对调度也产生很大的影响。因此接下来将通过AGV数量一定时不同电量AGV以及AGV电量一定时不同数量AGV，两种情况下各自有什么样的表现，分别观察这两个条件对调度的影响。

本文的算例是在车间调度经典算例FT06的基础上进行的拓展，附加了AGV的数量与电量等相关数据，采用文献[2]中对测试算例AGV与机器数量比例安排规则，选取AGV数量与机器数量比例为1:2，得到AGV数量应设置为5辆，为了研究不同数量AGV的影响，添加数量单位为1的左右邻域，将AGV数量分别设置为4、5、6辆。为了保证搬运需求，故设置AGV数量为6，先分析了不同容量电池对调度的影响，找到最优的电池容量，在此基础上，再研究不同数量AGV对调度影响。在考虑如何设置权重比时，参考了Udhayakumar[12]的权重比设置方案，此方案能确保AGV可以在负载平衡和搬运时间最短的条件下，找到一个接近最优的调度方式。本文在此方案的基础上进行分析，通过前期实验发现，AGV负载均衡与最短调度时间之间是一组非线性冲突关系，在调度时间最短时AGV的负载均衡性最差，因此先研究了在权重比ω1:ω2为1:0时，即在时间最短条件下的调度情况作为参考，同时在原方案基础上向左右两个方向上拓展权重比，再与权重比为1：0时进行参考，发现在权重比在7:1-1:7内，整体调度影响不大，均衡性却发生了显著变化，因此将接下来的的权重比变化设置为7:1-1:7。

表4是AGV数量为6时，不同电池容量的AGV的实验结果。表5则给出了电量为50的不同数量的AGV，在考虑任务均衡条件下的总体调度时间F1、均衡性偏差F2、AGV平均充电次数R、AGV运平均行时间T的实验结果。

表4 不同容量电池实验结果

表5 不同数量AGV实验结果

3.2.1 AGV电池容量分析

表4中加粗部分即为均衡偏差变化达到高峰的位置，从表中可以看到在电池容量为50或60时，对应权重比为1:1-1:2阶段，在电池容量为40或30时，对应权重比为1:2-1:3阶段。在此实例下可以看出50电池容量AGV是转折点，这是因为低于50容量后，由于在任务不变的情况下加大了AGV的任务量，导致充电频次急剧增大，且由图6可以看出，当电池容量由60转化为50后，充电频率在0-1之间，50减少至40后，充电频率在2-3.5之间，40减少至30后，充电频率在5-6.5之间，容量平均每减少10，频率增加的次数却不呈平均增加。

图6 AGV充电频率

从AGV的单个平均运行时间上也可以看出，容量为60的AGV在搬运时间上比容量为50的AGV仅降低了5%左右，但是容量为40的的AGV相比容量为30的AGV则降低了17%。说明不同电池容量的AGV，由于充电频率的恶化，导致搬运时间会突然增加，因此其调度时间和任务均衡偏差的权值也会随之变化，而不再是某一确定的值。根据表4比较调度时间，可以看出在权重比为1:2时，电池容量为50的AGV仅比容量为60的AGV平均调度时间增加5.4%，整体调度时间增加了1.73%，这说明使用容量为50的AGV即可基本实现搬运优化，继续增大电池容量，并不能明显提升AGV的搬运效率。

3.2.2 AGV数量影响分析

从表5可以看出，随着均衡偏差权重的增加调度的时间会逐渐增加，均衡偏差的值逐渐减小，这说明AGV的任务分配越来越均衡，同时AGV充电时间和搬运时间会有一定的增加。AGV数量一定，如当AGV数量为6时，权重在调度时间与均衡性之间的影响如图7所示，均衡性变化通过后一权重均衡性偏差值较前一均衡偏差值的减少量来观察，时间变化率为后一权重的调度时间相对前一时间的增加速度，可以看出均衡偏差的变化率与时间变化率都呈现出先增后减的趋势，而时间的变化率较均衡偏差的变化会迟一步，在权重为1：1时均衡性的变化达到最高峰，在权重比为1:2时，时间变化率达到高峰。说明在AGV数量一定时，不同的权重对调度产生的影响是不同的，在某一权重下在达到均衡偏差值变化最大的同时，避免了时间变化率最大导致调度时间增加过多的问题。

图7 均衡性和时间变化

同时通过表5可以看出，在权重比为1:1时，相对于不考虑均衡性的情况调度时间仅增加了5.4%，但是均衡性却大大提升。图8为均衡偏差值的变化，可以明显的看出在不同数量的AGV其均衡性变化规律都是，都是随着均衡偏差权重的增加，均衡偏差的值呈现出先缓慢减小在权重比为1:2时突然降低，随后再缓慢减小至0的一个过程，同时在这个过程中，均衡性的变化会先达到最大，随后在下一阶段时间的增加率会达到最大，如表5中加粗部分所示，不同数量的AGV不会对此权重产生影响。

图8 不同AGV均衡性变化

4 结语

本文针对带有电量约束条件下的AGV任务分配不均问题，通过建立带有最小化最大完工时间以及最小化均衡偏差的双目标优化模型，利用一种改进的自适应遗传算法，研究了相同电池容量下不同数量的AGV，以及相同数量下不同电池容量AGV，在不同权重中下如何能够均衡每辆小车的任务量。得到结论如下：

1）AGV随着均衡偏差权重的增加，均衡性的变化率呈现出先增后减的趋势，而时间的变化率较均衡性的变化会迟一步。

2）针对不同数量AGV，在电量相同的情况下，应选择权重在1:1至1:2之间进行优化。

3）AGV数量相同的情况下，由于充电问题，调度优化的结果会随着电池电量的减少急剧恶化。

本文是在AGV电量或者数量一定时，通过改变另一个量来对这种综合性调度问题进行研究。但在AGV数量和电量都不确定时，考虑在调度时间最短的基础上，如何均衡AGV的负载，本文还尚未考虑，因此将作为接下来的研究重点。