智能RGV的动态调度策略研究

熊珮全 胡文洁 尚裕博 黄乾鑫 张哲

摘   要：文章主要研究智能RGV的动态调度策略，针对只有一道工序的物料加工时，每台CNC都要安装一样的刀具，物料可以在任意一台CNC上加工完成的情况，建立相应的动态调度模型和求解算法。

关键词：最短路径;迪克斯特拉算法;贪心算法

对于8台计算机数控（Computerized Numerical Control，CNC）车床执行相同工序的情况，将8个CNC看作8个节点，将不同节点间到达的不同时间作为权值，使有轨制导车辆（Rail Guided Vehicle，RGV）在8个CNC中的调度形成一条最短的路径（见图1），建立了在双边搜索和约束条件下的迪克斯特拉算法，寻找弧段最少的情况下的RGV调度的路径，为V7，V8，V5，V6，V3，V4，V1，V2，最短通路的值为106，完成了RGV在8个CNC间的最优调度。用3组数据进行检验，得到模型的平均实用性为96.7%。在求CNC的上料时间和下料时间的问题上，建立了贪心算法的模型，利用RGV走完一次最短路径的最优解，通过若干次的贪心选择，最终求得8 h内各CNC的上料时间和下料时间，以及8 h内最多加工的个数为360，求得作业效率为45个物料/h。

1    问题分析

本文引进了最短路径的迪克斯特拉算法，把每个CNC都看作节点，将8个CNC看作一组无向图，将不同节点间到达的不同时间作为权值，以此建立了带权值的邻接矩阵，使RGV在调度中形成一条最短的路径。在双边搜索和约束条件下，寻找经过全部节点且弧段最少情况下的RGV调度路径，并进行了算法实现，完成了RGV在8個CNC间的最优调度。用3组数据分别进行检验，将实用性定义为实际加工的物料个数与理论完成物料个数之比，得到的结果为96.7%，判断为实用模型。在求CNC的上料时间和下料时间的问题上，建立了贪心算法的模型，利用RGV走完8个CNC的最佳路径时，每个CNC的上料时间和下料时间和CNC的编号，达到了局部最优解，通过一系列的贪心选择，达到了全局最优解，最终求得8 h内各CNC的上料时间和下料时间，以及8 h内最多加工的物料个数，从而求得每台CNC的作业效率。

2    模型的建立与求解

2.1  模型的建立

为了求一个CNC调度周期的最短路径，将CNC看作一个无向图，给图的每个边赋以权值，得到赋权图。以起始点CNC1#起点为中心，利用数组循环遍历起点距离其他顶点的u0距离，然后存储到一个数组中，这时候数组里对应的每一位就是各顶点到起点的最短距离，找出距离最小的那个顶点，以此循环，直到扩展到终点为止。

以每个CNC作为图M的节点，两节点间的路线作为图M相应两顶点的边，得到图M（见图2），对图M的每一边，赋以一个实数w（e）的权，得到赋权图M'（见图3）。

图1按照CNC的位置，以CNC1#起点，CNC8#为终点，8个CNC为一个周期，在一个周期内进行最短路径选取。图2给可行的线段加上了权值，CNC的顺序不动，在此基础上求解最优路径。

根据赋权图建立如下邻接矩阵：

依据邻接矩阵，可以看出任意两个顶点之间的权值。图M子图的权是指图各边的权之和。研究的目的是求赋权图M'中指定的两个顶点u0和v0间的权之和最小的轨迹。这条轨迹叫作u0和v0间的最短路径，最短路径上权的和叫作u0和v0的距离，记作d（u0，v0）。

求最短路径采用了比较成熟的算法：迪克斯特拉（Dijkstra）算法，使从起点u0到终点v0权值相加的值达到最小，建立模型如下：

迪克斯特拉的基本思想是按距u0从近到远为顺序，依次求得u0和M的各顶点的最短路和距离，直至v0顶点，算法结束。采用了标号记法，保证了标号没有重复并且记录了每一步的信息。得到如下算法：

从u0到各顶点v的距离由v的最后一次的标号l（v）给出。在v进入Si之前的标号l（v）叫一号标号，v进入Si时的标号l（v）叫二号标号。如果后来将要标号的值比已经标号的值小，则修改标号，直至获得最优的二号标号。若在算法运行过程中，将每一顶点获得二号标号所由来的边在程序注明，则算法结束时，u0至各顶点的最短路也会被标示出来。通过Matlab编程，得到了一号的标号为1，3，4，6，5，2，7，8，从中可以看出每个顶点被标注的次数，最终得出了一条通过全部节点且权值最小的RGV调度的路径，实现了以权值最小的RGV在8个CNC间的最优模型。

在求得最短路径的基础上，目的是求出每个CNC的上料时间和下料时间，以及CNC的编号。因此，不从整体考虑，而是选择从局部出发，求得每个局部的最优解。贪心算法通过一系列的选择来得到一个问题的解，它所作的每一个选择都是在当前状态下具有某种意义的最好选择，并且每次贪心选择都能将问题化简为一个更小的问题与原问题具有相同行驶的子问题。虽然局部的最优解不一定能够达到总体的最优解，但是最终结果却能够很好地近似最优解。

首先，一台CNC的一个周期的时间s进行分解：

其中，ur为CNC上料时间，ue为下料时间，tw为CNC加工的时间，ta为CNC加工完成之后的等待时间，tm为CNC收到请求后移动的时间，tq为完成下料后CNC清洗时间。

在CNC加工过程中，如果它的最后一个物料完成时间大于或者等于呼叫起始的时间hutime，即：

说明这台CNC已经在等待RGV下料，此时，定义它的值为1;否则，它的值为0。

在一个周期中，RGV对于一台CNC的移动时间yidongtime可以表示为：

其中，rgvlocation是RGV的位置。

根据先请求先下料的原则，需要对先请求的CNC先安排RGV，那么CNC下料的时间xialiaotime可表示为：

其中，timeend为CNC完成物料的时间，yidongtime为RGV在收到请求后移动到CNC的时间。

将CNC移动的时间进行排序，将CNC的编号定为k，那么k可以通过CNC移动时间的排序来确定，同时，k也表示了CNC的编号。通过这种关系，就可以Matlab运算得到CNC的编号[1]。

2.2  模型的求解

在最短路径模型中，用Matlab编写程序，最终得到了权值最优的一组路径V7，V8，V5，V6，V3，V4，V1，V2，用3组数据分别进行检验最短路径模型的实用性p，定义如下：

其中，ia为理论上完成的物料个数，it为实际上完成的物料個数。CNC的等待时间和CNC的清洗时间较加工时间短，并且在人类的发展进程中会使它逐渐减小趋近于0，因此，从理论上考虑，忽略CNC的等待时间和CNC的清洗时间。实际上：59it+560it+25it+ _it=28 800;理论上：59ia+560ia=28 800，求解出来最短路径模型的实用性的值为96.7%。这说明采用最短路径模型虽然简单，但是实用性很高，能够很真实地模拟出8台CNC的最优路径。

通过Matlab可以得出在最短路径时每台CNC的上料时间和下料时间，以及CNC的编号，并且求出CNC的总生产物料个数为360个，则系统的作业效率为360/8=45个物料/h，即一台CNC平均生产物料的个数[2]。

2.3  模型的改进

可以在RGV调度模型建模时改用粒子群算法计算最短路径，最终计算出调度模型结果为：CNC1—5.6—7.8—3.4—2—1，其中，编号CNC1，2加工一道工序物料，CNC3.4，5.6，7.8分别加工二道工序物料的第一道和第二道程序。

3    结语

在理想状态下，系统运行周期中，RGV的等待时间等于零在初始理想条件下慢慢将RGV的等待时间增加确保在下一个新的周期里，每个CNC的工作能连贯进行，不会因为CNC的不连续加工造成RGV静止等待CNC呼叫而浪费工作时间。由此，采取分支定界法，计算出最理想状态下系统的最高作业效率，作为可行的调度方案上限。

[参考文献]

[1]周品.Matlab数值分析应用教程[M].北京：电子工业出版社，2014.

[2]张建林.Matlab定量决策五大类问题—50个运作管理经典案例分析[M].北京：电子工业出版社，2013.