基于多任务理论的AGV协同多任务调度研究

董 航,楼佩煌,钱晓明,武 星,翟晶晶,胡 亚,胡子寒

(南京航空航天大学机电学院,江苏 南京 210016)

伴随“中国制造2025”战略的提出,自动导引车(automated guided vehicle,AGV)被广泛应用到各类柔性制造加工系统中,这也随之催生出具备不同工作能力的AGV。多AGV系统则是由多数量AGV、多种类AGV组成。

目前,国内外对于AGV系统的研究主要集中在单种类、少数量AGV系统的研究,关于多AGV系统的研究较少,如Mousavi等[1]提出了一种基于多种启发式算法(包括遗传算法(GA)、粒子群 (PSO) 算法和GA-PSO)的混合算法模型,对任务调度进行优化; Heger等[2]提出一种基于离散事件的物料工厂模型,有效降低了AGV任务调度系统的空载率;石宇强等[3]基于柔性系统中的协同搬运问题,对传统的粒子群算法进行改进,有效减少任务完成时间;张博晖等[4]提出了以聚类算法为模型的AGV调度策略;杨智飞等[5]提出一种基于自适应多目标的优化方式,并将遗传算法与差分进化算法(AMOGA-DE)结合,获得系统调度的最优解;刘旭等[6]提出了一种改进的遗传算法,进行AGV的任务分配和配送路径优化。本文采用基于多任务理论[7]的AGV协同多任务调度模型,提出一种改进的遗传算法(improved genetic algorithm,IGA),能有效提高制造系统的吞吐量与服务性能。

1 AGV协同多任务分配建模

1.1 任务描述

建立如图1所示的工件加工车间,本车间总共有9个加工中心Pi(i=1,2,…,9),每个加工中心都容纳一个输入缓冲区Ei和一个输出缓冲区Di,缓冲区容量为10件。工件从加工开始到成品交付的生产过程称为一次任务,在每个任务中含有若干个具有特定顺序的子任务。对于车间内的任何工件,在其从原料区取货到成品区交货的加工过程中都需要AGV完成包含牵引、搬运和装卸3种类型的子任务,每个子任务都需要1辆或者多辆AGV。

图1 加工车间

1.2 任务建模

为了计算归纳方便,采用整数规划法建造模型[8],用四元组{A,K,T,F}表示。

1)A={A1,A2,A3,…,AMs},为AGV车辆集合,Ai为AGVi,Ms为AGV的最大数量;

2)K={K1,K2,K3,…,KMn},为子任务类型集合,Ki为某种子任务类型,Mn为子任务类型的最大数量,在本文有3种子任务,分别是牵引、搬运和装卸;

3)T={T1,T2,T3,…,TMr},为所有任务集合,Ti为任务i,Mr为最大任务数量;

4)F={F1,F2,F3,…FMr},为任务约束集合,通常在AGV协同多任务中存在任务的时间约束、AGV是否协同搬运的约束以及AGV自身能力的约束等。

1.3 设定约束条件

1)时间约束。Tfloor为该任务执行时间的下限,Tceiling为该任务执行时间的上限,t为子任务Ki的完成时间,具体表示为:

Tfloor≤t≤Tceiling

(1)

2)AGV功能约束。对AGV的功能进行约束,即参与该项任务的AGV必须具有满足该任务要求的能力。设定AGV所能完成的子任务集合为tasktype(Ai),假定该AGV可以完成子任务Kj,则满足以下条件:

Kj∈tasktype(Ai)

(2)

(3)

1.4 设定调度优化目标

(4)

式中:L(Distancei)为AGVi在执行某个任务时的行驶距离。

2)时间代价。设q(i)为AGV执行子任务i的时间代价,则任务实际完成时间的总和C2为:

(5)

3)利用率代价。为确保执行任务过程中每个AGV行驶的路程都差不多,达到AGV利用率最大化,对AGV路径代价进行方差运算,方差C3可以反映数据的离散程度。

(6)

将以上3个指标进行归一化处理,可以得到AGV协同多任务分配问题的综合评价指标Cmin为:

(7)

2 改进的遗传算法设计

本节提出一种改进的遗传算法[10],为使初始种群结构多样化,使用随机函数构建种群,在交叉变异阶段采用自适应迭代模式以防止陷入局部最优并有效保留优秀个体。具体算法流程如图2所示。

图2 算法流程

2.1 基于任务排序的染色体编码

设W为任务分配矩阵,W=[wij]u×v,列数v为所有任务中子任务的总数量,如果某子任务为协同任务,则该子任务次数为所需车辆数;行数u为AGV数量。

(8)

矩阵W满足以下条件:

3)每个任务分配矩阵W代表一个任务分配方案;

4)总共有u辆AGV,从1～u分别编号,Pk,n表示Tk任务中Kn子任务需要几辆AGV执行,那么整个系统共有子任务:

(9)

2.2 构建初始种群

由于染色体编码方式不同,且在交叉变异操作中AGV自身能力的原因造成种群多样性减少,为使得初始种群在开始阶段就保持结构优良,提出改进的构建初始种群方法。

步骤1,根据AGV数量确定染色体矩阵行数,根据子任务总数量确定染色体矩阵列数;

步骤2,对染色体进行约束调整,使得AGV自身能力符合任务要求;

步骤3,使用创建离散随机种群的方式对染色体基因即矩阵中的列随机生成0或1;

步骤4,对染色体进行调整,若出现重复基因则采用覆盖法消除;

步骤5,以上步骤重复20次,直到生成具有20个个体的初始种群。

2.3 自适应迭代模式下的交叉变异

在染色体进化初期,交叉率较大和变异率较小会有助于适应度高的个体生成,而在后期优秀个体已经出现,使用较小交叉率和较大变异率可以防止陷入局部最优,并且可以维持目前较高的适应性群体。

(10)

(11)

1)交叉:每个AGV自身具有的能力不同,在交叉变异后不能改变自身能力,否则就会在实际工作中出现车辆与任务不相匹配的问题。

2)变异:由于AGV自身能力不能发生改变,因此变异操作只可以在其自身能力范围内发生,表现为同能力的列可以交换。

2.4 适应度计算

确定好染色体编码后,通过评价指标对其进行筛选。在前文中已经制定了相应的评价指标,因此改进遗传算法中适应度可以使用任务分配评价指标来衡量。

(12)

式中:F(Si)为个体适应度函数。选择操作使用轮盘赌方法,按照适应度从小到大进行排序,本文取σ=0.4,τ=0.2,π=0.4。

2.5 精英保留

为了保持群体规模不变,如果子代个体被加入到新一代群体中,则可以将新一代群体中适应度值最小的个体淘汰掉。精英个体是种群进化到当前为止遗传算法搜索到的适应度值最大的个体,它具有最好的基因结构和优良特性。采用精英保留的优点是:遗传算法在进化过程中,迄今出现的最优个体不会被选择、交叉和变异操作所丢失和破坏。精英保留策略对改进标准遗传算法的全局收敛能力产生了重大作用,使用高斯罚函数,δ=0.15。

(13)

2.6 迭代终止

算法达到了最大迭代次数Nm=100或者在交叉变异后Nr=20代个体中最佳个体没有发生变化,则操作结束。

3 仿真与结果分析

3.1 对比仿真设置

为了验证本文提出的IGA的合理性,首先与最小空闲时间优先原则(shortest vacancy time first,SVF)对比吞吐量(货物运送量),然后与GA(genetic algorithm,GA)及BBA(brand and bound algorithm,BBA)对比验证IGA的优越性。

使用MATLAB进行仿真，包括6台具有不同能力的AGV，8个任务目标，每个任务中都含有3种子任务类型。表1为AGV的能力约束表，标明了每台AGV具有的能力。任务目标由系统随机生成。共设置了6组AGV数量不同的对比实验组，即对表1AGV实验组扩充倍数，分别为1倍到6倍，每组仿真时间为24 h，AGV运行速度为1 m/s。

表1 AGV能力约束表

3.2 仿真结果分析

图3和图4所示为第一组实验下的最终仿真结果,从图中可看出,由于在算法中适应度计算是基于总行程、总时间和AGV总利用率三者进行的,因此在结果中可以发现,IGA方法中有T3、T4、T6和T84个任务皆出现由同一辆AGV完成同一任务中多个子任务的现象,而在SVF中由同一辆AGV完成同一任务中多个子任务的情况几乎没有,说明IGA算法会尽可能安排同一AGV执行同一个任务,减少了AGV不断更换子任务导致的空车路程与空车行驶时间,这对于系统整体的优化是有利的。

图3 第一组实验IGA方法任务分配图

图4 第一组实验SVF方法任务分配图

图5所示为各组实验下两种方法的系统总吞吐量,由图可知,IGA算法相比SVF能明显提高系统内吞吐量,并且可以发现,从第四组实验开始,IGA算法吞吐量的增长幅度逐渐减少,这是因为系统内AGV数量已经可以满足当前任务的需求,再增加AGV数量对系统并不会有太大好处。而SVF的增长幅度并没有实质变化,说明在同等数量AGV下,IGA算法可以有效提升AGV的利用率。

图5 各组实验的系统总吞吐量

图6所示为3种算法的适应度值对比,虽然3种算法都可以得到相同的适应度值,但IGA明显比GA和BBA更加优化,更快得到最佳适应度值。

图6 最佳适应度值曲线图

4 结束语

本文基于多任务理论基础对AGV协同多任务分配进行了研究。AGV种类较多,一方面由于不同种AGV可执行的任务不同,因此要对不同种类AGV进行能力限制;另一方面是任务数量多、类型多,包括单AGV任务与多AGV协同执行任务。在理论基础上对其进行数学建模并进行多种类型的约束,提出了一种改进的遗传算法,仿真分析结果证明该算法可以有效提升系统的吞吐量,相较于传统遗传算法性能更优。