基于短作业优先调度算法的智能RGV动态调度策略

田继宏,张 现,汪珂含,王 昆

(鞍山师范学院 数学与信息科学学院,辽宁 鞍山 114007)

随着现代工业的不断进步，人工智能的水平得到飞速发展，由信息技术、智能技术与装备制造技术的深度集成构成的智能制造系统得到广泛的应用[1].本案例中的智能RGV-CNC加工系统充分展现了自动化技术与人工智能相结合的特征.

1 问题的提出

本案例中的智能RGV-CNC加工系统是由8台计算机数控机床、一辆RGV有轨智能引导小车和上、下料传送带等设备组成.通过对系统的工作原理和智能RGV动态调度问题的分析，提出以下问题：

(1)对一般问题进行研究，给出RGV动态调度模型和相应的求解算法.

系统中的RGV可以在固定轨道上自由运行，RGV负责第一道工序下料和第二道工序的上料工作，下料优先上料.RGV的工作必须按某种顺序依次完成8台CNC发出的工作请求，RGV移动不同单位所用的时间是影响上述问题结果的重要因素.因此可以判断RGV在上、下料时优先选择奇数编号，并且优先选择在RGV最近距离的CNC 进行加工生料.由于下料传送带的完成品分为第一道工序物料和第二道工序物料，所以将8个CNC刀片分成两种状态，利用遗传算法确定最优CNC排布方案.

(2)检验模型的实用性和算法的有效性，给出RGV的调度策略和系统的作业效率.

通过(1)中构建的RGV动态调度模型了解到整个系统在正常工作中分为CNC加工时间、RGV清洗时间、RGV上、下料时间以及RGV等待时间和RGV移动时间.RGV的移动路线规划存在最优策略使得在移动的过程中有效时间增多，系统的作业效率提高，从而产生更多的市场价值，提高了系统实用性.

2 算法分析

2.1 上、下料过程算法分析

当多台CNC 发出上料请求时，多个请求之间会存在一定的时间差，为了建立最优状态下的动态模型，RGV按作业时间长短来确定优先级的高低，作业时间越短，优先级越高.这样避免按先到先得调度原则导致浪费过多的移动时间，减少了平均周转时间.根据上述分析，确定算法为短作业优先调度算法(SJF).作业的长短是以作业要求的运行时间来衡量的，SJF算法来自操作系统中的调度算法，可以分别用于作业和进程调度，当SJF算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业.

2.2 加工过程算法分析

两道工序的物料加工作业中，每个物料需要经过两个不同的CNC,可将加工同一个物料的第一道工序的CNC和加工第二道工序的CNC作为一组CNC序列，则可分为4组，此时，序列中CNC的位置将影响RGV引导小车的运动轨迹，因此CNC的位置排布成为影响该系统作业效率的因素之一，采用遗传算法求解CNC的具体摆放位置.

3 模型建立

3.1 模型建立假设条件

模型建立时需要建立以下假设条件:

(1)不可忽略RGV为奇数编号和偶数编号的CNC一次上、下料时间的不同，直接影响到RGV在多重信号时的优先选择.

(2)不可忽略RGV初步启动的时间，将间接影响算法中辅助时间的计算.

(3)可忽略RGV、CNC长时间连续工作等外界因素而产生的生产时间的差距.

(4)假设系统内摩擦损耗忽略不计.

(5)假设RGV、生料、完成品在各自轨道上匀速运作.

(6)假设上、下料传送带在不发生故障的情况下，沿同一固定方向匀速运动.

3.2 上、下料过程模型建立

3.2.1 上、下料过程模型准备

(1)CNC.在上料传送带和下料传送带的两侧各安装4台CNC，等距排列.如果物料的加工过程需要两道工序，则需要有不同的CNC安装不同的刀具分别加工完成，在加工过程中不能更换刀具.第一道工序和第二道工序需要在不同的CNC上依次加工完成，完成时间也不同，每台CNC只能完成其中的一道工序.

(2)RGV.RGV带有智能控制功能，能够接收和发送指令信号.根据指令在直线轨道上移动和停止等待，可连续移动1个距离(两台相邻CNC间的距离)、2个距离和3个距离.RGV同一时间只能执行移动、停止等待、上、下料和清洗作业中的一项.

(3)上、下料传送带.上料传送带由4段组成，在奇数编号CNC1#、3#、5#、7#前各有1段.下料传送带由4段组成，在偶数编号CNC2#、4#、6#、8#前各有1段.它们都由系统传感器控制，只能向同一个方向匀速传动，既能连动，也能独立运动.

(4)算法准备.通过任务的分析，将整个工作系统内的运作时间进行统一计算，并分情况进行处理.

3.2.2 上、下料过程模型建立

图1 RGV工作时的位置

(1)明确RGV在工作时的位置区间.首先在加工第一道工序物料的时候，8台CNC相对RGV只有相对距离以及上料时间的不同.为了方便表示相对位置，定义RGV在CNC1#和CNC2#之间时，标记为AⅠ区；定义RGV在CNC3#和CNC4#之间时，标记为AⅡ区；定义RGV在CNC5#和CNC6#之间时，标记为AⅢ区；定义RGV在CNC7#和CNC8#之间时，标记为AⅣ区.RGV工作时的位置如图1所示.

图2 RGV在AⅠ位置相对8台CNC的距离数 图3 RGV在AⅡ位置相对8台CNC的距离数

图4 RGV在AⅢ位置相对8台CNC的距离数 图5 RGV在AⅣ位置相对8台CNC的距离数

表1 RGV移动不同单位距离所用时间

以RGV在AⅠ区为例说明，当λ的值为0时，RGV不需要移动时间，而当RGV接受其他的6个CNC请求时，RGV需要移动一定单位的距离.根据表1中给出的测量数据分析出，RGV移动时间包含启动时间T启和移动行走时间Tm.RGV移动不同单位距离所用的移动时间如表1所示.

图6 计算加工单个工件总时间流程图

根据表1中给出的数据列出方程

可以求出

加工单个工件总时间应该为RGV工作时间(辅助时间)和CNC加工时间Tw之和，其中RGV工作时间由启动时间T启、移动行走时间Tm、清洗时间Tc和上、下料时间T上、下料这4项组成.

在CNC发出请求后，RGV根据流程图6中公式计算出该CNC加工单个工件总时间，并将计算结果加入请求集合，将新集合进行有序排列，RGV根据集合内最小值选择对应的CNC进行上料工作，该CNC即为短作业优先调度算法得出的当前最优CNC.计算加工单个工件总时间流程图如图6所示.

按照上述的流程图描述，计算出加工单个工件总时间Ts，将所得的加工工件总时间放入集合中进行优先排序，得到一个按时间大小升序排列的有序集合[2].

3.2.3 模型的解决 在得到升序有序集合后，RGV读取集合顶部元素对应的CNC编号并按所需相对距离移动，实施作业.

3.3 加工过程模型建立

3.3.1 加工过程模型准备 第二道工序的物料加工是在第一道物料加工的基础上进行的，第二道工序物料加工要考虑各台CNC之间的位置排布.CNC位置排布方案有多种，利于遗传算法在多种排布方案中筛选出一套最优方案，即先确立染色体(可行解)对象：将加工第二道工序的CNC1～CNC8分成两种：第一种是加工第二道工序的第一工步，第二种是加工第二道工序的第二工步，将所有CNC按位排列得到一组序列(染色体)，并定义加工第一工步的CNC为0，加工第二工步的CNC为1，则该序列(染色体)为一个8位二进制数.CNC序列编号如图7所示.

图7 CNC序列编号

3.3.2 加工过程模型建立[3]遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般用适应性函数来衡量解决方案的优劣.从一个基因组到其解的适应度形成一个映射，可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程，可以想象这个多维曲面里面有数不清的“山峰”，而这些山峰所对应的就是局部最优解.而其中也会有一个“山峰”的海拔最高，那么这个就是全局最优解，而遗传算法的任务就是尽量爬到最高峰，而不是停在一些小山峰.遗传算法结果为一个最优可行解序列，确定了8台CNC的位置排布.

通过“交叉”生成N～M条染色体，再对交叉生成的N～M条染色体进行“变异”操作适应度函数，得到8台CNC排布序列，其可行解序列为8元素的数组.可行解的优劣程度可以用RGV完成一个服务队列的总时间来进行比较，耗时越小则该染色体适应度越高.用3.2.2节提出的算法计算出该数，但对应的适应度函数值(即权值，算法中对应的实际工作场景可选取普通场景来计算RGV完成一次工作所用时长，适应度函数计算越靠近普遍情况，所得结果越优)，再通过轮盘赌算法完成对各个最优解的筛选，适应度越大的可行解被选中的概率越大.

根据上述算法确定了8台CNC的位置摆布，RGV执行策略采用短作业优先调度算法，实现第二道工序物料运输的工作，从而提高了系统作业效率.操作台模拟图如图8所示.

图8 操作台模拟图

4 模型评价及改进

建立模型之初，首要解决的矛盾就是如何在RGV移动中接受并处理多台CNC发出的上料信号，并且满足效率最高的条件.采用短距离工作调度算法可以有效解决这个问题，短作业优先调度算法从请求队列中选择一个估计运行时间最短的作业进行，针对RGV-CNC模型，将RGV工作时间定为RGV启动时间、RGV移动时间、CNC上下料时间和清洗时间之和，该运行时间值的大小作为判定请求集合内的请求优先度.但是这个优先度仅仅是单次作业执行的时间排序，并非完成请求队列所有作业的总时间排序.对于特例情况：当RGV位于中间位置而请求分布于RGV两侧时，RGV的执行顺序可能会比实际最优情况多出RGV移动一个单位的时间.此时,可以针对这类特殊情况跳出短作业优先算法，另做单独判断.

经过实践可以发现，在RGV开始工作时，由于CNC只有8台导致RGV等待时间过长，使工作效率下降.设想一下增加CNC的数量，一方面可以加快物料的传递速度，另一方面不会出现RGV等待时间过长，这样物料在CNC机床上加工时间远远大于辅助时间，同时单个RGV所承担的任务也会增加，导致单位时间内的产量有所提升；如果增加RGV的数量，它的增多会加快物料传递的速率，并且减少出现CNC长时间等待的概率，根据生产均衡的原则，结合遗传算法，将任务分配给每个RGV，单位时间内产量会有所增加，当RGV为3个时，产量提升的效果最为显著.当RGV的数量持续增加后，使得每个RGV所需要承担的任务数减少的幅度下降，另一方面直线轨道上多台RGV的引入极易造成“锁死”.在实际过程中，需要根据实际情况确定是增加RGV数量还是CNC的数量,主要应根据工件加工时间来考量.