貪婪算法在加工流水線的應用

吳鍇鑌

摘要：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