基于遗传算法的RGV调度优化模型

宫尚俊?贾慧?吴慧敏

在一个智能加工系统中，输送系统连接多个计算机数据机床和外部物料运送工具，其调度策略和工作效率对整个的智能加工过程至关重要。本文针对智能RGV的动态调度策略设计问题，通过分析RGV的工作条件以及作业流程，建立基于遗传算法的RGV动态调度优化模型，最后运用MATLAB软件编程，结合数据求出结果证明了模型的可操作性和算法的有效性，给出了具体的RGV的调度策略和系统的工作效率。

随着现代工业的快速发展，物流的自动化、智能化已是必然趋势，自动化立体仓库得到越来越多的应用。RGV（Rail Guided Vehicle）轨道式自动引导车能够结合各种高新技术于一身具有多种实用功能，被广泛地应用于物料加工处理系统当中，是实现可以感知、思维、推理、路径规划和决策的智能物流的中坚力量，可以有效的完成物料的运送、清理过程。RGV的动态调度问题很大程度决定了输送系统的运送效率。因此RGV动态调度问题一直是研究的热点，有很多学者在这方向上做出了自己的努力。刘永强采用遗传算法对自动化立体仓库进行建模，得到优化的调度多个RGV运送出入货任务方案，并运用仿真方法进行进一步研究；刘燚等针对扰动事件影响下的车间调度问题，综合考虑完工时间与交货期，运用模拟退火遗传算法，建立了作业车间动态调度模型；潘全科将双向调度方法嵌入到遗传算法中，结合神经网络对智能制造系统的多目标车间调度问题进行了研究；查申森等提出了一种基于RGV、AGV的柔性输送系统，有效地克服传统单一RGV输送系统轨道占用空间大、对场所适应性差等缺点。基于以上研究综述，结合直行轨道式自动化立体仓库智能加工需求，可知实现RGV穿梭车的合理调度、提高RGV系统的运行效率、研究并设计智能RGV系统的动态调度策略对促进智能加工行业高速发展具有深远的意义。

一、问题的分析

解决这类问题时，我们首先要了解RGV的工作条件以及作业流程，再设置一个算法调度RGV以实现在约束条件下处理最多生料，这个问题等价于设置一个算法确定一个稳定状态下的动态调度顺序使得在考虑一个稳定循环下所有的RGV移动距离的时间、RGV给每个CNC上下料的时间、RGV清洗熟料的时间之和最短。由于约束条件较多、较复杂而且经分析易得在一个稳定的循环周期内每个CNC都需要RGV给予上一次料，所以用一般的算法可能不能求出实际解，而遗传算法正好可以有效解决这个问题，它是从问题潜在的解集开始的，通过按照适者生存原理，将所有解与目标函数进行对比并排除掉相对远离目标的，最终会产生出越来越好的近似解。除此之外借助自然遗传学的遗传算子进行组合交叉和变异产生出新的种群，这种方法能够使种群进行优胜劣汰从而后生代种群比以前的更加适应环境。最后将最后一代种群中的最优个体经过解码，可以作为问题近似最优解即得出RGV的最优动态调度。

二、模型的假设

为方便解决具体问题，对文章作出以下假设：

（一）机械臂前端上方会一直能够保持生料的供应，清洗后的成料都能被传送带输出系统；

（二）CNC只有等待RGV上下料工作完全完成后才开始对生料进行加工处理，即RGV完成上下料作业后到机械臂将熟料放到清洗槽中的时间中CNC不对生料进行加工；

（三）RGV的初始上料过程与整个流程结尾回到初始位置时间与整个班次相比相对较少，为方便计算系统工作效率，假设这些时间为0。

三、模型的建立

遗传算法（Genetic Algorithms，简称GA）是一种基于生物的自然选择原理和基因遗传机理的搜索算法，通过模拟生物的遗传和进化过程，逐步筛选最终得到自己所想要目标的最优解。用这种算法建立动态调度模型有很多的优点，例如遗传算法能够从多个可行解开始搜索，比从单一可行解开始搜索的速度更快从而可以减少得到最优的结果的时间；遗传算法进行遗传操作时不需要设置太多的外部条件，只需要找到目标函数就行，非常适合像计算机数控机床这种比较复杂的系统；遗传算法的理论研究现在已经发展的比较成熟，针对很多的实际问题都有相应的理论和方法，因此用这种算法非常的方便，而且算法计算出来的结果可行性高。

遗传算法需要涉及五大要素：编码、初始群体的产生、适应度评估、遗传操作的设计和控制参数的设定。具体步驟如下：

（一）编码策略

在编码过程中本文使用十进制编码，用随机数列作为染色体，其中，；随机序列都与种群中的每一个个体相对应。

（二）初始种群

本文利用改良圈算法来获得一个比较不错的初始种群，即对于初始圈，，交换u与v之间的顺序，此时的新路径为：记，若，则用新的路径替代旧的路径，一直到不能替代为止。

（三）目标函数

目标函数为一个稳定周期RGV的给各个CNC上下料的时间最短

1.

（四）交叉操作

我们的交叉操作采用单点交叉，因为单点交叉在编辑程序的过程中较简单且能够有效的保证解的多样性。

（五）变异操作

变异能够实现群体的多样性，能够扩大寻找最优解的范围。具体操作如下，按照一定的变异率，对选定变异的个体，随机的选取3个整数，满足

（六）选择

采用确定性的选择策略，也就是说选择目标函数值最小的M个个体进化到下一代，这样可以保证父代的优良特性被保存下来。

为计算出具体结果定义稳定状态下的时间间隔矩阵Tij，

2.

为方便理解Tij的具体含义，文中列举了矩阵部分元素的具体表达形式。其中m1、m2、m3分别表示RGV移动1、2、3个单位所需时间；ti表示RGV为CNCi#一次上下料所需时间；tc表示完成一个物料的清洗作业所需时间。矩阵元素tij表示从CNCi#到CNCj#完成上下料并清洗过的时间。位置0表明位于初始位置即CNC1#和CNC2#正中间。因为RGV在完成一项作业任务后，才会判别执行下一个作业指令。如果没有接到其他的作业指令，则RGV就在原地等待直到下一个作业指令。又因为在初始上料过程中经计算经过不同的路径给所有CNC上料的总时长都远小于CNC加工物料时间，所以RGV还需要等待。因此经过分析易得为减少工作时间、提高工作效率，RGV的最终位置为回到原点，达成一个稳定的循环。在这里用位置9表示RGV回到末尾位置即初始位置。

最后将矩阵带入遗传算法求解的MATLAB程序中会求得一个稳定状态下的最优顺序，并能计算出RGV一个周期下的总调度时间。算出时间后，再计算RGV的工作效率。由于假设3，所以在计算系统工作效率时只需计算出一个稳定周期下的RGV工作效率就行，计算系统工作效率公式如公式3

3.

其中η为系统的作业效率，T0为RGV调度时间，T为系统工作的总时间。

四、模型的求解

将表1：智能加工系统作业参数的3组数据表中第一组数据带入并结合时间间隔矩阵的元素含义可得时间间隔矩阵，接着将所得的时间间隔矩阵带入遗传算法的MATLAB程序中即可得出RGV给CNC上料的顺序：2、4、3、6、5、8、7、1以及RGV一个调度周期耗时总时间为542秒，即经过542秒后RGV回到初始状态9开始进行第二次的循环。因为RGV总调度时间只需542秒，CNC加工完成一个一道工序的物料所需时间为560秒，最后用公式3计算系统作业的工作效率，得出结果为96.79%。

五、结论与讨论

本文讨论了RGV动态调度策略优化问题。根据分析RGV的工作条件以及作业流程得出一些基本的约束情况，建立了基于遗传算法的RGV动态调度优化模型，在模型的建立过程中构造了时间间隔距离矩阵将不可计算的最短时间长度问题转化为最短距离问题使模型显得更浅显易懂、RGV调度顺序结果更易计算出。最后结合2018高教社杯全国大学生数学建模竞赛B题第一种情况第1组数据求出稳定状态下RGV的调度顺序并计算出系统的作业效率来验证模型的实用性和算法的有效性。结果表明基于遗传算法的RGV动态调度模型具有实用性，算法能够求出RGV稳定状态下的调度顺序且该顺序下的系统工作效率为96.79%比较合理，因此该算法也具有有效性。（第一作者单位为安徽财经大学经济学院，第二作者单位为安徽财经大学国际经济贸易学院，第三作者单位为安徽财经大学会计学院）