基于遺傳算法的RGV智能車動態調度

曹言，曹家賡，吳靈媛

（1.華北理工大學機械工程學院；2.華北理工大學經濟學院；3.華北理工大學理學院，河北 唐山 063210）

RGV是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據指令能自動控制移動方向和距離，并自帶1個機械手臂、2只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業任務。目前RGV已經廣泛運用到柔性生產制造流程中，其調度規劃問題成為生產決策的重點。

圖1是一個智能加工系統的示意圖，由8臺計算機數控機床（Computer Number Controller，CNC）、1輛軌道式自動引導車（Rail Guide Vehicle，RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成。

圖1 智能加工示意圖

1 模型的初步建立

針對RGV動態運動的兩種情況：（1）一道工序的物料加工作業情況，每臺CNC安裝同樣的刀具，物料可以在任一臺CNC上加工完成。（2）兩道工序的物料加工作業情況，每個物料的第一和第二道工序分別由2臺不同的CNC依次加工完成；建立動態調度模型并提供相應的求解算法，以解決整個車床加工零件變化情況。

智能加工系統的效率主要取決于：（1）調度：給RGV選擇和派送任務的過程。（2）路徑：RGV從輸送源到目的地所走的路程，RGV調度是以子任務步為單位進行的，每個子任務步需RGV的兩次操作，也就是RGV從上料傳送帶取到物料和將清洗后的成料放到下料傳送帶上，這樣才能完成一個物料的加工。

考慮運輸時間對系統作業流程RGV調度的問題：n個物料 {J1，J2，J3...Jn}要在 8臺機器 {M1，M2，M3...Mn}上加工。每個物料包含一道或兩道工序，每道工序可以選擇不同的CNC加工，只能選擇其中一臺CNC，選擇不同的加工機器所需的加工時間和運輸時間也不一樣。Ojh為第j個工件的第h道工序，并定義Oj(h-1)表示第Ojh的前一道工序，Oj表示物料當前所在機器的一道工序。物料J的每道工序在機器i上的加工時間是給定的，設為（J=1,2,3,…,n;i=1,2,3,…,8）。RGV調度需要為每塊物料的每道工序選擇最合適的CNC，使得物料的加工時間達到最小。

物 料 集 J={J1，J2，J3...Jn}，CNC集 M=Mi（i=1,2,3,…,8），Tj為物料一道工序的加工時間，Tj1為物料加工的兩道工序中的第一道工序所需的加工時間，Tj2為物料加工的兩道工序中的第二道工序所需的加工時間，Time1為RGV為CNC1#，3#，5#，7#一次上下料所需時間，Time2為RGV為CNC2#，4#，6#，8#一次上下料所需時間，Tj為RGV移動所需時間（n=1,2,3）。Cj為第i個物料的完工時間，Cmax為最大完工時間。考慮最小化最大完工時間，目標函數的約束條件為：

式（4）表示若工序j在第i道的開始加工時間小于前一道工序運輸結束時間，則受運輸時間約束；否則，工序受當前加工機器的資源約束。即考慮了運輸時間對于同一機器的相鄰工序的加工效率影響。

2 遺傳算法求解

遺傳算法（Genetic Algorithm, GA）最先是由美國的John Holland于1975年提出的。遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。

（1）遺傳算法的編碼。遺傳算法首要解決的是編碼的問題，本文采用基于工序的整數編碼，將工序排序和機器選擇這兩個子問題編成一條染色體，用來表示RGV調度的一個可行解。①工序排布部分：工序的實數編碼。工件號表示每個基因的位置，每個工件號出現的次數代表這個工件對應的工序數，整個染色體長度為所有工件的所有工序數總和。例如一個可行基因串2-2，對應的工序是O21-O22，表示工件J出現的次數對應第幾道工序。②機器選擇部分：采用CNC上的編碼。例如一個可行基因串3-2，表示的是工序O21可在CNC3#上加工，工序O22可在CNC2#上加工，如此類推。（2）初始化方法。由于遺傳算法的求解質量和收斂度會受到初始解優劣的影響。隨機初始化是最常使用的方法。由于本文是基于生產時間建立的模型，因此問題的可行解搜索范圍比一般問題的求解還要大。故本文將采用考慮工序加工時間和運輸時間的最短工作法，RGV在每道工序上選擇就近較優的CNC來獲得較優的初始解，收斂尋優一個物件加工過程的最優時間。（3）交叉。通過交叉操作可以讓兩個染色體交換基因，得到新一代個體，新個體組合了其父輩個體的特性。本文將通過部分映射交叉的方式實現基因交換，如圖2所示，根據隨機選中的工件集{2,4}，保持父代基因不變，然后將父代基因映射交叉得到2個子染色體。從染色體中隨機選擇一個基因位，在該位置隨機選擇一個加工機器代替染色體中那個被選中的加工機器。具體如圖2所示，其中黃色部分表示基因變異部分。（4）變異。通過隨機改變染色體中的一位或多位基因，產生新的染色體，模擬生物遺傳中的變異。當群體早熟時，變異可以跳出局部最小，改善 GA 的局部搜索能力，增加種群的多樣性。（5）解碼。將染色體從左到右進行解碼，工件號出現的次序表示工件要加工的工序，根據兩道工序的加工機器和加工時間確定整個RGV的調度過程，并計算生產調度過程中的最大完工時間。關鍵是需要將工序排序部分解碼成對應于機器選擇部分的活動調度，具體的解碼步驟如下：①讀取工序部分的基因轉換為相應工序Ojh；②獲取該工序Ojh的加工機器Mi=JM(j，h)，并獲取加工時間Pjh=T(j，h)；③計算該工序Ojh的最早加工時間Sjh和完工時間Cjh，其計算公式為：在考慮物料加工作業過程中的工序加工時間時，考慮運輸時間和調整時間，計算最大完工時間。

圖2 映射交叉

通過遺傳算法以最大完工時間為目標調度對問題進行求解，設遺傳算法中的初始種群為100，交叉概率為0.8，變異率為0.01，通過100次的迭代，求出物料加工時間的最優最大完工時間為862s。

3 結語

最優化的車床的運輸次序分別為CNC1-CNC2-C N C 3-C N C 4-C N C 5、和，能夠加工的最優工件數分別為376與211件。

通過RGV動態調度問題由簡到繁研究，車間生產能夠依照調度模型更合理地安排生產，減少不必要的等待時間與因故障浪費的調度時間，并科學籌劃車輛調度的路線，使總生產時間最小，從而達到生產資源的節約與優化。