基于仿真優化模型的智能RGV 動態調度策略

李彬璠，郭 麗，楊騰飛，李 順，劉昊博

（1.北京機械工業自動化研究所，北京 100120；2.北自所（北京）科技發展股份有限公司，北京 100120）

0 引言

近年來，隨著我國大力推廣智能制造產業的發展，自動化設備的數量逐漸增多，在國民經濟中的各領域被廣泛應用。其中RGV（有軌制導車輛）與CNC（計算機數控機床）是比較常見的兩種設備。但其組合使用所涉及的時間利用率問題目前尚未解決，直接影響了生產效能。

針對這一現狀，首先進行了文獻調研，文獻[1～5]更多針對單目標的RGV調度，即只需要一道工序加工的產品，學者們利用雙重著色賦時Petri網構建系統實時模型，利用排隊論等提供一種有效的途徑，研究的相對比較成熟。而對于兩道工序的加工研究較少，時間利用率很多情況下達不到最佳狀態。因此本文以一個巷道一臺RGV和8個數控機床的組合為例，分別對一道工序和兩道工序的不同調度策略展開時間利用率的研究，通過模型數據分析，最終提出一種時間利用率較高的解決方案。實例應用的效果驗證了該策略的可行性、便捷性和高效性。

1 模型假設

1）RGV在做往復運動時的運行狀態、行走過程以及等待過程中的狀態相同，且對系統通知的接收頻率相同，RGV做勻速直線運動。

2）假設當CNC發出制料請求時，傳送帶上的物料及時、有效送達至CNC前方。

3）車間設施正常，工作的安全性可靠，且RGV在工作中不發生故障。

4）CNC在整個調度運行周期中有故障發生時，系統停止運行，對調度優化過程不產生影響。

2 模型的建立與求解

2.1 指標的選取

為分析在一般情況下RGV的動態調度，我們通過機理分析法選定了工作效率、時間利用率和工作完成數量三個指標作為動態調度的研究方向。綜合考慮工作期間RGV的工作時間、等待時間與故障時間對三大指標完成度的影響，進行仿真建模。選取指標后通過EM-plant軟件完成的仿真圖如圖1所示。

圖1 RGV通行3D仿真圖

2.2 符號說明

表1

2.3 模型的建立

2.3.1 一道工序

1）一道工序的模型建立

一道工序的模型主要使用了排隊論模型，通過對排隊論模型的框圖分析，我們建立的流程如圖2所示。

圖2 基于排隊論模型的流程框架

對于整個搬運過程，滿足以下條件：由于CNC發出請求的次數為無限次，故該等待時間服從指數分布；當CNC發出請求時，如果RGV當前正在工作，CNC會排隊等待；每臺CNC之間是相互獨立的；CNC發出請求的間隔時間分布及其數學期望、方差等數字特征都與時間無關；排隊方式為單列不循環隊列；每次只能有一臺機器提供服務；服務過程是先到先服務方式；服務時間等效為CNC發出請求到RGV收到訊息完成一次工作的時間，由于CNC發出請求的隨機性和RGV接受任務時位置的不確定性，該時間指數分布。

可見，本系統屬于發出請求時間為指數分布、服務時間為指數分布、單服務臺、等待制系統的排隊論問題，以Kendall 記號表示為 M/M/1/∞/∞/FCFS。設請求為泊松流，請求相繼發出時間服從參數為λ的負指數分布，服務時間服從參數為μ的負指數分布，則服務強度ρ及請求平均排隊長 L分別如式(1)所示：

服務強度表示單位時間（小時）內發出請求的CNC與單位時間內RGV能夠處理CNC的個數的比值。

其中平均排隊長L反映了隊列容器的平均容量，在這里表示空閑的CNC數量，其大小直接反映系統是否會產生阻塞。

2）變量計算

在此情況下，由于偶數編號CNC一次上下料所需時間要大于為奇數編號CNC一次上下料所需時間，故工作時間單獨考慮。則有：

當一次工作端為奇數時，此時上下料所用時間為：tupdo=todd；

當一次工作端為偶數端時，此時上下料所用時間要大于奇數端所用時間，即為：tupdo=teven。

由于只存在一輛自動引導車機器，故不存在出貨輸送系統堵塞的現象，機器不存在排隊的問題，因此穿梭車一個工作周期的時間即一次搬運的時間為機器運行一周的時間與機器完成一次工作時間之和。這里我們假定Twait為5min，則有：

則單位時間內CNC發出的請求為：

單位時間內CNC完成加工貨物的數量為：

2.3.2 兩道工序

這里我們假定只有第一次的加工過程需要等待，其余的加工過程都在循環工作中完成，且每次加工過程中都存在其他CNC工作。假設第一次加工過程時間為500秒。

由于兩道程序的加工具有極強的選擇性，情況錯綜復雜，故現假定兩種情況：一是假定奇數號機床完成第一道工序，偶數號機床完成第二道工序。這里我們采用了Floyd算法計算得出最短路徑，再通過最短路徑求得服務率和時間利用率；二是假定編號為1的CNC完成第一道程序，同時相鄰的CNC安裝不同的刀片進行第二道工序的改造，以此類推。而這種情況下，每四臺CNC又產生了兩種組合方式中，即相鄰兩臺CNC作為一個組合，或交叉方向的兩臺CNC為一個最優組合，從而進行服務率的計算。

在這里，我們將第二種情況單獨列開，于是產生了三種情境。

1）最短路徑下的RGV動態調度策略

對于第一種情況，我們采用了Floyd算法來求得最短路徑。

設圖G=(V，E)，xij表示邊（ζi，ζi）邊上的權（即為RGV到CNC的距離），若ζi和ζi不相鄰，則xij=+∞，用ηij表示頂點ζi和頂點ζi的最短距離。使用Floyd算法來計算ηij最短距離矩陣，步驟如下：

（1）輸入圖G權矩陣X，對所有的i，j，有ηij=χij，k=1；

（2）跟新ηij，對所有的i，j，若ηik+ηkj＜ηij，則令ηij=ηik+ηkj；

（3）若k=n算法終止，否則轉式(2)。

假設RGV的速度固定為υ（單位：m/h），RGV從起始位置ζi到CNC的位置ζj的時長為，由于從起始點i到CNC所在地j的RGV數量只有1，則CNC總等待時長為：

求得最短路徑行走路線如圖3所示。

圖3 RGV選擇最短路徑時的行走路線仿真

為尋求在一個固定班次內達到最大的時間利用率，我們令RGV在完成第一道工序且等待“半成品”完成后立刻轉入第二道工序（此過程不需要移動），在第二道工序加工過程中，RGV向后移動尋找下一生料，進行下一次的加工過程，則有：

其中，tupdo為一次加工過程中對于第一道工序與第二道工序的上下料時間之和，todd為一次加工過程中奇數號機床完成的第一道工序的上下料時間，teven為一次加工過程中偶數號機床完成的第二道工序的上下料時間之和。

故對于完成n件產品所需要的工作總時間，則有：

其中，T1表示完成n件產品所需要的工作總時間，twash為第二次工序過程中的清洗過程所需時間，twork為第一道工序加工所需時間，tml為RGV移動一個單位所需時間。

2)“相鄰組合”路徑下的RGV動態調度策略

對于第二種情況中的“相鄰組合”，為獲得最大時間利用率我們選取最有利的地理條件進行組合，將相鄰的兩組CNC相互組合，共同完成一個產品的加工，計算最終的時間利用率。

對于此種情況，若考慮RGV在編號為1-4的CNC間進行移動所形成的往復運動，則對于RGV的移動過程以及能源的消耗倍增，從而對時間利用率會產生負面影響。故我們假定RGV在行駛過程中保持直線行駛，到達終點后掉頭行駛，且保持勻速，故RGV所做運動為勻速直線運動，所行駛軌道為直線軌。即一個RGV系統中只有一輛RGV運行在一條直線形非閉合軌道上。在這樣的系統中也不存在RGV碰撞的問題。

圖4 RGV選擇相鄰路徑時的行走路線仿真

其中，T2表示完成n件產品所需要的工作總時間。

由上式可以看出，此種情況在與第一種情況占用時間相同的情況下，完成的成品數較少，從一次函數的角度來看，當生產件數越多時，第二種情況所要花的時間越長。大大減小了時間利用率。這與我們想要在規定班次內得到最大時間利用率的同時獲得更多產品的愿望相違背，故該模型的利用度小于第一種情況。

3)“交叉組合”路徑下的RGV動態調度策略

現在考慮第二種情況中的“交叉組合”。為了使在一定時間內RGV的移動率更大，我們選取最有利的地理條件進行組合，以編號為1的CNC作為初始機器，開始進行第一道工序的加工，其次轉到編號為3的機器進行第二道程序的加工，以此類推，求得最終的產品數量。

在此種情況下，由于往復運動的復雜性使得RGV在移動過程中循環次數變多，故假定RGV沿直線方向勻速行駛，行駛至終端進行掉頭，繼續進行其他生料的加工，且此過程仍假設在完成第二道工序后直接進入下一成品的加工過程種，故仍使RGV繼續運動，而“半成品”的加工過程所用時間包含于此。故RGV所做運動仍為勻速直線運動，所行駛軌道仍為直線軌。

圖5 RGV選擇交叉路徑時的行走路線仿真

則有：

其中，T3表示完成n件產品所需要的工作總時間。tchange表示RGV在由奇數端切換到偶數端前臂的擺動過程所用時間，且，tchange≥0通過計算可知，該情況下與情況一相比，同樣在時間相似情況下成品數較少，故時間利用率降低。且在于第二類情況相比下，由于tchange≥0，可以得到比情況二效率更為低下的作業效率，故該模型利用度也不高。

綜合三種情況下的所需時間，我們發現第一種方案更節約時間，而且所加工產品數目越多，優勢就越明顯。

2.4 模型的實用性檢驗

1）一道工序

在這里，我們根據所列模型與參考數據做出了各類數據的參考范圍，利用MATLAB軟件隨機生成了一些數據，代入算法進行檢驗求解得到相關數據，并利用SPSS求得測試結果如表2所示。

表2 通過SPSS計算得到的三組測試結果

由于數據的大量化我們無法一一列舉出所有可能的情況，且隨機數在生成過程中無法遵循一定的規律，故我們隨機抽取了部分數據作為樣本，由樣本數據得，機器的每班次能夠得到的成品數大致在350～420（單位：件）之間。

經過對數據的大規模分析，λ的值的取值在[30，40]、μ的值在[45，55]內系統的效率達到最大。此時ρ的強度可達到70%以上，時間利用率γ在80%以上。通過SPSS的正態檢驗得知成品數、時間利用率、服務強度、L的值均大于0.05，數據符合正態分布，該模型靈敏度較好。

2）兩道工序

對于兩道工序的加工情況，我們仍選用一道工序時通過MATLAB產生的隨機數作為參考數據，取樣后將數據代入模型算法中進行計算，得到表3所示。

表3 通過SPSS計算得到的三組測試結果

由表3可以看出，盡管我們選用了“最短路徑”的模式進行產品制作，但由于中間過程的等待時間較長，使得我們得到的成品數的數量大大降低。成品數數量降低帶來的結果是λ與μ的倍減；但由于RGV工作時間相對于一道工序時沒有變化，故與時間有關的參數ρ、γ未發生很大改變。

接下來結合數據，將我們建立的模型加以應用，使用SPSS軟件進行數學運算，得到以下的數據結果。

由表4可以看出，系統的服務強度與時間利用率在一定程度上仍未發生較大波動，而與模型測試的案例類似，系統在完成工作后得到的成品數相對于一道工序的情況仍發生了急劇下滑。故我們考慮模型出現的數據差異很大程度上歸因于只考慮了距離的最短問題而忽略了等待的時間問題。

表4 有兩道程序時的數據模型結果

綜合表中數據及算法模型中所選取的隨機數進行模擬的結果可以得到，在完成一道工序的情況下，我們優先選擇最短路徑，以此達到最大時間利用率；當存在兩道工序時，由于選擇的多樣性，盡量采取“就近原則”，并進行配對組合，從而實現產品的加工過程，達到動態分配。

3 結語

該模型可真實還原工作過程，所用算法聯系性，理論性較強，特別是目前機器化大生產的普遍化，我們的模型可以作為許多工廠在分析解決產品加工問題時的一種參考。當然假設的變量主觀性較強，會產生一定的誤差。提升整體性，使用更先進的算法將是未來的改進方向。