閆潔 王一寧 宋善洋

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

關(guān)鍵詞：動態(tài)規(guī)劃；遺傳算法；動態(tài)調(diào)度

中圖分類號：TP18；TP278 文獻(xiàn)標(biāo)識碼：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 引 言

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

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

1 動態(tài)任務(wù)調(diào)度模型

1.1 模型建立

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

1.1.1 加工任務(wù)

將加工設(shè)備執(zhí)行加工物料的加工工序過程中出現(xiàn)的任務(wù)按時間順序進(jìn)行編號，表示為Wirk。在每一時刻，進(jìn)入系統(tǒng)中的任務(wù)數(shù)目不超過一個班次中總的需要加工的物料個數(shù)m的最大值，且為隨機(jī)數(shù)值，系統(tǒng)在有限時間段內(nèi)出現(xiàn)的任務(wù)數(shù)為非無窮大的數(shù)值。

1.1.2 加工設(shè)備

將加工系統(tǒng)中每一個加工設(shè)備表示為i，在開始階段設(shè)備正常運行，加工時有一定概率出現(xiàn)故障，并需要一定的時間進(jìn)行維修。

1.1.3 時間

動態(tài)規(guī)劃模型中，以連續(xù)時間序列為約束條件[10，11]，如下：

（1）在引導(dǎo)車進(jìn)行調(diào)度的時候，加工設(shè)備對未加工生料進(jìn)行加工的某一道工序的開工時間Brk和該工序的加工時間xirk·Tirk應(yīng)該不能大于該物料的完工時間Erk，即：

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

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

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

（3）每一個未加工生料加工完成并經(jīng)過清洗后變?yōu)槌闪系臅r間應(yīng)該不大于總的完工時間Emax，即：

（4）在進(jìn)行不同的未加工生料之間的工序約束的時候，應(yīng)該滿足同一臺引導(dǎo)車上某物料的工序完成時間不大于上一件物料的工序完成時間，即：

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道工序加工開始時間應(yīng)該大于該物料的上料時間并且小于該物料的加工完成時間，即：

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

1.1.4 數(shù)量

在進(jìn)行RGV的動態(tài)調(diào)度過程中，除了要求的物料r（假設(shè)一個班組中加工物料數(shù)的最大值為m）的加工完成的最大拖延時間最短之外，還應(yīng)該要求在一個班次內(nèi)的CNC有較大的加工效率，即物料完成所有加工工序的物料數(shù)是最多的，即：

1.2 動態(tài)規(guī)劃任務(wù)調(diào)度尋優(yōu)算法

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

Step1：編碼策略。在解決上述RGV的動態(tài)調(diào)度問題中，將8臺CNC當(dāng)作8個染色體，并依次為基礎(chǔ)進(jìn)行編碼。

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

Step3：適應(yīng)度函數(shù)的確定。為了便于模型的求解，我們以動態(tài)規(guī)劃模型的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)：

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

Step5：終止條件。按照上述方法在迭代次數(shù)范圍內(nèi)逐代進(jìn)化，或者當(dāng)最優(yōu)個體的適應(yīng)度達(dá)到給定的閾值時，進(jìn)化過程結(jié)束，算法終止。

對于車間生產(chǎn)線任務(wù)分配問題，經(jīng)過上述算法，得到最優(yōu)的策略方案。

2 仿真實例

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

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

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

3 靈敏度分析

為了驗證模型結(jié)果的準(zhǔn)確性，根據(jù)文獻(xiàn)[13]給出的三組數(shù)據(jù)，利用上述建立的模型及算法求出加工設(shè)備在一個班次內(nèi)實際加工物料的個數(shù)m和理想狀態(tài)下的加工物料個數(shù)h，求出生產(chǎn)效率w，即：。則，在理想狀態(tài)下CNC加工物料的個數(shù)為：

，q+u=8小時

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

[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] 劉愛軍，楊育，邢青松，等.柔性作業(yè)車間多目標(biāo)動態(tài)調(diào)度 [J].計算機(jī)集成制造系統(tǒng)，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生產(chǎn)線動態(tài)調(diào)度策略 [J].機(jī)電一體化，2017，23（11）：15-19+56.

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

[9] 司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用 [M].北京：國防工業(yè)出版社，2011.

[10] 趙月.基于動態(tài)優(yōu)化的動態(tài)調(diào)度問題研究 [D].沈陽：東北大學(xué)，2013.

[11] 黃歆雨.基于混合遺傳算法的柔性作業(yè)車間動態(tài)調(diào)度問題研究 [D].福州：福州大學(xué)，2016.

[12] 劉永強(qiáng).基于遺傳算法的RGV動態(tài)調(diào)度研究 [D].合肥：合肥工業(yè)大學(xué)，2012.

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

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