基于貪心算法的RGV動態調度研究

姜嘉沁　吳思琪　陳天祺

摘 要：本文主要研究智能 RGV 的動態調度策略的問題，針對一道工序情況下的 RGV 動態調度進行了分析。首先，利用繪制時間坐標軸的方式，清晰刻畫每個時刻 RGV 和 CNC 的工作狀態，找出變量之間的相互關系;其次利用該函數關系，采用貪心算法，應用 MATLAB軟件將已知數據代入模型進行檢驗。最后利用數據檢驗結果可知，嚴格按照系統流程進行操作時，該調度模式已經達到較為高效的狀態。

關鍵詞：RGV 動態調度;貪心算法;時間坐標軸

引言

隨著我國科學技術的發展，現代化物流正在不斷發展和壯大，居民對高效的物流系統的要求越來越高，相繼而來發展的就是自動化立體倉庫。由于自動化物流系統的高速發展，傳統物流系統存在的弊端就暴露出來，RGV 也就應運而生，它無需耗費大量人力，大大提高了工作效率。

1. 模型建立

由于 RGV 的變化情況繁瑣復雜但存在一定的規律性，故選擇采取繪制如下

時間軸的方法，較為清晰地分析出各個變量之間的相關關系，其中，CNC1#～8#表示 CNC 上料時間。

上圖中各個點表示 RGV 給 CNC1#～8#上料對應的時間，根據上述的示意圖推導出如下關系：

（1）假設當 RGV 開始為 CNC1#進行上料作業為 0 時刻，則刨去初始特殊情況，接下來每臺 CNC 開始上料時刻隨著周期的變化存在一定的規律特征，故可根據之間的相關關系列出 8 臺 CNC 開始上料的時間函數式如下：

（2）根據上述時間示意圖，與第一次 CNC1#加工產生熟料相比較，每經過tc+t3時間，CNC1#會生成一單位熟料，而其余 7 臺 CNC 的產量和 CNC1#的關系只存在兩種狀態，一種等于 x1，另一種等于 x1-1，故 CNC1#加工生產量可表示為：

2. 求解算法

貪心算法是采用逐步求解最優解的方法，它是指在問題求解的過程中，不考慮整體最優情況，而是采取每步最優策略，得到在當前階段下的局部最優解。上述模型的建立即是建立在貪心算法的基礎上，每一個階段智能選擇最優路徑，在本模型中，RGV 則是嚴格按照順序依次對 CNC 進行作業。

對于一道工序的物料加工情況分析，RGV的動態調動運行模式為按照其接收信號的順序對相應的 CNC 進行上下物料作業和熟料的清洗工作。此時，我們假設固定軌道上有四臺 RGV 智能車，當系統啟動時，四臺智能車將同時運作，分別負責其相鄰兩臺CNC 的上下物料及清洗工作。

由于在每兩臺的 CNC 設備之間都有一臺 RGV 單獨負責其相關的加工相關作業，故而此時的產出量必然為一道工序加工作業下的最大物料產量。運用繪制時間軸的方式分析后可得每一臺 CNC 的加工產量滿足以下關系式：

在前文的求解過程之中已經求得 x1的關系式，故而選取 x1作為檢驗模型是否已經達到最優的代表量。有如下關系：

故而可看出此模型已經達到最優化。

結論：

通過本文研究發現 RGV 在運行過程中會對首先發出信號的 CNC 進行裝配，因為這一點所以 RGV 會產生忽略近處 CNC ，而跑去遠處 CNC 進行加工的情況，所以本文采取最小路徑、就近原則等條件對 RGV 的調度進行優化，達到產出最大化的目的。

參考文獻：

[1]M， H， AlSUWANEI. 算法設計技巧與分析[M]. 北京：電子工業出版社， 2004.

[2]陳敏瑩. 基于動態規劃的微弱目標檢測前跟蹤算法研究[D]. 西安：西安電子科技大學， 2013.