贪婪算法在加工流水线的应用

吴锴镔

摘要：RGV智能加工系统主要由RGV与CNC机器组成，其运行依赖于对RGV的智能调控，其能够接收和发送指令，根据指令可以移动或静止等待。按照一定的工作顺序对CNC进行上下料操作以及熟料清洗，从而实现物料的加工。本文对单工序情况，通过建立RGV动态调度模型，在保证CNC的工作时间最大，RGV的运动时间最小的前提下，有效减少在作业时发生时间浪费、提高系统的工作效率，避免紊乱，使整个系统以一定周期运行。

关键词：贪心算法；遍历；最近邻法则

中图分类号：TP391.4 文献标识码：A 文章编号：1007-9416（2019）01-0131-01

1 问题分析

1.1 未发生故障作业

针对加工作业工序为1道的作业情況，在第一次上料中，我们按照CNC的排列顺序依次进行上料，完整的一次上料结束时，机器在#7和#8之间停止作业，此时根据贪心算法计算每台CNC加工剩余时长，RGV移动过去的时长，RGV对其的上下料或清洗，三者时长之和，最短的CNC优先投料级别最高。在合理假设的情况下，问题可简化为返回#1和#2中间等待新一轮循环的开始。

如果算法推广应用到更多的CNC系统中，如果出现多台CNC完成加工之后同时向RGV发出信号，此时RGV根据就近原则，寻找离RGV最近的一个发出闲置信号的CNC，命令RGV对此CNC进行下料清洗以及第二次上料。

1.2 出现故障作业

针对有概率出现故障的单工序情况，根据1%的故障发生率，仿真开始前我们先分别对八台CNC机器进行故障发生信号进行随机选取，在1-100范围内产生随机数i，并以此随机数作为该CNC此次发生故障的位置，CNC将在其进行第i次工作时出现故障。……