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

来源:用户上传      作者:

　　摘要：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次工作时出现故障。故障发生后（我们认为CNC在第i次上下料结束之后开始进行加工的一瞬间进入故障状态）该CNC机器工作剩余时间变为10-20分钟内的任一数值，RGV将利用此数值重新计算该CNC的投料优先等级，重新进行工作排序。
　　2 模型的建立与求解
　　2.1 单工序无故障模型
　　考虑到加工时间远大于移动时间，在获得最大生产效率的情况下，CNC在中途无等待，RGV将连贯地依次为所有CNC上下料并清洗熟料，此时消耗时间最少，为理想时间Q。在单工序的作业中，物料在每一台CNC上加工都是等价的。如果不对RGV的运行方式做出相应控制，系统是杂乱无章的，时间分配不合理。
　　针对单工序的无故障连续工作，在题设假定RGV接受指令不会暂停的前提下，我们在python中建立二维数组表示CNC机器进行仿真，0表示闲置，1表示工作，上面一排代表偶数号机器，下面一排代表奇数号机器。根据贪心算法，RGV计算么它到每个闲置的CNC分别所用时长并加上上料时间，选取其中最短时间者进行上料，开始的一轮上料时，不难发现RGV为CNC上料为顺序方向。完成第一轮的上料后采用贪心算法，当CNC在#7和#8中间，此时立马判别每台CNC加工物件所剩余的时间与RGV移动到该CNC所需时间以及第二次上下料（包括清洗）的时间三者之和Ti（i=1，2，3，4，5，6，7，8），选min{Ti}的CNC作为目标对象，马上移动到该CNC进行等待，这就是一轮循环，此时CNC工作时间达到最长。第一轮的上料不存在等待下料与清洗的过程，不囊括在循环中。每一个工件的下料清洗，RGV都要经过该循环。
　　2.2 单工序有故障模型
　　针对有概率出现故障的单工序情况，根据1%的故障发生率，仿真开始前我们先分别对八台CNC机器进行故障发生信号进行随机选取，在1-100范围内产生随机数i，并以此随机数作为该CNC此次发生故障的位置，CNC将在其进行第i次工作时出现故障。依据模型假设我们认为CNC在第i次上下料结束之后开始进行加工的一瞬间进入故障状态，故障发生后，该CNC机器工作剩余时间变为10-20分钟内的任一数值，RGV将利用此数值重新计算该CNC的投料优先等级，重新进行工作排序，贪心算法将其维修的时间等同于加工的时长，但并未加工出熟料。
　　3 模型实用性与算法有效性检验
　　3.1 针对单工序无故障
　　根据仿真，当第一轮上料结束后，RGV在#7和#8之间，此时立马判别每台CNC加工物件所剩余的时间与RGV移动到该CNC所需时间以及第二次上下料（包括清洗）的时间三者之和Ti（i=1，2，3，4，5，6，7，8），选min{Ti}的CNC作为目标对象，马上移动到该CNC进行等待。
　　3.2 针对单工序有故障
　　针对有概率出现故障的单工序情况，建立“灾难-冻结”模型，我们在仿真过程中对每台机器加上了1%的灾难系数信号，在1～100的整数中选取一个作为故障发生信号，称为灾难因子，随机函数如果选中则该信号，则故障发生，机器进入修复时间，随后延迟了上下料时间，在模型的循环中将修复时间等效于工件加工时间的增加，但没有下料，因为该工件报废，需重新上料，由此实时调整动态调动模型。
　　4 作业效率和模型评价
　　4.1 作业效率
　　从实际出发，定义作业效率=实际产出工件个数/理想产出总个数*100%，作业效率η=n/（8*3600/加工一道工序所用时间），由此计算出非故障情况下三组数据的作业效率分别为90.44%；90.05%；91.10%，出故障情况下三组数据的作业效率分别为88.48%； 87.50%；89.66%。
　　4.2 模型评价
　　调度模型利用了贪心算法进行仿真，能迅速得到答案，在CNC个数较少的情况下，可以简化为无等待的往返循环模型，有效节约了RGV的利用时间，提高生产力。
　　贪心模型以其准确性优的特点可以推广到整条生产线，不限于8台CNC的工作生产系统，有效解决了当RGV返回起始点途中可能出现距离更近的CNC的问题。
　　Abstract：RGV intelligent processing system is mainly composed of RGV and CNC machines. Its operation depends on the intelligent control of RGV. It can receive and send instructions， and can move or wait according to the instructions. According to a certain sequence of work， CNC is operated by loading and unloading and clinker cleaning， so as to realize material processing. In this paper， by establishing RGV dynamic scheduling model for single process， on the premise of guaranteeing the maximum working time of CNC and the minimum moving time of RGV， it can effectively reduce the waste of time in operation， improve the working efficiency of the system， avoid disorder and make the whole system run in a certain period.
　　Key words：greedy algorithm； traversal； nearest neighbor rule
转载注明来源:https://www.xzbu.com/8/view-14760554.htm