智能RGV的動(dòng)態(tài)調(diào)度策略

閆潔 王一寧 宋善洋

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

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

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

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

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

1.1 模型建立

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

1.1.1 加工任務(wù)

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

1.1.2 加工設(shè)備

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

1.1.3 時(shí)間

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

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

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

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

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

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

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

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

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

1.1.4 數(shù)量

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

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

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

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

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

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

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

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

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

2 仿真實(shí)例

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

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

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

3 靈敏度分析

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

，q+u=8小時(shí)

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

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

4 結(jié) 論

本文首先在動(dòng)態(tài)規(guī)劃理論研究的基礎(chǔ)上，建立了基于RGV的車(chē)間生產(chǎn)線動(dòng)態(tài)調(diào)度數(shù)學(xué)模型。首先，該數(shù)學(xué)模型能夠清晰地描述在不確定情況下車(chē)間生產(chǎn)線動(dòng)態(tài)調(diào)度問(wèn)題；其次，該模型評(píng)價(jià)函數(shù)的目標(biāo)是RGV在有限時(shí)間內(nèi)加工物料個(gè)數(shù)的最大值，便于進(jìn)一步應(yīng)用遺傳算法求解最優(yōu)調(diào)度策略；接著，借助于隨機(jī)數(shù)模擬了加工設(shè)備CNC發(fā)生故障的情形，使得模型的結(jié)果更加接近實(shí)際生產(chǎn)情況；最后，進(jìn)行了靈敏度分析，分析的結(jié)果更加直接地說(shuō)明了模型的準(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] 劉愛(ài)軍，楊育，邢青松，等.柔性作業(yè)車(chē)間多目標(biāo)動(dòng)態(tài)調(diào)度 [J].計(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)線動(dòng)態(tài)調(diào)度策略 [J].機(jī)電一體化，2017，23（11）：15-19+56.

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

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

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

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

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

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

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