基于仿真优化模型的智能RGV 动态调度策略

李彬璠，郭 丽，杨腾飞，李 顺，刘昊博

（1.北京机械工业自动化研究所，北京 100120；2.北自所（北京）科技发展股份有限公司，北京 100120）

0 引言

近年来，随着我国大力推广智能制造产业的发展，自动化设备的数量逐渐增多，在国民经济中的各领域被广泛应用。其中RGV（有轨制导车辆）与CNC（计算机数控机床）是比较常见的两种设备。但其组合使用所涉及的时间利用率问题目前尚未解决，直接影响了生产效能。

针对这一现状，首先进行了文献调研，文献[1～5]更多针对单目标的RGV调度，即只需要一道工序加工的产品，学者们利用双重着色赋时Petri网构建系统实时模型，利用排队论等提供一种有效的途径，研究的相对比较成熟。而对于两道工序的加工研究较少，时间利用率很多情况下达不到最佳状态。因此本文以一个巷道一台RGV和8个数控机床的组合为例，分别对一道工序和两道工序的不同调度策略展开时间利用率的研究，通过模型数据分析，最终提出一种时间利用率较高的解决方案。实例应用的效果验证了该策略的可行性、便捷性和高效性。

1 模型假设

1）RGV在做往复运动时的运行状态、行走过程以及等待过程中的状态相同，且对系统通知的接收频率相同，RGV做匀速直线运动。

2）假设当CNC发出制料请求时，传送带上的物料及时、有效送达至CNC前方。

3）车间设施正常，工作的安全性可靠，且RGV在工作中不发生故障。

4）CNC在整个调度运行周期中有故障发生时，系统停止运行，对调度优化过程不产生影响。

2 模型的建立与求解

2.1 指标的选取

为分析在一般情况下RGV的动态调度，我们通过机理分析法选定了工作效率、时间利用率和工作完成数量三个指标作为动态调度的研究方向。综合考虑工作期间RGV的工作时间、等待时间与故障时间对三大指标完成度的影响，进行仿真建模。选取指标后通过EM-plant软件完成的仿真图如图1所示。

图1 RGV通行3D仿真图

2.2 符号说明

表1

2.3 模型的建立

2.3.1 一道工序

1）一道工序的模型建立

一道工序的模型主要使用了排队论模型，通过对排队论模型的框图分析，我们建立的流程如图2所示。

图2 基于排队论模型的流程框架

对于整个搬运过程，满足以下条件：由于CNC发出请求的次数为无限次，故该等待时间服从指数分布；当CNC发出请求时，如果RGV当前正在工作，CNC会排队等待；每台CNC之间是相互独立的；CNC发出请求的间隔时间分布及其数学期望、方差等数字特征都与时间无关；排队方式为单列不循环队列；每次只能有一台机器提供服务；服务过程是先到先服务方式；服务时间等效为CNC发出请求到RGV收到讯息完成一次工作的时间，由于CNC发出请求的随机性和RGV接受任务时位置的不确定性，该时间指数分布。

可见，本系统属于发出请求时间为指数分布、服务时间为指数分布、单服务台、等待制系统的排队论问题，以Kendall 记号表示为 M/M/1/∞/∞/FCFS。设请求为泊松流，请求相继发出时间服从参数为λ的负指数分布，服务时间服从参数为μ的负指数分布，则服务强度ρ及请求平均排队长 L分别如式(1)所示：

服务强度表示单位时间（小时）内发出请求的CNC与单位时间内RGV能够处理CNC的个数的比值。

其中平均排队长L反映了队列容器的平均容量，在这里表示空闲的CNC数量，其大小直接反映系统是否会产生阻塞。

2）变量计算

在此情况下，由于偶数编号CNC一次上下料所需时间要大于为奇数编号CNC一次上下料所需时间，故工作时间单独考虑。则有：

当一次工作端为奇数时，此时上下料所用时间为：tupdo=todd；

当一次工作端为偶数端时，此时上下料所用时间要大于奇数端所用时间，即为：tupdo=teven。

由于只存在一辆自动引导车机器，故不存在出货输送系统堵塞的现象，机器不存在排队的问题，因此穿梭车一个工作周期的时间即一次搬运的时间为机器运行一周的时间与机器完成一次工作时间之和。这里我们假定Twait为5min，则有：

则单位时间内CNC发出的请求为：

单位时间内CNC完成加工货物的数量为：

2.3.2 两道工序

这里我们假定只有第一次的加工过程需要等待，其余的加工过程都在循环工作中完成，且每次加工过程中都存在其他CNC工作。假设第一次加工过程时间为500秒。

由于两道程序的加工具有极强的选择性，情况错综复杂，故现假定两种情况：一是假定奇数号机床完成第一道工序，偶数号机床完成第二道工序。这里我们采用了Floyd算法计算得出最短路径，再通过最短路径求得服务率和时间利用率；二是假定编号为1的CNC完成第一道程序，同时相邻的CNC安装不同的刀片进行第二道工序的改造，以此类推。而这种情况下，每四台CNC又产生了两种组合方式中，即相邻两台CNC作为一个组合，或交叉方向的两台CNC为一个最优组合，从而进行服务率的计算。

在这里，我们将第二种情况单独列开，于是产生了三种情境。

1）最短路径下的RGV动态调度策略

对于第一种情况，我们采用了Floyd算法来求得最短路径。

设图G=(V，E)，xij表示边（ζi，ζi）边上的权（即为RGV到CNC的距离），若ζi和ζi不相邻，则xij=+∞，用ηij表示顶点ζi和顶点ζi的最短距离。使用Floyd算法来计算ηij最短距离矩阵，步骤如下：

（1）输入图G权矩阵X，对所有的i，j，有ηij=χij，k=1；

（2）跟新ηij，对所有的i，j，若ηik+ηkj＜ηij，则令ηij=ηik+ηkj；

（3）若k=n算法终止，否则转式(2)。

假设RGV的速度固定为υ（单位：m/h），RGV从起始位置ζi到CNC的位置ζj的时长为，由于从起始点i到CNC所在地j的RGV数量只有1，则CNC总等待时长为：

求得最短路径行走路线如图3所示。

图3 RGV选择最短路径时的行走路线仿真

为寻求在一个固定班次内达到最大的时间利用率，我们令RGV在完成第一道工序且等待“半成品”完成后立刻转入第二道工序（此过程不需要移动），在第二道工序加工过程中，RGV向后移动寻找下一生料，进行下一次的加工过程，则有：

其中，tupdo为一次加工过程中对于第一道工序与第二道工序的上下料时间之和，todd为一次加工过程中奇数号机床完成的第一道工序的上下料时间，teven为一次加工过程中偶数号机床完成的第二道工序的上下料时间之和。

故对于完成n件产品所需要的工作总时间，则有：

其中，T1表示完成n件产品所需要的工作总时间，twash为第二次工序过程中的清洗过程所需时间，twork为第一道工序加工所需时间，tml为RGV移动一个单位所需时间。

2)“相邻组合”路径下的RGV动态调度策略

对于第二种情况中的“相邻组合”，为获得最大时间利用率我们选取最有利的地理条件进行组合，将相邻的两组CNC相互组合，共同完成一个产品的加工，计算最终的时间利用率。

对于此种情况，若考虑RGV在编号为1-4的CNC间进行移动所形成的往复运动，则对于RGV的移动过程以及能源的消耗倍增，从而对时间利用率会产生负面影响。故我们假定RGV在行驶过程中保持直线行驶，到达终点后掉头行驶，且保持匀速，故RGV所做运动为匀速直线运动，所行驶轨道为直线轨。即一个RGV系统中只有一辆RGV运行在一条直线形非闭合轨道上。在这样的系统中也不存在RGV碰撞的问题。

图4 RGV选择相邻路径时的行走路线仿真

其中，T2表示完成n件产品所需要的工作总时间。

由上式可以看出，此种情况在与第一种情况占用时间相同的情况下，完成的成品数较少，从一次函数的角度来看，当生产件数越多时，第二种情况所要花的时间越长。大大减小了时间利用率。这与我们想要在规定班次内得到最大时间利用率的同时获得更多产品的愿望相违背，故该模型的利用度小于第一种情况。

3)“交叉组合”路径下的RGV动态调度策略

现在考虑第二种情况中的“交叉组合”。为了使在一定时间内RGV的移动率更大，我们选取最有利的地理条件进行组合，以编号为1的CNC作为初始机器，开始进行第一道工序的加工，其次转到编号为3的机器进行第二道程序的加工，以此类推，求得最终的产品数量。

在此种情况下，由于往复运动的复杂性使得RGV在移动过程中循环次数变多，故假定RGV沿直线方向匀速行驶，行驶至终端进行掉头，继续进行其他生料的加工，且此过程仍假设在完成第二道工序后直接进入下一成品的加工过程种，故仍使RGV继续运动，而“半成品”的加工过程所用时间包含于此。故RGV所做运动仍为匀速直线运动，所行驶轨道仍为直线轨。

图5 RGV选择交叉路径时的行走路线仿真

则有：

其中，T3表示完成n件产品所需要的工作总时间。tchange表示RGV在由奇数端切换到偶数端前臂的摆动过程所用时间，且，tchange≥0通过计算可知，该情况下与情况一相比，同样在时间相似情况下成品数较少，故时间利用率降低。且在于第二类情况相比下，由于tchange≥0，可以得到比情况二效率更为低下的作业效率，故该模型利用度也不高。

综合三种情况下的所需时间，我们发现第一种方案更节约时间，而且所加工产品数目越多，优势就越明显。

2.4 模型的实用性检验

1）一道工序

在这里，我们根据所列模型与参考数据做出了各类数据的参考范围，利用MATLAB软件随机生成了一些数据，代入算法进行检验求解得到相关数据，并利用SPSS求得测试结果如表2所示。

表2 通过SPSS计算得到的三组测试结果

由于数据的大量化我们无法一一列举出所有可能的情况，且随机数在生成过程中无法遵循一定的规律，故我们随机抽取了部分数据作为样本，由样本数据得，机器的每班次能够得到的成品数大致在350～420（单位：件）之间。

经过对数据的大规模分析，λ的值的取值在[30，40]、μ的值在[45，55]内系统的效率达到最大。此时ρ的强度可达到70%以上，时间利用率γ在80%以上。通过SPSS的正态检验得知成品数、时间利用率、服务强度、L的值均大于0.05，数据符合正态分布，该模型灵敏度较好。

2）两道工序

对于两道工序的加工情况，我们仍选用一道工序时通过MATLAB产生的随机数作为参考数据，取样后将数据代入模型算法中进行计算，得到表3所示。

表3 通过SPSS计算得到的三组测试结果

由表3可以看出，尽管我们选用了“最短路径”的模式进行产品制作，但由于中间过程的等待时间较长，使得我们得到的成品数的数量大大降低。成品数数量降低带来的结果是λ与μ的倍减；但由于RGV工作时间相对于一道工序时没有变化，故与时间有关的参数ρ、γ未发生很大改变。

接下来结合数据，将我们建立的模型加以应用，使用SPSS软件进行数学运算，得到以下的数据结果。

由表4可以看出，系统的服务强度与时间利用率在一定程度上仍未发生较大波动，而与模型测试的案例类似，系统在完成工作后得到的成品数相对于一道工序的情况仍发生了急剧下滑。故我们考虑模型出现的数据差异很大程度上归因于只考虑了距离的最短问题而忽略了等待的时间问题。

表4 有两道程序时的数据模型结果

综合表中数据及算法模型中所选取的随机数进行模拟的结果可以得到，在完成一道工序的情况下，我们优先选择最短路径，以此达到最大时间利用率；当存在两道工序时，由于选择的多样性，尽量采取“就近原则”，并进行配对组合，从而实现产品的加工过程，达到动态分配。

3 结语

该模型可真实还原工作过程，所用算法联系性，理论性较强，特别是目前机器化大生产的普遍化，我们的模型可以作为许多工厂在分析解决产品加工问题时的一种参考。当然假设的变量主观性较强，会产生一定的误差。提升整体性，使用更先进的算法将是未来的改进方向。