基于直线往复单智能RGV系统单工序调度研究

刘洪伟，胡 琪，徐 冉，王明洁

(1.北京物资学院 信息学院，北京101149；2.北京市东方德才学校，北京100038)

近年来，随着人力资源成本持续攀升和人工智能水平高速发展，生产制造加工系统中智能加工代替人力加工越来越广泛[1-2]。特别是在工业制造、机械加工、物料调度、仓库物资储存和物流产品的运输与分类等众多领域，存在越来越多的优化调度和优化控制问题[3]。一般智能加工系统由轨道式自动引导车(rail guide vehicle,RGV)、数控机床(CNC machine tools)、RGV轨道、上料传送带、下料传送带等附属设备组成。RGV是一种在固定轨道上无人驾驶自由运行的智能车，也是智能加工系统的主要组成部分[4]。RGV为CNC机床加工作业进行物料调度搬运及辅助作业，其作业效率对智能加工系统的加工效率有直接影响。因此，对RGV系统合理调度能有效地提高智能加工系统的作业效率。

为提高车间产能，降低成本，企业逐步引入现代化的RGV物料搬运工具。国内外学者对RGV系统的优化调度和控制做了一些仿真研究。Dotoli等[5-6]采用Petri着色网框架研究了巷道RGV物料搬运系统的数学模型，建立了避免死锁策略保护的RGV系统。Chen等[7]模拟仿真上下料操作的柔性生产制造，并阐述了智能生产系统的RGV调度和控制的具体运用。Lee等[8]给出生产制造加工系统中的RGV的5种派遣规则。吴长庆等[9]利用Petri双重着色网，建立了最短路径的RGV动态运行调度系统模型。杨少华等[10]对多RGV环轨协同作业进行了分析。吴焱明等[11]研究了环轨RGV系统的动态调度模拟问题。RGV调度与无质量保证解的RGV派遣规则、路径规划不同，能够给出每个RGV作业的细节[1]，包括上下料、清洗、移动时刻和位置。因此，在直线往复RGV系统中，给定了所有RGV的位置和时刻，也就确定了RGV的行进次序及路线[1]。

对于分段式、环形轨道式、直行轨道式的RGV调度问题，国内外已经作了一般性的研究。就现有的模型对RGV的调度和运输系统的设计较为简单，往往只是以RGV为单一研究对象。关于直线往复RGV调度问题的研究中，韩中庚等[3]在既定场合下给出RGV一般调度模型及产量估计；李国民等[12]在不确定性环境下提出了一种基于完全遍历路径规划的RGV调度规则。由于RGV可沿轨道往复双向行驶，并且可以访问任意CNC机床，因此，RGV在执行物料搬运任务时的行走路线有可能产生延迟，不能与CNC机床进行协调作业，这往往导致RGV系统成为智能加工系统的瓶颈。目前，针对这一问题的研究较少。在没有给定时刻和位置的情况下，本文建立一个优化调度模型，研究单RGV系统与CNC机床协调作业的调度问题，使得RGV在CNC机床加工前后等待时间最短。当加工物料数目比较多时，该问题的求解非常耗时。根据RGV与CNC机床加工物料调度的特征，提出计算机模拟仿真算法对问题进行求解。为检验算法的有效性，利用不同系统参数对模型的可行性和有效性进行了验证分析，并给出了最优调度方案的实际运行结果和结论。

1问题描述及数学模型

本文研究的问题描述如下[4]，如图1所示。该智能加工系统由1辆RGV、1条RGV直线轨道、K台CNC机床、1条上料传送带、1条下料传送带等附属设备组成。RGV根据系统指令能智能控制移动距离和方向，并自带1个机械手臂、1个物料清洗槽，能够完成上下料及清洗物料等作业任务。清洗槽每次只能清洗1个物料，机械手臂前端有2个机械手爪，可以通过机械手臂旋转手爪先后各自抓取1个物料，完成上下料作业。CNC机床排列在直线轨道两侧，且前方安装了一段物料传送带。右侧为上料传送带，负责为CNC机床输送未加工的物料；左侧为下料传送带，负责将加工并清洗完成的物料送出系统。本文研究的单工序是指物料在CNC机床上的单次加工作业；调度问题的目标是使所有下料时刻之和最小，即使得CNC机床和RGV等待时间尽可能少。这样可以保证在既定的时间里加工的物料尽可能多。

图1智能加工系统示意图Figure 1 Schematic diagram of intelligent processing system

1.1基本假设

为了便于问题的求解，明确问题的作业流程，本文有如下基本假设。

1)在上料传送带和下料传送带的两侧各安装数量相同的CNC机床，等距排列，每台CNC机床同一时刻只能加工1个物料。为了便于定位，记一侧奇数编号CNC机床#1、#3、#5、 ···、另一侧偶数编号CNC机床#2、#4、#6、 ···。

2)作业过程中RGV和CNC机床均不会发生故障。

3)RGV带有智能控制功能，能够接收和发送指令信号。

4)RGV根据指令能在直线轨道上移动、停止和等待，可连续移动k单位(即k+1台相邻CNC机床间的距离)。

5)RGV同一时间只能执行移动、停止等待、上下料和清洗作业中的一项。

6)RGV匀速行驶。

1.2参数和决策变量

1.2.1参数

N为待加工的物料总个数；

K为加工物料的CNC机床个数，K为偶数；

Q为一个极大数，本文取Q=106；

Tp为物料在CNC机床上的加工时长；

Tw为加工作业后物料清洗的时长；

k、l为CNC机床位置，k,l=1,2,···,K;

i、j为物料加工顺序，i,j=1,···,N；

Tk为第k个CNC机床上下料的时长，k=1,2,···,K；

Tkl为RGV从第k个CNC机床移动到第l个CNC机床所需的时长，k,l=1,2,···,K；

I j≥k为 示性参数，若j≥k，取1，否则取0。

1.2.2决策变量

x jk=1表 示物料j由第k个CNC机床加工，否则为0；

taj表 示物料j的上料开始时刻；

tdj表示物料j的下料开始时刻。

1.3数学模型

给定一组物料加工序列，在确定物料搬运目的CNC机床后，就可以确定决策变量的值。此时单智能RGV直线往复调度问题的数学模型构建如下。

式(1)为直线往复单智能RGV调度问题的目标函数，以所有下料时刻之和最小为指标，使得CNC机床和RGV等待时间尽可能少；式(2)给出了上料顺序约束；式(3)保证第j个物料一定是由某个CNC机床加工；式(4)保证第j个物料下料时刻不早于该物料加工完成时刻；式(5)保证同一个CNC机床上前后物料加工顺序的时间约束：后加工的物料上料时刻必须在前面物料加工下料之后；式(6)表示相邻2个物料开始加工时刻之间的空余时间，右边第1项表示第j-1个物料在第j台CNC机床上下料时刻，第2项表示RGV移动的时长(此项为二次项)，当物料需要被清洗时，第3项表示清洗时间；式(7)是决策变量的非负约束。

由于x jk是0-1整数决策变量，且式(6)右端不等式包含二次项，此模型是一个非线性混合整数规划模型，可以采用Gurobi等商用软件在较短时间对较小规模模型进行精确求解。但Gurobi对规模较大的模型求解时，经常会出现内存不足、计算时间过长等现象，因此，有必要设计有效的新算法，使模型能够在较短时间内得到满意解。

2计算机仿真建模算法设计

基于排序规则、指派规则[2]和计算机仿真模拟建模等方法是调度理论中算法设计常用且有效的技术手段。由于直线往复单智能RGV调度在规模较大时存在调度周期性，本文利用RGV调度周期性的特点进行计算机仿真模拟建模求解，既能提高模型求解速度，又能保证解的质量。

变量和事件是计算机仿真模拟建模中最重要的元素。在模拟中一般有3种常用的变量类型：时间变量、计数变量和系统状态变量[13]。只要出现1个事件，上述变量就要改变或更新，并且收集感兴趣的数据作为输出。

1)时间变量。当前时刻记为t，上料开始时刻记为ta，下料开始时刻记为td；tai为第i个物料的上料时刻，tdj为第j个物料的下料时刻。

2)计数变量。t时刻为止上料个数记为i,下料个数记为j。

3)系统状态变量。系统中t时刻正在加工的物料个数记为n，上料加1，下料减1。

由于加工初期只有上料和移动，当第1个加工作业结束后才有上下料、RGV移动和物料清洗。本文采用等待时间最长的先到先服务规则进行仿真。图2为加工系统调度的计算机模拟离散事件仿真的详细步骤。

图2直线往复单智能RGV协调CNC机床加工作业流程图Figure 2 Flow chart of one intelligent RGV coordinated CNC machine tools based on linear reciprocating

1)初始化数据。首先初始化时间变量(t=0,ta=0,td=∞)，计数变量(i=0，j=0)，系统状态变量为(n≥K)；设置CNC机床的个数K及事件列表(tai,tdj)，并读取其他参数。

2)上料。在加工初期加工前K个物料时还没有形成周期，只涉及上料和RGV移动；K个物料之后才涉及上下料、RGV移动以及物料清洗。对于这一过程，通过i与n、K的比较来实现。i＜K表示加工初期，n＜K说明存在CNC机床空闲或等待。为ta进行赋值并令n=n+1，同时考虑为不同CNC机床上料的用时及RGV的移动用时。

3)下料。这一过程的识别主要通过n≥K来实现。这部分处理无特殊情况，主要注意CNC机床上下料的用时、RGV的移动以及物料清洗。下料时刻通过对CNC机床加工结束时刻与RGV空闲时刻比较得出。

4)收集数据。设置加工作业总时长为T，收集每个加工物料的上下料始末时刻、CNC机床加工始末时刻、物料清洗始末时刻、RGV的移动始末时刻及等待始末时刻。

上料及下料部分的计数变量、时间变量和系统状态变量的更新计算，特别是事件列表(tai,tdj)的更新是该流程图的核心。

3算例实验

为了检验模型求解效果，本文对数学模型和计算机仿真模拟算法在不同参数下的结果进行了对比。参数设置及详细说明如表1所示[4]。

表1智能加工系统作业参数表Table 1 Parameter table of intelligent machining system

基于本文数学模型，利用Matlab 2014a，调用Gurobi软件包进行编程，对表1中的3组参数进行小规模物料加工求解，均得到全局最优解。当加工物料规模比较大时，耗时非常长。以第1组参数为例，当系统中有8个CNC机床，加工18个物料时，进行10次求解，平均耗时446.62 s；加工32个物料时，平均求解耗时近1 h，这在实际生产过程中是不可接受的。对计算的结果进行比较发现，加工32个物料的前18个解与加工18个物料的解完全相同，若以第1～16的解作为初始解，则求解第17～32的解耗时与求解第1～16个解的耗时基本相同。以此类推，可以求解中等规模的问题。而对于大规模问题的求解，采用上述阶段赋初值的策略仍然费时费力。

采用本文设计的计算机仿真模拟算法，并利用Matlab 2014a进行算法实现，对3组参数进行与上述数学模型相应规模的计算，发现计算结果完全相同，并且耗时非常短。图3～5是RGV分别与6个、8个、10个CNC机床在第1组参数设置下协调作业生产调度状态图。为了直观分析，只截取显示了0～3 000 s的RGV与CNC机床协调作业图。每个图中的图(a)为RGV分别为每个CNC机床服务状态示意图，图中的星号表示物料上料开始及结束时刻，圆圈表示物料下料开始及结束时刻，若二者重合，表示物料上下料时刻重合。三角图标表示清洗结束时刻，虚线表示RGV移动及等待时间区间。图(b)中的每个线段表明相应CNC机床的加工作业时间区间，星号之间的间断为CNC机床空闲时间区间。图(c)为RGV的4种状态：上下料、移动、清洗和等待。从图3～5中可以看出，500 s以后加工系统的RGV调度就出现了周期特性。每个图的RGV和CNC机床工作效率并不一样：图3中的每个周期RGV均存在着较长的空闲等待(188 s)，而CNC机床不存在超长等待(超长等待是指除上下料等待之外的空闲等待)；图4中每个周期RGV空闲等待的时间相对少得多(46 s)，CNC机床不存在超长等待(0 s)；图5中每个周期RGV不存在空闲等待，但CNC机床存在超长等待(96 s)。

利用表1提供的3组参数数据，在RGV协调不同数量的CNC机床加工作业8小时(28 800 s)的情况下，系统加工完成物料个数及RGV、CNC机床周期稳定后的等待时长数据汇总如表2所示。韩中庚等[3]利用表1中提供的3组参数，在RGV与8个CNC机床单工序协调作业8 h加工完成的物料个数分别为383、359、392，与本文模型RGV协同相同数量的CNC机床作业下求解出来的结果相同。这说明本文建立的模型是有效的。另外，从表2中的汇总数据不难发现，第1组参数RGV与10个CNC机床协调作业，加工物料数量最多；第2组参数RGV与8个CNC机床协调作业，加工物料数量最多；第3组参数RGV与10个CNC机床协调作业，加工物料数量最多。所以，RGV和CNC机床相互配合，即RGV不存在等待，而CNC机床等待时间尽可能少，加工系统的工作效率更高。

图3单RGV与6个CNC机床协调作业状态示意图Figure 3 Diagram of coordinated operation between RGV and 6 CNC machine tools

图4单RGV及8个CNC机床协调工作状态示意图Figure 4 Diagram of coordinated operation between RGV and 8 CNC machine tools

图5单RGV及10个CNC机床协调工作状态示意图Figure 5 Diagram of coordinated operation between RGV and 10 CNC machine tools

表2表1参数下RGV协调CNC机床产出状态汇总1)Table 2 Summary on RGV coordination CNC under parameters in Table 1

4结论

在直线布局的智能加工系统中，负责物料搬运直线往复的RGV与负责加工的CNC机床协调作业非常重要。RGV调度策略及协调恰当数量的CNC机床对智能加工系统的加工效率有直接影响。本文首先介绍了问题的实际背景和系统的作业流程。考虑到智能RGV与加工设备CNC机床协调作业的特点，建立了以RGV与CNC机床协调作业完成物料下料时刻之和最小为目标的非线性整数规划模型。根据RGV与CNC机床物料加工调度特征，提出计算机仿真算法并对问题进行了求解。在RGV不存在等待、CNC机床等待尽可能少，即在RGV和CNC机床相互配合的情况下，最优调度方案的工作效率最高。为了检验算法的有效性，利用文献[4]提供的3组参数对模型的实用性和有效性进行了验证，并给出了最优调度方案的实际运行结果。本文为RGV与CNC机床协调作业策略研究提供了一定的参考，对工业加工生产具有一定的借鉴意义。