基于混合优化算法的RGV动态调度策略方案

陈恩宏　刘陈帅　贾学勇

摘 要：本文以智能物料加工系统中轨道式自动引导车（RGV）的最优动态调度问题为研究背景，建立了基于动态规划—粒子群耦合算法的单工序调度模型，并结合自适应遗传算法得出多道工序的动态调度方案，通过软件仿真验证了模型的合理性和有效性 。对于一道工序的RGV动态调度问题，建立动态规划—粒子群算法模型。首先选取8小时内RGV移动的总距离最短作为目标函数，根据RGV同一时间只能完成一个任务，数控机床（CNC）在某一时间只能加工一个物料以及RGV执行任务的顺序等原则确定约束条件。然后利用动态规划算法以时间轴为划分原则，将整个调度过程转化为若干个子过程，各子过程之间状态函数相互关联，最后结合粒子群算法寻找各子过程的最优轨迹即可得出基于RGV移动总距离最短的单目标优化的动态调度策略。为了解决两道工序的RGV动态调度问题，本文首先建立自适应遗传模型，对多目标函数进行优化，并提出额外作业效率和修正系数的概念对模型进行完善；然后增加模型的约束条件来达到明确两道工序时间上的先后性的目的；采用自适应理论对目标函数的权重进行确定，来达到减少遗传算法迭代次数的目的；最后根据遗传算法的寻优过程来得出RGV具体的行走轨迹，进而得到效率较高的动态调度策略。

关键词：动态调度 动态规划—粒子群 自学习遗传算法

模拟仿真

1. 引言

简易的智能加工系统由数控机床（CNC）、轨道式自动引导车（RGV）、引导车直线轨道等其他附属设备组成，其中RGV是一种自动沿用轨道的自动运行，在轨道两侧传送带用于上料、下料，RGV可通过移動到数控机床（CNC）旁，使用引导车自身带有的机械手臂、两只机械手爪和物料清洗槽，完成上、下料和物料清洗。

物料的加工作业大致可分为两种情况，一是由一台CNC就可以完成，二是由两台CNC完成，且两台机器的刀具不同。

2.基于两道工序的RGV动态调度模型

RGV对CNC上料需求的选择若仅仅依靠就近原则，可能会造成多台CNC的空闲和RGV长时间停止等待任务的情况，这种简单的调度方式效率低，因此，基于两道工序加工物料的RGV需考虑多个目标函数。

2.1模型的准备

将GRV作业过程中任意时刻的状态进行量化，以便后续约束条件和目标函数的建立。根据表格中GRV系统作业参数，得出物料加工的第一、二道工序基本相等，所以将8个CNC平均分为两部分，1#、3#、5#、7#可完成物料加工的第一道工序，中，；表示第个物料在任一个CNC上开始加工的时刻，表示第个物料开始加工第二道工序的时刻，。

其中，约束条件（7）表示一个物料的第一道工序完成总成第二道之前，目标函数（8）表示RGV在工作时间8小时内执行次指令时移动总路程的最小值；系统作业效率，目标函数（12）表示RGV作业过程的最短总路径和最大作业效率。

2.2自学习遗传算法模型的建立

自学习遗传算法避免传统遗传算法局部搜索的不敏感，可解决多个目标函数的优化问题，算法中引入遗传算子和妥协解自学习，提高了遗传算法的局部收敛速度。

1.编码、变异和交叉遗传

遗传染色体的编码方式采用二进制编码方法，对一辆RGV工作状态和作业进度进行编码，组成染色体，具体编码为：；

直线往复式RGV进行作业时，实时自主变化的是作业任务点，随之变化的是RGV的移动路线，在遗传变异中，采用多点交叉法，交叉位置为RGV小车等待状态=0，交叉点数服从泊松分布：

（14）

2.自适应交叉、变异概率

等研究人员提出改变算法遗传变异中交叉概率和变异概率都不变的条件，提出遗传适应度自动进行改变和优化，其中交叉概率，变异概率计算公式为：

其中，为种群最大、最小交叉概率；为种群最大、最小变异概率； 为种群的最大适应值；为每代种群的平均适应值；为两个个体中较大的适应度值。

减少时，种群中个体的适应度高于平均适应值，较小时，进行遗传变异时，将被保留下来，否则将被淘汰。

3.自适应函数

由于轨道往复式小车的在不同时间的作业情况可能出现重复，引入知识专家种群模块，当出现相同的路径选择时直接调用库中之前生成的种群收敛性最优解，不仅提高迭代效率，在随机种群的不断生成中，更新知识专家库。妥协方法是通过不断训练，随着子代数的不断增加，染色体发生遗传和变异趋向稳定，最终得出与实际中与理想条件最接近的最优解。

总 结

动态规划—粒子群算法在优化实现上迭代计算比遗传算法容易，并且在优化的结果上相较于动态规划计算结果精度显著提高，该结合算法不易陷入局部最优，保证了全局优化结果的有效性，试用于大量难以全面研究的领域，例如航空航天领域、大型水库蓄水量管理等等，可其中的部分粒子划分为若干个阶段，以局部粒子的最优取向得出全局的发展趋势。

本文中定义的RGV的作业时间是除原地等待以外所有的有效时间，在确保全局路径在一定值的情况下，还需要借助效率目标函数进行最优趋向引导，自适应遗传算法可同时设立多个目标函数，求解各个目标函数在执行决策中的权重，能够准确的得出RGV动态调度策略。并且CNC出现故障对于RGV路径和作业时间的影响不同，通过公式得出理论修正系数也不同，多个目标函数与其不同的修正系数匹配得到实际RGV调度策略和系统作业效率。

参考文献

[1] 江唯，何非，童一飞，李东波. 基于混合算法的环形轨道RGV系统调度优化研究[J]. 计算机工程与应用，2016，52（22）：242-247.

[2] 王晓宁. 直线往复式轨道穿梭车避让策略仿真研究[D].北京邮电大学，2012.

[3] 吴孟达. 数学建模教程[M]. 高等教育出版社， 2011.

[4] 唐猛. 自动小车存取系统建模及调度优化研究[D].武汉大学，2015.

[5] 聂峰. 自动化立体仓库穿梭车系统控制方法与优化调度研究[D].太原理工大学，2009.