基于遺傳算法的車間調(diào)度算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 得分：_南 京 大 學(xué)研究生課程論文20112012學(xué)年 第一學(xué)期課 程 號：73327 課程名稱：Matlab語言論文題目：基于遺傳算法的車間調(diào)度算法學(xué)科專業(yè)：交通運(yùn)輸工程學(xué) 號：姓 名：李三立任課教師：王雄 二一一年十二月基于遺傳算法的車間調(diào)度算法【摘要】車間調(diào)度問題具有建模復(fù)雜性、計(jì)算復(fù)雜性、動(dòng)態(tài)多約束、多目標(biāo)性等特點(diǎn)。近幾年，各種演化計(jì)算方法逐漸被引入到生產(chǎn)調(diào)度中，特別是遺傳算法的應(yīng)用。本文主要介紹了企業(yè)車間調(diào)度問題的遺傳算法實(shí)現(xiàn)，通過Matlab實(shí)現(xiàn)對遺傳算法的編程，其仿真調(diào)度結(jié)果驗(yàn)證了遺傳算法用于求解車間調(diào)度問題的可行性和有效性?！娟P(guān)鍵詞】遺傳算法 車間

2、調(diào)度 MatlabFlow-Shop scheduling based on genetic algorithmAbstract：The Flow-Shop scheduling problem has the property of modeling complexity, computational complexity, dynamic multi-constraint and multi-targeted. In recent years a variety of evolutionary computation methods, in particular, the applicat

3、ion of genetic algorithms has been gradually introduced into the production scheduling problem. This paper puts forward a method to design Flow-Shop by using genetic algorithm. Program about genetic algorithm designs by using Matlab, Simulation results of our experiment show the feasibility and effe

4、ctiveness of genetic algorithm for solving Flow-Shop scheduling.Key words：Genetic algorithm Flow-Shop scheduling Matlab引言生產(chǎn)調(diào)度對企業(yè)的生產(chǎn)作業(yè)過程具有重要的作用。有效的調(diào)度方法和優(yōu)化技術(shù)是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。研究和解決好調(diào)度問題，能極大提高企業(yè)的生產(chǎn)效率，從而提高這些企業(yè)的競爭力。自從1954年Johnson發(fā)表第一篇關(guān)于流水車間調(diào)度問題的文章以來，流水車間調(diào)度問題引起了許多學(xué)者的關(guān)注，提出了許多解決的方法。其中，以遺傳算法、模擬退火、禁忌搜索以及人工

5、神經(jīng)網(wǎng)絡(luò)為代表的智能化優(yōu)化技術(shù)迅速發(fā)展，用來解決流水車間調(diào)度問題，受到人們的普遍關(guān)注。遺傳算法以其優(yōu)良的計(jì)算性能和顯著的應(yīng)用效果而特別引人注目，很多啟發(fā)式混合方法都是在此基礎(chǔ)上發(fā)展起來的。本文采用遺傳算法進(jìn)行求解。1車間調(diào)度問題描述車間調(diào)度是指根據(jù)產(chǎn)品制造的合理需求分配加工車間順序，從而達(dá)到合理利用產(chǎn)品制造資源，提高企業(yè)經(jīng)濟(jì)效益的目的。車間調(diào)度問題從數(shù)學(xué)上可以描述為有n個(gè)代加工的零件在m臺機(jī)器上加工，車間調(diào)度的數(shù)學(xué)模型如下：（1） 機(jī)器集，表示第j臺機(jī)器，j=1,2,m。（2） 零件集，表示第i個(gè)零件，i=1,2,n。（3） 工序序列集，表示零件加工工序序列。（4） 可選機(jī)器集,表示零件加工工

6、序j可以選擇的加工機(jī)器。（5） 使用機(jī)器加工零件的時(shí)間矩陣T，表示第i個(gè)零件使用第j個(gè)機(jī)器的加工時(shí)間。（6） 使用機(jī)器加工零件的費(fèi)用矩陣C，表示第i個(gè)零件使用第j個(gè)機(jī)器的加工費(fèi)用。另外，問題需要滿足的條件包括每個(gè)零件的各道工序使用每臺機(jī)器不多于1次，每個(gè)零件加工都按照一定的順序進(jìn)行加工。2遺傳算法的車間調(diào)度算法模型建立基于多層編碼遺傳算法的車間調(diào)度算法流程如下圖所示。其中，種群初始化模塊初始化種群構(gòu)成問題的初始解集，適應(yīng)度值計(jì)算模塊計(jì)算染色體的適用度值，選擇操作采用輪盤賭法選擇優(yōu)秀個(gè)體；交叉操作采用整數(shù)交叉法得到優(yōu)秀個(gè)體，變異操作采用證書變異法得到優(yōu)秀個(gè)體。算法流程圖3模型算法的實(shí)現(xiàn)3.1個(gè)體

7、編碼染色體編碼方式為證書編碼，每個(gè)染色體表示全部工件的加工順序，當(dāng)待加工的工件總數(shù)為n，工件的加工工序共為時(shí)，則個(gè)體表示為長度為的整數(shù)串。其中，染色體的前半部分表示所有工件在機(jī)器上的加工順序，后半部分表示工件每道工序的加工機(jī)器序號。如個(gè)體2 4 3 1 1 2 3 4 2 1 3 3 2 2 1 3該個(gè)體表達(dá)了4個(gè)加工工序都是2次的工件在3臺機(jī)器上的加工順序。其中，前8位表示工件的加工順序，為工件2工件4工件3工件1工件1工件2工件3工件4；9到16位表示加工機(jī)器，依次為機(jī)器2機(jī)器1機(jī)器3機(jī)器3機(jī)器2機(jī)器2機(jī)器1機(jī)器3。3.2適應(yīng)度值染色體的適應(yīng)度值為全部工件的完成時(shí)間，適應(yīng)度值計(jì)算公式為：其

8、中，time指全部任務(wù)完成時(shí)間，全部工件完成時(shí)間越短，該染色體越好。3.3選擇操作選擇操作采用輪盤賭法選擇適應(yīng)度較好的染色體，個(gè)體選擇概率為：；其中，表示染色體i在每次選擇中被選中的概率。3.4交叉操作種群通過交叉操作獲得新染色體，從而推動(dòng)整個(gè)種群向前進(jìn)化，交叉操作采用整數(shù)交叉法。交叉操作首先從種群中隨機(jī)選取兩個(gè)染色體，并取出每個(gè)染色體的前位，然后隨機(jī)選擇交叉位置進(jìn)行交叉。操作方法如下：交叉位置為5，只對個(gè)體前位進(jìn)行交叉。個(gè)體-112 3 2 2 3 交叉 極值-221 211 1 221 211 1交叉后某些工件的工序多余（如個(gè)體中的工件2），某些工件的工序缺失（如個(gè)體中的工件1），因此，把

9、工件工序多余的操作變?yōu)楣ぜば蛉笔У牟僮鳎唇徊媲皞€(gè)體的操作機(jī)器來調(diào)整個(gè)體位到位的加工機(jī)器，如下所示：交叉后個(gè)體- 調(diào)整 3.5變異操作種群通過變異操作獲得新的個(gè)體，從而推動(dòng)整個(gè)種群向前進(jìn)化。變異算子首先從種群中隨機(jī)選取變異個(gè)體，然后選擇變異位置pos1和pos2，最后把個(gè)體中pos1和pos2位的加工工序以及對應(yīng)的加工機(jī)器序號對換，如下列示，交叉位置為2和4。個(gè)體- 交叉 個(gè)體-4Matlab程序?qū)崿F(xiàn)和仿真結(jié)果采用多層編碼遺傳算法求解車間調(diào)度問題，共有6個(gè)工件，在10臺機(jī)器上加工，每個(gè)工件都要經(jīng)過6道加工工序，每個(gè)工序可選擇機(jī)器序號下表所示。工序可選機(jī)器表工件工件1工件2工件3工件4工件5

10、工件6工序13，1023，9452工序2134，71，92，74，7工序325，86，83，73，106，9工序44，76，712，86，91工序56，812，10515，8工序654，10564，83每道工序加工時(shí)間如下表所示。工序加工時(shí)間表工件工件1工件2工件3工件4工件5工件6工序13，561，4762工序21085，74，310，124，7工序391，45，64，67，96，9工序45，45，653，58，81工序53，339，11155，8工序6103，3134，73根據(jù)多層編碼遺傳算法原理，在Matlab中編程實(shí)現(xiàn)基于多層編碼遺傳算法的車間調(diào)度算法，首先進(jìn)行個(gè)體初始化，然后采用選擇

11、、交叉和變異操作搜索最佳個(gè)體，得到最優(yōu)的車間調(diào)度方法，主要代碼如下：PNumber MNumber=size(Jm); %PNumber 工件個(gè)數(shù)、MNumber工序個(gè)數(shù)trace=zeros(2, MAXGEN); %尋優(yōu)結(jié)果的初始值WNumber=PNumber*MNumber; %工序總個(gè)數(shù)Number=zeros(1,PNumber); for i=1:PNumber Number(i)=MNumber; endChrom=zeros(NIND,2*WNumber);for j=1:NIND WPNumberTemp=Number; for i=1:WNumber val=unidrn

12、d(PNumber); while WPNumberTemp(val)=0 val=unidrnd(PNumber); end Chrom(j,i)= val; WPNumberTemp(val)=WPNumberTemp(val)-1; Temp=Jmval,MNumber-WPNumberTemp(val); SizeTemp=length(Temp); Chrom(j,i+WNumber)= unidrnd(SizeTemp); endend PVal ObjV P S=cal(Chrom,JmNumber,T,Jm); %計(jì)算目標(biāo)函數(shù)值while gen<MAXGEN % 循環(huán)尋

13、找 FitnV=ranking(ObjV); %分配適應(yīng)度值 SelCh=select('rws', Chrom, FitnV, GGAP); %選擇操作 SelCh=across(SelCh,XOVR,Jm,T); %交叉操作 SelCh=aberranceJm(SelCh,MUTR,Jm,T); %變異操作PVal ObjVSel P S=cal(SelCh,JmNumber,T,Jm); %計(jì)算目標(biāo)適應(yīng)度值end Chrom ObjV =reins(Chrom, SelCh,1, 1, ObjV, ObjVSel); %重新插入新種群 gen=gen+1; trace(1

14、, gen)=min(ObjV); %保存最優(yōu)值 trace(2, gen)=mean(ObjV); if gen=1 % 記錄最佳值 Val1=PVal; Val2=P; MinVal=min(ObjV); STemp=S; end if MinVal> trace(1,gen) % 記錄最小的工序 Val1=PVal; Val2=P; MinVal=trace(1,gen); STemp=S; endendPVal=Val1; P=Val2; S=STemp; figure(1) % 描繪解的變化plot(trace(1,:);hold on;plot(trace(2,:),'

15、;-.');grid;legend('解的變化','種群均值的變化');figure(2); % 顯示最優(yōu)解MP=S(1,PNumber*MNumber+1:PNumber*MNumber*2);for i=1:WNumber val= P(1,i); a=(mod(val,100); b=(val-a)/100); Temp=Jmb,a; mText=Temp(MP(1,i); x1=PVal(1,i); x2=PVal(2,i); y1=mText-1; y2=mText; PlotRec(x1,x2,mText); PlotRec(PVal(1,i

16、),PVal(2,i),mText); hold on; fill(x1,x2,x2,x1,y1,y1,y2,y2,1-1/b,1/b,b/PNumber); text(x1+x2)/2,mText-0.25,num2str(P(i);end算法的基本參數(shù)為：種群數(shù)目為40，最大迭代次數(shù)為50，交叉概率為0.8，變異概率為0.6，算法搜索得到的全部工件完成的最短時(shí)間為47s，算法搜索過程和最優(yōu)個(gè)體對應(yīng)的零件加工甘特圖如下圖所示。5結(jié)論本文提出多層編碼遺傳算法的車間調(diào)度算法可以滿足生產(chǎn)調(diào)度的動(dòng)態(tài)性要求。Matlab仿真結(jié)果顯示該算法具有實(shí)用性和有效性，為生產(chǎn)應(yīng)用提供一個(gè)強(qiáng)有力的輔助工具，不需要做過多的改變就能滿足其他類似調(diào)度應(yīng)用。該遺傳算法對車間調(diào)度問題大有改進(jìn)，縮短了整個(gè)加工工序時(shí)間，減少目標(biāo)函數(shù)運(yùn)算量，為快速制訂生產(chǎn)計(jì)劃提供了一種切實(shí)有效的方法。參考文獻(xiàn)1金志勇.基于遺傳算法的車間調(diào)度系統(tǒng)研究D.武漢理工大學(xué),學(xué)位