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

陈 颖，葛显龙

（重庆交通大学 经济与管理学院，重庆 400074）

1 引言

随着机械自动化、计算机集成技术以及自动化立体仓库的发展，RGV成为自动化装卸搬运的重要手段，有灵活、可控、易维护、自动化程度高、安全等优势[1]，因此在物流活动中得到了广泛的应用。但是，目前对于智能RGV的动态调度策略还需进一步研究和完善。当自动化仓库中有多台RGV时，若调度不当，容易造成运输和调度的碰撞和锁死[2]；当产品需要多工序加工时，不同工序的加工设备安置不当，就会造成资源、时间的浪费[3]；当加工产品时，如果RGV不能对同时发出的信号做出正确的判别和响应[4]，选择正确的路线以及需要完成的操作，就会降低生产效率；当机器发生故障时，就会影响调度方案和降低产量[5]。因此，需要解决RGV的合理调度问题，提高RGV系统的运行效率，使产量最大化。

国内外文献关于RGV调度的研究主要是控制、设计、路线的优化以及碰撞和锁死等方面，但是关于RGV动态调度的研究却很少。陈华针对自动化立体仓库的2-RGV调度问题，建立了基于分区法的混合整数线性规划，使所有物料的总加工时长最短[6]。杨少华等研究了环形输送系统中多个RGV调度模型[7]，根据出入库指标和各种运行参数，利用排队论构建了在不同状态下的RGV调度模型。M.Dotoli和M.P Fanti应用着色赋时Petri网络构建了一个具有环形输送系统的自动化立体仓库模型[8]，从六种RGV和堆垛机的利用率调度策略下选择出最高效的调度策略。宴鹏宇与杨乃定[9]提出禁忌搜索和遗传算法的混合模型，通过搜索最满意的机器人作业顺序来求解自动化工作单元最小完工时间调度问题。Liu Y K等研究了2-RGV系统的路径区分模式和路径整合模式[10]，并通过仿真实验对两种策略的优劣进行比较。吴焱明等对RGV的动态调度建立了遗传算法模型，使得调度方案更符合实际情况[11]。徐伟华等针对双工位的穿梭机系统运用了约束理论，由先到先搬运策略改为数学模型优化调度[12]。刘晓平等提出了适用于工件工序存在并行性的染色体解码方法，能够有效解决工件可并行性加工的作业车间调度问题[13]。吴正佳等针对柔性作业车间的故障问题，提出了一种基于组合策略的重调度方法，可以有效地处理多种状况下的设备故障扰动[14]。前述文献局限于利用智能优化算法、仿真实验对机器的调度和路径选择进行模拟，这些方法的优点是可以得到一个可行方案，缺点是算法过于复杂以及不能对问题进行精确求解。

本文在前人研究的基础上，探索得到车间调度具有周期性，并且初始周期对以后的加工作业周期调度起到了决定性的作用，因此提出了最短路算法、多目标优化模型，解决了单工序、多工序RGV的动态调度问题，利用最小支撑树和0-1整数规划模型简化了算法、缩短了求解时间。

2 RGV动态调度问题描述

智能加工系统由带有机械手抓和清洗槽的RGV、Computer numerical control（数控机床，以下简称CNC）、RGV直线轨道、上料传送带和下料传送带等附属设备构成。机械手可以先后各抓取一个物料，完成上下料作业，清洗槽每次只能清洗一个物料。

图1 RGV—CNC车间布局图

图2 带机械手臂和清洗槽的RGV实物图

在工作正常情况下，如果某CNC处于空闲状态，则向RGV发出上料需求信号；否则，CNC处于加工作业状态，在加工作业完成即刻向RGV发出需求信号。RGV在收到某CNC的需求信号后，会自行确定该CNC的上下料作业次序，并依次按顺序为其上下料作业。根据需求指令，RGV运行至需要作业的某CNC处，同时上料传送带将生料送到该CNC正前方，供RGV上料作业。在RGV为某CNC完成一次上下料作业后，就会转动机械臂，将一只机械手上的熟料移动到清洗槽上方，进行清洗作业（只清洗加工完成的熟料）。RGV在完成一项作业任务后，立即判别执行下一个作业指令。此时，如果没有接到其他的作业指令，则RGV就在原地等待直到下一个作业指令。当某CNC完成一个物料的加工作业任务后，即刻向RGV发出需求信号。如果RGV没能即刻到达为其上下料，该CNC就会出现等待。

本文主要研究的是智能RGV的动态调度问题。首先针对一道工序的加工作业，优化计算出在固定工作时长内的物料加工量。其次是针对两道工序的加工作业，求得设备柔性和工艺路线柔性并存时的最大产量。

针对单工序RGV动态调度的问题，基于多目标优化的思想，建立最短路模型。由于初始周期RGV的工艺路线对以后的调度具有决定性的影响，因此必须确定初始周期的工艺路线和CNC加工顺序。首先将各CNC之间的作业耗时量化为各CNC之间的路程大小，建立关于CNC之间耗时的赋权图G(V,E)，并且求解出最小支撑树，其次对解得的两个最小支撑树进行具体分析，确定RGV的最短路和周期时长。

针对两工序RGV动态调度的问题，基于单工序RGV的动态调度模型，虽然两工序加工存在着设备的柔性和工艺路线的柔性两个问题，但是实质还是最短路问题，与单工序加工不同的是，当参数还没有确定时，两工序加工没有唯一确定的最短路，因为两道工序的加工时长和时长比例决定了工艺路线的走向，但是有最根本的、确定的操作流程。在流程设计中，需要解决RGV的响应原则问题，即当有信号冲突时，RGV先响应完成加工第一道工序的CNC发出的信号。另一个需要确定的问题是不同工序CNC的数量和位置情况。

3 调度优化模型的建立

3.1 参数和变量

模型所需参数和变量见表1。

表1 符号说明

3.2 模型假设

假设1：RGV上物料与下物料的时间相等。由于在实际操作过程中，有时上下物料一次性进行，有时只进行上、下物料其中一个操作，为了方便计算，使上下物料时间相等。

假设2：当信号冲突时，RGV首先响应加工前一道工序CNC发出的信号。这样可以提高工序间衔接和时间的利用率。

假设3：当RGV机械手上已有半成品时，在原地等待加工后一道工序的CNC发出信号，不响应加工前一道工序的CNC发出的信号，否则就会使RGV系统发生混乱，导致自动化加工的暂停，就需要人工解除障碍。

3.3 单工序RGV动态调度的模型建立与分析

由于单工序调度具有周期性，并且初始周期也就是最开始的行驶线路和机床加工顺序不仅影响到了用时的多少，也对以后物料的装卸及清洗作业顺序起到了决定性的作用。因此，单工序RGV动态调度的关键就在于优化初始周期机床的加工顺序和RGV的行驶线路。

将各个CNC机床看成一个点，用Vi表示，制作一个赋权图G=(V,E)，G中每一条边[vi,vj]上的ωij表示RGV加工作业所需要消耗的时间，例如ω13，则表示实际从CNC1#移动到CNC3#所消耗的时间以及其过程中所需要的上下物料的时间。令上下物料时间、清洗时间、移动时间、等待时间分别为x1i、x2i、x3i、x4i。

如果T=是G的一个支撑树[15]，称E′中所有边的权之和为支撑树T的权，记为ω(T)，即：

如果支撑树T*的权ω(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树，即：

得到的最小支撑树即为耗时最少的最优初始周期RGV行驶路线以及机床加工顺序。

3.4 多工序RGV动态调度的模型建立与分析

多工序加工与单工序加工不同之处在于设备的柔性和工艺路线的柔性，同时还有不同工序之间加工顺序的先后性，由单工序RGV动态调度模型可得，将各CNC机床之间所需要的移动、上下料、清洗、加工时间等消耗的时间量化为各CNC机床之间的路径，若要使得产量最大化，即求RGV行驶的最短路，RGV动态调度过程操作流程[9]如图3所示。

图3 多工序RGV动态调度流程图

根据图3多工序RGV动态调度流程图，假设总共需要完成M道工序，且各工序必要按照一定的先后顺序进行加工，xki表示第i个物料正在进行第k道工序，建立的数学模型如下：

由于物料是否清洗取决于物料是否完成了全部的工序，而成品数量取决于物料是否清洗完成，因此利用0-1判断矩阵来刻画是否清洗物料和成品的数量。

另外要使物料加工多工序时间利用率以及物料加工产量最大化需要解决两个问题，一是CNC机床的刀具分配问题，包括了数量和位置的分配；二是RGV对机床发出信号的处理问题。

首先是CNC机床的刀具分配问题：由于物料需要进行M道工序，且必须先完成前一道工序才能完成后一道工序，因此n台机床中必须要有分别完成M道工序的刀具，且一开始会出现加工后一道工序的机床等待加工前一道工序的机床完成前一道工序加工的情况。由于物料的初始机床加工顺序以及RGV的行驶路线决定了以后的物料加工作业，因此必须确定物料的初始加工情况。

对于CNC刀具数量的分配问题，如果完成前一道工序的机床数量大于完成后一道工序的机床数量，意味着多出机床能够进行后一道加工的半成品必须在原来的机床上等待，因此，这不仅影响了该物料加工成为成品的时间，也浪费了机床正常工作的时间。例如当刀具分配为：5个加工第一道工序的机床和3个加工第二道工序的机床时，当5个机床接连完成第一道工序时，只能前3个物料进行第二道工序的加工，剩下两个半成品只能在原地等待，并且装有半成品的机床不能进行别的工作，随着时间的推移，等待的时间会越来越长，使得半成品排队需要第二道加工的个数和时间都会增大，最后可能导致系统拥堵。

同理，当加工前一道工序的CNC数量小于加工后一道工序的数量时，就会造成加工后一道工序的CNC有大量的空闲、等待时间，导致时间利用效率低，从而生产效率降低。因此，当刀具数量分配差异越大时，排队越加严重，为了将时间利用率最大化、生产产量最大化，CNC的刀具数量分配应该相同，即台CNC装配加工第k道工序的刀具，

对于CNC刀具位置的分配问题，当M=2时，可以简化为加工第一道工序的CNC的位置分布问题，当这台CNC确定后，另外加工第二道工序的CNC也随之确定了。由单工序加工RGV动态调度模型求得的最小支撑树可知，RGV移动与上下料耗时最少的情况是奇数与偶数编号分为一个组合的情况，如图4所示。

即CNC1#和CNC2#为一组，CNC3#和CNC4#为一组，CNC5#和CNC6#为一组，CNC7#和CNC8#为一组。

图4 两工序动态调度的工序组合

由于上料传送带靠近奇数号的CNC，因此奇数号CNC比偶数号的CNC上下物料时间更短，所以在循环周期组合顺序确定的情况下，使得循环周期耗时最小，只需将初始耗时最小化即可，即将台加工第一道工序的CNC排放在距离上料传送带的位置即可。因此台加工第一道工序的CNC为图4靠近上料传送带的CNC，即CNC1#、CNC3#、CNC5#、CNC7#。当M＞2时，也和加工两道工序类似，奇数号和偶数号的CNC编为一组加工单元，才能优化线路和最大化利用时间。

其次是RGV对机床发出信号的响应问题：由于不确定前一道工序和后一道工序的加工时间，因此存在着半成品、成品加工完成时间的先后顺序问题[13]，如果半成品和成品同时完成，同时发出信号时，RGV应该如何选择？由于后一道工序必须依赖于前一道工序的完成，因此当一个CNC发出半成品完成信号时，RGV就应该立即响应它，不管其它的CNC发出成品完成的信号，因为只有把半成品卸下后才能装在其它后一道工序加工的CNC，不致浪费此CNC的时间，如果先响应成品完成信号，CNC卸下成品后，没有现成的半成品装上去，必须得再去取半成品回来，这样一来一回无形之中就浪费了时间，还妨碍了完成了半成品加工的CNC继续加工生料的时间，因此当信号冲突时，必须先响应半成品完成的信号，也就是加工前一道工序机床发出的信号。当无信号冲突时，就依据先发出信号先响应的原则，使得等待时间最少。当然，不存在相同的信号同时发出的情况，比如两台不同加工前一道工序的CNC同时发出半成品完成的信号，因为RGV不可能同时为两台CNC上料。

4 算法求解

4.1 单工序RGV动态调度模型求解

最短路算法用Dijkstra法求解步骤如下：

Step2：根据RGV收到的信号判断进行了上下物料、清洗和移动中的哪一项操作，否则就为等待时间。如果Si=V，算法终止，这时，对每个v∈Si，d(vs,v)=P(v)；否则转入第三步。

4.2 多工序RGV动态调度模型求解

Step1：计算xki的最早开始时间，判断xki是否为物料的第一道工序，如果是第一道工序，则转入第二步，否则，转入第三步。

Step2：遍历所有空闲的加工第一道工序的CNC与RGV的距离，找到距离最短的CNC开始加工物料，使得

Step3：判断RGV是否收到了加工工序更少的半成品完成的信号，如果是，则先进行响应处理，否则遍历所有加工后一道工序空闲的CNC与RGV的距离，找到距离最短的CNC开始加工物料，使得ω(vs,vj)=min{ω(vs,vi)+ωij}。

Step4：判断xki是否为最后一道工序，即xki=xMi，如果是，则进行成品的清洗，P(x)=P(x0)+x2i，否则转入第三步。

5 算例分析

5.1 参数设置

算例参数设置见表2。

表2 参数设置

共有8台CNC，固定工作时长为8h，一条上料、下料传送带，一条RGV轨道。具体情况如图5所示。

图5 车间作业图

5.2 结果分析

（1）单工序RGV动态调度模型的求解。用破圈法和避圈法可以得到赋权图中的最小支撑树，从V1即从CNC1#开始，箭头方向表示行驶路线以及机床加工顺序，本文采用避圈法，求得最终最小支撑树如图6、图7所示。

将所得到的最小支撑树放到实际加工系统调度操作中，可以得到两种初始周期的机床加工顺序以及RGV行驶路线的方式，对其具体的工艺路线和机床的加工顺序进行系统、动态的分析，从中选出用时最少、产量最大的一种方式，具体分析如下：

最小支撑树1：按相邻操作间移动距离最短原则，初始加工顺序如图8所示。

图6 最小支撑树1

图7 最小支撑树2

图8 最小支撑树1的机床初始加工顺序

最小支撑树1表示RGV首先选择距离初始位置最近且货源最近的CNC1#机床进行第一个物料的装卸加工，然后转向对另外一边的距离初始位置最近的CNC2#机床进行第二个物料的装卸加工，接着向前移动一个单位，重复刚才的步骤，直至将第八个物料装在CNC8#机床上进行加工。最后由于物料加工时间较长，RGV停在CNC7#-CNC8#机床之间等待。当最先装上CNC的物料加工完成后，CNC1#机床发出成品加工完成的信号，RGV车获得信号后向左移动三个单位到达CNC1#机床，然后进行上下物料以及清洗物料的工作，随后对CNC2#机床进行同样的处理，最后以此方式循环往复。

最小支撑树2：按距离货源最近原则，初始加工顺序如图9所示。

图9 最小支撑树2的机床初始加工顺序

最小支撑树2表示RGV首先选择距离初始位置最近且货源最近的CNC1#机床进行物料的装卸加工，然后移动一个单位到CNC3#机床进行与CNC1#机床同样的操作，接着按原路线返回，依次经过CNC8#-CNC2#机床，最后停留在CNC2#机床旁等待。当CNC1#机床上的物料加工完成之后，RGV直接进行物料的装卸和清洗工作，然后向右移动一个单位，对CNC3#的物料进行同样的操作，最后以此方式循环往复。

最小支撑树1与最小支撑树2的区别和联系：

①当RGV移动x个单位是移动1个单位的整数倍时，最小支撑树1和2的总耗时相同。

②由于在实际情况下，当行驶总路程相同时，机械启动次数越多花的时间越多，最小支撑树1完成一次周期循环需要启动RGV四次，最小支撑树2需要启动六次，因此最小支撑树1比最小支撑树2用时更少。

结论：选择最小支撑树1的方式，即相邻操作间移动距离最短原则。

将参数带入模型以此来检验模型的实用性和有效性，由结果可得，单工序RGV动态调度的周期为634s，8个连续作业时长下，第一组能够加工358个物料，第二组能加工338个物料，第三组能加工368个物料。

（2）两工序RGV动态调度模型的求解

①第一组数据的求解。第一组RGV的动态调度过程为：先对奇数号的CNC从编号1-7进行上料，然后在CNC7#与CNC8#之间等第一道工序加工完成的信号，接着将CNC1#上的半成品放入到CNC2#上进行第二道工序加工，以此类推，直到将CNC7#上的半成品放入CNC8#机床上进行加工，然后又在CNC7#与CNC8#之间等待，由于第一组数据中，第二道加工工序的时间与第一道加工工序的时间相差不大，但是CNC1#先上料，因此，CNC1#先加工完成，然后发出半成品加工完成信号，于是，RGV移动到CNC1#并对此进行上下料，在进行此操作时，CNC3#也发出了半成品加工完成的信号，但是RGV机械手上已经拥有一个半成品，且这个半成品还需要等待CNC2#机床发出成品加工完成的信号后安装到CNC2#上，因此，本文给出了假设3：当RGV机械手上已有半成品时，在原地等待加工第二道工序的CNC发出信号，不响应加工第一道工序的CNC发出的信号，如果响应了，会造成RGV系统混乱，因为没有多余的机械槽口来存放多余的半成品，最多只能暂存一个半成品，才能实现半成品与成品之间的上下料。

最终的动态调度结果为：总共能完成235个成品的加工（包括清洗在内），多余5个加工完成的半成品，1个加工完成的成品来不及清洗。

②第二组数据的求解。第二组RGV的动态调度过程与第一组相同。

最终的动态调度结果为：总共能完成209个成品的加工（包括清洗在内），多余4个加工完成的半成品。

③第三组数据的求解。第三组RGV的动态调度过程为：由于第三组数据中第一道工序加工时长接近第二道工序时长的三倍，因此，与前两组的RGV调度有很大的差异。首先对奇数号的CNC从编号1-7进行上料，然后在CNC7#与CNC8#之间等第一道工序加工完成的信号，接着将CNC1#上的半成品放入到CNC2#上进行第二道工序加工，以此类推，直到将CNC7#上的半成品放入CNC8#机床上进行加工，然后又在CNC7#与CNC8#之间等待。因为第二道工序时长比第一道加工时长小很多，因此，偶数号的CNC从CNC2#开始先发出成品加工完成信号，RGV立即对其响应，将CNC2#上的成品卸下并且清洗，此时，CNC2#暂时空闲，而在执行清洗工作时，CNC4#也发出了成品加工完成信号，所以RGV立即响应新的信号，以此类推，RGV将CNC8#上的成品卸下并且清洗，然后在CNC8#和CNC7#之间等待CNC1#发出信号，然后立即对其进行响应，重复以上的工序。

最终的动态调度结果为：总共能完成184个成品的加工（包括清洗在内），多余5个加工完成的半成品，1个加工完成的成品来不及清洗。

将三组数据的不同参数与求解结果放在一起进行比较，见表4。

表4 两工序RGV动态调度结果

由表4可知，在其他因素相差不大的情况下，不同工序的耗时对成品产量有很大的影响。

第一组数据中，第一道工序和第二道工序耗时相差不大，但是由于第一道工序先进行加工，因此不会有较长时间的等待问题，对时间的利用率较高。

第二组数据中，第一道工序耗时比第二道工序耗时几乎少了一半，加工完成的半成品可以快速地投入到第二道工序的加工中，但是由于第二道工序的耗时过长，则取完半成品后必须等待CNC第二道工序完成，因此对时间的利用率比第一组低，所以产品产量也比第一组低。由于第二组数据中，RGV的移动、上下料、清洗等耗时均比第一组高，因此为了使第一组和第二组具有可比性，除了第一道和第二道工序保留不变外，其它都用第一组的参数计算，结果完成成品的数量为211，与原来的209相比，效果并不显著。由此可见，对产量数量影响最大的是加工不同工序的时间和时间比例。

第三组数据中，加工第二道工序的耗时远小于加工第一道工序耗时，并且第二道工序的进行必须依赖于第一道工序的完成，所以造成了加工第二道工序的CNC工作时间的大量浪费。同理，为了使第三组和第一组具有可比性，除了第一道和第二道工序保留不变外，其它都用第一组的参数计算，结果完成成品的数量为210，与原来的209相比，影响很小，效果并不显著。

两道工序加工RGV动态调度的结论：

加工不同工序的时间和时间比例是影响产量最重要的原因，其他清洗时间、上下料时间、移动时间等因素对产量的联合影响可以微乎不计。由于此两道工序有顺序上的依赖性，因此，第一道工序和第二道工序不宜相差太大，否则就会出现等待或者排队的情况。当加工第二道工序时间远大于加工第一道工序的时间时，就会造成加工第一道工序的CNC等待，反之，则会造成加工第二道工序的CNC等待。最好的情况是第一道工序加工时间比第二道工序加工时间少一点，以此来弥补进行其他操作所消耗的时间。

6 结语

本文主要研究的是智能RGV的动态调度问题。首先针对单工序的加工作业调度问题，由于初始周期时正常工作循环周期起着决定性的作用，因此对于初始周期建立了关于耗时的赋权图，求解出最小支撑树，得到最优调度方案。其次是针对多工序的加工作业调度问题，分析在设备柔性和工艺路线柔性并存时的最优调度，由此建立了多目标优化模型，并采取了0-1整数规划模型进行求解。最后设置相关参数进行案例求解和分析，最后得出，在一个班次内，对于不同操作参数的RGV进行了比较与分析，得到不同工序加工时长对RGV的动态调度起到了绝对性的影响，其他的上下物料、清洗、移动时间对RGV的调度情况几乎没有影响，因此，该模型对于车间内不同设备模拟效果好，实用性强。