李一　蔡礼渊　贾汝凌　张一鸣　朱雪梅

摘要：为提高智能RGV同步加工过程中真实工作场景的动态调度性能和计算效率，根据智能RGV的加工工序、作业流程、设备故障、系统交互协作等生产情境特征，建立以CNC空闲等待时间总计最小为目标函数的动态调度整数规划模型，依据剩余加工时间短优先、后序工序优先、移动距离短优先等非抢占式优先和故障修复抢占式优先，构建基于先到先服务的动态优先级排队算法（DP-FCFS）。仿真结果表明，RGV和CNC作业效率较高。

关键词：作业车间;先到先服务;动态优先级;动态调度

中图分类号：O226;TP391文献标志码：A

文章编号：2095-5383（2020）02-0048-06

Abstract： In order to improve the dynamic scheduling performance and calculation efficiency of real work scenarios in the intelligent RGV simultaneous processing process， a dynamic scheduling integer programming model was establised according to the production situation characteristics of intelligent RGV， such as processing procedures， operation processes， equipment failures， system interaction and cooperation， which takes the minimum total CNC idle waiting time as the objective function. According to non-preemptive priority such as short remaining processing time priority， subsequent sequence priority， short moving distance priority and fault repair preemptive priority， a dynamic priority queuing algorithm （DP-FCFS） based on first-come-first-served service was constructed.The simulation results show that RGV and CNC work with higher efficiency.

Keywords：job shop; first come first serve; dynamic priority; dynamic scheduling

隨着传感设备和人工智能的发展，利用生产系统的实时状态信息进行生产动态调度，尤其是作业车间调度（Job Shop Scheduling Problem，JSSP）受到广泛关注。作业车间调度既需要解决物料的机器选择问题，又需要解决空闲机器从队列中选择物料进行加工问题，是一个NP难问题[1]，具有很强的复杂性和不确定性。

作业车间调度策略演化出以智能算法为主追求算法的有效性和以调度算法为主追求策略的实用性2种趋势。智能算法多以寻求局部或全局最优解为目标，通过仿真算法、启发式算法、遗传算法、蚁群算法等，搜寻适合的生产工艺和调度方案，提出的集成解决方案，但是缺少对影响生产调度的工作场景、原材料、设备的随机性和不确定性等实际生产情境考虑，简单套用智能算法基本失效[5]。调度算法多从具有复杂工序的生产现场监控信息出发，根据加工设备的实时作业状态，综合不同优先调度规则，基于人机协同机制，将人的知识、经验与计算智能相结合，获得较优的调度性能指标。

本文针对智能轨道式自动引导车加工系统（智能RGV），考虑多道工序加工过程中存在计算机数控机床（CNC）设备故障引起的物料报废和加工任务中断情况，基于先到先服务的动态优先级排队算法（Dynamic Priority-based First Come First Serve，DP-FCFS）[10]，先对智能RGV接收到的CNC物料加工请求按照预判加工时刻的先后顺序进行初步排队，兼顾物料加工任务的作业要求和设备协同，再按照后序工序优先、剩余加工时间短优先、智能RGV移动距离短优先的非抢占式优先以及故障修复抢占式优先的动态优先级进行最终排队，实现兼顾灵活性和实用性的调度策略，解决作业车间生产过程中面临的调度难题。

1 应用背景分析

本文作业车间调度实际生产场景为2018年全国大学生数学建模竞赛B题提供的轨道式自动引导车智能加工系统，赛题列出若干物料作业加工状况和作业参数，需要给出智能RGV的动态调度策略，系统的场景及说明如下：

1.1 智能RGV加工系统

智能加工系统主要包括智能RGV及直线轨道1套、两侧各安装4台CNC、上下料传送带各1条，如图1所示。智能RGV自带清洗槽和机械手，同一时刻能自动完成移动、上下物料、熟料清洗、停止等待4项工作中的1项。上料传送带位于右侧，为CNC输送未加工的物料（生料）;下料传送带位于左侧，将加工并清洗完成的物料（熟料）送出系统。传送带安装传感器，可控制连动或独立运动。

1.2 物料加工加工流程

CNC安装不同刀具，物料可以在相同刀具CNC任意1台且仅1台上完成相同工序的加工作业。物料在第1次经过CNC加工后，仅仅变成半熟料，在第2次CNC加工后，物料变成熟料，再经历过清洗后，熟料变成成料，物料被下料传送带传送走，完成整个加工过程。

某CNC完成1个物料的加工作业任务后，向智能RGV发出上料需求信息，智能加工系统会立即判别。如果智能RGV沒能即刻到达并为其上下料，该CNC将处于等待状态。智能RGV在完成1项作业任务后，智能加工系统执行下一个作业指令。如果未接到任何作业指令，智能RGV将原地等待，直到下一个作业指令发出。

1.3 故障对加工作业的影响

CNC在加工过程中整个系统在1个班次内存在1个或多个CNC发生故障的概率为1%。若在CNC加工物料的过程中出现了故障，则该加工中的物料报废。每次故障排除时间包含维修人员赶来维修所花费的时间，每次故障排除时间为10～20 min，故障排除后即刻加入作业序列，加入新的生料进行加工。

2 模型建立

为简化计算，减少更换刀具时间等不确定因素对模型的影响，假设智能RGV加工系统每班次连续作业8 h，每台CNC同一班次只能安装1种刀具加工物料的1个工序，在加工过程中不能更换刀具，直至该班次工作结束。假设传送带等辅助设备运作良好，物料充足，能够保证系统正常运行，不会因辅助设备问题影响物料加工的效率。上料传送带上的生料充足，下料传送带上的空位充足。假设到达1个班次的截止时间，智能RGV系统能够马上停止工作，且已经加工的物料均已完成下料、清洗等工序。

2.1 目标函数：总计空闲等待时间的最少

智能加工系统在一个班次内工作效率最高，等价于所有CNC的空闲等待时间总计最少。某台CNC空闲等待时间等于其上下物料的时刻间距减去加工时间。在考虑CNC出现故障的条件下，空闲等待时间为未发生故障时的空闲等待时间加上物料加工数量以概率发生故障时的故障修复时间，假设故障修复时间服从均匀分布。目标函数为：

3 仿真实验设计

根据生产车间的作业流程、智能RGV与CNC的交互、物料加工的作业情境、调度原理等生产特征，将智能RGV加工系统视为单核多道批处理系统和软实时操作系统的有机整合。组合经典的先到先服务、优先级等操作系统调度算法，加入动态优先，构建出基于先到先服务的动态优先级排队算法（DP-FCFS）。

3.1 智能加工系统与操作系统的相似性

智能RGV加工系统与操作系统极为相似。智能RGV可视为操作系统的CPU，智能RGV的工作状态视为CPU进程，每台CNC物料加工作业对智能RGV的需求可视为单核多道批处理作业系统，CNC故障则要求智能RGV加工系统实时响应，快速修复故障并对加入物料加工序列。

3.1.1 单核多道批处理系统

智能RGV物料加工任务就绪序列同时存在多台CNC发出的物料加工需求，就绪序列加工任务执行的次序与进入就绪序列的次序无严格的对应关系。物料加工任务通过一定的作业调度算法来使用智能RGV，1项预判加工作业任务在等待进入或退出处理时，智能RGV调度另外1项预判加工作业任务运行，多台CNC能交替使用智能RGV，提高了智能RGV及其他系统资源的利用率，同时也提高了系统的效率。

3.1.2 软实时操作系统

软实时操作系统按照任务的优先级，尽可能快地完成操作任务。虽然智能RGV不是严格的实时系统，仍然能够解决一部分实时应用问题。每台CNC将上下料需求信号及故障信号实时发送到智能RGV加工系统就序列，智能RGV预判此台CNC下一次发出的作业信号时间，将各CNC预判作业信号及时间信息进入就绪序列。智能RGV根据预判加工任务的紧迫性，对实时物料加工任务加以分类和排序，并以足够快的速度予以处理。因此，智能RGV处理结果能在规定的时间之内对各CNC做出快速响应，并控制所有实时任务协调一致运行，高可靠性地及时响应实时事件中断，同时及时调度运行实时任务。

3.2 基于先到先服务的动态优先级排队算法

基于先到先服务的动态优先级排队算法，综合先到先服务算法和优先级调度算法的优点，当有紧急的任务需要执行，默认抢占信道命令不受排队就绪序列的控制。具有资源抢占权的任务，按照任务优先级顺序和进入就绪序列先后顺序排成1队，其他任务按照任务优先级及任务源（加工工序）优先级进行先到先服务排队。[10]该算法能够兼顾信令的执行要求及服务公平性，具有较高的调度效率。

3.2.1 先到先服务

先到先服务排队算法是操作系统常用的进程和作业调度算法之一。智能GRV接收各CNC发出的作业任务需求，设定该CNC暂无设备故障发生，预判此台CNC下一次发出的作业任务需求时间，将各CNC预判作业任务及待作业时间信息进入就绪序列，按作业到达系统就绪队列的先后次序作为选择原则，优先选择就绪序列头部的作业任务调入内存，即优先选择作业任务就绪序列最前的第1个作业任务，智能GRV前往该加工任务CNC所在位置完成物料上下料作业。

3.2.2 动态优先级

优先级调度算法也是操作系统常用的进程和作业调度算法之一，优先级用于描述作业任务的紧迫程度。

1）故障修复抢占式优先。当某台CNC发出设备故障，该CNC向智能GRV发出故障信号，采用抢占式优先级，将其列为就绪序列中选择优先级最高的进程，智能GRV即刻将该故障修复信号加入就绪序列的最前端，动态更新优先级，待智能GRV完成正在作业工作，立即前往该故障CNC位置，进行故障修复工作。

2）非抢占式优先规则。按照第2道工序优先于第1道工序规则，采用非抢占式优先级，智能GRV将预判进入就绪队列的作业任务，赋予第2道工序的作业任务较高优先级，综合剩余加工时间少优先规则和智能GRV移动距离短优先规则，进行先到先服务排队。尽可能多地完成两道工序物料加工作业，使生料变成成料，完成整个加工过程，退出智能GRV加工系统。

3.3 算法的伪代码

基于先到先服务的动态优先级排队算法的伪代码如下：

while（在一个班次时间内）

{

do RGV分析全部CNC需求，使用先到先服务算法指定目標;

do前往目标CNC;

if（目标CNC在工作）

{

do RGV等待

}

if（CNC具有半熟料）

{

do记录半熟料下料时间;

do下料;

doRGV分析第2道工序CNC需求，使用动态优先级先到先服务排队算法，指定目标CNC

do前往目标CNC;

if（CNC在工作）

{

do RGV等待

}

else if（CNC上有成料）

{

do记录成料工序2下料开始时间;

do下料;

do清洗

}

else

{

do记录物料编号及上料开始时间;

do上料;

doCNC开始加工;

if（CNC故障）

{

do使用抢占式动态优先级先到先服务排队算法，指定目标CNC，CNC故障修复

}

}

}

else

{

do记录物料编号及上料开始时间;

do上料;

doCNC开始加工

if（CNC故障）

{

使用抢占式动态优先级先到先服务算法算法，指定目标CNC，CNC故障修复

}

}

}

print（解）

4 模型求解

4.1 系统作业参数

智能RGV加工系统3组作业参数数据如表1所示。

4.2 调度策略

因每组加工作业各道工序所需作业时间不同，每道工序分配的CNC数量和位置有很大差异。智能RGV加工系统3组物料加工任务CNC工序分配如表2所示。

智能RGV加工系统在物料加工过程中，物料有1%的概率在加工过程中遇到承担作业任务的CNC发生故障，发生故障的CNC编号、故障发生时间和故障修复时间均由CNC实时向智能RGV发送信息。随机模拟3组物料作业的故障数据，待设备修复后按照抢占式优先进入物料加工动态就绪队列，等待智能RGV正在执行任务完成后，立即执行该CNC物料加工需求任务。

4.3 系统的作业效率

仿真运行100个班次的动态调度，总计空闲等待时间基本稳定在第1组43 908 s，第2组81 615 s，第3组76 863 s。智能加工系统的平均作业效率结果如表3所示。

5 结论与展望

1）研究了智能RGV动态调度问题。提出以轨道式自动引导车（RGV）加工系统中计算机数控机床（CNC）的空闲等待时间总计最小为目标函数，其中，空闲等待时间为未发生故障时的空闲等待时间加上物料加工数量以概率发生故障时的故障修复时间，结合真实工作场景的作业工序、加工流程、设备性能、系统协作、故障修复等约束条件，建立动态调度整数规划模型。

2）采用基于先到先服务的动态优先级排队算法。整合单核多道批处理系统的先到先服务算法、优先级规则等软实时操作系统调度算法，加入故障修复抢占式优先和剩余加工时间短优先、后序工序优先、移动距离短优先等非抢占式优先，构建出符合智能RGV加工系统真实工作场景的基于先到先服务的动态优先级排队算法。

3）算法具有较好的适应性、实用性和灵活性。3组算例的仿真计算结果表明，算法充分挖掘设备空闲时间累积形成的潜在生产能力，兼顾了智能RGV加工系统同步加工过程中真实工作场景对动态调度性能和计算效率的要求，加工系统总计空闲等待时间基本稳定，系统的作业效率较高，基于先到先服务的动态优先级排队算法在该场景下具有较好的适应性、实用性和灵活性。

本文提出的基于先到先服务的动态优先级算法可推广到包含多个中心枢纽复杂智能加工系统类似于多核多道批处理系统的柔性车间调度问题，为加工系统中涉及多个智能体、多种物料、多道工序的物料加工作业的动态调度问题提供新的解决方案和思路。

参考文献：

[1]汤洪涛，费永辉，陈青丰，等.基于工业大数据的柔性作业车间动态调度研究[J/OL].计算机集成制造系统.（2019-04-16）[2019-05-08].http：//kns.cnki.net/kcms/detail/11.5946.TP.20190412.

1637.020.html.

[2]王进峰，阴国富，雷前召，等.蚁群算法在工艺规划与车间调度集成优化中的应用[J].东南大学学报（自然科学版），2012，42（S1）：173-177.

[3]陈鸣，朱海华，张泽群，等.基于信息素的多Agent车间调度策略[J].中国机械工程，2018，29（22）：2659-2665.

[4]陈霞，陈浩文.单亲遗传算法求解飞机降落排序问题的研究[J].科学技术与工程，2009（10）：2828-2831.

[5]韩中庚.2018CUMCM-B题解析[R/OL].（2018-11-29） [2019-05-08]. http：//special.univs.cn/service/jianmo/sxjmyw/2018/1129/1188033_39.shtml.

[6]余鹏飞，姜康，曹文钢.基于人机协同机制的动态作业调度系统研究[J].制造技术与机床，2016（12）：118-122.

[7]丛龙水.动态优先级作业调度算法与实现[J].计算机工程与应用，2013，49（10）：267-270.

[8]轩华.基于FCFS策略的带时间窗车队调度问题研究[J].交通运输系统工程与信息，2013，13（6）：140-146.

[9]刘想德，张根保.柔性作业车间动态调度方法研究[J].机械设计与制造，2014（5）：243-245，249.

[10]刘君瑞，陈颖图，樊晓桠.基于先到先服务的二维动态优先级信令排队算法[J].计算机科学，2011，38（5）：89-92.