智能RGV的動態調度策略研究

熊珮全 胡文潔 尚裕博 黃乾鑫 張哲

摘? ?要：文章主要研究智能RGV的動態調度策略，針對只有一道工序的物料加工時，每臺CNC都要安裝一樣的刀具，物料可以在任意一臺CNC上加工完成的情況，建立相應的動態調度模型和求解算法。

關鍵詞：最短路徑;迪克斯特拉算法;貪心算法

對于8臺計算機數控（Computerized Numerical Control，CNC）車床執行相同工序的情況，將8個CNC看作8個節點，將不同節點間到達的不同時間作為權值，使有軌制導車輛（Rail Guided Vehicle，RGV）在8個CNC中的調度形成一條最短的路徑（見圖1），建立了在雙邊搜索和約束條件下的迪克斯特拉算法，尋找弧段最少的情況下的RGV調度的路徑，為V7，V8，V5，V6，V3，V4，V1，V2，最短通路的值為106，完成了RGV在8個CNC間的最優調度。用3組數據進行檢驗，得到模型的平均實用性為96.7%。在求CNC的上料時間和下料時間的問題上，建立了貪心算法的模型，利用RGV走完一次最短路徑的最優解，通過若干次的貪心選擇，最終求得8 h內各CNC的上料時間和下料時間，以及8 h內最多加工的個數為360，求得作業效率為45個物料/h。

1? ? 問題分析

本文引進了最短路徑的迪克斯特拉算法，把每個CNC都看作節點，將8個CNC看作一組無向圖，將不同節點間到達的不同時間作為權值，以此建立了帶權值的鄰接矩陣，使RGV在調度中形成一條最短的路徑。在雙邊搜索和約束條件下，尋找經過全部節點且弧段最少情況下的RGV調度路徑，并進行了算法實現，完成了RGV在8個CNC間的最優調度。用3組數據分別進行檢驗，將實用性定義為實際加工的物料個數與理論完成物料個數之比，得到的結果為96.7%，判斷為實用模型。在求CNC的上料時間和下料時間的問題上，建立了貪心算法的模型，利用RGV走完8個CNC的最佳路徑時，每個CNC的上料時間和下料時間和CNC的編號，達到了局部最優解，通過一系列的貪心選擇，達到了全局最優解，最終求得8 h內各CNC的上料時間和下料時間，以及8 h內最多加工的物料個數，從而求得每臺CNC的作業效率。

2? ? 模型的建立與求解

2.1? 模型的建立

為了求一個CNC調度周期的最短路徑，將CNC看作一個無向圖，給圖的每個邊賦以權值，得到賦權圖。以起始點CNC1#起點為中心，利用數組循環遍歷起點距離其他頂點的u0距離，然后存儲到一個數組中，這時候數組里對應的每一位就是各頂點到起點的最短距離，找出距離最小的那個頂點，以此循環，直到擴展到終點為止。

以每個CNC作為圖M的節點，兩節點間的路線作為圖M相應兩頂點的邊，得到圖M（見圖2），對圖M的每一邊，賦以一個實數w（e）的權，得到賦權圖M'（見圖3）。

圖1按照CNC的位置，以CNC1#起點，CNC8#為終點，8個CNC為一個周期，在一個周期內進行最短路徑選取。圖2給可行的線段加上了權值，CNC的順序不動，在此基礎上求解最優路徑。

根據賦權圖建立如下鄰接矩陣：

依據鄰接矩陣，可以看出任意兩個頂點之間的權值。圖M子圖的權是指圖各邊的權之和。研究的目的是求賦權圖M'中指定的兩個頂點u0和v0間的權之和最小的軌跡。這條軌跡叫作u0和v0間的最短路徑，最短路徑上權的和叫作u0和v0的距離，記作d（u0，v0）。

求最短路徑采用了比較成熟的算法：迪克斯特拉（Dijkstra）算法，使從起點u0到終點v0權值相加的值達到最小，建立模型如下：

迪克斯特拉的基本思想是按距u0從近到遠為順序，依次求得u0和M的各頂點的最短路和距離，直至v0頂點，算法結束。采用了標號記法，保證了標號沒有重復并且記錄了每一步的信息。得到如下算法：

從u0到各頂點v的距離由v的最后一次的標號l（v）給出。在v進入Si之前的標號l（v）叫一號標號，v進入Si時的標號l（v）叫二號標號。如果后來將要標號的值比已經標號的值小，則修改標號，直至獲得最優的二號標號。若在算法運行過程中，將每一頂點獲得二號標號所由來的邊在程序注明，則算法結束時，u0至各頂點的最短路也會被標示出來。通過Matlab編程，得到了一號的標號為1，3，4，6，5，2，7，8，從中可以看出每個頂點被標注的次數，最終得出了一條通過全部節點且權值最小的RGV調度的路徑，實現了以權值最小的RGV在8個CNC間的最優模型。

在求得最短路徑的基礎上，目的是求出每個CNC的上料時間和下料時間，以及CNC的編號。因此，不從整體考慮，而是選擇從局部出發，求得每個局部的最優解。貪心算法通過一系列的選擇來得到一個問題的解，它所作的每一個選擇都是在當前狀態下具有某種意義的最好選擇，并且每次貪心選擇都能將問題化簡為一個更小的問題與原問題具有相同行駛的子問題。雖然局部的最優解不一定能夠達到總體的最優解，但是最終結果卻能夠很好地近似最優解。

首先，一臺CNC的一個周期的時間s進行分解：

其中，ur為CNC上料時間，ue為下料時間，tw為CNC加工的時間，ta為CNC加工完成之后的等待時間，tm為CNC收到請求后移動的時間，tq為完成下料后CNC清洗時間。

在CNC加工過程中，如果它的最后一個物料完成時間大于或者等于呼叫起始的時間hutime，即：

說明這臺CNC已經在等待RGV下料，此時，定義它的值為1;否則，它的值為0。

在一個周期中，RGV對于一臺CNC的移動時間yidongtime可以表示為：

其中，rgvlocation是RGV的位置。

根據先請求先下料的原則，需要對先請求的CNC先安排RGV，那么CNC下料的時間xialiaotime可表示為：

其中，timeend為CNC完成物料的時間，yidongtime為RGV在收到請求后移動到CNC的時間。

將CNC移動的時間進行排序，將CNC的編號定為k，那么k可以通過CNC移動時間的排序來確定，同時，k也表示了CNC的編號。通過這種關系，就可以Matlab運算得到CNC的編號[1]。

2.2? 模型的求解

在最短路徑模型中，用Matlab編寫程序，最終得到了權值最優的一組路徑V7，V8，V5，V6，V3，V4，V1，V2，用3組數據分別進行檢驗最短路徑模型的實用性p，定義如下：

其中，ia為理論上完成的物料個數，it為實際上完成的物料個數。CNC的等待時間和CNC的清洗時間較加工時間短，并且在人類的發展進程中會使它逐漸減小趨近于0，因此，從理論上考慮，忽略CNC的等待時間和CNC的清洗時間。實際上：59it+560it+25it+ _it=28 800;理論上：59ia+560ia=28 800，求解出來最短路徑模型的實用性的值為96.7%。這說明采用最短路徑模型雖然簡單，但是實用性很高，能夠很真實地模擬出8臺CNC的最優路徑。

通過Matlab可以得出在最短路徑時每臺CNC的上料時間和下料時間，以及CNC的編號，并且求出CNC的總生產物料個數為360個，則系統的作業效率為360/8=45個物料/h，即一臺CNC平均生產物料的個數[2]。

2.3? 模型的改進

可以在RGV調度模型建模時改用粒子群算法計算最短路徑，最終計算出調度模型結果為：CNC1—5.6—7.8—3.4—2—1，其中，編號CNC1，2加工一道工序物料，CNC3.4，5.6，7.8分別加工二道工序物料的第一道和第二道程序。

3? ? 結語

在理想狀態下，系統運行周期中，RGV的等待時間等于零在初始理想條件下慢慢將RGV的等待時間增加確保在下一個新的周期里，每個CNC的工作能連貫進行，不會因為CNC的不連續加工造成RGV靜止等待CNC呼叫而浪費工作時間。由此，采取分支定界法，計算出最理想狀態下系統的最高作業效率，作為可行的調度方案上限。

[參考文獻]

[1]周品.Matlab數值分析應用教程[M].北京：電子工業出版社，2014.

[2]張建林.Matlab定量決策五大類問題—50個運作管理經典案例分析[M].北京：電子工業出版社，2013.