0 引言
轨道自动导引车（rail guided vehicle，RGV）是一种在智能车间或自动化立体仓库中沿着预设轨道运行的物料运送工具，RGV在物流系统和自动存储与检索系统中的应用较早［1－3］。随着自动化系统在烟草、金融、医药、日化等行业的广泛应用，对输送设备的需求也日益突显。
为提高物料运输效率，增加车间产能，企业逐步引入现代化的RGV物料搬运工具。CHEN等［4］模拟柔性制造系统的上料／卸料操作，并阐述了RGV系统的智能生产调度和控制框架的具体应用；JAIGANESH等［5］阐述了自动导引车（automated guided vehicle，AGV）的 物 流 系 统；HU等［6］对线性跟踪自动货运处理系统的多载量RGV进行研究，考虑双边上料／卸料操作的最优路径，并指出最小化能源消耗目标的同时要考虑避免冲突和时间窗约束。NEJAD等［7］对RGV上下料进行了研究。
随着车间作业规模的扩大，人们结合不同学科理论和优化算法开展了提升RGV综合调度性能的研究，如约束理论［8］、粒子群优化算法［9-12］、遗 传 算 法［13－14］、组 合 拍 卖 算 法［15］、模 糊算法［16］、模 拟 退 火 算 法［17］。FAZLOLLAHTABAR等［18］从周期角度进行研究以减少延迟造成的损失；YILDIZ等［19］也从周期角度对加工单元进行研究。FOUMANI等［20］对多功能RGV加工单元进行研究，其目标为最小化RGV的加工周期或者最大化车间生产效率，同时，为计算加工单元产能，考虑上坡和下坡排列目标函数的下界。
完全遍历路径规划算法（complete coverage path planning，CCPP）的调度规则是在满足某种性能评价指标最优的前提下寻找一条在设定区域内从始点到终点且经过所有可达点的连续路径。该算法在自动化系统中易于实现且具有实用性、可重复性、效率高等特点，在机器人领域得到广泛应用，主要涉及机器人清洗、采矿、检查、探测等［21－24］。
从目前的文献来看，RGV动态调度大多是在理想状态下进行研究的，没有考虑不确定性环境下由于存在异常断刀、刀具寿命到期、零件报废、机器故障等一系列不确定性因素导致的CNC设备（以下简称CNC）停机问题。为此本文基于CCPP调度规则对生产车间不确定性环境下RGV动态调度问题进行研究。
1 问题描述及数学模型
1.1 问题描述
某手机后壳加工车间有10条产线，每条产线包含10个加工单元，每个加工单元配备若干台CNC（编号 Mi，i＝1，2，…，N）和1台 RGV（图1）。CNC发出物料需求信号并通过中央控制系统将信号传送给RGV，RGV检测物料需求信号并依据一定规则为CNC上下料。RGV沿直线型轨道运行，安装在RGV上的机械手执行上下料作业。由于不同加工单元的RGV调度可以独立进行，为了简化问题，本文仅以车间中的1个加工单元为研究对象。定义RGV依次为加工单元N台CNC全部上下料完毕为1个作业周期，RGV完成1个作业周期包含以下5个操作过程。
图1 加工单元布局图
Fig.1 The layout of manufacturing cell
（1）RGV用机械手的一个手爪从来料顶升Tray盘内抓取未加工的物料移至Mi，用另一个手爪在Mi内抓取已加工物料A，然后将未加工物料放置于加工位置。
（2）上料完毕后，机械手将抓取的物料A移至RGV自带的清洗槽，取出已清洗完毕的上一片物料B，并把物料A放入清洗槽，然后把物料B放置于对面出料顶升的Tray盘内。判断Tray盘是否装满，若装满则出料顶升Tray盘下降并将Tray盘放置于传送带上；若未装满，则不作处理。
（3）RGV判断来料顶升Tray盘内物料是否取完，若取完，则吹气清理空的Tray盘，并将其转移到出料顶升台，来料顶升从传送带顶起Tray盘；若未取完，则不作处理。
（4）RGV检测物料需求信号，依据调度规则移动至下一台需要上下料的CNC设备Mi＋1。
（5）移动至Mi＋1时，若Mi＋1 加工完毕，则RGV直接进行上下料作业；否则，RGV等待Mi＋1加工完毕后进行上下料作业。
在加工生产过程中，可能会因CNC故障、异常断刀、刀具寿命到期、切削液异常等因素导致CNC报警甚至停机，待CNC维修完毕或者更换刀具确保能够正常加工生产后再次进行加工作业。加工过程中刀具会有不同程度的磨损，导致加工产品尺寸不合格，这时就必须对CNC的刀具进行调整和补偿，从而致使CNC停机。在正常加工情况下，RGV会按照原有顺序依次为CNC进行上下料作业，但当某台因异常情况而停机的CNC维修好可重新加工时，由于RGV的排他性，CNC之间存在叫料竞争，即RGV同一时间只能为1台CNC上下料。目前车间采用的是就近调度规则，即RGV作业完成后检测所有发出物料需求信号的CNC，选择离其最近的CNC进行上下料作业，但是采用这种调度规则时存在CNC等待的现象。如何确定RGV调度规则、确定调度期内CNC上下料顺序、提高CNC产能是值得研究的问题。
1.2 基本假设
调度问题必须满足以下假设：①起始时刻RGV在M1与M2之间的轨道位置，所有CNC处于空闲状态；②1台CNC同一时间只能加工1片物料，每片物料只能被1台CNC加工；③RGV同一时间只能为1台CNC进行上下料操作，不考虑RGV故障的情况；④物料使用传送带传送，生产过程中不存在缺料现象；⑤每个Tray盘只能放置2片物料；⑥RGV轨道是双向的，CNC之间的间距固定。
1.3 参数和变量
所涉及的集合、变量和参数见表1。
表1 相关参数
Tab.1 Related parameters
注：稳态期即RGV和CNC工作时间节点固定的稳定周期；过渡期即故障CNC维修完成插入后至稳态期的中间过程。
W 正常工作CNC集合F 故障CNC集合R 维修完成的CNC集合W′ 对集合R中CNC遍历后插入到W的序列集合W″ 对集合R中CNC重排后插入到W的序列集合th RGV等待上下料时间t1 RGV移动1单位距离的时间tk＋1，k RGV从第k台CNC移动至第k＋1台CNC的时间N CNC数量C Tray盘容量TRCi 集合W′内第i个序列在稳态期时的RGV周期T′RCi 集合W′内第i个序列在过渡期时的RGV周期TRCmin 集合W′内序列在过渡期时RGV周期的最小值TRCmax 集合W′内序列在过渡期时RGV周期的最大值TCC CNC加工周期tC CNC加工1片物料时间tw RGV洗料时间tm 移动Tray盘时间tMi RGV为CNC上下料时间。下标 M2i－1表示奇数编号CNC且M2i－1＝M1，M2i表示偶数编号CNC且M2i＝M2
1.4 数学函数
随着生产的进行，CNC会出现停机等待的现象，不恰当的调度规则会导致RGV路径迂回，增加RGV行走时间，进而增加RGV的上下料周期，一旦RGV的上下料周期超过CNC的加工周期，会导致CNC停机等待，影响CNC产能。因此，本研究的目标是，在确保稳态期RGV周期小于CNC周期的前提下，最小化RGV的过渡周期。基于上述参数设置，该RGV动态调度数学模型如下：
约束条件：
式（1）表示最小化过渡期时RGV周期，保证RGV能够及时为CNC进行上下料作业。其中RGV周期包含加工单元内所有CNC的上下料时间和所有RGV洗料时间、移动Tray盘时间、RGV在CNC间的移动时间及等待时间；式（2）保证Tray盘只能放置2片物料；式（3）表示通过调整CNC上下料顺序，在CNC上下料周期稳定后，存在部分序列的RGV周期小于CNC加工周期。式（4）、式（5）是为了最大化加工单元CNC数量，保证RGV与CNC数量能够得到有效配置，在此配置机制下，RGV能够在CNC加工结束之前返回，保证CNC不因缺料而停机。
2 完全遍历路径规划算法设计
完全遍历路径规划类似于旅行商问题（traveling sales-man problem，TSP），要求移动机器人在满足一定的指标下完全覆盖目标环境中的可达区域［25－26］。RGV 动态调度采用 CCPP算法调度规则的思想是：对维修完成的CNC遍历后插入到正常工作的CNC序列中，计算各遍历序列的稳态期和过渡期的RGV周期，在满足TRCi≤TCC的前提下，最小化RGV的过渡周期。若不存在TRCi≤TCC的情况，则对正常的加工序列进行重排。CCPP算法的流程见图2，具体描述如下。
图2 完全遍历路径规划算法流程图
Fig.2 The flow chart of CCPP
（1）初始化集合，初始化正常工作CNC集合W＝ ｛wiwi∈N，i＝1，2，…，l｝、故障CNC集合F＝ ｛fifi∈N，i＝1，2，…，m｝、维修完成CNC集合R＝ ｛riri∈N，i＝1，2，…，n｝，其中，N ＝l＋m＋n。
（2）判断维修完成CNC集合R是否为空，若为空则RGV按照原有CNC加工顺序进行上下料作业；否则，将集合R中的Mri按照维修完成时间依次遍历插入到正常加工的CNC集合W中，得到新的CNC集合：W′＝（W∪R）。
（3）计算集合W′各个序列在稳态期时RGV周期TRCi 和过渡期时 RGV 周期 TRC′i，若 TRCi≤TCC，则从集合W′中选择过渡期RGV周期最小的CNC上下料作业序列作为CCPP算法的可行解，转步骤（6）；否则，对正常加工的CNC集合W 进行重排，转步骤（4）。
（4）检测维修完成的CNC集合R中Mri对面正常加工Mwi的邻位是否有单侧上料（相对的两台CNC上下料顺序不相邻）的Mi，若有，则将最早完工的单侧上料Mi移至其对位CNC的邻位，并将Mri放置于Mi的位置，得到新的CNC集合W″，若TRCi≤TCC则将该集合作为CCPP算法的可行解；否则，从正常加工的CNC集合W中寻找最早完工的单侧上料Mi并移至其对位CNC的邻位，同时将Mri放置于其对位CNC的邻位得到集合W″，若TRCi≤TCC则转步骤（6），否则转步骤（5）。
（5）将集合W″中最早完工的单侧上料Mj移至其对位CNC的邻位，若TRCi≤TCC则转步骤（6），否则执行步骤（5）。
（6）从集合R中移除维修完成的Mri。
（7）重复步骤（1）～步骤（6）。
特别说明的是，基于CCPP算法的重排是依据车间实际参数而提出，并依据式（3）～式（5）计算RGV服务CNC的数量，即RGV为加工单元内CNC上下料结束后返回第一台需要上下料的CNC时，该台CNC恰好加工结束或者即将加工结束，以保障CNC不出现等待的现象。所以，若CNC上下料顺序混乱导致CNC等待，通过调整CNC的上下料顺序必有TRCi≤TCC存在。
3 算例分析
由于直接计算目标函数值、更新已有和未来的上下料任务等过程非常复杂，故对智能车间加工单元N台CNC分别采用就近调度规则、CCPP算法并运用Java语言进行建模仿真。
3.1 参数设置
在进行模拟仿真之前，首先要确定系统输入参数，恰当的输入参数对生产车间的产能具有重要影响，依据车间生产现状，对RGV动态调度系统参数进行统计，分别收集各指标的20组数据并取均值见表2。
表2 RGV动态调度参数值
Tab.2 The parameters values of RGV
参数 值 参数 值tC 560s tm 25s tM1 26s t1 17.6s tM2 29s t2 24.6s tw 20s t3 32.6s
本文对车间加工单元10H的加工状况进行模拟。在模型中输入CNC停机数据，包含停机CNC编号（e）、停机开始时间（tF）和停机结束时间（tR），停机数据是从智能车间监控系统中实时收集的，随机选取一组CNC停机数据，见表3。在1 500s时编号为5的CNC开始停机，在1 797s时该CNC维修结束，该台CNC需要按照本文提出的CCPP算法重新加入加工序列。
表3 10H内停机数据
Tab.3 Downtime data in 10H s
e 5 7 1 3 6 5 tF 1 500 2 400 2 700 3 500 9 700 11 065 tR 1 797 2 588 2 825 3 579 10 106 11 221 e 7 1 3 8 8 7 tF 11 127 11 393 11 454 11 480 12 144 17 800 tR 11 299 11 500 11 532 11 995 12 173 18 413 e 1 3 5 1 7 tF 18 120 18 538 18 664 32 551 32 692 tR 18 497 18 743 18 774 32 582 32 739
3.2 方案分析与评价
在表2参数设置的情况下，通过式（3）～式（5）计算得加工单元CNC台数N 最多为8，即1台RGV为8台CNC上下料的配置比较合理，模拟CCPP算法下加工单元的加工过程得到CNC的上下料顺序见表4。
由表3CNC停机数据和表4CNC加工序列可以看出，加工单元8台CNC均未出现停机状况时，CNC的上下料初始顺序为M1—M2—M3—M4—M5—M6—M7—M8；第2 400s时，M7 出现停机状况，加工单元CNC的上下料顺序变为M1—M2—M3—M4—M5—M6—M8；第2 588s时M7处理完毕，需要重新加入正常工作CNC上下料序列中，通过CCPP算法模拟得到CNC上下料顺序为M7—M1—M2—M3—M4—M5—M6—M8，该顺序表示RGV先给M7上下料再为M1上下料，依此类推。
表4 CNC加工序列
Tab.4 CNC machines scheduling sequences
序列1 序列2 序列3 1，2，3，4，5，6，7，8 2，1，4，3，5，7，67，2，1，4，3，5，6，8 2，1，4，3，5，8，7，6 1，2，3，4，5，6，7，8 7，2，1，4，3，5，8 1，2，3，4，6，7，8 7，2，1，4，3，5，8 2，1，4，3，5，8，7，6 1，2，3，4，6，7，8 7，2，1，4，3，5，8 2，1，4，3，5，8，6 1，2，3，4，6，7，8 7，2，1，4，3，5，8 2，1，4，3，5，8，6 1，2，3，4，5，6，7，8 7，2，1，4，3，5，8 2，1，4，3，5，8，67，2，1，4，3，6，5，8 2，1，4，3，5，8，6 1，2，3，4，5，6，7，8 2，4，3，5，8，6 1，2，3，4，5，6，8 7，2，1，4，3，6，5，8 2，4，3，5，8，6 1，2，3，4，5，6，8 7，2，1 4，3，6，8 2，4，3，5，8，6 1，2，3，4，5，6，8 2，1，4，3，6，8 2，4，3，5，8，6 7，1，2，3，4，5，6，8 2，1，4，3，5，6，8 2，4，3，5，7，8，6 7，1，2，3，4，5，6，8 2，1，4，3，5，6，8 2，1，4，5，7，8，6 7，2，3，4，5，6，8 2，1，4，3，5，7，6，8 2，1，4，7，8，6，3 7，2，3，4，5，6，8 2，1，4，3，5，7，6，8 2，1，4，7，8，5，6，3 7，2，1，3，4，5，6，8 2，4，5，7，6，8 2，1，4，3，5，7，6 2，1，4，7，8，5，6，3 7，2，1，3，4，5，6，8 2，1，4，3，5，7，6 2，4，7，8，5，6，3 7，2，1，4，5，6，8 2，1，4，3，5，7，6 2，1，4，7，8，5，6，3 7，2，1，4，3，5，6，8 2，1，4，3，5，7，6
在就近调度规则、CCPP算法两种不同规则的调度情况下，对表3CNC故障数据进行模拟，两种方案在加工单元10h内8台CNC的产能见表5。通过表中数据可以看出，与就近调度规则相比，采用CCPP算法时CNC总产能较高。该数据表明在产能方面，CCPP算法优势明显，能够达到提高车间产能的目的。
表5 CNC产能对比
Tab.5 The comparison of CNC capacity pcs
CNC编号 1 2 3 4 5 6 7 8 总产能就近规则 54 59 55 58 53 58 53 55 445 CCPP 56 61 56 59 54 58 56 58 458
另外，随机选取5组不同时间段的CNC停机数据，对加工单元8台CNC加工状况进行模拟，两种调度规则时RGV行驶总路程见表6。
表6 不同停机情况下RGV行驶总路程对比
Tab.6 Comparison of total distance of RGV under different shutdown conditions m
调度规则 情景1 情景2 情景3 情景4 情景5 平均总路程就近规则 274 269 283 279 262 273.4 CCPP 237 234 242 241 227 236.2
由表6可以看出，在5种不同时间段停机状况下，采用CCPP算法时RGV平均总路程明显少于就近规则下的RGV平均总路程，该数据表明CCPP算法能够很好地对RGV进行调度，减少RGV行驶路程，避免RGV因路径迂回导致的CNC停机等待现象的发生。
因此，在车间调度过程中，不论是在产能提升方面还是在RGV总路程减少方面，采用CCPP算法的RGV动态调度效果都优于车间现行的就近调度规则。
4 结语
本文针对智能车间RGV作业流程进行了详细分析，建立了在稳态期存在RGV周期小于CNC周期的前提下，最小化RGV过渡期的数学模型；通过模拟验证了CCPP算法优于车间现行的就近调度规则，能够实现增加CNC产能、减少RGV行驶路径的目的，避免RGV因路径迂回导致CNC停机等待，为直线型轨道自动导引车的实际规划设计提供依据。
［1］ LEE S G，SOUZA R D，ONG E K.Simulation Modelling of a Narrow Aisle Automated Storage and Retrieval.System （AS／RS）Serviced by Rail-guided Vehicles［J］.Computers in Industry，1996，30（3）：241-253.
［2］ MALMBORG C J.Design Optimization Models for Storage and Retrieval Systems Using Rail Guided-Vehicles［J］.Applied Mathematical Modelling，2003，7（12）：929-941.
［3］ DOTOLI M，FANTI M P.A Coloured Petri Net Model for Automated Storage and Retrieval Systems Serviced by Rail-guided Vehicles：a Control Perspective［J］.International Journal of Computer Integrated Manufacturing，2005，18（2／3）：122-136.
［4］ CHEN F F，HUANG J，CENTENO M A.Intelligent Scheduling and Control of Rail-guided Vehicles and Load／Unload Operations in a Flexible Manufacturing System［J］.Journal of Intelligent Manufacturing，1999，10（5）：405-421.
［5］ JAIGANESH V，DHILEEP K J，GIRIJADEVI J.Automated Guided Vehicle with Robotic Logistics System［J］.Procedia Engineering，2014，97：2011-2021.
［6］ HU Wuhua，MAO Jianfeng，WEI Keji.Energy-efficient Rail Guided Vehicle Routing for Two-sided Loading／Unloading Automated Freight Handling System［J］.European Journal of Operational Research，2015，258（3）：1-30.
［7］ NEJAD M G，GDEN H，VIZVRI B，et al.A Mathematical Model and Simulated Annealing Algorithm for Solving the Cyclic Scheduling Problem of a Flexible Robotic Cell［J］.Advances in Mechanical Engineering，2018，10（1）：1-12.
［8］ KOO P H，JANG J，SUH J.Vehicle Dispatching for Highly Loaded Semiconductor Production Considering Bottleneck Machines First［J］.International Journal of Flexible Manufacturing Systems，2005，17（1）：23-38.
［9］ GAO Liang，ZHANG Guohui，ZHANG Liping，et al.An Efficient Memetic Algorithm for Solving the Job Shop Scheduling Problem［J］.Computers and Industrial Engineering，2011，60（4）：699-705.
［10］ LI Xinyu，GAO Liang，WEN Xiaoyu.Application of an Efficient Modified Particle Swarm Optimization Algorithm for Process Planning［J］.International Journal of Advanced Manufacturing Technology，2013，67（5／8）：1355-1369.
［11］ NAGESWARARAO M，NARAYANARAO K，RANAGAJANARDHANA G.Simultaneous Scheduling of Machines and AGVs in Flexible Manufacturing System with Minimization of Tardiness Criterion［J］.Procedia Materials Science，2014，5（3）：1492-1501.
［12］ WANG Y，LIU J H.Chaotic Particle Swarm Optimization for Assembly Sequence Planning［J］.Robotics and Computer-Integrated Manufacturing，2010，26（2）：212-222.
［13］ XU Weihua，XIONG Jian，YAO Guozhong.Selflearning Genetic Algorithms for RGV Optimization Scheduling［J］.Advanced Materials Research，2012，562／564 ：1706-1711.
［14］ UMAR U A，ARIFFIN M K A，ISMAIL N，et al.Hybrid Multiobjective Genetic Algorithms for Integrated Dynamic Scheduling and Routing of Jobs and Automated-guided Vehicle（AGV）in Flexible Manufacturing Systems （FMS）Environment［J］.International Journal of Advanced Manufacturing Technology，2015，81（9／12）：2123-2141.
［15］ FAUADI M H F B M，YAHAYA S H，MURATA T.Intelligent Combinatorial Auctions of Decentralized Task Assignment for AGV with Multiple Loading Capacity［J］.IEEJ Transactions on Electrical ＆ Electronic Engineering，2013，8（4）：371-379.
［16］ CARIDV F，MORANDIN O，TUMA C C M.Approaches of Fuzzy Systems Applied to an AGV Dispatching System in a FMS［J］.International Journal of Advanced Manufacturing Technology，2015，79（1／4）：615-625.
［17］ YEH W C，LAI P J，LEE W C，et al.Parallel-machine Scheduling to Minimize Makespan with Fuzzy Processing Times and Learning Effects［J］.Information Sciences，2014，269（4）：142-158.
［18］ FAZLOLLAHTABAR H，MEHRABAD M S，BALAKRISHNAN J.Mathematical Optimization for Earliness／Tardiness Minimization in a Multiple Automated Guided Vehicle Manufacturing System Via Integrated Heuristic Algorithms［J］.Robotics and Autonomous Systems，2015，72（C）：131-138.
［19］ YILDIZ S，KARASAN O E，AKTURK M S.An Analysis of Cyclic Scheduling Problems in Robot Centered Cells［J］.Computers ＆ Operations Research，2012；39（6）：1290-1299.
［20］ FOUMANI M，GUNAWAN I，IBRAHIM Y.Scheduling Rotationally Arranged Robotic Cells Served by a Multi-function Robot［J］.International Journal of Production Research，2014，52（13）：4037-4058.
［21］ WU J H，QIN T D，CHEN J，et al.Complete Coverage Path Planning and Obstacle Avoidance Strategy of the Robot［J］.Advanced Materials Research，2012，756／759：497-503.
［22］ RASHIDI H，TSANG E P K.A Complete and an Incomplete Algorithm for Automated Auided Vehicle Scheduling in Container Terminals［J］.Computers and Mathematics with Applications，2011，61（3）：630-641.
［23］ DAKULOVIC M，PETROVIC I.Complete Coverage Path Planning of Mobile Robots for Humanitarian Demining［J］.Industrial Robot，2012，39（5）：484-493.
［24］ JANCHIV A，BATSAIKHAN D，KIM B S，et al.Time-efficient and Complete Coverage Path Planning Based on Flow Networks for Multi Robots［J］.International Journal of Control Automation ＆Systems，2013，11（2）：369-376.
［25］ 田春颖，刘瑜，冯申珅，等.基于栅格地图的移动机器人完全遍历算法：矩形分解法［J］.机械工程学报，2004，40（10）：56-61.TIAN Chunying，LIU Yu，FENG Shenkun，et al.The Rectangle Decomposition Method：a Complete Algorithm for Mobile Robot based on Raster Map［J］.Journal of Mechanical Engineering，2004，40（10）：56-61.
［26］ 张赤斌，王兴松.基于蚁群算法的完全遍历路径规划研究［J］.中国机械工程，2008，19（16）：1945-1949.ZHANG Chibin，WANG Xingsong.The Research of Full Traversal Path Planning Based on Ant Colony Algorithm［J］.China Mechanical Engineering，2008，19（16）：1945-1949.
