基于遗传算法下智能RGV动态调度策略

刘敏敏丁宁何延崔辉辉

摘要：本文用建立数学模型的方法对RGV的调动策略进行最优化的讨论，结合题目要求，运用遗传算法与粒子群排队论等方法对问题进行求解。一般RGV的联合调度算法，系统的效率主要取决于调度、路径、规划和RGV配置数量。本系统路径和RGV数量已确定，因此主要从调度和规划两方面来研究RGV的智能调度系统。

关键词：遗传算法；RGV；动态调度；策略

1概述

本系统路径和RGV数量已确定，因此主要从调度和规划两方面来研究RGV的智能调度系统。针对问题一，给出一般RGV动态调度模型和相应求解算法。先对发车时间和一次的搬运量建模，再对消耗量进行建模，设立现边缓存中的物料存储量联合，最后设立约束条件制定物料的搬运方案求得结果为365。针对问题二，分两种情形建模分析。CNC未发生故障情形时，采用自适应遗传算法（AGA），此时CNC变成两道工序，构造免疫克隆算法（ImmuneCloneAlgorithm）有效解决装配线准时配送问题，再结合自适应遗传算法建立模型求解。利用智能加工系统作业参数的3组数据分别检验模型的实用性和数据的有效性，先生成种群得出变异率再进行拟合、变异，得出结果。CNC发生故障情形时，对一般模型加入控制条件，采用混合遗传算法将规则调度和GA算法相结合，优化初始种群质量，促使算法尽快收敛得到较好计算结果。论文所建立各模型之间联系紧密，且理论性强，覆盖面广，能体现真实情况，也保证了一定的可靠性，对物料存取，搬运都具有一定的参考价值。

2RGV动态调度建模分析与求解

智能加工系统如图1所示，其中，直线轨道式导引小车系统包括RGV直线轨道、出入货站台和出入货传送带。

当CNC需要投料时向RGV发出信号，RGV进行上料，CNC进行加工，但是有可能多台CNC同时发出信号，由RGV自动为CNC判别上料顺序，即

（1）当RGV有运送任务时，确定RGV运送的任务；

（2）在确定RGV的运送任务后，若RGV的任务多于一个，这些任务运送顺序的安排由RGV系统选用节拍时间作为基本时间单位。

假设生产线上不存在物料不足的情况，每补充一次货物都会更换一个线边库；小车的运载量不得超过工位的装载能力（Gs），物料的线边库存量不可超越缓冲能力（Vs）；物料的搬运资本与工位的工作时长（αs）成正比例，系数为β，原料库藏成本与其在装配线线边缓存中的停留时长成正比，系数为ds；各工位所需物料依据车型的准配依次装车进行配送；各工位装配作业开始时，线边缓存立刻消耗一单位线边库存用于生产线的装配作业。

当多个CNC需要上料时候，工位完成i次搬运后，工位s的线边物料到达量为搬运成本为CD（Λ）搬运方案Λ、Λ′满足：，对有等式恒成立且物料在缓存中耗费的库存成本CI（Λ）当CD（A）的值加上CI（A）的值最小时候RGV的路径最短为本模型的最终解，综合上述数据可以计算出最优解的值为365。

3CNC机器加工时间排序方法检验

若只考虑两台CNC机器加工时间排序问题时，假设有n个物料需要在CNC机器A和CNC机器B上加工，每个物料都必须经过先A后在经过B两道加工工序。以Ai、Bi分别表示工件i在A、B加工时间。安排两CNC机器上各物料的加工顺序，使在CNC机器A上加工第一个物料开始到在CNC机器B上将组后一个物料加工完为止，所用的加工总时间最少。当加工顺序定好之后，物料在A上加工时没有等待时间，而在B上经常需要等待。因此最优方案只有尽可能的减少在B上的等待时间，才能使总加工时间减少。相关符号说明如下：

X为CNC机器A上待加工的按按顺序排列的物料集合；

x表示不属于X的在A上最后加工完的工件；

T为A上加工完x那一刻到的时刻算起到B上加工结束x所需时间。

（X，t）为CNC机器A和机器B在作业过程中的变量，则X包含有s个物料时，过程有s段；

F（X，t）表示由（X，t）开始，对未加工物料采取最优加工顺序后，对未加工的工件采取最优加工顺序后，将X中所有物料加工完所需时间

F（X，t，i）表示由（X，t）开始，在A上添加物料i，然后再对以后的加工物料采取最后顺序后，把X中的物料全部加工完所需时间；

F（X，t，j）表示由（X，t）开始，在A上相继添加i与j之后，对以后的加工物料采取最后顺序后，把X中的物料全部加工完所需时间；

依据上述分析可知：

在M中找出最小元素，如果在上，则排在最前面；若在下，排在最后。将已经有位置的列从M中划掉，对余下任务重复按本步骤进行，如此直到把所有的工件都排完为止。

根据经验性数据，数值的选择将会直接影响最终结果的好坏与否，且RGV调度是具有即时性特色，固定数值不利于模型的求解。利用自适应的交叉变异参数的自适应遗传算法，当个别差别大时可以自适应缩小能让优秀的个体充分发挥，也能给差的进化机会。当他们差别小的时候也能增大差距，有利于种群的进化。

在实际中，任务的发出具有间接性特点，因此对调度的计算也具有时间性要求特色。基于此，利用现代智能算法与规则调度算法相结合的方式，提出比较合理的基于规则的混合算法。

4结论

规则调度算法相对比较简单，可以在比较短的时间内得到比较有效的合理调度方案。然而，该法调度规则过于片面，其最终方案会伴随着车间规模的扩大，其有效度与合理度随之降低。而自适应遗传算法相比传统算法，采用自适应概率计算公式计算交叉变异算子，可以防止片面化求解。当然，初始种群质量影响模型较大，很难做到全部最优解。因此，采用规则的混合遗传算法，即将规则调度和GA算法相结合，可有效得到一个比较合理的结果。

5参考文献

[1]宋来忠，王志明.数学建模与实验[M].北京：科学出版社，2005.

[2]王正东.数学软件与数学实验[M].北京：科学出版社，2010.

[3]赵静，但琦.数学建模与数学实验[M].北京：高等教育出版社，2008.

[4]楼顺天，姚若玉，沈俊霞.MATLAB7.x程序设计语言[M].西安：西安电子科技大学出版社，2008.

[5]费浦生，羿旭明.数学建模及其基础知识详解[M].湖北：武汉大学出版社，2006.5.

[6]《运筹学》编写组.运筹学（修订版）.北京：清华大学出版社，1990.

[7]胡守信，李柏年.基于matlab的数学实验[M].北京:科学出版社，2004年第1版.

[8]杨桂元，黄己立.数学建模[M].合肥：中国科学技术大学出版社，2008年8月第1版.

[9]龙锋.基于自适应遗传算法的W公司仓库货位分配与优化研究[D].广州：华南理工大学，2015.

[10]王军强，郭银洲，崔富东等.基于多样性增强的自适应遗传算法的开放式车间调度优化[J].计算机集成制造系统，2014，20(10):2479-2493.

[11]邹敢.柔性搬运系统的智能作业调度方法研究[D].昆明：昆明理工大学，2014.

[12]聂峰，程珩.多功能RGV优化调度研究[J].物流技术，2008，27(10):251-253.