不確定性環境下軌道自動導引車動態調度

李國民 高 亮 李新宇

華中科技大學機械科學與工程學院，武漢，430074

0 引言

軌道自動導引車（rail guided vehicle，RGV）是一種在智能車間或自動化立體倉庫中沿著預設軌道運行的物料運送工具，RGV在物流系統和自動存儲與檢索系統中的應用較早［1－3］。隨著自動化系統在煙草、金融、醫藥、日化等行業的廣泛應用，對輸送設備的需求也日益突顯。

為提高物料運輸效率，增加車間產能，企業逐步引入現代化的RGV物料搬運工具。CHEN等［4］模擬柔性制造系統的上料／卸料操作，并闡述了RGV系統的智能生產調度和控制框架的具體應用；JAIGANESH等［5］闡述了自動導引車（automated guided vehicle，AGV）的 物 流 系 統；HU等［6］對線性跟蹤自動貨運處理系統的多載量RGV進行研究，考慮雙邊上料／卸料操作的最優路徑，并指出最小化能源消耗目標的同時要考慮避免沖突和時間窗約束。NEJAD等［7］對RGV上下料進行了研究。

隨著車間作業規模的擴大，人們結合不同學科理論和優化算法開展了提升RGV綜合調度性能的研究，如約束理論［8］、粒子群優化算法［9-12］、遺 傳 算 法［13－14］、組 合 拍 賣 算 法［15］、模 糊算法［16］、模 擬 退 火 算 法［17］。FAZLOLLAHTABAR等［18］從周期角度進行研究以減少延遲造成的損失；YILDIZ等［19］也從周期角度對加工單元進行研究。FOUMANI等［20］對多功能RGV加工單元進行研究，其目標為最小化RGV的加工周期或者最大化車間生產效率，同時，為計算加工單元產能，考慮上坡和下坡排列目標函數的下界。

完全遍歷路徑規劃算法（complete coverage path planning，CCPP）的調度規則是在滿足某種性能評價指標最優的前提下尋找一條在設定區域內從始點到終點且經過所有可達點的連續路徑。該算法在自動化系統中易于實現且具有實用性、可重復性、效率高等特點，在機器人領域得到廣泛應用，主要涉及機器人清洗、采礦、檢查、探測等［21－24］。

從目前的文獻來看，RGV動態調度大多是在理想狀態下進行研究的，沒有考慮不確定性環境下由于存在異常斷刀、刀具壽命到期、零件報廢、機器故障等一系列不確定性因素導致的CNC設備（以下簡稱CNC）停機問題。為此本文基于CCPP調度規則對生產車間不確定性環境下RGV動態調度問題進行研究。

1 問題描述及數學模型

1.1 問題描述

某手機后殼加工車間有10條產線，每條產線包含10個加工單元，每個加工單元配備若干臺CNC（編號 Mi，i＝1，2，…，N）和1臺 RGV（圖1）。CNC發出物料需求信號并通過中央控制系統將信號傳送給RGV，RGV檢測物料需求信號并依據一定規則為CNC上下料。RGV沿直線型軌道運行，安裝在RGV上的機械手執行上下料作業。由于不同加工單元的RGV調度可以獨立進行，為了簡化問題，本文僅以車間中的1個加工單元為研究對象。定義RGV依次為加工單元N臺CNC全部上下料完畢為1個作業周期，RGV完成1個作業周期包含以下5個操作過程。

圖1 加工單元布局圖Fig.1 The layout of manufacturing cell

（1）RGV用機械手的一個手爪從來料頂升Tray盤內抓取未加工的物料移至Mi，用另一個手爪在Mi內抓取已加工物料A，然后將未加工物料放置于加工位置。

（2）上料完畢后，機械手將抓取的物料A移至RGV自帶的清洗槽，取出已清洗完畢的上一片物料B，并把物料A放入清洗槽，然后把物料B放置于對面出料頂升的Tray盤內。判斷Tray盤是否裝滿，若裝滿則出料頂升Tray盤下降并將Tray盤放置于傳送帶上；若未裝滿，則不作處理。

（3）RGV判斷來料頂升Tray盤內物料是否取完，若取完，則吹氣清理空的Tray盤，并將其轉移到出料頂升臺，來料頂升從傳送帶頂起Tray盤；若未取完，則不作處理。

（4）RGV檢測物料需求信號，依據調度規則移動至下一臺需要上下料的CNC設備Mi＋1。

（5）移動至Mi＋1時，若Mi＋1加工完畢，則RGV直接進行上下料作業；否則，RGV等待Mi＋1加工完畢后進行上下料作業。

在加工生產過程中，可能會因CNC故障、異常斷刀、刀具壽命到期、切削液異常等因素導致CNC報警甚至停機，待CNC維修完畢或者更換刀具確保能夠正常加工生產后再次進行加工作業。加工過程中刀具會有不同程度的磨損，導致加工產品尺寸不合格，這時就必須對CNC的刀具進行調整和補償，從而致使CNC停機。在正常加工情況下，RGV會按照原有順序依次為CNC進行上下料作業，但當某臺因異常情況而停機的CNC維修好可重新加工時，由于RGV的排他性，CNC之間存在叫料競爭，即RGV同一時間只能為1臺CNC上下料。目前車間采用的是就近調度規則，即RGV作業完成后檢測所有發出物料需求信號的CNC，選擇離其最近的CNC進行上下料作業，但是采用這種調度規則時存在CNC等待的現象。如何確定RGV調度規則、確定調度期內CNC上下料順序、提高CNC產能是值得研究的問題。

1.2 基本假設

調度問題必須滿足以下假設：①起始時刻RGV在M1與M2之間的軌道位置，所有CNC處于空閑狀態；②1臺CNC同一時間只能加工1片物料，每片物料只能被1臺CNC加工；③RGV同一時間只能為1臺CNC進行上下料操作，不考慮RGV故障的情況；④物料使用傳送帶傳送，生產過程中不存在缺料現象；⑤每個Tray盤只能放置2片物料；⑥RGV軌道是雙向的，CNC之間的間距固定。

1.3 參數和變量

所涉及的集合、變量和參數見表1。

表1 相關參數Tab.1 Related parameters

1.4 數學函數

隨著生產的進行，CNC會出現停機等待的現象，不恰當的調度規則會導致RGV路徑迂回，增加RGV行走時間，進而增加RGV的上下料周期，一旦RGV的上下料周期超過CNC的加工周期，會導致CNC停機等待，影響CNC產能。因此，本研究的目標是，在確保穩態期RGV周期小于CNC周期的前提下，最小化RGV的過渡周期。基于上述參數設置，該RGV動態調度數學模型如下：

約束條件：

式（1）表示最小化過渡期時RGV周期，保證RGV能夠及時為CNC進行上下料作業。其中RGV周期包含加工單元內所有CNC的上下料時間和所有RGV洗料時間、移動Tray盤時間、RGV在CNC間的移動時間及等待時間；式（2）保證Tray盤只能放置2片物料；式（3）表示通過調整CNC上下料順序，在CNC上下料周期穩定后，存在部分序列的RGV周期小于CNC加工周期。式（4）、式（5）是為了最大化加工單元CNC數量，保證RGV與CNC數量能夠得到有效配置，在此配置機制下，RGV能夠在CNC加工結束之前返回，保證CNC不因缺料而停機。

2 完全遍歷路徑規劃算法設計

完全遍歷路徑規劃類似于旅行商問題（traveling sales-man problem，TSP），要求移動機器人在滿足一定的指標下完全覆蓋目標環境中的可達區域［25－26］。RGV 動態調度采用 CCPP算法調度規則的思想是：對維修完成的CNC遍歷后插入到正常工作的CNC序列中，計算各遍歷序列的穩態期和過渡期的RGV周期，在滿足TRCi≤TCC的前提下，最小化RGV的過渡周期。若不存在TRCi≤TCC的情況，則對正常的加工序列進行重排。CCPP算法的流程見圖2，具體描述如下。

圖2 完全遍歷路徑規劃算法流程圖Fig.2 The flow chart of CCPP

（1）初始化集合，初始化正常工作CNC集合W＝ ｛wiwi∈N，i＝1，2，…，l｝、故障CNC集合F＝ ｛fifi∈N，i＝1，2，…，m｝、維修完成CNC集合R＝ ｛riri∈N，i＝1，2，…，n｝，其中，N ＝l＋m＋n。

（2）判斷維修完成CNC集合R是否為空，若為空則RGV按照原有CNC加工順序進行上下料作業；否則，將集合R中的Mri按照維修完成時間依次遍歷插入到正常加工的CNC集合W中，得到新的CNC集合：W′＝（W∪R）。

（3）計算集合W′各個序列在穩態期時RGV周期TRCi和過渡期時 RGV 周期 TRC′i，若 TRCi≤TCC，則從集合W′中選擇過渡期RGV周期最小的CNC上下料作業序列作為CCPP算法的可行解，轉步驟（6）；否則，對正常加工的CNC集合W 進行重排，轉步驟（4）。

（4）檢測維修完成的CNC集合R中Mri對面正常加工Mwi的鄰位是否有單側上料（相對的兩臺CNC上下料順序不相鄰）的Mi，若有，則將最早完工的單側上料Mi移至其對位CNC的鄰位，并將Mri放置于Mi的位置，得到新的CNC集合W″，若TRCi≤TCC則將該集合作為CCPP算法的可行解；否則，從正常加工的CNC集合W中尋找最早完工的單側上料Mi并移至其對位CNC的鄰位，同時將Mri放置于其對位CNC的鄰位得到集合W″，若TRCi≤TCC則轉步驟（6），否則轉步驟（5）。

（5）將集合W″中最早完工的單側上料Mj移至其對位CNC的鄰位，若TRCi≤TCC則轉步驟（6），否則執行步驟（5）。

（6）從集合R中移除維修完成的Mri。

（7）重復步驟（1）～步驟（6）。

特別說明的是，基于CCPP算法的重排是依據車間實際參數而提出，并依據式（3）～式（5）計算RGV服務CNC的數量，即RGV為加工單元內CNC上下料結束后返回第一臺需要上下料的CNC時，該臺CNC恰好加工結束或者即將加工結束，以保障CNC不出現等待的現象。所以，若CNC上下料順序混亂導致CNC等待，通過調整CNC的上下料順序必有TRCi≤TCC存在。

3 算例分析

由于直接計算目標函數值、更新已有和未來的上下料任務等過程非常復雜，故對智能車間加工單元N臺CNC分別采用就近調度規則、CCPP算法并運用Java語言進行建模仿真。

3.1 參數設置

在進行模擬仿真之前，首先要確定系統輸入參數，恰當的輸入參數對生產車間的產能具有重要影響，依據車間生產現狀，對RGV動態調度系統參數進行統計，分別收集各指標的20組數據并取均值見表2。

表2 RGV動態調度參數值Tab.2 The parameters values of RGV

本文對車間加工單元10H的加工狀況進行模擬。在模型中輸入CNC停機數據，包含停機CNC編號（e）、停機開始時間（tF）和停機結束時間（tR），停機數據是從智能車間監控系統中實時收集的，隨機選取一組CNC停機數據，見表3。在1 500s時編號為5的CNC開始停機，在1 797s時該CNC維修結束，該臺CNC需要按照本文提出的CCPP算法重新加入加工序列。

表3 10H內停機數據Tab.3 Downtime data in 10H s

3.2 方案分析與評價

在表2參數設置的情況下，通過式（3）～式（5）計算得加工單元CNC臺數N 最多為8，即1臺RGV為8臺CNC上下料的配置比較合理，模擬CCPP算法下加工單元的加工過程得到CNC的上下料順序見表4。

由表3CNC停機數據和表4CNC加工序列可以看出，加工單元8臺CNC均未出現停機狀況時，CNC的上下料初始順序為M1—M2—M3—M4—M5—M6—M7—M8；第2 400s時，M7出現停機狀況，加工單元CNC的上下料順序變為M1—M2—M3—M4—M5—M6—M8；第2 588s時M7處理完畢，需要重新加入正常工作CNC上下料序列中，通過CCPP算法模擬得到CNC上下料順序為M7—M1—M2—M3—M4—M5—M6—M8，該順序表示RGV先給M7上下料再為M1上下料，依此類推。

表4 CNC加工序列Tab.4 CNC machines scheduling sequences

在就近調度規則、CCPP算法兩種不同規則的調度情況下，對表3CNC故障數據進行模擬，兩種方案在加工單元10h內8臺CNC的產能見表5。通過表中數據可以看出，與就近調度規則相比，采用CCPP算法時CNC總產能較高。該數據表明在產能方面，CCPP算法優勢明顯，能夠達到提高車間產能的目的。

表5 CNC產能對比Tab.5 The comparison of CNC capacity pcs

另外，隨機選取5組不同時間段的CNC停機數據，對加工單元8臺CNC加工狀況進行模擬，兩種調度規則時RGV行駛總路程見表6。

表6 不同停機情況下RGV行駛總路程對比Tab.6 Comparison of total distance of RGV under different shutdown conditions m

由表6可以看出，在5種不同時間段停機狀況下，采用CCPP算法時RGV平均總路程明顯少于就近規則下的RGV平均總路程，該數據表明CCPP算法能夠很好地對RGV進行調度，減少RGV行駛路程，避免RGV因路徑迂回導致的CNC停機等待現象的發生。

因此，在車間調度過程中，不論是在產能提升方面還是在RGV總路程減少方面，采用CCPP算法的RGV動態調度效果都優于車間現行的就近調度規則。

4 結語

本文針對智能車間RGV作業流程進行了詳細分析，建立了在穩態期存在RGV周期小于CNC周期的前提下，最小化RGV過渡期的數學模型；通過模擬驗證了CCPP算法優于車間現行的就近調度規則，能夠實現增加CNC產能、減少RGV行駛路徑的目的，避免RGV因路徑迂回導致CNC停機等待，為直線型軌道自動導引車的實際規劃設計提供依據。