口腔设备加工系统的RGV动态调度

王和旭 谢飞 张伟

摘要：该文通过分析国内外对RGV在加工系统应用的现状，结合口腔设备加工的实际情况，在熟悉RGV构成及作业流程的基础下，对口腔设备的自动加工系统中RGV动态调度问题展开研究。结合加工系统参数，针对加工系统中的单个RGV进行动态调度分析，构建贪心算法模型，找出RGV工作时的最佳路线，提高加工效率，运用Matlab对该最优路线进行迭代，验证了该RGV动态调度顺序的可信性和可行性。

关 键 词：口腔设备；贪心算法；RGV动态调度

中图分类号：F259.27

DOI：10.16152/j.cnki.xdxbzr.2020-01-003开放科学（资源服务）标识码（OSID）：

RGV dynamic scheduling of oral equipment processing system

WANG Hexu1， XIE Fei2，3，  ZHANG Wei3

（1.Xijing University， Xi ′an 710123， China;

2.School of Computer Science， Northwestern Polytechnical University， Xi′an 710129， China;

3.School of Computer Science， Xianyang Normal University， Xi′an 712000， China）

Abstract： The application status of RGV（rail guided vehicle） in processing system at home and abroad is analyzed， and the dynamic scheduling of RGV in the automatic processing system of oral equipment is studied which combined with the actual situation of oral equipment processing on the basis of familiarity with RGV composition and operating procedures.Combined with machining system parameters， the dynamic scheduling analysis is carried out for a single RGV in the machining system.The greedy algorithm model is built to find the best route to improve the processing efficiency.In addition， Matlab programming was used to verify the optimal route iteratively to ensure the credibility and feasibility of the dynamic scheduling sequence of RGV.

Key words： oral equipment; greedy algorithm; RGV dynamic scheduling

据《2018中国卫生健康统计年鉴》对我国口腔就诊数据进行市场调查表明，去年该行业规模已增长至1 215亿元［1］。与此同时，我国口腔医疗市场正在以每年250亿元左右的速度飞速成长。“十三五”规划再一次表现了我国对发展医疗器械产业，尤其是高端医疗器械的重视。

随着居民消费升级，我国口腔医疗市场正处于快速发展的阶段。来自行业协会的统计数据显示，预计到2020年，口腔医疗设备的市场需求将突破4 000亿元大关。毋庸置疑，医疗服务行业是我国的朝阳产业，尤其以牙科等专科为代表的医疗领域在进行消费升级，从而成为医疗行业中的翘楚。

数据显示，2016年全年中国口腔科技工室设备及器具制造出口交货值15.4亿元，同比上升25.2％。随着中国制造技术的提升，先进设备对外依赖度越来越小，预计到2022年，出口交货值26.63億元，行业市场规模近90亿元。以牙科激光治疗仪为例，2018年我国需求量约255台，市场规模约4 896万元。该数据在2024年有望突破20 130万元。

随着我国医疗设备制造技术的升级优化，将CNC（计算机数控机床）以及RGV（有轨穿梭小车）相结合的加工生产系统正在逐步应用于口腔医疗设施的生产活动中［2-3］。该系统与物流信息系统相结合，实现了生产自动化，能够使得物料的运输按照既定的生产计划有序进行，同时保持其生产质量和性能的稳定，并且维持在较高的生产效率水平上［4］，从而将口腔医疗设施生产流水线的整体劳动生产率提升。

截至目前，对于RGV的动态调度的研究主要集中在路线设计问题。例如运用避碰防撞算法去避免2辆RGV在工作中出现相向碰撞或同向追尾的问题［5］;针对网络控制系统中采样周期时变不确定性对控制和运行性能的影响，提出了基于反馈控制原理和预测机理的动态调度策略［6］。在此基础上对6种调度策略下 RGV 和堆叠器的使用情况进行了比较，确定了利用率最高的调度策略［7］。智利学者在文献［8］提出使用预先预测的任务来建立动态调度模型。首先，收集历史数据，利用模糊分类算法找出生成任务的概率；然后，对现有任务进行整合，并采用遗传算法对 RGV 调度进行合理分析，通过查询 RGV 在工作中问题的所在，根据自己假设的参数研究了多种系统中的几种 RGV，使用遗传算法，构建了如何配置不同状态的 RGV 车辆数量的模型［9］；最后，利用原有数据进行模型有效性的检验，最终得出该算法切实可行。该方法可以为设计合理数量的 RGV 提供更有效的方法［10］。

在智能加工系统中， 轨道式自动引导车的出现虽然使得工作效率有了很大提高， 但仍旧在设计流程中存在着浪费的现象， 出现闲置等弊病［11］。 浪费设计的一个重要因素是过程的随意性， 导致在设计过程中产生大量的非增值活动，过载活动和不平衡。 当设计任务落后于预期， 形成恶性循环时， 这些现象通常会使情况变得更糟［12］。 本文主要针对 RGV 在口腔医疗设备的加工运输中对运动路线进行一个合理的动态调度。

1 RGV系统的构成及作业流程描述

1.1 RGV系统的构成

图1为RGV系统的基本构造，包括8台CNC，RGV的直线轨道和RGV工作小车1辆，上料传送带和下料传送带各1条。

如图1所示，将4台CNC等距离排列安装在该系统的上料传送带和下料传送带的两侧。在工作时，单台CNC 在同一时间只能完成1个物料的加工，对于多道工序的加工也只能一次性完成一道工序。如果执行多道工序的加工任务，则需要在不同的CNC上进行依次加工，同时完成时间也有所差异。

RGV具有智能控制功能，以保证其能够在工作中进行信号的接收和发送指令，从而完成移动和停止等待的相关指令。RGV可根据工作要求完成在两台相邻CNC间的移动，记为1个单位距离，在3台相邻CNC间的移动记为2个单位距离，在4台相邻CNC间的移动则记为3个单位距离。在工作中，RGV在同一时间内只能执行一项指令任务，即移动、停止等待、上下料和清洗作业。

上料传送带共4段，分别在图1中4台奇数编号的CNC前，即1＃，3＃，5＃，7＃。4段下料传送带与4段上料传送带对应。分别在图1中4台偶数编号的CNC前，即2＃，4＃，6＃，8＃。上料下料传送带均是由系统传感器控制，在启动时可以完成4段在同一个方向的连动或者单独段的独立运动。

1.2 RGV的作业步骤

1） RGV在CNC1＃和CNC2＃的正中间为RGV的初始位置，系统中所有CNC此时都保持空闲状态。

2） RGV接收到上料需求信号，立即确定本次工作的上下料作业次序，以此决定在CNC中进行上下料的作业。即上料传送带将本道工序所需的生料送到正确编号的CNC正前方时，RGV恰好运行至此，并完成上料作业。

3） 在RGV完成一次某编号CNC的上下料作业后，就会转动机械臂到清洗槽上方，进行上下料后的清洗作业。

4） 每完成一项作业任务后，RGV则立即进行下一个作业指令的判别以及执行。若无作业指令发出，则RGV将停留在原地等待。同样，若CNC在完成加工作业任务后随即发出下一个需求信号，而RGV却未到达为其进行上下料的作业，则该CNC将出现等待。

5）系统将不断重复上述工作，直到系统停止作业，RGV回到初始位置。

2 贪心算法理论概述

贪心算法可以简单描述为：对一组数据进行排序，找到每步的最小值，然后对其进行处理［13］。也就是说，贪心算法的基本思路是从问题的某个初始解出发，一步步进行，根据优化测度，确保每一步能获得局部最优解。

从问题的初始状态出发，按照既定的贪心标准去寻找系统中所涉及到的每个步骤的最优解，从而求得该问题的最优解。贪心算法是一种分层处理方法，可以在某个度量的意义上获得最优解。它所做的每一个选择都是当前状态中某种意义的最佳选择，即贪婪的选择［14］。也就是说，通过问题的局部最优解来找到整个问题的最优解，这种策略是一种非常简洁的方法。因为它不是所有问题的总体最优解决方案，所以，只能说它的解决方案是最佳解决方案的良好近似。由于贪心算法没有针对所有问题的总体最优解，所以，在做策略选择时必须注意到某个状态之后的进程是否会影响以前的状态，需要保证其只与当前状态有关，因此，必须仔细分析所采用的策略是否满足后果［15］。

3 口腔设备加工系统RGV动态调度

3.1 指标确定

根据加工系统作业流程，汇总作业参数，如表1所示。

3.2 贪心算法模型建立

当时间限定时，数量就成了检验模型是否合理的指标。在物料加工时，一轮时间最短就成为了总时间最短的前提，下面针对小车运动的时间进行考虑：

1）初始状态：RGV在CNC1＃，2#之间闲置。

2）预处理：按直线顺序1-3-5-7-8-6-4-2放置生料，最终回到原初始位置，全程消耗时间记为t0。

3）设第一道工序完成需要时间为t，则小车等待下次运动时间td=t-t0;小车移动一个单位时间记为tm，取料时间记为tr。

4）设xit=x1t，x2t，…，x8t，其中，xit表示第i个CNC上加工产品完成剩余时间。当xit≤0时，物料完成，发出信号，小车前去相应位置完成上下料工作。

5） 此时

xit=x1t-tm-tr，x2t-tm-tr，…，xkt-tm-tr。

其中，xkt=t，即刚完成物料投放，进行下一个产品的生产。以此重复第4）和5）步工作，则完成一个动态调度。

为建立合理的加工工序 RGV 调度模型，首先要对 CNC 的作业流程进行分析。由上述过程可知，当设定CNC1＃为运动的起点开始上下料，将有多条为不同CNC上下料的路线，但在限定班次内，使得每個 CNC 等待时间最短，则可获得最大产量，因此，引入改良圈算法对 RGV 进行优化路径，得到合理的调度方案［16］。

若xit>0，则第i个CNC上加工产品还需xit秒可以加工完成;若xit=0，则第 i 个CNC上加工产品已经加工完成;若xit<0，则第 i 个CNC上加工产品已经等待（-xit）秒。

当CNC上的产品加工完成，RGV立即进行上下料，可使得系统效率最高，但在实际问题中，基于对成本的管理，设备有限，这个过程很难实现。在此，本文采用改良圈算法来寻找合理的RGV调度路线，

即确保同一零件的各个工序加工时间最短的同时，实现系统中所有CNC等待时间最短，从而获得最大的产量。

作业工序时间间隔最短。同一零件设计多个加工工序，各工序键的紧密衔接可以使整个加工过程时间最小。最小总时间间隔表达式为

f1=min∑Mi=1∑Nj=1tDij。（1）

总生产时间最短。尽可能消除系统中设备的等待时间，确保其处于高利用率，以实现总体的高效率，即全部CNC等待时间最短。

f2=min（maxtEij）。（2）

约束条件为

∑kjk=1xijk=1（i=1，2，…，N； j=1，2，…，M）   ，（3）

tEij ≤tSij  ，（4）

tDijj′=tSij′-tEij ，（5）

tEij=tSij+tij，（6）

tSijk=tEi′jk+，j=1。（7）

式（3）描述了每个 CNC 每个工序必须有且仅有一台设备进行服务;式（4）表示后一个工序只有在前一个工序结束后才能开始工作;式（5）能够求出工序时间间隔，即同一编号的CNC在前一个工序结束后和后一个工序开始的时间差值;式（6）描述了CNC的开始工作时间与该工序的作业时间之和等于其结束时间;式（7）表示同一台 CNC 加工的零件开始时间滞后于前一个工序的结束时间。

具体符号说明如表2所示。

4 RGV动态调度结果及验证性分析

通过Matlab编程得到该加工、系统的调度结果，部分展示如表3所示。

得到调度顺序如图2所示。

为了验证效果是否理想，利用Matlab编程对RGV动态调度模型进行迭代，效果图如图3所示。参数在进化1～10代期间内，成品完成量急剧上升，在第 10～90代时出现了很大的波动，但增加较为缓慢，为此可以看出随着迭代次数的增加，每一代平均成品完成量趋于稳定状态。当迭代次数超过100次后，浮动变大，因此，认定迭代100次左右时较为合适。图4为RGV调动的轨迹路线图，可以看出，RGV在运行过程中具有十分明显的周期性，与最初提出的做策略选择时需要保证每一步达到局部最优解的目的一致，因此可信度很高。

5 结 论

本文主要研究在口腔设备加工系统中单辆RGV的动态调度策略，结合系统作业参数，搜寻最优路径算法和仿真技术，提高系统加工效率，得出一般性RGV动态调度模型，并对该模型的实用性及算法的有效性进行探讨。首先，分析了一道工序系统的作业流程，遍历不同RGV调度路径，比较每班次生产成品的数量，选择一道工序下最优RGV调度策略；然后，在此基础上探讨两道工序的情况，选择使用遗传算法对该任务作进一步探究，对8台CNC进行编码；接着，建立可变换CNC数量的RGV动态调度模型，并给出算法求解结果；最后，进行效果检验，得出该结果可信度较高。

参考文献：

［1］ 张锦，王耀飞，李建生，等.283家医院医疗器械物流管理存在的问题分析及建议［J］.中国医疗管理科学，2016，6（01）：54-56.

ZHANG J， WANG Y F， LI J S， et al. Analysis and suggestions on logistics management of medical devices in 283 hospitals［J］.Chinese Journal of Medical Management Sciences，2016，6（1）：54-56.

［2］ 袁夢婷，杨碧容，孙瑞，等.环形智能加工系统中RGV的动态调度策略［J］.价值工程，2019，38（27）：43-45.

YUAN M T， YANG B R， SUN R， et al.Dynamic scheduling strategy of RGV in ring intelligent machining system［J］.Value Engineering，2019，38（27）：43-45.

［3］ 周妍敏，李勇，左敏，等.智能RGV的动态调度策略研究［J］.齐齐哈尔大学学报（自然科学版），2019，35（05）：72-77.

ZHOU Y M， LI Y， ZUO M， et al.Research on dynamic scheduling strategy of intelligent RGV［J］.Journal of Qiqihar University （Natural Science Edition），2019，35（5）：72-77.

［4］ 孙刚豪，渠继涵，沈方燮，等.智能RGV的动态调度策略［J］.内蒙古科技与经济，2019（13）：74-80.

SUN G H， QU J H， SHEN F X， et al.Dynamic scheduling strategy of intelligent RGV［J］.Inner Mongolia Science Technology ＆ Economy，2019（13）：74-80.

［5］ 张桂琴，张仰森.直线往复式轨道自动导引车智能调度算法［J］.计算机工程，2009，35（15）：176-178.

ZHANG G Q， ZHANG Y S.Intelligent scheduling algorithm for linear reciprocating track automatic guided vehicle ［J］. Computer Engineering，2009，35（15）：176-178.

［6］ 沈艳，郭兵.网络控制系统变采样周期智能动态调度策略［J］.四川大学学报（工程科学版），2010，42（1）：162-167.

SHEN Y， GUO B. Intelligent dynamic scheduling strategy for variable sampling period of NCS［J］.Advanced Engineering Sciences，2010，42（1）：162-167.

［7］ 查振元，李计星，绳润涛，等.智能平移轨道导引车的应用［J］.机器人技术与应用，2017（5）：42-43.

ZHA Z Y， LI J X， SHENG R T， et al. Application of intelligent translation track guide car［J］.Robot Technique and Application，2017（5）：42-43.

［8］ DOTOLI M， FANTI M P， MANGINI A M， et al. On-line fault detection in discrete event systems by Petri nets and integer linear programming ［J］. Automatica， 2009，45（11）：2665-2672.

［9］ FUKUNARI M， MALMBORG C J.A network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems［J］.European Journal of Operational Research，2009，193（1）：152-167.

［10］DANIELIS R， DOTOLI M， FANTI M P， et al. Integrating ICT into logistics intermodal systems： A petri net model of the Trieste port［C］∥2009 European Control Conference（ECC）. IEEE，Budapest， 2009：4769-4774.

［11］马昌谱，张一纯.物流中心自动货物搬运系统2-RGV调度优化模型［J］.系统工程，2019，37（5）：109-116.

MA C P， ZHANG Y C.Logistics center automatic cargo handling system 2-RGV scheduling optimization model［J］.Systems Engineering，2019，37（5）：109-116.

［12］姚天慧，徐宁.智能RGV的动态调度策略［J］.电脑知识与技术，2019，15（22）：270-273.

YAO T H， XU N.Dynamic scheduling strategy of intelligent RGV［J］.Computer Knowledge and Technology，2019，15（22）：270-273.

［13］潘舒曼，薛怡寧，许诺.基于贪心算法的RGV动态调度模型［J］.自动化应用，2019（5）：96-97.

PAN S M， XUE Y N， XU N.RGV dynamic scheduling model based on greedy algorithm［J］.Automation Application，2019（5）：96-97.

［14］李应林，高华，罗宁.基于贪婪算法的城区配电网三级网格智能规划研究［J］.自动化与仪器仪表，2019（7）：39-42.

LI Y L， GAO H， LUO N.Study on three-level intelligent grid planning of urban distribution network based on greedy algorithm［J］.Automation ＆ Instrumentation，2019（7）：39-42.

［15］刘开南.云数据中心基于贪心算法的虚拟机迁移策略［J］.计算机应用，2019，39（11）：3333-3338.

LIU K N.Cloud data center virtual machine migration strategy based on greedy algorithm［J］.Journal of Computer Applications，2019，39（11）：3333-3338.

［16］段渊.基于两道工序加工顺序安排的解法创新［J］.湖南文理学院学报（自然科学版），2011，23（3）：33-36.

DUAN Y.Innovation of solution method based on processing sequence arrangement of two processes［J］.Journal of Hunan University of Arts and Science（Science and Technology），2011，23（3）：33-36.

（编 辑 李 静）