基于贪心算法的RGV动态调度研究

姜嘉沁　吴思琪　陈天祺

摘 要：本文主要研究智能 RGV 的动态调度策略的问题，针对一道工序情况下的 RGV 动态调度进行了分析。首先，利用绘制时间坐标轴的方式，清晰刻画每个时刻 RGV 和 CNC 的工作状态，找出变量之间的相互关系;其次利用该函数关系，采用贪心算法，应用 MATLAB软件将已知数据代入模型进行检验。最后利用数据检验结果可知，严格按照系统流程进行操作时，该调度模式已经达到较为高效的状态。

关键词：RGV 动态调度;贪心算法;时间坐标轴

引言

随着我国科学技术的发展，现代化物流正在不断发展和壮大，居民对高效的物流系统的要求越来越高，相继而来发展的就是自动化立体仓库。由于自动化物流系统的高速发展，传统物流系统存在的弊端就暴露出来，RGV 也就应运而生，它无需耗费大量人力，大大提高了工作效率。

1. 模型建立

由于 RGV 的变化情况繁琐复杂但存在一定的规律性，故选择采取绘制如下

时间轴的方法，较为清晰地分析出各个变量之间的相关关系，其中，CNC1#～8#表示 CNC 上料时间。

上图中各個点表示 RGV 给 CNC1#～8#上料对应的时间，根据上述的示意图推导出如下关系：

（1）假设当 RGV 开始为 CNC1#进行上料作业为 0 时刻，则刨去初始特殊情况，接下来每台 CNC 开始上料时刻随着周期的变化存在一定的规律特征，故可根据之间的相关关系列出 8 台 CNC 开始上料的时间函数式如下：

（2）根据上述时间示意图，与第一次 CNC1#加工产生熟料相比较，每经过tc+t3时间，CNC1#会生成一单位熟料，而其余 7 台 CNC 的产量和 CNC1#的关系只存在两种状态，一种等于 x1，另一种等于 x1-1，故 CNC1#加工生产量可表示为：

2. 求解算法

贪心算法是采用逐步求解最优解的方法，它是指在问题求解的过程中，不考虑整体最优情况，而是采取每步最优策略，得到在当前阶段下的局部最优解。上述模型的建立即是建立在贪心算法的基础上，每一个阶段智能选择最优路径，在本模型中，RGV 则是严格按照顺序依次对 CNC 进行作业。

对于一道工序的物料加工情况分析，RGV的动态调动运行模式为按照其接收信号的顺序对相应的 CNC 进行上下物料作业和熟料的清洗工作。此时，我们假设固定轨道上有四台 RGV 智能车，当系统启动时，四台智能车将同时运作，分别负责其相邻两台CNC 的上下物料及清洗工作。

由于在每两台的 CNC 设备之间都有一台 RGV 单独负责其相关的加工相关作业，故而此时的产出量必然为一道工序加工作业下的最大物料产量。运用绘制时间轴的方式分析后可得每一台 CNC 的加工产量满足以下关系式：

在前文的求解过程之中已经求得 x1的关系式，故而选取 x1作为检验模型是否已经达到最优的代表量。有如下关系：

故而可看出此模型已经达到最优化。

结论：

通过本文研究发现 RGV 在运行过程中会对首先发出信号的 CNC 进行装配，因为这一点所以 RGV 会产生忽略近处 CNC ，而跑去远处 CNC 进行加工的情况，所以本文采取最小路径、就近原则等条件对 RGV 的调度进行优化，达到产出最大化的目的。

参考文献：

[1]M， H， AlSUWANEI. 算法设计技巧与分析[M]. 北京：电子工业出版社， 2004.

[2]陈敏莹. 基于动态规划的微弱目标检测前跟踪算法研究[D]. 西安：西安电子科技大学， 2013.