RGV动态调度策略研究

方卫杰，赖威鹏，耿昆仑，赵凯芳

（1.天津大学仁爱学院信息工程系，天津 301636；2.天津大学仁爱学院数学教学部，天津 301636）

0 引言

随着信息技术的快速崛起，自动化控制、机电一体化和机械智能化的发展，工业上出现了越来越多的自动化加工的车间与工厂。RGV（Rail Guide Vehicle）轨道式自动引导车被广泛应用于物流运输和物料加工。由于实际生产的时候是一辆RGV对多个CNC（Computer Number Controller），合理的安排RGV的调度策略是提高生产效率的重要因素。

1 基于贪心算法建模思想

考虑到 RGV的调度与物料的加工是动态过程，本文采用贪心算法。 贪心算法（又称贪婪算法）是指，在对问题求解时，总是作出在当前是最好的选择。基本思想是：每次从系统每一步结束处出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，选取其应该满足局部优化的条件。

针对本问题，RGV每走一步之前会先向下搜索三层，找出这三步总用时最短的一条路线，然后RGV会选择该路线的第一步作为局部最优路线。贪心选择图示如下：

C - CNC的编号

T - RGV移动所需的时间

F - 层数

图1 贪婪算法选择示意图

2 双工序无故障调度模型

将加工第一道工序的CNC称为A类CNC，而加工第二道工序的CNC称为B类CNC。

2.1 两道工序CNC的数量和分布位置模型

针对有两道加工工序的情况，确定CNC的排布位置，使得系统加工物料的效率更高.通过两道工序加工所需的时间Tf，Ts来确定分别加工两道工序的CNC的台数N1，N2。

两道工序CNC的位置分布关系到RGV总体的调度效率，即RGV从A类CNC处到B类CNC处所需的时间尽可能的少。

则可建立如下模型：

2.2 双工序无故障调度模型

物料第一道工序加工完成后，无需清洗，直接进行第二道工序；在初始状态时，无论加工两道工序CNC的比例是多少，RGV总是先为所有的A类CNC上料；在为B类CNC上下料前，必须先为A类CNC下料，并携带已完成第一道工序的物料，而后对B类CNC进行上下料，所以无需专门为A类CNC上下料，只需研究第二道工序时RGV的调度。

取料阶段RGV所需时间：

上料阶段RGV所需时间

则对B类CNC进行一次上下料处理所需总时间为：

综上所述可得动态规划模型为：

2.3 模型求解

（1）由两道工序CNC的数量和分布位置模型，得到 A、B类CNC分布.下图为一二道工序所用时间不同比例下的CNC的分配案示意图：

图2 A、B类CNC分布

（2）调度模型求解：

算法步骤：

Step2：因为B类CNC需要A类CNC提供已完成第一道工序的物料，所以RGV会先给所有的A类CNC上好料再给B类CNC上料，下图为CNC在各种比例下，工作开始时A类CNC上的顺序：

图3 初始RGV移动方式

Step3：遍历RGV下一步所有可能的走法，并找出其中耗时最少的哪条路线。

Step4：循环往复步骤三，直到加工总时间超过一个工时退出循环。

Step5：最后输出算法结果。

（3）将结果绘制成甘特图，由此可得RGV的调度策略，这里只给出RGV前3000秒在三组不同情况下加工时间及工序的甘特图。横轴为时间刻度，纵轴为CNC的编号（由上到下依次为1-8）。图4为RGV前3000秒在三组不同情况下给CNC做上下料处理的时间与工序的甘特图。

图4

3 实物模型

图5 智能加工系统模型

图6 树派编程环境