考虑充电的多 AGV 的作业车间调度探讨
（湖北省机电研究设计院，湖北 武汉 430000）
摘 要：本文针对 AGV 运输的作业车间调度问题特点，综合考虑工件调度、AGV 运输任务调度、AGV 充电约束以及 AGV 数量等因素，对考虑 AGV 充电的作业车间调度优化问题展开研究并设计求解算法，并进行仿真验证。
关键词：充电；AGV；作业车间调度
1 问题描述与模型
1.1 问题模式
某企业作业车间调度问题简单描述为：n 个工件在 m 台机器上同时并行进行加工，并有 K 台 AGV 把工件在机器之间进行工件运输，每个工件有 d 道不同的工序，d 不大于 m，每台工序只能在一台机器上进行加工。目前制造企业生产车间的 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 参数符号定义
1）M 表示设备，Ml 表示第 l 个设备，设备数量为 m；2）A 表示AGV，Ak 表示第 k 个 AGV，AGV 数量为 K；3）J 表示工件，Ji 表示第 i 个工件，工件数量为 n4）O 表示工序，Oij 表示第 i 个工件的第 j道工序，工件最大工序数 d5）A 表示 AGV，Ak-bat 表示第 k 个 AGV的电池实际电量 6）Ak-max 表示最大电量 7）Ak-able 表示 AGV 可用时刻 8）Ak-threshold 表示 AGV 电量阈值 9）Ak-pos 表示 AGV 当前位置 10）Ak-start 表示 AGV 开始运输时刻 11）Ak-end 表示 AGV 运输完成时刻 12）Ak-total 表示 AGV 每次任务总运行时间 13）Ak-power 表示 AGV 单位时间能耗 14）Ak-chargeRate 表示 AGV 充电速率 15）Ak-charge 表示充电时长 16）Mij 表示工件 i 工序 j 的加工设备 17）Tk-pos-mij 表示 AGV 从当前位置到 Mij 的时间 18）TijAk 工件 i 的 j工序用 AGVk 运输的时间 19）Sij 表示工件 i 工序 j 的加工开始时间，20）Cij 表示工件 i 工序 j 的完工时间，21）pij 表示工件 i 工序 j 的工艺加工时间。
1.3 优化模型
优化目标为工件最大完工时间最小化：
（1）
在考虑 AGV 充电的作业车间调度的约束有：
工件最后一道工序加工结束就是完工时间，工件工序的开始加工时间是受上一道工序加工时间和运输时间约束，工件工序完工时间受开始加工时间与加工工艺时间约束，AGV 开始运输时间受 AGV 可用时间、AGV 到上道工序加工设备的时间，以及工件上道工序完工时间的约束，AGV 运输完成时间，实际运输时间受 AGV 可用时间、AGV 当前位置、运输任务起止位置，以及上道工序完工时间约束，完成运输任务 AGV 总运输时间，AGV 实际运行时间和距离，AGV 消耗电量，AGV 充电时长约束。
2 改进遗传算法
求解含有多 AGV 的作业车间调度问题可以分解为两个子问题：工件在设备上的调度、运输任务 AGV 的分配问题。针对考虑充电的多AGV 车间调度的特点，设计如下的改进 GA 算法，其基本流程框架如图 1。
图 1 改进 GA 程序结构流程
针对两个子问题，采用工序和 AGV 两段染色体编码。考虑到 AGV运输问题，由于工件需要在原料库、设备和成品库之间进行运输，所以每个工件的运输任务比工序数多 1，为了两段编码方便统一，把成品库假设为一个虚拟设备，其加工时间为 0。工序编码采用整数编码，基因为工件编号，长度为总工序数+总工件数 n。AGV 编码采用整数编码，基因为 AGV 编号，该段染色体长度为总工序数+总工件数 n。
3 仿真测试与分析
3.1 算法有效性验证
为了验证算法的有效性，仿真程序采用 VC6++实现，初始种群数量为 200，交叉概率 0.8，变异率为 0.01，迭代 200，并采取保优策略，运行 10 次取运算结果的平均值作为参考值。
3.2 运输时间影响分析
简化情况下，不考虑其他约束，在 AGV 速度固定不变，运输时间指工件在设备间的移动的时间，与设备间的距离成正比关系。设备间运输时间相对工件工序工艺加工时间的比例是更准确的反应运输时间对对优化目标的影响。不失一般性，假设相邻设备距离为单位距离，选择单位距离的运输时间与单个工序平均加工时间的比值来进行分析其影响。在用例 FT06 中，工序工艺加工时间范围为 1 至 10，平均工艺加工时间为 5.7，我们测试单位距离运输时间在 1 到 8 之间对优化目标的影响。此时 AGV 数量为 6 和 AGV 电量为 100，即 AGV 数量和电量都足够完成所有运输任务。
3.3AGV 数量影响分析
在考虑采用 AGV 运输工件的车间优化中，AGV 作为运输的载体，是否能够及时把工件送达设备，成为影响完工时间的关键因素。AGV的数量的多少直接影响运输的任务分配，AGV 数量对优化目标有着直接明显的影响。最理想情况下，每一个工件都有一个 AGV 专职该工件的运输，这样 AGV 就完全不会成为运输的制约。针对 FT06 用例，工件工序的加工时间数值在 1 至 10 之间。单位运输时间为 1 且 AGV 电量充足不需要充电的情况下，研究 AGV 数量对完工时间的影响。
结束语
针对考虑多 AGV 充电的作业车间调度问题进行研究，建立了考虑充电的 AGV 运输工件的作业车间调度模型，并设计了集成工件加工机器分配和运输任务 AGV 分配的集成遗传编码方式，设计相应的改进遗传算法进行求解，最后分析了单位运输时间相对长短、AGV 数量、AGV电量（单次充电可用时间）对优化作业车间工件完工时间的影响，并进行了仿真测试和验证。在下一步的的工作中，针对运输时间相对时长、AGV 数量、AGV 电量及 AGV 充电站位置之间的相互影响，AGV轻载和重载对耗电量的影响，AGV 路径冲突，以及相关多目标优化进一步展开研究，同时再进一步改进求解算法的收敛性和寻优能力。
参考文献：
[1]张国辉，高亮，李培根，等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报，2019，45(07)：145-151.
[2]赵诗奎，方水良，顾新建.柔性车间调度的新型初始机制遗传算法[J].
浙江大学学报(工学版)，2019，47(06)：1022-1030.
