智能RGV的动态调度策略

杜一婷，冯梦若，李佳军，方 睿

（汕头大学数学系，广东 汕头 515063）

0 引 言

智能轨道式自动引导车（Rail Guide Vehicle，RGV）是现代自动化生产车间中的重要工具，其可连接不同数量，不同种类的计算机数控机床（Computer Number Controller，CNC）.随着我国自动化行业的发展，智能RGV 逐渐应用到大物流的输送、调度问题.同时，智能加工系统中存在机器故障等情况，会对RGV 动态调度提出挑战.为提高物流系统效率，需要设置合理的“智能RGV 的动态调度策略”.本文根据2018 年全国大学生数学建模竞赛B 题给定的智能加工系统作业情况以及作业参数，尝试解决以下两项任务：

任务1：对一般问题进行研究，给出RGV 动态调度模型和相应的求解算法；

任务2：利用表1 中系统作业参数的3 组数据分别检验模型的实用性和算法的有效性，给出RGV 的调度策略和系统的作业效率，并将具体的结果填入附件.

其中智能加工系统作业3 种具体情况为：

（1）一道工序的物料加工作业情况，每台CNC 安装同样的刀具，物料可以在任一台CNC 上加工完成；

（2）两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC 依次加工完成；

（3）CNC 在加工过程中可能发生故障的情况，人工处理，且故障的发生概率约为1%，每次故障排除时间介于10-20 min 之间，故障排除后即刻加入作业序列，未完成的物料报废.分别考虑一、二两道工序的物料加工作业情况.

注：题目、参数和附件可到全国大学生数学建模竞赛官方网站http：//www.mcm.edu.cn 下载

1 模型的假设

为了方便研究，在不改变题目要求的前提下，我们对模型作以下假设：

（1）假设每台RGV 每次清洗作业和上下料作业的时间相同；

（2）每台CNC 的加工效率相同且保持稳定；

（3）假设RGV 先将生料放到CNC，完成上料工作后，再进行熟料的清洗工作；

（4）假设上下料传送带的连动或独立运动对模型无影响；

（5）假设智能加工系统中的所有传感器反应时间很短，可忽略不计.

2 任务1的模型建立与求解

2.1 任务1的分析

首先需要考虑一道工序的物料加工作业，且CNC 没有故障的情况，设该情况为情况1.

2.1.1 情况1 分析

在此情况中，每个物料只有一道加工工序，所以每台CNC 安装同样的刀具.此时，物料可以在任意一台CNC 上加工完成，即8 个CNC 是通用并行机，可视为是性质相同的8 个固定点.每两个不同点之间可以通过RGV 连接，为了提高调度效率，RGV 需要寻找最短路径，所以该问题为最短路问题.

RGV 的路径取决于RGV 和CNC 的状态和位置，是动态的.所以可以用RGV 动态路径的旅行时间代表其路径长度，利用动态规划的思想进行路径选择的决策，建立基于动态路径的调度模型，并且利用MATLAB 编写对应程序.

再者，我们需要考虑两道工序的物料加工作业，此时，若仍不考虑CNC 出现故障的情况，设该情况对应情况2.若考虑CNC 在加工过程中可能发生故障，设该情况对应情况3.

2.1.2 情况2，3 分析

在情况2、3 中，每个物料需要两道加工工序，所以不同CNC 可能安装不同刀具.基于情况1 的分析，需要在动态规划中加入与工序相关的约束条件，并且将其具体体现在算法中.此时的物料调度步骤增多，不仅需要考虑RGV、CNC 的状态以及位置，而且需考虑安装两种刀片的CNC 各有多少个，以及不同类型的CNC 的排布.通过分析表1 中的数据可得，RGV 的运行时间相对CNC 加工时间很短，所以不同类型CNC 的数量对系统效率的影响要远大于CNC 分布的影响.

2.2 模型建立

2.2.1 基于动态路径的调度模型

基于情况1 的分析，RGV 的旅行路径是动态的，为寻找最短路径，需建立基于动态路径的调度模式.

2.2.1.1 固定起点的最短路问题

应用到任务问题中，RGV 在固定8 个CNC 任务点之间寻找运动的最短路径，且此过程在8 h 班次中，不断重复迭代更新最短路径，具有周期性.

RGV 在智能加工系统开始工作后，能在直线轨道上移动或停止等待；以两台相邻CNC 的距离为1 个单位，RGV 可连续移动1 个单位、2 个单位和3 个单位.RGV 给两台CNC 放置生料的顺序类型，可分为从奇数侧到偶数侧、奇数侧到奇数侧及偶数侧到偶数侧，如图1 所示.

图1 RGV 工作路径的类型及物料需求点CNC

一般情况下，物料输入智能加工系统的状态服从均匀分布.设系统停止工作时，得到成料量为n，单位为一台CNC 加工的量，对应加工物料的序号.在系统工作的过程中，RGV 的运输要满足8 台CNC 的上料和下料的需求，因此，在存在服务质量和可行性约束且消耗最少的能量的情况下，RGV 的工作量为2n.

定义 P 为 RGV 上料，D 为 RGV 下料，其中 P＝{1，2，…，n}，D＝{n＋1，n＋2，…，2n}.当RGV 放置第i（1≤i≤n）个物料时，它与RGV 给CNC 进行第i＋n 个下料工作相关联.此时RGV 的路径问题，由一个有向的图G＝（V，E）描述，V 中的顶点i 表示RGV 上料或下料工作的需求点，其中e＝（i，j）表示两个工作之间的可能处理顺序，即工作j 是否可以在工作i 之后立即处理.为保证系统作业的开始和结束，还增加了两个虚拟的工作任务，分别为 0 和 2n＋1，表示 RGV 的起始位置和结束位置.因此定义 V′＝P∪D＝{1，2，…，2n}，则V＝{0}∪V′∪{2n＋1}，对应的i，j∈V，k＝1，2，…，2n＋1.

2.2.1.2 RGV 判断过程

在假设条件的基础下，RGV 动态调度需要在RGV 对某些时间状态做出判断后开始，判断出到某台CNC 进行工作的过程总时间最小，则到相应CNC 进行作业.RGV 判断过程涉及的时间变量如表1 所示.

表1 RGV 判断时间段

RGV 判断后，要得到移动到哪一台CNC 的时间最短，即最短路径，然后再进行调度作业，不断针对路径进行循环判断，直到智能加工系统工作时间结束.实际过程中可能存在的一种情况，如图2 所示，即CNC4#的加工完成时间比CNC6#长，RGV 移动到CNC4#，但在去CNC4#的过程中，经过CNC6#之前，若此时CNC6#也给RGV 发出需求讯号.

图2 判断的特殊情况

那么若此时依然移动到CNC4#，将会浪费时间资源，减少成料产出.所以RGV先决定给CNC6#作业，此外RGV 给不同编号的CNC 上下料的时间也不同，也会产生影响.因此，当设定RGV 决策时，要判断三者之和的最小值，即

2.2.1.3 分治法确定成料产出量及上下料作业时间点

动态规划基本上是一种完全枚举算法，尝试通过分治法以使需要进行的计算量最小化.这种方法在找到最终答案之前解决了一系列的子问题，并确定每一个子问题的最优解以及每个子问题对于最终目标问题的贡献.在每一次迭代过程中，其所确定的子问题最优解均大于以往求解的子问题的解，从而为了求解当前的子问题，需使用求解以往所有子问题获得的信息.

根据文献[1]的研究结果，我们将每个迭代过程的最短时间分为5 个时间段，综合判断后得到一个迭代过程的最短时间，再迭代n 次，得到所用时间最短，成料产出最大的作业方案.

（1）初始状态：T1＝0

（2）迭代方程：minTi＝Σ（Td＋Tl＋Tz）min＋Tj＋Tq，i＝1，2，…，n.

（3）最优值方程：ΣTi≤8×60×60.

系统的初始状态：RGV 位于CNC1#、2#前，不论先为哪台投放物料，初始时间总为0；每一次迭代过后，RGV 得到最短时间minTi，迭代n 次；由于系统一个班次的工作时间为8 h，而我们在建模过程中所用的时间单位为s，所以有最优值方程.

2.2.1.4 确定RGV 为CNC 加工的方向顺序

根据文献[2]的研究结果，我们可以结合有向图G，给出设置RGV 路径移动方向顺序的模型.最优RGV 路径问题的求解过程可以表述为下列公式中定义的混合整数规划.此部分建立了一个RGV 最优路径问题的数学模型.

主要参数和符号被定义如下：

P 是任务集，P＝{1，2，…，n}，n≤8；

D 是任务集，D＝{n＋1，n＋2，…，2n}；

V′＝P∪D，V＝{0}∪V′∪{2n＋1}；

ti表示 RGV 到上下料需求点的旅行时间，i∈V{2n＋1}，t0＝0；

Sij表示在上下料点i，j 之间的RGV 行驶距离；

Tij是在上下料点i，j 之间的RGV 行驶时间；

xij表示上下料需求i 是否在j 之前处理0，1 变量；

bi表示第i 个任务的初始时间；

wi表示RGV 完成某台CNC 上料或下料后的负载物料单位，i∈P，w0＝0.

约束条件：

目标函数表示RGV 的总时间成本最小值，也是wi和xij的双线性函数，RGV 最优路径（i，j）∈E 与一个耗能成本cij（wij）及一段行驶时间Tij相关联.RGV 负载的物料最多为3 个种类，即RGV 抓取的未加工的生料、从CNC 中取回的已加工的熟料和清洗后的成料.

当RGV 判断出在当前位置沿路径（i，j）移动到下一个CNC 进行作业的最优路径时，我们可以利用牛顿法则，求得总时间成本cij（wij），即

经过约束条件的筛选计算，得出一次循环中耗时耗能最小的路径.

2.3 RGV实时路径仿真算法

对于智能RGV 动态调度问题.存在许多智能高级算法，例如遗传算法和模拟退火算法.但是对于这些算法，RGV 运动路径随机性太强，且算法中参数的设计很大程度上取决于经验，准确率常常不够高.对此我们选择用MATLAB 软件编写符合实际的模拟仿真算法，提高算法对该问题的适用程度.

假设智能加工系统的运行状态稳定且CNC 无故障，在此情况下得出物料最大产出以及最优路径.为了能让RGV 动态调度过程更切合实际生产过程，对RGV 设置滞留时间惩罚系数.

RGV 一共有四个位置可供选择，{1，2，3，4}.每一个位置的操作对象只有两个.令RGV 的位置为a，当a＝1 时，RGV 可以操作的对象为CNC1，CNC2；

当a＝2 时，RGV 可以操作的对象为CNC3，CNC4；

当a＝3 时，RGV 可以操作的对象为CNC5，CNC6；

当a＝4 时，RGV 可以操作的对象为CNC7，CNC8.

将RGV 位置以及操作对象作为变量，则一共有八种方案.可以考虑穷举法.令操作对象为c，c 为八行一列的向量，c 中元素的值域取值为{0，1}，c 里面的元素最多有一个1.元素为1 的那一列的编号，代表的是RGV 操作对象的CNC 编号.例如c＝［0 1 0 0 0 0 0 0］，表示RGV 将要对CNC2 进行操作.综上所述，RGV 位置以及操作对象，只有以下八种方案.

当 a＝1 时：c＝［1 0 0 0 0 0 0 0］或［0 1 0 0 0 0 0 0］

当 a＝2 时：c＝［0 0 1 0 0 0 0 0］或［0 0 0 1 0 0 0 0］

当 a＝3 时：c＝［0 0 0 0 1 0 0 0］或［0 0 0 0 0 1 0 0］

当 a＝4 时：c＝［0 0 0 0 0 0 1 0］或［0 0 0 0 0 0 0 1］

算法的主要参数和符号被定义并列在表2 中，以便于参考.算法步骤：

表2 算法中的变量与符号

Step1：RGV 判断通过路径所需的时间以及CNC 的工作状态.首先，RGV 根据当前位置到下一个物料投放的每个CNC 之间的路径距离长短和每一台CNC 是否处于加工状态，以确定通过路径的最短时间.

Step2：每一次移动需要服从的调度要求：符合调度的要求：

Step3：RGV 做出调度决策后，立即移动到下一个上下料需求点.

Step4：RGV 上下料操作完成前后记录耗费的总时间，更新CNC 的状态、物料的装载、更新已使用的总时间ΣminTi.

Step5：循环条件ΣTi≤8×60×60；若总时间超过8 h，则停止循环，输出物料最大产出以及最优路径；反之，则继续循环判断，重复Step1-4.

2.4 基于空闲时间插入法的故障扰动模型

基于不考虑故障时的情况3，在生成预调度时，根据故障特征——以1%的几率随机产生，插入空闲时间——10 到20 min，故障间隔时间一般服从离散随机分布，根据文献[3]研究结果，设其为泊松分布：

则加工工件n 时发生故障的概率为

发生故障的工件n 需要插入的额外时间为

其中，

2.4.1 故障扰动下的RGV 动态调度算法

基于情况1，2 中的求解算法，该空闲时间插入的算法步骤为：

Step1：首先确定处于工作状态的CNC，若CNC 处于工作状态则进入Step2；

Step2：在“RGV 位置及状态判断”函数中考虑故障情况，从而影响可供RGV 决策集；

Step3：在迭代中对8 个CNC 设置故障扰动；

Step4：确定出现故障的CNC 编号；

Step5：将故障处理时间插入更新机制.

2.5 模型结果

2.5.1 一道工序的智能调度模型结果

一道工序的物料加工作业情况，每台CNC 安装同样的刀具，物料可以在任一台CNC 上加工完成.

我们建立的模型的动态调度模型基本适用于情况1，因此，基于动态路径规划及TSP 的动态调度模型，以及最短路径算法，用已给数据设置对应的参数，用MATLAB编写程序，得到RGV 为CNC 上下料作业的编号顺序，即最优的动态路径.运行结果显示，对不同组数据的最优动态路径相同，如图3 所示.

图3 CNC 加工系统只有一道工序的最优路径

即最优路径是RGV 为CNC 进行上下料工作的编号先后顺序为CNC#1、CNC#2、CNC#3、CNC#4、CNC#5、CNC#6、CNC#7、CNC#8.并且在此调度方案下每班次8 h结束时，得到最多的成料产出.分别给出3 组实验中最优路径循环的相关数据，如表3，4，5 所示.

表3 第1 组数据：成料产出n＝365

表4 第2 组数据：成料产出n＝342

表5 第3 组数据：成料产出n＝375

2.5.2 两道工序的智能调度模型的结果

针对两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC 依次加工完成.在情况1 的基础上，RGV 增加2 种不同的状态，即是否载有第一道工序加工完成的物料.由于物料调度复杂提高，建立优化的RGV 动态调度算法，在该算法中，主要通过优化RGV、CNC 的状态.

表6 不同情况的RGV 状态对比

首先，我们要确认安装两种不同刀具的CNC 数量分配比例，根据CNC 加工完成一个两道工序的物料过程中第一和第二道工序所需的时间，进行对比.对比效率＝1/CNC加工时间，得到表7 的分配比例.

表7 每组数据的刀具分配比例

由表7 可得，我们发现每个配比均为非整数的，由整数规划中的分支定界法可得，每个比例可能的整数解有两种.我们先假设其比例效果与CNC 的位置分布无关，仅与CNC 刀具配比数量有关.但经验证，发现预测是有偏差的，若忽略CNC 位置分布进行调度，那么加工完成的物料数将会减少.

设RGV 状态为二进制变量，当RGV 状态为0 时，表示没有载有第一道工序加工完成的物料，此时应调度到装有TP1的CNC 处；当RGV 状态为1 时，表示载有第一道工序加工完成的物料，此时应调度到装有TP2的CNC 处；基于CNC 仅加工一道工序的模型，我们将针对每一种刀具的分配比例TP1：TP2进行迭代计算，得到结果如表8所示.

表8 CNC 仅加工两道工序的刀具配比及加工完成的物料数

2.5.3 基于空闲时间插入法的故障扰动模型的结果

经过MATLAB 求解，得到调度策略和8 h 内的系统作业效率，其结果部分如表9、10 所示.

表9 第1 组数据：一道工序有故障

表10 第1 组数据：两道工序有故障

3 任务二：仿真检验

3.1 任务2的分析

任务2 要求用表1 的三组数据检验任务1 中模型的实用性以及算法的有效性.为了达到此目标，我们可以构建可视化仿真模型.我们通过Tecnomatix Plant Simulation 生产加工仿真软件构建了智能RGV 动态调度可视化仿真验证模型.该软件具有丰富且实用的处理功能，可以方便的选择系统零件、设置参数以及搭建路径.我们可以将仿真得到的结果与建立动态路径调度模型的结果进行比较，以检验模型的实用性和算法的有效性.基于仿真结果和模型结果，给出调度策略和系统的作业效率.最后把模型验证的具体结果分别填入EXCEL 表中.

3.2 TPS可视化仿真

为了验证模型的实用性和算法的有效性，根据文献[4]的仿真方法，我们用Tecnomatix Plant Simulation 仿真软件（以下简称“TPS”）输入的三组数据进行模拟仿真，导出相关数据，与算法计算结果比较，从而达到验证的目的，如图4（a）所示.

选择TPS 作为模型验证的仿真软件主要的原因是：TPS 具有模型所需要的所有对应实物的对象，比如有模拟RGV 的“小车”，“装配”模拟CNC 加工台等，这样就不需要自己创建对象，使得模拟出来的数据更加符合实际.并且TPS 生产加工仿真系统中自带可设置CNC 故障率，这给我们的仿真验证模型带来了极大的便利，设置CNC 故障率为1%，即仿真模型中CNC 组件可用性为99%，如图4（b）所示.

在原始智能加工系统的TPS 模拟仿真模型基础上，设物料输入服从均匀分布.并且对任务1 中的每种情况进行设置.经过比对，仿真模型结果与我们算法得到的结果相同.这说明我们建立的模型具有实用性，我们建立的算法也是有效的.因此，我们可以根据所建立的模型作为实际调度策略的应用，系统的工作效率由成料产出除以每班次的时间得出.

图4

4 总结

本文通过建立了不同情况下的动态调度模型，完整解决了任务1 和任务2.我们利用图论和规划论的内容，将复杂的实际问题转化为数学模型，并利用仿真算法精准地模拟了RGV 的决策过程、旅行过程和作业过程.在模型逐渐复杂化的情况下，对原有模型添加约束条件，使得其能更好地模拟实际问题.通过增加状态变量，缩小RGV 决策集等方法优化了算法.基于得到的算法，可以编写对应的程序，从而得到RGV 的调度策略和系统的作业效率.最终的模型和算法实用性较强，可以应用于实际的动态调度中.