貪婪算法在加工流水線的應(yīng)用

吳鍇鑌

摘要：RGV智能加工系統(tǒng)主要由RGV與CNC機(jī)器組成，其運(yùn)行依賴于對RGV的智能調(diào)控，其能夠接收和發(fā)送指令，根據(jù)指令可以移動或靜止等待。按照一定的工作順序?qū)NC進(jìn)行上下料操作以及熟料清洗，從而實現(xiàn)物料的加工。本文對單工序情況，通過建立RGV動態(tài)調(diào)度模型，在保證CNC的工作時間最大，RGV的運(yùn)動時間最小的前提下，有效減少在作業(yè)時發(fā)生時間浪費、提高系統(tǒng)的工作效率，避免紊亂，使整個系統(tǒng)以一定周期運(yùn)行。

關(guān)鍵詞：貪心算法；遍歷；最近鄰法則

中圖分類號：TP391.4 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）01-0131-01

1 問題分析

1.1 未發(fā)生故障作業(yè)

針對加工作業(yè)工序為1道的作業(yè)情況，在第一次上料中，我們按照CNC的排列順序依次進(jìn)行上料，完整的一次上料結(jié)束時，機(jī)器在#7和#8之間停止作業(yè)，此時根據(jù)貪心算法計算每臺CNC加工剩余時長，RGV移動過去的時長，RGV對其的上下料或清洗，三者時長之和，最短的CNC優(yōu)先投料級別最高。在合理假設(shè)的情況下，問題可簡化為返回#1和#2中間等待新一輪循環(huán)的開始。

如果算法推廣應(yīng)用到更多的CNC系統(tǒng)中，如果出現(xiàn)多臺CNC完成加工之后同時向RGV發(fā)出信號，此時RGV根據(jù)就近原則，尋找離RGV最近的一個發(fā)出閑置信號的CNC，命令RGV對此CNC進(jìn)行下料清洗以及第二次上料。

1.2 出現(xiàn)故障作業(yè)

針對有概率出現(xiàn)故障的單工序情況，根據(jù)1%的故障發(fā)生率，仿真開始前我們先分別對八臺CNC機(jī)器進(jìn)行故障發(fā)生信號進(jìn)行隨機(jī)選取，在1-100范圍內(nèi)產(chǎn)生隨機(jī)數(shù)i，并以此隨機(jī)數(shù)作為該CNC此次發(fā)生故障的位置，CNC將在其進(jìn)行第i次工作時出現(xiàn)故障。故障發(fā)生后（我們認(rèn)為CNC在第i次上下料結(jié)束之后開始進(jìn)行加工的一瞬間進(jìn)入故障狀態(tài)）該CNC機(jī)器工作剩余時間變?yōu)?0-20分鐘內(nèi)的任一數(shù)值，RGV將利用此數(shù)值重新計算該CNC的投料優(yōu)先等級，重新進(jìn)行工作排序。

2 模型的建立與求解

2.1 單工序無故障模型

考慮到加工時間遠(yuǎn)大于移動時間，在獲得最大生產(chǎn)效率的情況下，CNC在中途無等待，RGV將連貫地依次為所有CNC上下料并清洗熟料，此時消耗時間最少，為理想時間Q。在單工序的作業(yè)中，物料在每一臺CNC上加工都是等價的。如果不對RGV的運(yùn)行方式做出相應(yīng)控制，系統(tǒng)是雜亂無章的，時間分配不合理。

針對單工序的無故障連續(xù)工作，在題設(shè)假定RGV接受指令不會暫停的前提下，我們在python中建立二維數(shù)組表示CNC機(jī)器進(jìn)行仿真，0表示閑置，1表示工作，上面一排代表偶數(shù)號機(jī)器，下面一排代表奇數(shù)號機(jī)器。根據(jù)貪心算法，RGV計算么它到每個閑置的CNC分別所用時長并加上上料時間，選取其中最短時間者進(jìn)行上料，開始的一輪上料時，不難發(fā)現(xiàn)RGV為CNC上料為順序方向。完成第一輪的上料后采用貪心算法，當(dāng)CNC在#7和#8中間，此時立馬判別每臺CNC加工物件所剩余的時間與RGV移動到該CNC所需時間以及第二次上下料（包括清洗）的時間三者之和Ti（i=1，2，3，4，5，6，7，8），選min{Ti}的CNC作為目標(biāo)對象，馬上移動到該CNC進(jìn)行等待，這就是一輪循環(huán)，此時CNC工作時間達(dá)到最長。第一輪的上料不存在等待下料與清洗的過程，不囊括在循環(huán)中。每一個工件的下料清洗，RGV都要經(jīng)過該循環(huán)。

2.2 單工序有故障模型

針對有概率出現(xiàn)故障的單工序情況，根據(jù)1%的故障發(fā)生率，仿真開始前我們先分別對八臺CNC機(jī)器進(jìn)行故障發(fā)生信號進(jìn)行隨機(jī)選取，在1-100范圍內(nèi)產(chǎn)生隨機(jī)數(shù)i，并以此隨機(jī)數(shù)作為該CNC此次發(fā)生故障的位置，CNC將在其進(jìn)行第i次工作時出現(xiàn)故障。依據(jù)模型假設(shè)我們認(rèn)為CNC在第i次上下料結(jié)束之后開始進(jìn)行加工的一瞬間進(jìn)入故障狀態(tài)，故障發(fā)生后，該CNC機(jī)器工作剩余時間變?yōu)?0-20分鐘內(nèi)的任一數(shù)值，RGV將利用此數(shù)值重新計算該CNC的投料優(yōu)先等級，重新進(jìn)行工作排序，貪心算法將其維修的時間等同于加工的時長，但并未加工出熟料。

3 模型實用性與算法有效性檢驗

3.1 針對單工序無故障

根據(jù)仿真，當(dāng)?shù)谝惠喩狭辖Y(jié)束后，RGV在#7和#8之間，此時立馬判別每臺CNC加工物件所剩余的時間與RGV移動到該CNC所需時間以及第二次上下料（包括清洗）的時間三者之和Ti（i=1，2，3，4，5，6，7，8），選min{Ti}的CNC作為目標(biāo)對象，馬上移動到該CNC進(jìn)行等待。

3.2 針對單工序有故障

針對有概率出現(xiàn)故障的單工序情況，建立“災(zāi)難-凍結(jié)”模型，我們在仿真過程中對每臺機(jī)器加上了1%的災(zāi)難系數(shù)信號，在1～100的整數(shù)中選取一個作為故障發(fā)生信號，稱為災(zāi)難因子，隨機(jī)函數(shù)如果選中則該信號，則故障發(fā)生，機(jī)器進(jìn)入修復(fù)時間，隨后延遲了上下料時間，在模型的循環(huán)中將修復(fù)時間等效于工件加工時間的增加，但沒有下料，因為該工件報廢，需重新上料，由此實時調(diào)整動態(tài)調(diào)動模型。

4 作業(yè)效率和模型評價

4.1 作業(yè)效率

從實際出發(fā)，定義作業(yè)效率=實際產(chǎn)出工件個數(shù)/理想產(chǎn)出總個數(shù)*100%，作業(yè)效率η=n/（8*3600/加工一道工序所用時間），由此計算出非故障情況下三組數(shù)據(jù)的作業(yè)效率分別為90.44%；90.05%；91.10%，出故障情況下三組數(shù)據(jù)的作業(yè)效率分別為88.48%； 87.50%；89.66%。

4.2 模型評價

調(diào)度模型利用了貪心算法進(jìn)行仿真，能迅速得到答案，在CNC個數(shù)較少的情況下，可以簡化為無等待的往返循環(huán)模型，有效節(jié)約了RGV的利用時間，提高生產(chǎn)力。

貪心模型以其準(zhǔn)確性優(yōu)的特點可以推廣到整條生產(chǎn)線，不限于8臺CNC的工作生產(chǎn)系統(tǒng)，有效解決了當(dāng)RGV返回起始點途中可能出現(xiàn)距離更近的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