結合貪心策略的RGV動態規劃調度模型

丁飛陽 張逸博 邱洪斌 陳勇

（浙江工業大學機械工程學院 浙江省杭州市 310032）

隨著控制工程、信息技術、機電一體化等多個領域的快速發展，工業與新興制造業開始向自動化、無人化、智能化發展，RGV（railguidevehicle）軌道式自動引導車作為一種集各種高新技術于一體可自主運行的系統，被廣泛應用于現代化生產流水線中。RGV可用于各類高密度儲存方式的倉庫，其通道可設計成任意長。使用RGV 可以提高整個倉庫儲存量，并且代替傳統叉車駛入巷道，使其安全性更高。RGV 的應用可以有效提高倉庫的運行效率，并且可以十分方便地與其他物流系統實現自動連接，按照計劃進行物料的輸送。

如何合理調度RGV，提高 RGV 系統的運行效率，是促進制造業高速發展的一個重要問題。目前有劉豐瑞等人提出的基于各種模型而形成的高效率調度策略[1]；Liu YK 等人研究了RGV-CNC 系統的作業策略[2]；Dotoli M 和Fanti MP 研究了RGV 系統的死鎖[3]；馮倩倩等人針對兩道工序的調度問題，以CNC 任務分配和RGV 路徑為決策變量，以物料剩余加工時間和RGV 狀態建立了對應的數學模型[4]；江唯等人建立了以RGV 路徑最短和移動過程中堵塞最少為目標的優化模型[5]；張明鵬等人以RGV 移動用時最短和RGV等待與工作時間最短為目標，得到了魯棒性較好的調度策略[6]；徐曉龍得出了RGV 在CNC 加工一道和兩道工序情況下的最優路徑[7]。

針對本文相同或類似背景問題，也已經有許多人建立了各式的算法和模型。牛藝璇設計了混合編碼粒子群優化的約束優化模型，雖然求解速度塊，但是推廣性差，對于更為復雜的調度情況其搜索精度會下降，容易陷入局部最優解或者無法得到可行解[8]；朱志斌等人設計了基于工序編碼的粒子群算法，但是求解得到一個班次內的加工總數并不理想[9]；李昊哲基于對蟻群算法的優化，提出了優秀指標的概念，利用指標的歸一化協助判定最優調度策略并構建了模型，但是模型中的RGV 無法在CNC 完成前或完成時到達上下料處，造成了時間浪費[10]；田繼宏等人利用最短作業優先調度算法、遺傳算法以及輪盤賭算法設計了模型，最后得到的調度策略中優先度僅依據單次作業執行的時間排序，在一些特殊情況下RGV 可能會比實際需求耗費多余的時間進行移動[11]；賈艷武等人使用最短路徑法，根據線性規劃建立了具有通用性的優化模型，但是在模型中出于清洗環節耗時相對較短而將其忽略了，導致最后調度策略與實際存在偏差[12]。

本文通過引入最短距離原則和盡快響應原則的貪心策略，對建立的動態規劃數學模型進行改進，加速了解空間的搜索進程，在保證結果可靠性的同時加快了算法的求解效率，提高了模型的實用性。

1 問題描述及分析

本文研究的問題如下，有一個智能加工系統如圖1所示，由8臺計算機數控機床（以下簡稱CNC）、1 輛軌道式自動引導車（以下簡稱RGV）、1 條RGV 直線軌道、1 條上料傳送帶、1 條下料傳送帶等附屬設備組成。RGV 的軌道兩邊等距分布四臺數控機床。其中每臺CNC 只能同時加工一個物料。RGV 根據指令能自動控制移動方向和距離，并自帶一個機械手臂、兩只機械手爪和物料清洗槽，兩只機械手可各自抓取一個物料完成上下料作業，CNC 加工完成的熟料經過清洗放至下料傳送帶即視為加工完成。RGV 在上下料、清洗過程中均不能移動。本文研究在僅一道工序情況下使加工完成一定數量物料用時最短的RGV 調度策略。

圖1：智能加工系統示意圖

對RGV 工作流程進行分析，可以發現：除了最開始的階段只需要給8 臺CNC 上生料但不需要清洗環節，剩下的工作流程中，對于RGV 車而言始終都是上下料、清洗、等待（也可以不等待，即等待時間為0）、移動四個流程的不斷重復，從而可根據每個成料加工完成的時刻將整個工作流程劃分為一個個相似的階段，每個階段都是一個子問題。而這些子問題滿足重疊性，因此可以嘗試采用動態規劃的數學思想在給定一個初始階段的規劃方案后對后續的調度進行規劃，找到最優的調度策略。

2 建立動態規劃數學模型

2.1 模型假設

（1）假設RGV 車前一階段的狀態只對相鄰的后一階段的狀態產生影響，即無后效性。因為實際生產過程中有較多不可控因素無法被狀態變量概括，從而使狀態變量失去無后效性，導致動態規劃模型失效；

（2）假設導軌兩側CNC 等距排列，間隔距離記為一個單位，且編號如圖1所示；

（3）假設作業過程中RGV 車和CNC 均不發生故障；

（4）假設RGV 車移動過程不能中斷。

2.2 符號說明

如表1所示。

表1：符號說明表

2.3 階段劃分

設需要加工n 個物料，由此前的分析，RGV 車始終都是上下料、清洗、等待、移動四個流程的不斷重復且每個階段都完成了一個物料的加工過程，從而可以將整個過程劃分為n 個階段。每個階段內RGV 車都是完成上下料、清洗、等待、移動四個流程，如圖2所示。

圖2：加工階段劃分示意圖

2.4 確定狀態變量

對于每一個階段，其狀態就是這個階段開始時RGV 所在位置以及階段的起始時刻。這里不妨用RGV 車所在機床編號表示其位置。若RGV 車在第k 階段開始時為第tk秒在i 號機床處，那么第k階段狀變量如下：

2.5 確定決策變量

這里用uk(sk)表示第k 階段當狀態變量為sk時的決策變量。RGV 車在完成清洗作業后經若干時長等待后可選擇前往1 至8 號CNC 中的任意一個，即允許決策集合Dk(sk)={1,2,3,4,5,6,7,8}。各階段決策確定后，整個問題決策序列就構成一個可行策略p1,n{u1(s1),u2(s2),…, un(sn)}。

2.6 確定狀態轉移方程

這里下一個階段狀態中RGV 車的位置就是上一階段決策變量的值，起始時刻為上一階段起始時刻加上一階段所花時間。每一階段所花時間為上下料及清洗作業時長、等待時長、移動時長之和。由此可寫出狀態轉移方程如下：

其中，表示RGV 車從i 點移動到j 點的所需時間，在本文所研究的情況下，RGV 車移動時間與移動距離有關，設tmx表示移動x個單位所需時間，Δ t(i,j)可寫成如下表達式：

2.7 確定指標函數

設RGV 車在第k 階段從sk出發，采用uk時的效益為：d(sk,uk)。由上述分析，這里的效益即時間，并且希望時間最短。因此d(sk, uk)為RGV 車在第k 階段上下料、清洗、等待、移動所花時間之和：

設V1,k(sk, p1,k)表示從初始階段到第k 階段采取策略p1,k下的時間，若fk(sk)表示從初始狀態到第k 階段狀態sk所花的最短時間，則可得以下表達式：

設RGV 從第0 秒開始工作，所以f1(s1)=0。

2.8 最終數學模型

綜上所述，以完成n 個物料加工時間最短為目標的動態規劃數學模型如下：

3 引入貪心策略

上述模型理論上可以求解得到加工n 個物料用時最短的調度策略，但這是一個具有指數復雜度的問題[13]，求解時間實測在1 小時以上。實際應用中往往將調度求解耗時也算在工作時間內，尤其在中途發生意外需要重新計算調度策略時，花費大量時間求解得不償失。因此需要找一種求解效率較高并調度策略相對較優的調度策略。

本文第二節已經將整個問題轉換為一個多階段決策問題，在每一個階段能讓RGV 根據當前CNC 狀態、RGV 自身所處位置以及調度規則直接做出一個在大多數情況下都是最優的決策，是一個更加貼合實際情況的方案。為此基于貪心算法的思想，引入了對每一個階段內的調度優化策略。

（1）最短距離原則：若當前有多個CNC 需要服務，則選擇最近的服務。因為選擇更遠的會使RGV 移動使用的總時間增加，導致CNC 等待時間變長，使總體效率降低。

（2）盡快響應原則：若當前暫時沒有需要服務的CNC，則前往最早完工的CNC 處。這個原則在多數情況下確實是響應最早完工的CNC 效率高。但出現以下情況：當最早完工的CNC 離當前的RGV位置很遠，又有比較近的CNC 完工時間稍晚于最早的那個，在這種情況下選擇最早完工的CNC 可能并不是最優解，在特定狀況下先去最近的CNC 可使CNC 總等待時間減少。但在實際過程中由于上下料也是由RGV 處理，正常情況下兩個CNC 完工時間差會大于CNC 的移動時間，因此這種情況比較少見，盡快響應原則仍然有效。

4 算法流程

4.1 初始狀態的確定

當系統開始運行時，所有CNC 都沒有熟料，即RGV 剛啟動時的唯一任務就是分別給8 臺CNC 上料。根據這一點，將啟動后的這一段過程進行分析，采用排列組合的方式求出RGV 給CNC 上料的所有組合。

剛啟動時RGV 位于1 號和2 號CNC 之間，顯然應該優先給這兩臺CNC 中的一臺進行上料，然后再去為剩余的CNC 上料，所以可得初始的組合方案數量為NUM：

4.2 算法流程

（1）對初始啟動階段排列組合生成初始調度計劃，即通過排列組合的方式求解出初始8 個階段的狀態變量集合{s1, s2,…, s8};

（2）隨機選取一個初始狀態變量集合，根據“最短距離原則”求解出此種初始解條件下的所有可行調度策略；

（3）重復（2），找出所有可行的調度策略，完成第一輪調度；

（4）給定任意一個確定的成料數n，已完成確定數量的成料所需的總加工時間最短為目標進行優化得到完成此數量的成料要求的最佳調度策略pk,n;

（5）重復步驟（4），且規定每次要求的成料數不同，計算不同成料數的最優調度策略，比較這些策略，找到出現次數最多的策略作為最終的最優調度策略;

算法的流程圖可見圖3。

圖3：算法流程示意圖

5 求解結果與對比分析

5.1 MATLAB求解結果

本文采用2018年高教社杯全國大學生數學建模競賽B 題中附件的相關數據，使用MATLAB 進行編程計算。得到的三組最優調度策略結果如表2至表4所示。

表2：第一組求解結果

表3：第二組求解結果

表4：第三組求解結果

第一組調度結果中，最后剩余88 秒的加工時間未得到利用；CNC 加工順序按照1 →3 →5 →7 →8 →6 →4 →2 進行循環。

第二組調度結果中，最后剩余188 秒的加工時間未得到利用；CNC 的加工順序同第一組，按照1 →3 →5 →7 →8 →6 →4 →2進行循環。

第三組調度結果中，最后剩余52 秒的加工時間未得到利用；CNC 的加工順序依然按照1 →3 →5 →7 →8 →6 →4 →2 進行循環。

綜上可得，通過該模型和算法流程得到的8 臺CNC 最佳調度策略，是按照1 →3 →5 →7 →8 →6 →4 →2 的策略進行循環加工物料。

5.2 計算結果對比

史愛武等人也基于貪心算法設計針對相同問題的調度算法[14]，他們通過不斷尋找局部最優解來企圖獲取全局最優；潘舒曼等人結合動態調度，設計了純貪心和基于二分圖的貪心算法[15]。將上述兩種模型的求解結果和重復10000 次的蒙特卡洛仿真得到的平均結果與本文的計算結果進行對比，詳見表5。由此表對比結果可知，本文提出的模型得到的RGV-CNC 調度方案效果更好。（本文利用Anylogic 仿真軟件實現蒙特卡羅仿真實驗，詳見圖4和圖5。

圖4：Anylogic 仿真模型運行過程示意圖

圖5：Anylogic 仿真邏輯示意圖

表5：求解結果對比

6 結論

本文針對一道工序的RGV-CNC 調度問題，基于貪心策略和動態規劃思想，建立了RGV 動態調度的優化模型。將本文的計算結果與其他使用同一數據集的論文結果以及蒙特卡羅仿真結果進行對比，優異的表現驗證了本文所建立模型的實用性。

目前國內智能車間布局逐步普遍，本文的研究對于RGV-CNC系統的動態調度策略的制定具有一定的實際參考意義。