曹言，曹家賡，吳靈媛

（1.華北理工大學(xué)機(jī)械工程學(xué)院；2.華北理工大學(xué)經(jīng)濟(jì)學(xué)院；3.華北理工大學(xué)理學(xué)院，河北 唐山 063210）

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

圖1是一個(gè)智能加工系統(tǒng)的示意圖，由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（Computer Number Controller，CNC）、1輛軌道式自動(dòng)引導(dǎo)車（Rail Guide Vehicle，RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。

圖1 智能加工示意圖

1 模型的初步建立

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

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

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

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

式（4）表示若工序j在第i道的開(kāi)始加工時(shí)間小于前一道工序運(yùn)輸結(jié)束時(shí)間，則受運(yùn)輸時(shí)間約束；否則，工序受當(dāng)前加工機(jī)器的資源約束。即考慮了運(yùn)輸時(shí)間對(duì)于同一機(jī)器的相鄰工序的加工效率影響。

2 遺傳算法求解

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

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

圖2 映射交叉

通過(guò)遺傳算法以最大完工時(shí)間為目標(biāo)調(diào)度對(duì)問(wèn)題進(jìn)行求解，設(shè)遺傳算法中的初始種群為100，交叉概率為0.8，變異率為0.01，通過(guò)100次的迭代，求出物料加工時(shí)間的最優(yōu)最大完工時(shí)間為862s。

3 結(jié)語(yǔ)

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

通過(guò)RGV動(dòng)態(tài)調(diào)度問(wèn)題由簡(jiǎn)到繁研究，車間生產(chǎn)能夠依照調(diào)度模型更合理地安排生產(chǎn)，減少不必要的等待時(shí)間與因故障浪費(fèi)的調(diào)度時(shí)間，并科學(xué)籌劃車輛調(diào)度的路線，使總生產(chǎn)時(shí)間最小，從而達(dá)到生產(chǎn)資源的節(jié)約與優(yōu)化。