焦安康 鄒文忠 胡濤

摘要：根據(jù)RGV的指令選取方式，將當(dāng)前狀態(tài)下的局部最優(yōu)路徑與動(dòng)態(tài)優(yōu)化方案相結(jié)合，建立最優(yōu)路徑調(diào)度模型，再對(duì)遺傳算法中變異的方式進(jìn)行改進(jìn)，調(diào)整個(gè)體適應(yīng)性評(píng)估函數(shù)，對(duì)最優(yōu)子代選取的方式進(jìn)行改變，得到兩道工序下動(dòng)態(tài)調(diào)度模型。

關(guān)鍵詞：RGV動(dòng)態(tài)調(diào)度模型；遺傳算法；動(dòng)態(tài)優(yōu)化

1 問題一的模型建立與求解

1.1模型Ⅰ的建立

本文利用遺傳算法對(duì)最優(yōu)路徑分析，使用到當(dāng)前所有已知信息，不僅能考慮當(dāng)前的最優(yōu)路徑，還能顧及到之后已知的八步的路徑選取，使RGV移動(dòng)的指令收斂到全局最優(yōu)路徑。

Step1 利用遺傳算法建立模型

對(duì)RGV的調(diào)度進(jìn)行個(gè)體與基因的模擬，個(gè)體的基因被定義為一個(gè)信號(hào)處理序列的排列。

Step2 建立動(dòng)態(tài)調(diào)度模型

模擬RGV動(dòng)態(tài)調(diào)度時(shí)的指令預(yù)測(cè)范圍，選取step1中所得個(gè)體基因的最小單位，即第一個(gè)基因片段，視為動(dòng)態(tài)情況下的全局最優(yōu)解。

Step3 得到完整的個(gè)體基因

不斷重復(fù)step2，更新個(gè)體每一段基因的全局最優(yōu)基因，最終得到個(gè)體的最優(yōu)完整基因。

1.2 問題一算法的求解

Step1 對(duì)CNC進(jìn)行處理：將CNC進(jìn)行編碼，且對(duì)8臺(tái)CNC進(jìn)行無序排列，得到一個(gè)CNC隊(duì)列，該隊(duì)列即為模型Ⅰ中種群的初始條件。

Step2：本算法所有的指令，都是建立在模型Ⅰ中遺傳算法選取最優(yōu)解的基礎(chǔ)上的，得到假想的種RGV移動(dòng)作業(yè)路徑。

選取初始種群：從種隊(duì)列中隨機(jī)選出100種隊(duì)列，作為初始種群。

進(jìn)行基因的變異：，將該100種隊(duì)列復(fù)制2次。第一份復(fù)制得到的100種隊(duì)列中每組隊(duì)列隨機(jī)選取兩對(duì)CNC進(jìn)行位置交換。第二份復(fù)制得到的隊(duì)列，隨機(jī)選取相鄰兩個(gè)的CNC隨機(jī)插入到隊(duì)列中其他位置。

評(píng)估個(gè)體的適應(yīng)性：計(jì)算每組隊(duì)列情況的RGV執(zhí)行指令所需總時(shí)間記為Mi。

再將Mi （i=1，2…300）進(jìn)行升序排列，選取前100個(gè)Mk （k=1，2…300），作為下一子代。

對(duì)子代重復(fù)上述操作，得到新的子代。循環(huán)繁殖30代之后，輸出最終子代中用時(shí)最少的隊(duì)列，即認(rèn)為是最優(yōu)路徑。

Step3對(duì)step2中所得的最優(yōu)路徑，只保留其第一步選擇，視為智能加工系統(tǒng)對(duì)RGV當(dāng)前狀態(tài)調(diào)度的指令。

Step4 在完成step3對(duì)其下達(dá)的指令后，重復(fù)step2、3得到下一步所需要執(zhí)行的指令。

在對(duì)step2、3進(jìn)行操作的過程中，對(duì)RGV執(zhí)行每一步指令所需的時(shí)間進(jìn)行求和，記為變量Q。直到智能加工系統(tǒng)連續(xù)作業(yè)8小時(shí)后，RGV回到初始位置，結(jié)束物料加工工作，計(jì)算總加工物料件數(shù)。

2 問題二的模型與求解

2.1 模型II的建立

Step1 利用遺傳算法建立模型

對(duì)問題一中模型Ⅰ的遺傳算法模型進(jìn)行修改：

先編碼模擬第一道工序的基因，再編碼其所對(duì)應(yīng)的第二道工序的基因，接著編碼下一段第一道工序的基因，依次下去，直至編碼完8段基因。

個(gè)體適應(yīng)性評(píng)估的標(biāo)準(zhǔn)，同模型Ⅰ，但改變了計(jì)算編碼基因段時(shí)間的方式。

Step2 建立動(dòng)態(tài)調(diào)度模型

按照step1篩選出的基因也為當(dāng)前最優(yōu)基因片段，故選取step1中所得個(gè)體基因的最小單位。

Step3 得到完整的個(gè)體基因

不斷重復(fù)step1、2，從而不斷更新個(gè)體每一段基因的全局最優(yōu)基因，最終得到個(gè)體的最優(yōu)完整基因。

2.2 問題二算法的求解

Step2 遍歷加工第一，二道工序的CNC的排列位置

對(duì)加工第一，二道工序的CNC的個(gè)數(shù)分k1=k2、k1>k2、k1

Step3 對(duì)以上每一種CNC的順序情況進(jìn)行如下操作：

依據(jù)物料加工需分工序的規(guī)則，得到種RGV移動(dòng)作業(yè)路徑。

選取初始種群：從種隊(duì)列中隨機(jī)選出100種隊(duì)列，作為初始種群。

再進(jìn)行基因的變異，同模型Ⅰ。

對(duì)子代重復(fù)上述操作，得到新的子代。循環(huán)繁殖30代之后，輸出最終子代中用時(shí)最少的隊(duì)列。

Step3對(duì)step2中所得的最優(yōu)路徑，將第一道工序與其對(duì)應(yīng)的第二道工序的指令進(jìn)行捆綁，只保留其第一步捆綁的選擇，視為智能加工系統(tǒng)對(duì)RGV調(diào)度的下兩步指令。

Step4 在重復(fù)step3得到下一步執(zhí)行的指令。

在對(duì)step3進(jìn)行操作的過程中，對(duì)RGV執(zhí)行所有指令所需的時(shí)間進(jìn)行求和，記為變量Q。直到加工系統(tǒng)連續(xù)作業(yè)8小時(shí)后，結(jié)束工作，計(jì)算總加工物料件數(shù)，得到最優(yōu)路徑。

3 模型的誤差分析

在本模型中，利用遺傳算法選取局部最優(yōu)解時(shí)，初始種群與子代繁殖的有限性，并沒有取出所有可能的解來得到全局最優(yōu)解，所以會(huì)產(chǎn)生一定的誤差，得到的最優(yōu)解可能收斂到局部最優(yōu)解，非全局最優(yōu)解。遺傳算法的實(shí)現(xiàn)有許多參數(shù)，如交叉率和變異率，會(huì)對(duì)結(jié)果有影響。

參考文獻(xiàn)：

[1]吳焱明，劉永強(qiáng)，張棟，趙韓.基于遺傳算法的RGV動(dòng)態(tài)調(diào)度研究[J].合肥：合肥工業(yè)大學(xué)，2012：20-23.