工业RGV的动态调度策略

孟芳汀 李庆祥 付辉

摘 要：本文运用有向线段旅行商，动态规划，组合调度等方法解决了题RGV动态调度模型的问题。分析了故障影响生产结果的情况，进行对静态模型的分析，对动态模型的仿真，根据动态静态模型的分析，确定所述情况下的调度模型。

关键词：向线段旅行商；动态规划；组合调度；matlab仿真求解

随着科技的进步，生产过程的自动化程度越来越高，更多的大型企业倾向于选择智能加工系统代替人力进行生产加工，智能RGV就是典型的工业机器人中的一种。RGV通过接受数控机床的指令进行移动，并完成上下料和清洗作业的机器。本文RGV是一种装载有机械手，清洗槽的智能有轨制导小车，本文是针对较为简单的工业加工流程进行数学模型求解，即一台RGV为8台CNC服务，且每次作业的物料只需要在一台CNC进行一道加工工序；两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由两台不同的CNC依次加工完成，以下是对数学模型的具体求解过程。

首先对所述问题进行分类讨论。在只有一道加工的情况下，通过有向线段旅行商和对比分析的方法给出RGV路线的最短时间路线。通过运用单片机的仿真发现并不是简单循环结构，RGV是在收到信号后才会到有需求的数控机床的位置，这样必然会导致一个时间差，致使前一个数控机床与后一个数控机床的开始进行操作的时间会越来越大。再一次对模型进行讨论，在确定初始顺序的基础上，添加插队机制，即RGV取去最先发出需求指令的数控机床。两道加工工序的情况，取各自加工时间的倒数作为节拍，进行同期化处理，安排机器的分布，进而得出调度安排。考虑到工序的先后关系，子问题在一次路线中被多次考虑，建立目标调度优化模型。目标函数为Z=min max（ek）， ，xik为0/1变量，表示工序wk是否选择CNC#i进行加工。

1、一道工序的物料加工作业的讨论求解

首先采用动态规划[1]的方法进行理论分析。第二个等待的时间等于上一个的总时间加上它上下料的时间和清洗作业的时间再加上RGV移动一个单位长度的时间，即tk+1=tk+ur+tm1（其中ur=t上下料+t清洗作业），所求的最短时间设为A（tq，0），两个阶段的传递最短时间为T=（tk+1，tk），所以A（tq，0）=min{T=（tk+1，tk），tk}。

RGV在完成一项作业任务后，立即判别执行下一个作业指令。如果没有接到其他的作业指令，则RGV就在原地等待直到下一个作业指令。再基于任务1的分析可知，智能小车RGV只需要在CNC#1发出换料的信号之前，回到初始位置即可，这样CNC#1需要等待的时间是最小值，然后CNC#2—CNC#8因为上下料的时间差依次发出信号。

从CNC#1出发，最后依据CNC#2发出信号，智能小车回到初始位置的路线有很多种方式。在此基础上只需要满足在RGV给8个数控机床完成换料的时间，小于CNC#1对物件操作的时间即可。

实际上，RGV运动的形式可以分为两大类：闭环圈型或按照CNC的编号顺序，直线式的回到初始位置。对于第一种闭环圈型的路线，可以举个简单的例子阐述，假如RGV的路线按环形排布，将#3和#6交换，易知初始位置到#3的顺序路线，比到6#的路线短，同样的逻辑，将#7与#4交换，路线也会更短，最后得到效果最好的结果，即路径最短。

第二种按编号的路线，第二种方式从初始位置开始，对两侧的数控机床进行分配。这种方式，可以看作是在初始点开始进行路线，把剩余的运作点，看作随机分布。初始点最先上料，则初始点应最先发出信号，将RGV从它终止的点召回。因此，采用有向线段的旅行商算法[2]进行计算，得出等待时间最少的结论：RGV小车从#1出发，依次经过#2，#3，#4，#5，#6，#7，#8，然后#1优先完成，RGV收到信号，回到初始点（#1）。

对两种不同的调度路线分析以后，发现按照编号顺序的路线进行安排，这种方式的等待时间是最小值，但是很明显，RGV小车收到初始点的数控机床发出的信号，再从最远的位置，花费最长的时间是不合理的。因此，大胆假设，假设数控机床第一次布料为人工布料，布料顺序为#1，#3，#4，#5，#6，#7，#8，#2。这种方式既利用了等待时间最小，RGV智能小车也不用接受信号后从最远位置开始移动。因为加工系统的调度特性与单片机相同，所以对数控机床按路线设计优先级。即使出现数控机床同时对RGV发出需求指令（即中断请求信号）的情况，也不会打乱原始路线安排。

值得注意的一点是，在这里仅考虑了RGV行走路线不同造成的差异。

运用单片机仿真效果图可以发现，按照固定的顺序进行循环，循环的周期是逐渐增大的

再次对模型进行分析，发现无论路线安排怎么被安排，时间的消耗不会是简单的循环结构。小车对不同的数控机床操作的时候，由于RGV是在收到信号后才会到有需求的数控机床的位置，这样必然会导致一个时间差，致使前一个数控机床与后一个数控机床的开始进行操作的时间会越来越大，更加不满足循环的要求。

2、两道工序的物料加工作业的讨论求解

对于只有一道加工工序的问题，只需要考虑时间安排进行调度，不多过多论述，下面对于需要兩道加工工序的问题进行进一步求解。由问题分析可知，此问题运用动态规划最为合适。首先考虑工序存在的先后关系。物件必须经历第一道工序才可以经过第二道工序，而是否经历第二道工序对第一道工序并没有关系，即后无效性，后面的决策对不会影响前面的。其次，存在重叠子问题，子问题在一次一次的路线行走过程中会多次被使用。此种情况建立调度目标优化模型[3]。设目标函数为 = min max（ek）， ，xik为0/1变量，表示工序wk是否选择 进行加工。易知，两道加工工序的时间函数为ek = sk + Tik，且时间函数具有约束：Ek ≤ sk + 1。

两道工序加工的问题流程其实很明显，对数控机床进行上料以后，首先需要经历第一道工序，其次第二道工序，最后清洗作业下料。

令S1={进行第一道工序的数控机床}，S2={进行第二一道工序的数控机床}依次寻找配对关系，每个工序的节拍为Ri = 1/ti（ti为工序进行的时间， 取1，2）使一二道工序的节拍相等或成倍，即工艺同期化。为了不使一二道工序之间的半成品出现堆积情况，影响生产，则假设第二道工序有略比第一道工序高的优先等级。因此得出一二道工序两和的分布关系，以此为基准进行接下来的机械化生产。

总结：

本文中运用了matlab软件对所收集到的数据进行了初步检验，主要使用了有向线段旅行商算法和动态规划的方法，再结合组合调度的方法，较为合理地研究了RGV动态调度模型的建立问题，给出了比较客观的结论，为智能加工系统的合理安排提供了科学的理论依据，虽然文章中针对问题有较为全面的论述，但是却还依然存在一些问题，例如未考虑机器故障的情况，此外，实际情况中有许多复杂的情况，所述的模型也就具有局限性。

参考文献

[1] 姜启源，谢金星.数学模型（第四版）：高等教育出版社.2010年。

[2] 司守奎，孙玺菁.数学建模算法与应用：国防工业出版社.2011年。

[3] 韩中庚.数学建模方法及其应用（第二版）：高等教育出版社.2005年。