王明星,李利民
WANG Ming-xing1,LI Li-min2
(1.中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院,太原 030051;2.山西汾西重工有限責(zé)任公司,太原 030027)
科學(xué)的計(jì)劃排產(chǎn)是提升加工制造企業(yè)市場競爭力的關(guān)鍵因素。但車間計(jì)劃排產(chǎn)長期以來都是生產(chǎn)調(diào)度的難題[1,2],原因在于車間加工過程復(fù)雜,把不同零件按各自工藝路線有效的組織起來進(jìn)行加工并非易事,所以能以最短的時(shí)間、最高的效率、最少的成本完成生產(chǎn)指標(biāo)是很多企業(yè)的共同追求。20世紀(jì)80年代以來,模擬退火算法(Simulated Annealing, SA)、禁忌搜索算法(Tabu Search, TS)和遺傳算法(Genetic Algorithms, GA)等智能算法在生產(chǎn)調(diào)度領(lǐng)域應(yīng)用廣泛,優(yōu)化效果顯著[3]。其中,遺傳算法求解復(fù)雜優(yōu)化問題時(shí)潛力巨大,為車間的排產(chǎn)調(diào)度提供了新的思路。
遺傳算法(Genetic Algorithm, GA)是由美國學(xué)者J.H.Holland等人提出,模擬生物進(jìn)化自然選擇過程的計(jì)算模型。Wang H[4]用標(biāo)準(zhǔn)遺傳算法(SGA)求解調(diào)度問題時(shí)存在早熟收斂、求解精度低等問題,劉晶晶等人[5]將適應(yīng)度引入到父代之間的交叉操作中,克服了SGA交叉操作中較大的盲目性,劉愛珍等人[6]利用混沌優(yōu)化技術(shù),對遺傳算法的交叉和變異概率進(jìn)行動態(tài)控制,得到了可行解。
目前對基本遺傳算法改進(jìn)后應(yīng)用于機(jī)加車間排產(chǎn)的研究很少。借鑒相關(guān)文獻(xiàn)算法優(yōu)點(diǎn),以工件加工時(shí)間最短為目標(biāo),結(jié)合機(jī)加車間實(shí)際生產(chǎn)情況,建立對應(yīng)數(shù)學(xué)模型,以個體適應(yīng)度值為參照自動調(diào)節(jié)交叉概率和變異概率,根據(jù)加工任務(wù)高度值劃分基因段來改善交叉操作,引入混沌理論優(yōu)化變異算子增強(qiáng)算法的全局搜索能力。最后用此算法和參考文獻(xiàn)中方法對給定算例進(jìn)行求解并做了對比分析。
機(jī)加車間依靠機(jī)床加工零件,主要負(fù)責(zé)中小型零件的車、銑、鏜、鉆、鉗、磨、電加工等機(jī)械加工及熱處理。其車間調(diào)度問題可描述如下:
在m臺機(jī)床上加工n個不同的工件,機(jī)床集M由m臺機(jī)床Mj(j=1,2,…,m)組成,工件集N由n個待加工工件Pi(i=1,2,…,n)組成,工件Pi的加工工藝有qi道工序序列集Oik(k=1,2,…,qi)組成,工序Oik的加工機(jī)床組合為Mik,對應(yīng)加工時(shí)間為tik,Mik表示第i個工件的第k道工序使用的機(jī)床號,Mik=0表示工件Pi在第k道工序不加工。機(jī)床集,工件集,工序序列集都用矩陣表示[7]。
該調(diào)度問題要求在一定條件下,整個調(diào)度的最大完工時(shí)間Cmax(從第一個工件開始加工到最后一個工件完成加工所需時(shí)間)最小,即:
其中,Cik表示工序Oik完工時(shí)間,Sik表示工序Oik開始加工時(shí)間,tik表示工序Oik加工時(shí)間。調(diào)度方案末道工序完工時(shí)間就是整個調(diào)度最大完工時(shí)間Cmax。假設(shè)改進(jìn)的遺傳算法在以下條件運(yùn)行:
1)每臺機(jī)床同一時(shí)間只能有一個加工任務(wù)且不能中斷;
2)各工件的加工工序一般相同,不同工件同一工序加工時(shí)間一般不同;
3)每個工件工序之間存在約束關(guān)系,工序應(yīng)該依次按順序執(zhí)行;
4)每個工件的工藝路線事先確定;
5)初始時(shí)刻,任何工件都能被加工。
由于工件的加工順序存在優(yōu)先級,我們采用基于工序的編碼方式,每段基因代表加工的工序數(shù),對于n個工件m臺機(jī)床的調(diào)度問題,編碼可表示為[k11,k12, …, k1m,…kn1,kn2,knm],其中kj(j=11,12, …, nm)表示工件編號。工件Ji(i=1,2, …, n)的工件編號i在整個編碼中出現(xiàn)m次表示該工件共m道工序。上述編碼中,工件號i第一次出現(xiàn)表示Ji的第一道工序Oi1,工件號i第二次出現(xiàn)表示Ji的第二道工序Oi2,以此類推,Oim表示Ji的末道工序。
例如編碼[251415]表示工序順序?yàn)閇O21,O51,O11,O41,O12,O52]。
交叉與變異算子是影響遺傳算法性能的關(guān)鍵因素,通過交叉和變異不但可以把父代個體的優(yōu)秀品質(zhì)遺傳給子代,而且子代可能獲得比父代更好的基因結(jié)構(gòu)。SGA通常設(shè)定一定的交叉概率和變異概率,然后由貝努利實(shí)驗(yàn)決定是否進(jìn)行交叉或變異運(yùn)算,交叉概率和變異概率過大可能導(dǎo)致隨機(jī)搜索,過小可能導(dǎo)致早熟收斂,產(chǎn)生局部極值。對交叉概率和變異概率的改進(jìn)如下:
其中,Pc0和Pm0是初始化的交叉概率和變異概率,Pc1和Pm1是調(diào)整后的交叉概率和變異概率,Wmax是群體中的最大適應(yīng)度,Wavg是群體平均適應(yīng)度,W(x)是兩個待交叉?zhèn)€體中的較大適應(yīng)度。觀察表達(dá)式(2)和式(3)可知,適應(yīng)度低于平均適應(yīng)度的個體受破壞的可能性大,被淘汰;適應(yīng)度高于平均適應(yīng)度的個體受破壞的可能性小,被保存到下一代。
交叉在遺傳算法中發(fā)揮核心作用,當(dāng)交叉概率偏大時(shí),遺傳算法對新空間的搜索能力增強(qiáng),但優(yōu)秀基因遭到破壞的可能性也變大,算法收斂速度和穩(wěn)定性下降;當(dāng)交叉概率偏小時(shí),遺傳算法的搜索會有滯后性。
隨機(jī)在父代中選擇交叉點(diǎn)盲目性很大,算法性能會嚴(yán)重下降,此改進(jìn)策略放棄對父代基因隨機(jī)交換,而是按照加工任務(wù)的高度值把父代基因劃分為若干個小段,高度值相同的加工任務(wù)劃分到一個基因段,劃分完成后在父代中按序選取等位基因段組成一個子代。父代的等位基因段適應(yīng)度越高,被選作子代基因段的可能性越大。這一改進(jìn)的最大優(yōu)勢在于:沒有改變加工任務(wù)的任何前驅(qū)限制關(guān)系,得到的結(jié)果都是可行解。交叉算法具體操作步驟如下:
1)計(jì)算工件x1和x2中每道工序的加工時(shí)間,然后將分配到同一機(jī)床的加工任務(wù)按加工時(shí)間劃分為若干個基因段;
2)按照如下方法選取等位基因段(即工件x1和x2工序中在相同機(jī)床上相等的基因段)概率;
3)生成一個任意的隨機(jī)數(shù)Hi(i=1,2,3…,k;k為基因段個數(shù)),然后將Hi與 P (x1)或P (x2)進(jìn)行比較來確定所選取的等位基因段。如果 P(x1)< P (x2),當(dāng)Hi> P (x2)時(shí),選取x2的等位基因;當(dāng)Hi< P (x1)時(shí),選取X1的等位基因。
受加工任務(wù)之間約束關(guān)系的限制,SGA容易產(chǎn)生早熟收斂。SGA的變異操作通常采用隨機(jī)數(shù)決定,這會導(dǎo)致新個體產(chǎn)生的隨機(jī)性過大,不具有遍歷性和規(guī)律性?;煦缡亲匀唤缙毡榇嬖诘姆蔷€性現(xiàn)象,它看似很混亂,內(nèi)部結(jié)構(gòu)卻很精致,具有遍歷性、隨機(jī)性、敏感性和規(guī)律性?;煦绗F(xiàn)象在一定范圍之內(nèi)能依據(jù)自身規(guī)律沒有重復(fù)的遍歷所有狀態(tài),這一特性可作為搜索過程中避免陷入局部最優(yōu)解的優(yōu)化機(jī)制[8]。因此,本文把混沌理論應(yīng)用到遺傳算法的變異操作中?;煦缧蛄胁捎萌缦滤緇ogistic映射公式,其中k為控制系數(shù):
其中k=4,此時(shí)系統(tǒng)處于完全混沌狀態(tài)。任意取一個初始值X0,可產(chǎn)生一個迭代序列Xn+1,該序列會在[0,1]之間來回變化。本文將Xn+1作為控制遺傳算法是否變異的標(biāo)尺。
假設(shè)染色體中個體基因的取值范圍是[α,β],即可供選擇的加工工序的范圍,混沌優(yōu)化變異的操作步驟如下:
1)選出待變異個體,確定個體進(jìn)行變異操作的基因位i和基因位對應(yīng)的工序碼Gi,取X0=Gi;
2)將X0代入式(7)調(diào)整為基因取值范圍內(nèi)的數(shù);
3)將X1代入混沌優(yōu)化的映射公式(6),得到X2;
4)再將X2調(diào)整為[0,1]之間的數(shù);
5)令Gi= X3,更新個體基因編碼;
6)判斷變異操作是否結(jié)束,若結(jié)束,則返回到遺傳算法中,否則,選取下一個待變異的個體,轉(zhuǎn)步驟1)。
車間排產(chǎn)問題是求解加工工件耗費(fèi)總時(shí)間的最小值,這需要讓適應(yīng)度值最大化,所以適應(yīng)度函數(shù)定義為:
其中,tij為第i個工件第j道工序的加工時(shí)間;qi是加工第i個工件需要的最大工序數(shù);n是最大工件數(shù);C是的某極限值,保證F(x)是非負(fù)數(shù),便于選擇和排序概率的計(jì)算。
改進(jìn)的遺傳算法操作步驟:
1)獲取算法基礎(chǔ)數(shù)據(jù):讀入工件的種類、加工工序數(shù)和對應(yīng)工序的加工時(shí)間,讀入機(jī)床的加工產(chǎn)能;
2)初始化算法各參數(shù):設(shè)定算法的群體規(guī)模和結(jié)束的循環(huán)代數(shù),設(shè)定算法的初始交叉概率Pc0和變異概率Pm0。設(shè)定初始解集作為初始染色體;
3)計(jì)算當(dāng)前染色體適應(yīng)度值,把函數(shù)適應(yīng)度值最大的個體設(shè)定為當(dāng)前一代的最佳解;
4)檢驗(yàn)是否滿足算法收斂準(zhǔn)則 ,若滿足,則轉(zhuǎn)步驟7),否則進(jìn)行步驟5);
5)對染色體當(dāng)前的交叉概率和變異概率進(jìn)行動態(tài)的自適應(yīng)調(diào)整,以調(diào)整后的交叉概率進(jìn)行改進(jìn)的交叉操作,以調(diào)整后的變異概率進(jìn)行混沌優(yōu)化變異操作;
6)對染色體進(jìn)行選擇操作[9],把經(jīng)過遺傳操作的染色體作為當(dāng)前染色體。轉(zhuǎn)步驟3);
7)得到最佳個體,輸出結(jié)果。
該算法的流程圖如圖1所示。
圖1 改進(jìn)的遺傳算法流程圖
設(shè)定機(jī)加車間要加工9個工件,每個工件都要經(jīng)過車、銑、磨3道工序的處理,現(xiàn)有2臺車床,3臺銑床,2臺磨床,不同工件在不同機(jī)床的加工時(shí)間各不相同,具體加工情況如表1所示。
表1 工件加工時(shí)間明細(xì)表
將標(biāo)準(zhǔn)遺傳算法(SGA)[4]和本文算法應(yīng)用于該車間實(shí)際生產(chǎn)進(jìn)行仿真對比。設(shè)定初始交叉概率Pc0=0.70,變異概率Pm0=0.05,種群規(guī)模M=100,進(jìn)化代數(shù)T=100,分別獨(dú)立運(yùn)行20次取平均值[10]。得到的結(jié)果如表2所示。
表2 SGA和本文算法排產(chǎn)結(jié)果
比較分析可得:本文算法波動率小,動態(tài)穩(wěn)定性高,最優(yōu)解為77.7,排產(chǎn)效果優(yōu)于SGA。但由于算法復(fù)雜,運(yùn)行時(shí)間比SGA稍長,這對于排產(chǎn)優(yōu)化效果影響不大。
我們選用標(biāo)準(zhǔn)遺傳算法(SGA)、文獻(xiàn)[5]中算法、文獻(xiàn)[6]中算法和本文算法分別求解進(jìn)行性能評估。文獻(xiàn)[4~6]中GA主要參數(shù)見原文,本文算法參數(shù)和4.2中設(shè)置相同。仿真過程在一臺PC機(jī)上完成,操作系統(tǒng)是Windows XP,CPU是Intel(R)Q6600,內(nèi)存為3GB,工具是Matlab2012b。設(shè)平均改進(jìn)量為I,仿真結(jié)果如圖2所示。
為了減小算法隨機(jī)性產(chǎn)生的誤差,更加準(zhǔn)確的體現(xiàn)各算法的性能,圖2中每組數(shù)據(jù)都是各自運(yùn)行20次取平均值得到的,觀察可知,此算法得到的加工時(shí)間最短,全局搜索能力最好。
8個機(jī)床加工40個工件條件下四種算法分別進(jìn)化產(chǎn)生的靜態(tài)性能曲線如圖3所示。
圖2 各算法仿真結(jié)果比較
圖3 靜態(tài)性能曲線(m=8,n=40)
觀察圖3可以得到以下結(jié)論:
1)在不降低獲得最優(yōu)解質(zhì)量的前提下,本文算法擴(kuò)大了搜索范圍,提高了收斂速度,求解質(zhì)量和運(yùn)行效率比圖中其他算法顯著提高;
2)隨著進(jìn)化代數(shù)的遞增,完成時(shí)間持續(xù)減少最后趨于穩(wěn)定,說明優(yōu)秀基因被遺傳下來,使排產(chǎn)效果得以優(yōu)化;
3)收斂速度方面:此算法>文獻(xiàn)[6]算法>文獻(xiàn)[5]算法> SGA;
4)收斂代數(shù)方面:各算法進(jìn)化代數(shù)收斂區(qū)間:[50,200]。
通過研究某公司機(jī)加車間排產(chǎn)調(diào)度問題,建立其數(shù)學(xué)模型,并用遺傳算法對其求解。通過對基本遺傳算法三個方面的改進(jìn),即以個體適應(yīng)度值為參照自動調(diào)節(jié)交叉概率和變異概率,根據(jù)加工任務(wù)高度值劃分基因段來改善交叉操作,引入混沌理論優(yōu)化變異算子,極大提高了遺傳算法的收斂速度和對最優(yōu)解的搜索能力。通過對仿真結(jié)果的分析比較,改進(jìn)算法顯著縮短了機(jī)加車間的生產(chǎn)總時(shí)間,優(yōu)化效果比現(xiàn)有的算法更明顯,對機(jī)器加工行業(yè)排產(chǎn)優(yōu)化有一定借鑒意義。
[1]帥飛,陳兆剛,李向東.基于遺傳算法的橋式起重機(jī)節(jié)能調(diào)度優(yōu)化研究[J].制造業(yè)自動化,2013, 35(14):97-99.
[2]王進(jìn)峰,陰國富,雷前召,等.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J].現(xiàn)代制造工程,2013(5):50-53.
[3]張國慶,劉永進(jìn),梅中義.改進(jìn)的遺傳算法在復(fù)合材料車間計(jì)劃排產(chǎn)中的應(yīng)用研究[J].現(xiàn)代制造工程,2010(7):56-59.
[4]Wang H.Flexible flow shop scheduling: optimum,heuristics and artificial intelligence solutions[J].Expert Systems,2005,22(2):78-85.
[5]劉晶晶,翟正軍.基于改進(jìn)的遺傳算法的任務(wù)分配與調(diào)度[J].微電子學(xué)與計(jì)算機(jī),2006, 23(6):216-219.
[6]劉愛珍,王嘉禎,賈紅麗,等.改進(jìn)的多任務(wù)分配與調(diào)度遺傳算法[J].微電子學(xué)與計(jì)算機(jī),2007,24(9):162-168.
[7]張昕.改進(jìn)的遺傳算法在車間作業(yè)調(diào)度中的應(yīng)用研究[J].國防制造技術(shù),2013,2:019.
[8]李耀華,徐樂江,胡國奮,等.基于混沌遺傳算法的板坯入庫決策優(yōu)化方法[J].系統(tǒng)仿真學(xué)報(bào),2006,17(11):2620-2623.
[9]陳憶群,周如旗,林淑金,等.有車輛數(shù)限制的開放式車輛調(diào)度問題研究[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(003):595-601.
[10]蔣佳穎,王萬良,徐新黎,等.基于量子遺傳算法的染缸排產(chǎn)問題研究[J].計(jì)算機(jī)工程,2011,37(21):159-161,164.