基于最小等待時間和圖游走模型的RGV動態(tài)調(diào)度策略

徐海龍 劉樹樹 牛學果 司 睿 李夢璇

（1.蘭州交通大學交通運輸學院，甘肅 蘭州 730070；2.蘭州交通大學土木工程學院，甘肅 蘭州 730070）

隨著自動化技術和制造業(yè)的進步和發(fā)展，智能化、自動化、柔性化[1]為三個主要發(fā)展趨勢。柔性作業(yè)車間調(diào)度以其以需定產(chǎn)和定制模式向顧客提供優(yōu)質(zhì)服務，車間產(chǎn)品加工的效率逐年提升，能更好地完成車間的生產(chǎn)計劃。但是，傳統(tǒng)的柔性車間調(diào)度策略往往忽略了加工產(chǎn)品的個體化差異以及單個產(chǎn)品每道工序之間的銜接問題，使得智能化機器設備沒有得到充分利用。如果從單個產(chǎn)品工序之間的相互等待時間最小為切入點，可使調(diào)度策略得到優(yōu)化，增加可行性。

目前有很多文獻著述了關于柔性車間的調(diào)度問題，大部分趨于加工時間調(diào)整和多目標優(yōu)化的動態(tài)調(diào)度[2-4]，以近似求得此NP難問題的最優(yōu)解。然而，對于加工產(chǎn)品的工序銜接和時間順序調(diào)整方面的文獻相對不多。文獻[5]針對模糊柔性車間調(diào)度問題，提出一種混合超啟發(fā)式遺傳算法進行求解。文獻[6]針對虛擬制造網(wǎng)絡中的車間調(diào)度問題，提出了一個非合作博弈調(diào)度優(yōu)化模型。文獻[7]為了實現(xiàn)機械加工車間的節(jié)能優(yōu)化運行，建立了節(jié)能柔性作業(yè)車間調(diào)度模型。

本文主要基于圖論知識進行建模，研究了CNC智能加工系統(tǒng)，分析論證了基于圖游走和最小等待時間的調(diào)度模型和策略，同時，利用JAVA語言進行了多線程并行編程，模擬RGV的運行以及各個CNC工作臺的狀態(tài)，驗證調(diào)度策略的可行性和相對高效性，評價系統(tǒng)的作業(yè)效率。

1 問題描述和數(shù)學模型

1.1 問題描述

智能車間加工系統(tǒng)[9]主要是由數(shù)臺計算機數(shù)控機床（Computer Number Controller，CNC）、1臺固定軌道自動引導車（Rail Guide Vehicle，RGV）、1條RGV固定軌道、2條分上下料的傳送帶等設備組成。RGV是一種智能小車，可根據(jù)特定指令自動運行。并利用自帶的機械手臂、手爪等裝置，完成產(chǎn)品的上下料、清洗等作業(yè)。對于該系統(tǒng)，需要設計合理實用的調(diào)度策略，提高平臺工作效率以增加產(chǎn)出率。本文針對一道工序、兩道工序加工和CNC故障情況進行研究，建立調(diào)度數(shù)學模型并設計求解算法，并用JAVA進行仿真，驗證了其可行性。

1.2 模型建立

將8臺CNC假設為8個節(jié)點，由此構成一個圖，邊表示RGV在兩節(jié)點間可移動。在RGV小車在每進行一次作業(yè)，其他的CNC工作臺發(fā)出請求后，經(jīng)過篩選和權值的判斷，做出相應的命令執(zhí)行。在車間調(diào)度問題中，它是一個多項等式和不等式約束下的組合優(yōu)化問題。從計算時間的復雜度看，它可以看作是NP難問題，隨著調(diào)度規(guī)模數(shù)的增加，問題的可行解的數(shù)量呈指數(shù)級增加。

目標是在一定時間內(nèi)要獲得最大的加工產(chǎn)品數(shù)，就要使得總的等待時間越少?？偣采a(chǎn)的總共件數(shù)為：

每臺CNC生產(chǎn)的臺數(shù)由（2）式?jīng)Q定：

由（1）式：

目標追求最大化N pro，等價最小化，所以最小化目標函數(shù)為：

式（1）～（4）中：N pro—加工總產(chǎn)品數(shù)（個）；k—CNC臺數(shù)（臺）；ni—第i臺CNC加工產(chǎn)品數(shù)（個）；T—一個工作周期（s）；—第i臺CNC等待時間（s）；—第i臺CNC工作時間（s）；Twait—總的等待時間（s）。當該系統(tǒng)加工兩道工序時，只需更改目標函數(shù)中的相應等待時間。如式（5）：

當該系統(tǒng)加工工序發(fā)生故障時，如式（6）：

2 求解策略算法設計

針對單工序產(chǎn)品，圖鄰接矩陣的權值為節(jié)點間小車移動和上下料時間之和。當有1臺CNC發(fā)出請求時，RGV對該CNC進行相應作業(yè)；當有多個節(jié)點發(fā)出請求時，按照總體最小等待時間的策略選擇RGV移動的位置。RGV在接收到兩道工序混合發(fā)出的請求之后，按照考慮了不同刀具平臺的等待時間，根據(jù)緊后工序依賴于緊前工序的完成的均衡原則和權值進行判斷，從而選擇最優(yōu)的路徑。

對于系統(tǒng)故障的模擬和處理時間，本文均采用了生成隨機數(shù)的方法。規(guī)定當隨機產(chǎn)生的數(shù)小于0.01時，CNC便會發(fā)生故障。經(jīng)人工恢復（10～20 min）后重新進入選擇隊列之中。以單工序為例，如圖1所示，多臺CNC發(fā)出請求，選擇邊權最小的路徑，移動至相應CNC。算法設計如下：

圖1 三個CNC發(fā)出請求狀態(tài)

（1）相關參數(shù)初始化，請求隊列R={1，2，…，8}，RGV在第一臺CNC的位置Gp=1，加工產(chǎn)品數(shù)為i=0，相關時間記錄表Tb，Artnum={0，0，0，0，0，0，0，0}//每臺CNC計數(shù)。（2）獲取當前系統(tǒng)的時間。為每個CNC上料，new workThread（k，art[k]）.start；// 啟動工作并行線程。并記錄相關CNC平臺上下料的時間。（3）RGV.scan（R）；//掃描請求隊列，若為空，則處于阻塞狀態(tài)[10]，停止執(zhí)行。否則，執(zhí)行4）。（4）若R中只有一個元素為n，Ob=n；//找到下次工作CNC相應的編號。否則，從請求隊列R={1，2，…，8}中找到RGV智能車移動時間和對應CNC上下料時間最短的元素j。Ob=j；//找到權值最小元素。（5）RGV.move（ob，tm）；//RGV智能車用時tm移動到ob對應的CNC。RGV位置Gp=ob。（6）RGV.get（tq，Tb，art[ob]，td））；//RGV智 能車以tq的時間給ob對應的CNC上料，并在Tb表中記錄上料開始時間。（7）RGV.put（tp，ob，Tb，tpc，i）；//RGV智能車以tp的時間給ob對應的CNC下料，并在Tb表中記錄下料開始時間。i=i+1；new workThread（k，art[k]）.start；Artnum[ob]=i；//此時，i發(fā)生變化，多線程并行。（8）Tc=Sys.getCurrentTime（）；//獲取系統(tǒng)當前時間。若Tc-Tbegin＜T，T為時間周期（取為8小時）轉(zhuǎn)（3）。否則，轉(zhuǎn)（9）。（9）結束。

3 系統(tǒng)作業(yè)效率評價

在評價系統(tǒng)的作業(yè)效率時，本文采用的是產(chǎn)品模擬加工數(shù)量所用的時間與一個加工時間周期的比值。其評價模型表達式如下：

式中：Tud——上下料時間（s）；k——CNC數(shù)量（臺）。

對于模擬加工產(chǎn)品數(shù)量，本文取3～5次模擬結果的平均值。做出該調(diào)度策略下不同參數(shù)的系統(tǒng)作業(yè)效率分析。經(jīng)過JAVA仿真模擬運算結果如表1所示。

表1 不同參數(shù)系統(tǒng)作業(yè)效率統(tǒng)計表 /%

4 結語

基于圖游走和最小等待時間建立模型，抽象8臺CNC為圖的節(jié)點，以RGV游走距離和上下料時間為圖邊權值，將NP難的調(diào)度問題，通過模型和求解策略，各階段局部優(yōu)化，最終達到整體近似最優(yōu)。以圖論的相關知識建立模型，比較切合實際CNC的工作狀態(tài)。用JAVA多線程編程進行并行工作模擬，減少并驗證了實際的調(diào)度時間。多次進行模擬，消除了故障的隨機性。本文中大多數(shù)模型都是自行推導建立的，可以推廣到柔性車間的調(diào)度、小工廠的車間生產(chǎn)、智能化的選擇需求等問題。