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

王涵

摘 要：本文针对智能RGV的动态调度问题，根据贪心算法和回溯遍历法在某种特殊情况下的动态调度模型和相应的求解算法。由于每个物料都只需一道工序而且可以在任意一台CNC上完成加工，为了计算出RGV的最优动态调度方案，需要使得一定时间内加工系统加工出的物料数量最多，即使得加工一定数量的物料所需时间最短。采用贪心算法和回溯遍历法，得到RGV的每一次工作指令都是局部最优解，即是使得完成当前各CNC的上料需求时间最短的调度方案。对每一步都采用局部最优解，在选择的贪心策略不会对以后的状态产生影响的条件下，即可得到全局最优解。

关键词：智能RGV；贪心算法；回溯遍历法；动态调度

引言

RGV，是有轨制导车辆（Rail Guided Vehicle）的英文缩写，又叫有轨穿梭小车，RGV小车可用于各类高密度储存方式的仓库，小车通道可设计任意长，可提高整个仓库储存量，并且在操作时无需叉车驶入巷道，使其安全性会更高。在利用叉车无需进入巷道的优势，配合小车在巷道中的快速运行，有效提高仓库的运行效率。本文是研究RGV在直线轨道上往返的动态调度问题，并且考虑了多种情况，如CNC加工的物料只有一道工序、CNC加工的物料有两道工序以及发生故障之后如何调度使得加工的物料最多等。

1模型准备

本文解决的问题是在一道工序物料加工作业，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成的情况下，在一定的时间T内最多可以加工多少物料。那么在考虑RGV动态规划的情况下，对于目标函数和约束条件的给出较为困难。因此，为简化模型，本文假设在生产第 个物件的情况下要在第i个阶段对熟料进行上下料操作，这时需要考虑每一次RGV移动的时间和其上下料的时间之和 。

首先，可能在某一时刻有多个CNC需要进行上下料，必须对这些CNC的上下料顺序进行排列，以达到Ti最少的目的。

其次，由于给奇数CNC上下料的时间与给偶数CNC上下料的时间不同，因此当与上述考虑上下料时间的和为最小时，即考虑局部最优的情况下，那么给定的T就是由局部最优的时间加上清洗熟料的时间、初始上料的时间以及VG可能等待的空闲时间之和。因此，在这种情况下，局部最优就可以代表的全局最优，实现RGV的动态规划。下面给出最优规划模型：

目标函数：min

约束条件：

2模型建立

由于模型中的約束条件所包含的情况较为复杂，为了求解出目标函数的最优解，采用贪心算法将对全局最优解的计算转化为对所求问题的各个子问题的局部最优解的寻找。贪心算法采用逐步逼近最优解的思想，在选择的贪心策略不会对以后的状态产生影响的条件下，做出当前状态下的局部最优策略，当RGV收到k台CNC的上料需求信号，要对满足这k台CNC上料需求的所有可能次序安排所花费的移动时间以及上下料时间进行比较，选取最少的一种次序安排作为该子问题的局部最优解。通过每一步的贪心选择，可得到整体的最优解，即加工完成数量n的物件所需的最短时间。

为了求出每个时刻的子问题的最优解，采用回溯遍历法和MATLAB软件得出使得RGV的移动时间及上下料时间之和最短的安排作为RGV对各CNC的上下料作业次序，即为RGV的动态调度方案。

3模型求解

根据表1中各组的作业参数，将其带入建立的模型中，可以计算得出加工物料CNC的编号的循环路径以及上下料的开始时间，结果如下表：

图1到图2表示的是三种情况下每一个CNC处的一个周期下的加工情况，纵坐标的每一个数字对应与第m个CNC，横坐标为时间，单位为秒。

结论

本文解决的问题是在一道工序物料加工作业，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成的情况下，在一定的时间T内最多可以加工多少物料，将其简化为求局部最优的问题，而这个局部最优的问题最后可以转化为全局最优，如果直接考虑全局最优的化会使模型十分复杂。

参考文献

[1] 王雷，蔡劲草 .基于可变重调度区间的柔性作业车间动态调度策略[J] .南京航空航天大学学报，2018，50（3）：397-403 .

[2] 吴云高.王万良 基于遗传算法的混合Flowshop.浙江工业大学