动态循环分类法解决RGV调度问题

青岛工程职业学院 邱勇进

对于一道工序的物料加工情况，我们首先根据RGV在各个CNC之间的移动时间，建立各CNC之间移动时间的图。对于两道工序的物料加工情况，针对工序一和工序二的配置比例及位置安排问题，我们仿照问题一提出了位置配比的原则，再针对不同的配置原则进行验证，从中选出8种位置安排。对于有潜在故障的一道工序的物料加工情况，考虑到每个故障情况是相互独立的，我们将所有错误依据是否影响循环周期分成两种。对于有潜在故障的两道工序的物料加工情况，选择使用类似问题二的方法计算出物件总量。在讨论故障时候，类似问题三，我们同样分类对是否影响周期分开进行讨论。

1 问题的提出

1.1 背景介绍

RGV，是有轨制导车辆（Rail Guided Vehicle）的英文缩写 ，又叫有轨穿梭小车， RGV小车可用于各类高密度储存方式的仓库，小车通道可设计任意长，可提高整个仓库储存量，并且在操作时无需叉车驶入巷道，使其安全性会更高。在利用叉车无需进入巷道的优势，配合小车在巷道中的快速运行，有效提高仓库的运行效率。

一个智能加工系统的示意图1，由8台计算机数控机床（Computer Number Controller，CNC）、1辆轨道式自动引导车（Rail Guide Vehicle，RGV）、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。它根据指令能自动控制移动方向和距离，并自带一个机械手臂、两只机械手爪和物料清洗槽，能够完成上下料及清洗物料等作业任务。

图1 智能加工系统示意图

1.2 问题重述

一个由8台数控机床和1个轨道式自动引导车的智能系统加工系统，针对如下几种情况：（1）每个物件在每台CNC上加工一次；（2）每个物件在不同两件CNC上先后加工两次；（3）CNC在加工过程中出现故障，故障时间介于10～20min。请建立相应的RGV动态调度模型和相应的求解算法，并利用表中系统作业参数的三组数据检验模型的实用性和算法的有效性。给出RGV的调度策略和系统的作业效率，并将具体的结果填入附件的表格中。

2 问题分析

2.1 情况一的分析

问题整体分为两个阶段：第一个阶段为第一次上料，此时RGV可使用功能有且只有为CNC上料和移动。第二个阶段为第二次及以后，RGV利用旋转将上下料同时进行。在上下料过程完成后，RGV会对物件进行清洗并将其放在传送带上。这样，一个物料的加工完成。在第一阶段，我们有如下问题：（1）是否有必要在第一阶段为所有CNC上料；（2）是否会出现循环工作情况；（3）是否有必要在循环阶段让所有CNC保持工作。

2.2 情况二的分析

问题二要求我们针对需要两道工序加工的物料，配置CNC和RGV轨迹，保证8h内产出尽可能多的物件。我们将其分为两大部分：（1）确定第一道工序和第二道工序的CNC配比；（2）确定RGV最佳移动轨迹。

2.3 情况一的故障问题分析

故障的CNC分布符合b（0.01，m），m为该CNC的启动次数。则每一个CNC工作的概率为0.01。因为每一次CNC工作都可能出现故障，故应把单个CNC独立出来进行讨论。而有的CNC错误出现不会改变RGV运行轨迹，只是单纯地浪费时间少产出了1个物件，这里需要着重讨论的是会改变RGV运动轨迹的错误。

2.4 情况二的故障问题分析

类比问题二和问题三来解决问题四。只不过相比于问题三，问题四中的情况更为复杂，需要就不同工序发成错误再进行一次讨论。

3 模型的建立与求解

3.1 模型建立

总体示意图如图2所示。

图2 流程示意图

局部循环示意图如图3所示。

图3 循环示意图

3.2 初步模型架构

初步模型参考贪心算法，考虑局部最优解和生产过程中生成的循环情况，我们在响应完成工序2加工的CNC时需要考虑以下三原则：（1）需要同时存在完成工序1的CNC，否则等待至完成工序1的CNC出现；（2）优先选择距离最近的完成工序1的CNC；（3）若存在同样近的完成工序1的CNC，优先使用编号为奇数的CNC。

通过此种原则，我们的每一步操作均为该操作的最优解。以此为依据我们提出了一种递推模式的贪心算法。

我们采用时间轴的思想，采用时间为单位推进，判断各个工作台和RGV的状态，RGV的动作会造成时间轴的变动，进而产生各种需要判断处理的事件。通过提出的三原则，我们即可得到最优解，累加生成的成品物料个数。当时间轴推动到八个小时时，终止程序，我们就得到了最终产生的成品物料个数。

3.3 模型重建结果

通过使用上面模型编程计算，我们通过代入第一组数据发现程序输出的数值并不合理，这是由于时间轴推动会造成时间的冗余，我们处理数据的即时化效果并不好。因此我们转而寻找另外的编程思路。如图4所示。

图4 问题二最终流程图

4 模型评价

4.1 模型的优点

假设的合理性：在查阅相关物理、数学模型文献的基础上做出了一系列科学的假设，抓大放小，有的放矢，忽略了对结果影响较小的因素，从而大大简化了模型和算法，同时取得了很好的建模效果。

建模的科学性：模型建立的理论知识基于动态规划、最小路程、遗传算法等多门交叉学科，就建模的科学论证、知识储备上，本模型以小窥大、由浅到深的对相关知识进行联结整理。

建模的可推广性：本模型基于1个RGV在8个CNC的移动问题，显然可以拓展到n个CNC工作的问题。

4.2 模型的缺点

误差的必然存在性：考虑到存在实际产品安装匹配、操作使用以及模型的转换取舍中，必然存在误差，模型就误差的减少上提出循环优化。但就误差取舍的选择问题上，还仍有参数改进的空间。

算法的适用性：本文模型中适用于RGV数量为1的工作问题，当RGV数量增加后，需要考虑碰撞问题。

算法的准确性：在问题四中，我们因计算过于庞大，选择忽略了第一道工序中周期改变的情况，这样在极端情况下（等待时间远远大于加工时间）可能出现误差。