宮尚俊?賈慧?吳慧敏

在一個(gè)智能加工系統(tǒng)中，輸送系統(tǒng)連接多個(gè)計(jì)算機(jī)數(shù)據(jù)機(jī)床和外部物料運(yùn)送工具，其調(diào)度策略和工作效率對(duì)整個(gè)的智能加工過(guò)程至關(guān)重要。本文針對(duì)智能RGV的動(dòng)態(tài)調(diào)度策略設(shè)計(jì)問(wèn)題，通過(guò)分析RGV的工作條件以及作業(yè)流程，建立基于遺傳算法的RGV動(dòng)態(tài)調(diào)度優(yōu)化模型，最后運(yùn)用MATLAB軟件編程，結(jié)合數(shù)據(jù)求出結(jié)果證明了模型的可操作性和算法的有效性，給出了具體的RGV的調(diào)度策略和系統(tǒng)的工作效率。

隨著現(xiàn)代工業(yè)的快速發(fā)展，物流的自動(dòng)化、智能化已是必然趨勢(shì)，自動(dòng)化立體倉(cāng)庫(kù)得到越來(lái)越多的應(yīng)用。RGV（Rail Guided Vehicle）軌道式自動(dòng)引導(dǎo)車能夠結(jié)合各種高新技術(shù)于一身具有多種實(shí)用功能，被廣泛地應(yīng)用于物料加工處理系統(tǒng)當(dāng)中，是實(shí)現(xiàn)可以感知、思維、推理、路徑規(guī)劃和決策的智能物流的中堅(jiān)力量，可以有效的完成物料的運(yùn)送、清理過(guò)程。RGV的動(dòng)態(tài)調(diào)度問(wèn)題很大程度決定了輸送系統(tǒng)的運(yùn)送效率。因此RGV動(dòng)態(tài)調(diào)度問(wèn)題一直是研究的熱點(diǎn)，有很多學(xué)者在這方向上做出了自己的努力。劉永強(qiáng)采用遺傳算法對(duì)自動(dòng)化立體倉(cāng)庫(kù)進(jìn)行建模，得到優(yōu)化的調(diào)度多個(gè)RGV運(yùn)送出入貨任務(wù)方案，并運(yùn)用仿真方法進(jìn)行進(jìn)一步研究；劉燚等針對(duì)擾動(dòng)事件影響下的車間調(diào)度問(wèn)題，綜合考慮完工時(shí)間與交貨期，運(yùn)用模擬退火遺傳算法，建立了作業(yè)車間動(dòng)態(tài)調(diào)度模型；潘全科將雙向調(diào)度方法嵌入到遺傳算法中，結(jié)合神經(jīng)網(wǎng)絡(luò)對(duì)智能制造系統(tǒng)的多目標(biāo)車間調(diào)度問(wèn)題進(jìn)行了研究；查申森等提出了一種基于RGV、AGV的柔性輸送系統(tǒng)，有效地克服傳統(tǒng)單一RGV輸送系統(tǒng)軌道占用空間大、對(duì)場(chǎng)所適應(yīng)性差等缺點(diǎn)。基于以上研究綜述，結(jié)合直行軌道式自動(dòng)化立體倉(cāng)庫(kù)智能加工需求，可知實(shí)現(xiàn)RGV穿梭車的合理調(diào)度、提高RGV系統(tǒng)的運(yùn)行效率、研究并設(shè)計(jì)智能RGV系統(tǒng)的動(dòng)態(tài)調(diào)度策略對(duì)促進(jìn)智能加工行業(yè)高速發(fā)展具有深遠(yuǎn)的意義。

一、問(wèn)題的分析

解決這類問(wèn)題時(shí)，我們首先要了解RGV的工作條件以及作業(yè)流程，再設(shè)置一個(gè)算法調(diào)度RGV以實(shí)現(xiàn)在約束條件下處理最多生料，這個(gè)問(wèn)題等價(jià)于設(shè)置一個(gè)算法確定一個(gè)穩(wěn)定狀態(tài)下的動(dòng)態(tài)調(diào)度順序使得在考慮一個(gè)穩(wěn)定循環(huán)下所有的RGV移動(dòng)距離的時(shí)間、RGV給每個(gè)CNC上下料的時(shí)間、RGV清洗熟料的時(shí)間之和最短。由于約束條件較多、較復(fù)雜而且經(jīng)分析易得在一個(gè)穩(wěn)定的循環(huán)周期內(nèi)每個(gè)CNC都需要RGV給予上一次料，所以用一般的算法可能不能求出實(shí)際解，而遺傳算法正好可以有效解決這個(gè)問(wèn)題，它是從問(wèn)題潛在的解集開(kāi)始的，通過(guò)按照適者生存原理，將所有解與目標(biāo)函數(shù)進(jìn)行對(duì)比并排除掉相對(duì)遠(yuǎn)離目標(biāo)的，最終會(huì)產(chǎn)生出越來(lái)越好的近似解。除此之外借助自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異產(chǎn)生出新的種群，這種方法能夠使種群進(jìn)行優(yōu)勝劣汰從而后生代種群比以前的更加適應(yīng)環(huán)境。最后將最后一代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼，可以作為問(wèn)題近似最優(yōu)解即得出RGV的最優(yōu)動(dòng)態(tài)調(diào)度。

二、模型的假設(shè)

為方便解決具體問(wèn)題，對(duì)文章作出以下假設(shè)：

（一）機(jī)械臂前端上方會(huì)一直能夠保持生料的供應(yīng)，清洗后的成料都能被傳送帶輸出系統(tǒng)；

（二）CNC只有等待RGV上下料工作完全完成后才開(kāi)始對(duì)生料進(jìn)行加工處理，即RGV完成上下料作業(yè)后到機(jī)械臂將熟料放到清洗槽中的時(shí)間中CNC不對(duì)生料進(jìn)行加工；

（三）RGV的初始上料過(guò)程與整個(gè)流程結(jié)尾回到初始位置時(shí)間與整個(gè)班次相比相對(duì)較少，為方便計(jì)算系統(tǒng)工作效率，假設(shè)這些時(shí)間為0。

三、模型的建立

遺傳算法（Genetic Algorithms，簡(jiǎn)稱GA）是一種基于生物的自然選擇原理和基因遺傳機(jī)理的搜索算法，通過(guò)模擬生物的遺傳和進(jìn)化過(guò)程，逐步篩選最終得到自己所想要目標(biāo)的最優(yōu)解。用這種算法建立動(dòng)態(tài)調(diào)度模型有很多的優(yōu)點(diǎn)，例如遺傳算法能夠從多個(gè)可行解開(kāi)始搜索，比從單一可行解開(kāi)始搜索的速度更快從而可以減少得到最優(yōu)的結(jié)果的時(shí)間；遺傳算法進(jìn)行遺傳操作時(shí)不需要設(shè)置太多的外部條件，只需要找到目標(biāo)函數(shù)就行，非常適合像計(jì)算機(jī)數(shù)控機(jī)床這種比較復(fù)雜的系統(tǒng)；遺傳算法的理論研究現(xiàn)在已經(jīng)發(fā)展的比較成熟，針對(duì)很多的實(shí)際問(wèn)題都有相應(yīng)的理論和方法，因此用這種算法非常的方便，而且算法計(jì)算出來(lái)的結(jié)果可行性高。

遺傳算法需要涉及五大要素：編碼、初始群體的產(chǎn)生、適應(yīng)度評(píng)估、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定。具體步驟如下：

（一）編碼策略

在編碼過(guò)程中本文使用十進(jìn)制編碼，用隨機(jī)數(shù)列作為染色體，其中，；隨機(jī)序列都與種群中的每一個(gè)個(gè)體相對(duì)應(yīng)。

（二）初始種群

本文利用改良圈算法來(lái)獲得一個(gè)比較不錯(cuò)的初始種群，即對(duì)于初始圈，，交換u與v之間的順序，此時(shí)的新路徑為：記，若，則用新的路徑替代舊的路徑，一直到不能替代為止。

（三）目標(biāo)函數(shù)

目標(biāo)函數(shù)為一個(gè)穩(wěn)定周期RGV的給各個(gè)CNC上下料的時(shí)間最短

1.

（四）交叉操作

我們的交叉操作采用單點(diǎn)交叉，因?yàn)閱吸c(diǎn)交叉在編輯程序的過(guò)程中較簡(jiǎn)單且能夠有效的保證解的多樣性。

（五）變異操作

變異能夠?qū)崿F(xiàn)群體的多樣性，能夠擴(kuò)大尋找最優(yōu)解的范圍。具體操作如下，按照一定的變異率，對(duì)選定變異的個(gè)體，隨機(jī)的選取3個(gè)整數(shù)，滿足

（六）選擇

采用確定性的選擇策略，也就是說(shuō)選擇目標(biāo)函數(shù)值最小的M個(gè)個(gè)體進(jìn)化到下一代，這樣可以保證父代的優(yōu)良特性被保存下來(lái)。

為計(jì)算出具體結(jié)果定義穩(wěn)定狀態(tài)下的時(shí)間間隔矩陣Tij，

2.

為方便理解Tij的具體含義，文中列舉了矩陣部分元素的具體表達(dá)形式。其中m1、m2、m3分別表示RGV移動(dòng)1、2、3個(gè)單位所需時(shí)間；ti表示RGV為CNCi#一次上下料所需時(shí)間；tc表示完成一個(gè)物料的清洗作業(yè)所需時(shí)間。矩陣元素tij表示從CNCi#到CNCj#完成上下料并清洗過(guò)的時(shí)間。位置0表明位于初始位置即CNC1#和CNC2#正中間。因?yàn)镽GV在完成一項(xiàng)作業(yè)任務(wù)后，才會(huì)判別執(zhí)行下一個(gè)作業(yè)指令。如果沒(méi)有接到其他的作業(yè)指令，則RGV就在原地等待直到下一個(gè)作業(yè)指令。又因?yàn)樵诔跏忌狭线^(guò)程中經(jīng)計(jì)算經(jīng)過(guò)不同的路徑給所有CNC上料的總時(shí)長(zhǎng)都遠(yuǎn)小于CNC加工物料時(shí)間，所以RGV還需要等待。因此經(jīng)過(guò)分析易得為減少工作時(shí)間、提高工作效率，RGV的最終位置為回到原點(diǎn)，達(dá)成一個(gè)穩(wěn)定的循環(huán)。在這里用位置9表示RGV回到末尾位置即初始位置。

最后將矩陣帶入遺傳算法求解的MATLAB程序中會(huì)求得一個(gè)穩(wěn)定狀態(tài)下的最優(yōu)順序，并能計(jì)算出RGV一個(gè)周期下的總調(diào)度時(shí)間。算出時(shí)間后，再計(jì)算RGV的工作效率。由于假設(shè)3，所以在計(jì)算系統(tǒng)工作效率時(shí)只需計(jì)算出一個(gè)穩(wěn)定周期下的RGV工作效率就行，計(jì)算系統(tǒng)工作效率公式如公式3

3.

其中η為系統(tǒng)的作業(yè)效率，T0為RGV調(diào)度時(shí)間，T為系統(tǒng)工作的總時(shí)間。

四、模型的求解

將表1：智能加工系統(tǒng)作業(yè)參數(shù)的3組數(shù)據(jù)表中第一組數(shù)據(jù)帶入并結(jié)合時(shí)間間隔矩陣的元素含義可得時(shí)間間隔矩陣，接著將所得的時(shí)間間隔矩陣帶入遺傳算法的MATLAB程序中即可得出RGV給CNC上料的順序：2、4、3、6、5、8、7、1以及RGV一個(gè)調(diào)度周期耗時(shí)總時(shí)間為542秒，即經(jīng)過(guò)542秒后RGV回到初始狀態(tài)9開(kāi)始進(jìn)行第二次的循環(huán)。因?yàn)镽GV總調(diào)度時(shí)間只需542秒，CNC加工完成一個(gè)一道工序的物料所需時(shí)間為560秒，最后用公式3計(jì)算系統(tǒng)作業(yè)的工作效率，得出結(jié)果為96.79%。

五、結(jié)論與討論

本文討論了RGV動(dòng)態(tài)調(diào)度策略優(yōu)化問(wèn)題。根據(jù)分析RGV的工作條件以及作業(yè)流程得出一些基本的約束情況，建立了基于遺傳算法的RGV動(dòng)態(tài)調(diào)度優(yōu)化模型，在模型的建立過(guò)程中構(gòu)造了時(shí)間間隔距離矩陣將不可計(jì)算的最短時(shí)間長(zhǎng)度問(wèn)題轉(zhuǎn)化為最短距離問(wèn)題使模型顯得更淺顯易懂、RGV調(diào)度順序結(jié)果更易計(jì)算出。最后結(jié)合2018高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題第一種情況第1組數(shù)據(jù)求出穩(wěn)定狀態(tài)下RGV的調(diào)度順序并計(jì)算出系統(tǒng)的作業(yè)效率來(lái)驗(yàn)證模型的實(shí)用性和算法的有效性。結(jié)果表明基于遺傳算法的RGV動(dòng)態(tài)調(diào)度模型具有實(shí)用性，算法能夠求出RGV穩(wěn)定狀態(tài)下的調(diào)度順序且該順序下的系統(tǒng)工作效率為96.79%比較合理，因此該算法也具有有效性。（第一作者單位為安徽財(cái)經(jīng)大學(xué)經(jīng)濟(jì)學(xué)院，第二作者單位為安徽財(cái)經(jīng)大學(xué)國(guó)際經(jīng)濟(jì)貿(mào)易學(xué)院，第三作者單位為安徽財(cái)經(jīng)大學(xué)會(huì)計(jì)學(xué)院）