智能RGV的動態調度策略

閆潔 王一寧 宋善洋

摘 要：研究智能軌道式自動導引車在兩道工序的物料加工作業過程中的動態調度策略，以時間軸為主線，以各個調度操作的時間不沖突為約束條件，建立動態規劃模型，采用遺傳算法對模型進行求解，從而得出軌道式自動導引車的動態調度策略以及作業效率。

關鍵詞：動態規劃；遺傳算法；動態調度

中圖分類號：TP18；TP278 文獻標識碼：A 文章編號：2096-4706（2019）04-0170-03

Dynamic Scheduling Strategy for Intelligent RGV

YAN Jie1，WANG Yining2，SONG Shanyang1

（1.School of Management Engineering，Qingdao University of Technology，Qingdao 266520，China；

2.School of Information and Control Engineering，Qingdao University of Technology，Qingdao 266520，China）

Abstract：This paper studies the dynamic scheduling strategy of intelligent RGV in the process of material processing in two processes. With the time axis as the main line and the time conflict of each scheduling operation as the constraint condition，a dynamic programming model is established，and the genetic algorithm is used to solve the model，so as to obtain the dynamic scheduling strategy and operation efficiency of RGV.

Keywords：dynamic programming；genetic algorithm；dynamic scheduling

0 引 言

軌道式自動導引車（Rail Guide Vehicle，以下簡稱RGV）在智能化加工系統中有著非常廣泛的應用，它可大大提高加工系統的作業效率。在實際生產環境中，單個RGV通常需要為多個生產線運輸物料，由于系統的生產任務和生產線狀態是變化的，所以傳統的靜態調度方案將會在一定程度上限制智能加工系統的生產效率，對RGV動態調度的優化的研究已經成為生產調度研究中的熱點之一。動態調度的概念最初是由美國加州大學的Jackson[1]提出，Sabuncuoglu等提出了針對在生產加工過程中，由于機器故障和加工時間改變等情況的變周期重調度策略，并分別于在線與離線狀態下進行實驗，最終驗證了調度策略的有效性[2]。Nelson和Holloway提出了以一個周期性的調度算法來解決工作間隔到達的生產調度問題，即所形成的調度方案一直執行到下個周期開始前，中間不進行任何的修改[3]。Yamamoto和Nof[4]則研究了隨機機器發生故障時事件驅動的重調度策略。劉愛軍等設計了以最小化加工時間和最小化拖期為目標，并用一種自適應的遺傳算法對的柔性作業車間動態調度進行求解和檢驗的調度策略[5]。智力學者Doris Saez和Cristian E.Cortes[6]等提出了提前預測將要發生的任務，利用遺傳算法以更有效地解決多個RGV的動態調度問題。

以上針對動態調度問題[7]的研究提出了許多有價值的思想和方法，但當RGV應用在多道工序的智能化加工車間執行生產時，由于生產任務的工序、時間、數量會經常變化，欲在未知動態環境下尋找智能RGV的最優調度策略，關鍵是要確定RGV接收到的指令來自于哪一臺CNC、其接受指令的時間點以及位置如何，這也是突破RGV動態調度問題的核心之處。針對該問題，本文基于動態規劃和遺傳算法的理論進行數學建模，并通過MATLAB[8]軟件編寫程序，以求解智能RGV的最優調度策略，從而實現智能加工車間的最大生產效率。

1 動態任務調度模型

1.1 模型建立

本文針對車間生產線動態調度任務分配問題的特點，基于動態規劃理論，將生產線執行任務決策的過程描述為在限定時間段內有序增加生產任務分配決策問題，建立基于動態規劃的動態任務分配模型[9]。RGV的動態任務分配模型由四個參數表示：加工任務、加工設備、時間、數量[7]。

1.1.1 加工任務

將加工設備執行加工物料的加工工序過程中出現的任務按時間順序進行編號，表示為Wirk。在每一時刻，進入系統中的任務數目不超過一個班次中總的需要加工的物料個數m的最大值，且為隨機數值，系統在有限時間段內出現的任務數為非無窮大的數值。

1.1.2 加工設備

將加工系統中每一個加工設備表示為i，在開始階段設備正常運行，加工時有一定概率出現故障，并需要一定的時間進行維修。

1.1.3 時間

動態規劃模型中，以連續時間序列為約束條件[10，11]，如下：

（1）在引導車進行調度的時候，加工設備對未加工生料進行加工的某一道工序的開工時間Brk和該工序的加工時間xirk·Tirk應該不能大于該物料的完工時間Erk，即：

Brk+xirk·Tirk≤Erk，（i=1，2…n，r=1，2…m；k=1，2 …kr）

（2）下一道工序的開工時間Br（k+1）要應該不小于上一道工序的完工時間Erk、引導車為CNC一次上下料所需時間tir、引導車在這個過程中移動的時間p，即：

p+Erk+tir≤Br（k+1），（r=1，2…m；k=1，2…kr-1）

（3）每一個未加工生料加工完成并經過清洗后變為成料的時間應該不大于總的完工時間Emax，即：

（4）在進行不同的未加工生料之間的工序約束的時候，應該滿足同一臺引導車上某物料的工序完成時間不大于上一件物料的工序完成時間，即：

Brk+Tirk≤Bsl+M（1-yirksl），（i=1，2…n；r，s=1，2…m；k=1，2…kr；l=1，2…ks）

（5）物料r的第k道工序加工開始時間應該大于該物料的上料時間并且小于該物料的加工完成時間，即：

uri≤Brk≤dri-Tirk，（i=1，2…n；r=1，2…m；k=1，2 …kr）

1.1.4 數量

在進行RGV的動態調度過程中，除了要求的物料r（假設一個班組中加工物料數的最大值為m）的加工完成的最大拖延時間最短之外，還應該要求在一個班次內的CNC有較大的加工效率，即物料完成所有加工工序的物料數是最多的，即：

1.2 動態規劃任務調度尋優算法

考慮到基于自然選擇原理的搜索尋優算法在解決最優化問題中的優勢，我們利用遺傳算法來求解。遺傳算法的實質是通過在一個種群中進行搜索，以適者生存為尋優原則，通過個體的隨機交叉和突變等過程生成下一代群體，并按照上述方法使一個種群中的群體不斷進化，直到滿足最后的終止條件。遺傳算法的具體步驟如下[11，12]。

Step1：編碼策略。在解決上述RGV的動態調度問題中，將8臺CNC當作8個染色體，并依次為基礎進行編碼。

Step2：設置初始參數。設置初始種群的大小為32，交叉概率為10%，變異概率為50%，最大的迭代次數為100。

Step3：適應度函數的確定。為了便于模型的求解，我們以動態規劃模型的目標函數作為適應度函數：

Step4：遺傳操作。該過程包括三個基本的遺傳算子：選擇、交叉以及變異。

Step5：終止條件。按照上述方法在迭代次數范圍內逐代進化，或者當最優個體的適應度達到給定的閾值時，進化過程結束，算法終止。

對于車間生產線任務分配問題，經過上述算法，得到最優的策略方案。

2 仿真實例

以2018年全國大學生數學建模競賽B題[13]——《智能RGV的動態調度策略》中兩道工序的物料加工作業為例，實例問題基于求解兩道加工作業對RGV的最優動態調度策略這一情形。利用本文所建立的動態任務調度模型，并通過遺傳算法結合MATLAB編程進行求解，得出結果。

遺傳算法在產生新一代的過程中，每次運行的結果都是不一樣的，經過多次仿真模擬得到如下適應度曲線，見圖1、圖2。

在遺傳算法運行一次后，如圖1所示，種群的適應度曲線振蕩程度較大，此時還未找到最優解，即在現有的CNC設備和加工條件的約束下，仍存在對RGV更優的動態調動策略。當遺傳算法運行兩次后，如圖2所示，隨著代數的增加，種群的平均適應度逐漸向最大適應度收斂，在這個范圍內存在全局最優解，結合先后兩次的運行結果可以認定，在現有約束條件的限制下實現了對RGV最優的動態調度。

3 靈敏度分析

為了驗證模型結果的準確性，根據文獻[13]給出的三組數據，利用上述建立的模型及算法求出加工設備在一個班次內實際加工物料的個數m和理想狀態下的加工物料個數h，求出生產效率w，即：。則，在理想狀態下CNC加工物料的個數為：

，q+u=8小時

其中，T為一個班次的時間，q為加工第一道工序的加工設備數量，u為加工第二道工序的加工設備數量。

通過靈敏度分析的結果可以得出：在一定加工時間內，加工時間越長，生產效率越高；當加工時間超過了某一臨界值的時候，設備加工時間越長，生產效率越低。這是因為，在一定的加工時間范圍內，總時間是一定的，隨著加工時間的變長，有效利用的時間變長，生產效率變大，當加工時間超過一定范圍的時候，RGV等待的時間變長，生產效率變低。這一結果符合生產加工車間的實際情況，進一步驗證了模型的邏輯性及準確性，使得模型更具說服力。

4 結 論

本文首先在動態規劃理論研究的基礎上，建立了基于RGV的車間生產線動態調度數學模型。首先，該數學模型能夠清晰地描述在不確定情況下車間生產線動態調度問題；其次，該模型評價函數的目標是RGV在有限時間內加工物料個數的最大值，便于進一步應用遺傳算法求解最優調度策略；接著，借助于隨機數模擬了加工設備CNC發生故障的情形，使得模型的結果更加接近實際生產情況；最后，進行了靈敏度分析，分析的結果更加直接地說明了模型的準確性。

參考文獻：

[1] Jackson JR. Simulation research on job shop production [J]. Naval Research Logistics Quarterly，1957，4（4）：287-295.

[2] Ihsan Sabuncuoglu，Suleyman Karabuk. Rescheduling frequency in an FMS with uncertain processing times and unreliable machines [J]. Journal of Manufacturing Systems，1999，18（4）：268-283.

[3] Rosser T. Nelson，Charles A. Holloway，Ruby Mei-Lun Wong. Centralized Scheduling and Priority Implementation Heuristics for a Dynamic Job Shop Model [J]. IIE Transactions，1977，9（1）：95-102.

[4] Yamamoto M，Nof S Y. Scheduling/rescheduling in the manufacturing operation system environment [J].International Journal of Production Research，1985，23（4）：705-722.

[5] 劉愛軍，楊育，邢青松，等.柔性作業車間多目標動態調度 [J].計算機集成制造系統，2011，17（12）：2629-2637.

[6] Doris Sáez，Cristián E. Cortés，Alfredo Núez. Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering [J]. Computers & Operations Research，2008：3412-3438.

[7] 陳明，周云龍，劉晉飛，等.基于MDP的多Agent生產線動態調度策略 [J].機電一體化，2017，23（11）：15-19+56.

[8] 賀超英.MATLAB應用與實驗教程 [M].北京：電子工業出版社，2012.

[9] 司守奎，孫璽菁.數學建模算法與應用 [M].北京：國防工業出版社，2011.

[10] 趙月.基于動態優化的動態調度問題研究 [D].沈陽：東北大學，2013.

[11] 黃歆雨.基于混合遺傳算法的柔性作業車間動態調度問題研究 [D].福州：福州大學，2016.

[12] 劉永強.基于遺傳算法的RGV動態調度研究 [D].合肥：合肥工業大學，2012.

[13] 中國工業與應用數學學會.2018年全國大學生數學建模競賽B題 [EB/OL].http：//www.mcm.edu.cn/html_cn/node/7cec7725b9a0ea07b4dfd175e8042c33.html，2019-01-22.

作者簡介：閆潔（1999-），女，漢族，山東菏澤人，本科在讀，主要研究方向：工程造價；通訊作者：宋善洋（1998-），男，漢族，河南濮陽人，本科在讀，主要研究方向：國際工程項目管理。