基于现代优化算法对RGV动态调度问题的研究

王晨旭 漆映彤 盛玮桐

摘 要：研究轨道式自动引导车（RGV）的动态调度问题对自动化仓库领域以及物流系统具有重要的意义。本文重点考虑了两道工序的物料加工作业情况，基于现代优化算法建立了动态调度模型，给出了最优的调度方案。针对两道工序的物料加工作业情况，本文以基于现代优化算法中的遗传算法对其进行求解，并且在编码过程中摒弃了常用的一维编码，进行了二重结构编码，接着再结合数据进行了模型实用性和算法有效性的检验，得到此种情况下三组数据产出的成品个数分别为159，161，165，系统作业效率较高，结论为该模型较为合理。

关键词：遗传算法;RGV;动态调度

引言

智能加工系统是通过充分利用各种机械，运输设备，计算机系统和综合作业协调等技术手段，更精准，高效的完成加工物流的相关作业和内容。轨道自动导引车RGV拥有价格低廉，灵活和方便的特点，它能方便地与各种数控机床，机器人等加工设备实现连接，进行作业，提高工作效率，因此被广泛应用于智能加工系统。在智能加工系统的运输系统中，轨道式自动引导车RGV的效率是瓶颈，因此RGV的动态调度是关键。

1. 模型准备

RGV是一種无人驾驶、能在固定轨道上自由运行的智能车。它根据指令能自动控制移动方向和距离，并自带一个机械手臂、两只机械手爪和物料清洗槽，能够完成上下料及清洗物料等作业任务。图1为一个示意图，它表示一个智能加工系统，且这个加工系统由8台计算机数控机床、1辆轨道式自动引导车、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。

根据经验，无论是几台CNC的协同运作，对其进行调度的核心是用时最短，也就是效率最高，还可以理解为走的路径最短。因此此种情况便可以理解成存在一些约束条件的情况下，将一款产品从一个地方运输到另一个地方，而目标函数则可以看成所有的运送过程中最晚完成运送的时间。然后再用遗传算法对此问题就行求解，最后将数据带进模型进行检验，并求得此时的最优调度策略以及系统的作业效率。

2 .RGV动态调度模型建立及求解

遗传算法解决的关键步骤便是编码，编码不仅决定了个体基因的排列方式，决定了GA搜索的复杂程度和困难程度，也决定了最终求解的精度。

本文只考虑含有一个RGV小车的情况，由于两道工序中的协作任务是成对出现的，常规的一维编码（二进制编码）便难以解决此问题，因此在这里可以使用二重编码。如下所示：

即可以将1和3号CNC进行搭配，2和4号CNC进行搭配，6和7号CNC进行搭配，5和8号CNC进行搭配。

Step1：产生初始化的种群。

群体的初始化值一般随机生成，初始值最好可以在解空间中均匀采样;而对于非二进制的编码程序还必须要思考所产生的染色体是否在可行域内。

Step2：个体的目标函数和适应度值的计算：目标函数为运送完一组出入货任务所用的总时间。

Step3：选择、交叉、变异。

首先选择要用的算子以及选择操作。常用的个体选择概率的方法有按比例的适应度分配以及基于排序的适应度分配。

按比例的适应度分配也可称为蒙特卡洛算法，它通过利用各个个体适应度的概率决定它后代遗留的可能性。若某个体为p，它的适应度为fp ，那么被选中的几率为：

显然，若个体的选择概率较大，则能够被更多次的选中，而它的遗传因子也将不断在种群中扩大。

但是在基于排序的适应度分配中，适应度仅仅取决于一个个体在一个种群中的地位，并非实际目标值。

其次，进行交叉操作。对于常用的二进制编码，我们可以使用均匀交叉，单点交叉以及多点交叉等方法。

最后，进行变异操作。常用的变异操作有二进制变异法、实值变异法。

对于上述模型本文采用matlab遗传算法工具箱进行计算。再将相关数据代入模型进行检验，得到三组数据下分别产出的成品个数为159，161，165。得出结论为该模型实用性较强，算法较为有效。

结论：

与传统的优化算法不一样，本文的算法是基于现代优化算法而来的，这种启发式算法可以大大节省运算的时间，并且可以将模型进行简化，相比于一般的规划类问题较为简便。遗传算法因其具有良好的全局搜索能力，可以快速地将将空间中的全体解搜索出，不会陷入局部出现死循环，且其使用概率机制进行迭代，具有随机性，结论更加客观可靠。

参考文献：

[1]张剑秋.基于马尔科夫排队模型的流水车间调度问题研究[D].兰州理工大学，2017.

[2]司守奎，张兆亮.数学建模算法与应用[M].北京：国防工业出版社，2017.

[3]余有明，刘玉树，阎光伟.遗传算法的编码理论与应用[J].计算机工程与应用，2006（03）：86-89.