【正文】 。在此，我對機械工程與自動化學院的所有老師表示感謝，祝你們身體健康，工作順利！同時還要感謝所有的同學們，正是因為有了你們的支持和鼓勵，此次畢業(yè)設(shè)計才能順利完成。大學四年來老師們給了我們很多指導和幫助。在這次設(shè)計的撰寫過程中，我得到了侯老師的精心指導。作為一個本科生，由于經(jīng)驗和知識的匱乏，如果沒有導師的督促指導以及周圍同學們的支持，很難獨立完成畢業(yè)設(shè)計。作為企業(yè)應(yīng)綜合考慮所有方面的影響，使企業(yè)綜合效益最大。本文基于車間生產(chǎn)局部考慮，選定的適應(yīng)度評價函數(shù)表明，生產(chǎn)任務(wù)越早完成越好。仍然存在需要進一步探討和研究之處，具體如下：可以探索將遺傳算法與其它領(lǐng)域搜索算法，如模擬退火算法、神經(jīng)網(wǎng)絡(luò)方法等結(jié)合，是否能獲得更佳的效果。遺傳算法作為一種非確定性的模擬自然算法，為作業(yè)車間調(diào)度等復雜系統(tǒng)的優(yōu)化提供了一種新的方法，并且已經(jīng)取得了很多的成果。本文通過簡易的編程即可實現(xiàn)生產(chǎn)車間作業(yè)的模擬調(diào)度，并且得到了最佳調(diào)度方案。通過MATLAB仿真驗證：較之其它調(diào)度方法，仿真調(diào)度的優(yōu)越性比較突出，能適合多條件約束的生產(chǎn)情形，能有效地提高生產(chǎn)效率。該模型是基于實際生產(chǎn)調(diào)度情況得到。遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，它在解決生產(chǎn)車間作業(yè)調(diào)度問題時，具有明顯的優(yōu)勢。在解決組合優(yōu)化問題方面的優(yōu)勢己受到各個領(lǐng)域?qū)＜?、學者的關(guān)注，其應(yīng)用領(lǐng)域已涉及自適應(yīng)控制、組合優(yōu)化、模式識別、機器學習、信息處理和人工生命等。本文主要研車間作業(yè)調(diào)度問題，研究是基于遺傳算法進行的。由于程序比較簡單，運行時間很短，所以程序比較合理。程序是我運行時間也與計算機的CPU有關(guān)，所以要提高程序的運行時間要從兩個方面入手，即計算機和程序本身。⑤最后輸出整個程序運行時間使用tic和toc函數(shù)，連續(xù)5次運行程序，時間如下： 程序運行時間次數(shù)12345時間/s 由表可得，每次的運行時間不同，但都是2秒多。由圖4，很容易得知每個機床在任何時間段的加工任務(wù)。例如,第一臺機床加工的第一道工序是“5” ,可以得知第五類工件的第一個工件。④： 基于機器的甘特圖圖4標明了工序和機床的分配關(guān)系,其間還標明各工序在對應(yīng)機器上的操作時間。 最優(yōu)適應(yīng)值收殮曲線 ③： 基于工件的甘特圖 根據(jù)圖3可以很明了的看出各工件的各個工序的開始加工時間、加工結(jié)束時間、還有各個工件工序?qū)?yīng)的加工機器。遺傳算法模擬生物進化的優(yōu)勝劣汰的規(guī)則，能在較大的范圍內(nèi)搜索并逐漸逼近最優(yōu)解，圖中的曲線記錄了這個逼近過程。由圖不難看出，最優(yōu)個體適應(yīng)值在進化代數(shù)10左右的時候已經(jīng)開始收斂。本調(diào)度問題的評價指標是尋求最短生產(chǎn)周期，根據(jù)輸出的Xp，再結(jié)合Q、W矩陣可以計算出最短的加工周期（目標函數(shù)值）: Tmin=63。按照工件編碼的出現(xiàn)順序依次，可將對應(yīng)的工件安排到指定的機器上加工，如第3次出現(xiàn)“2”代表工件2的第三道工序安排到機器5上加工。②運行結(jié)果輸出：最佳調(diào)度方案Xp（最優(yōu)染色體）；最優(yōu)適應(yīng)值收殮曲線和各代群體平均適應(yīng)值曲線；基于工件的工序時間甘特圖；基于機器的工序時間甘特圖；程序運行時間。 2 4 2 1 5 3 ]。 2 1 3 4 5 4 。 2 3 5 2 1 4 。 ％變異概率P=6。 % N 種群規(guī)模(取偶數(shù))Pc=。 endend 分析結(jié)果的可行性、運行時間以及目標函數(shù)值 仿真輸出結(jié)果①在仿真的過程中，輸入如下參數(shù)：M=100。 %收斂曲線2，各代群體平均適應(yīng)值的記錄% pos=find(FITNESS==minfitness)。 LC1(counter+1)=minfitness。 %記錄最佳個體和收斂曲線 minfitness=min(fitness)。OPT_E(counter+1,:)=Y2p(index(1),:)。farm1=POPU(index,:)。 FITNESS(i)=Z。 Y2p(i,:)=PE。 Y3p(i,j)=Q(Xp(j),num(Xp(j)))。 s4(Q(Xp(j),num(Xp(j))))= s3(Q(Xp(j),num(Xp(j))))+W(Xp(j),num(Xp(j)))。 s2(Xp(j))=s1(Xp(j))+W(Xp(j),num(Xp(j)))。 s3(Q(Xp(j),num(Xp(j))))=max(s1(Xp(j)),s4(Q(Xp(j),num(Xp(j)))))。 s1(Xp(j))=max(s2(Xp(j)),s4(Q(Xp(j),num(Xp(j)))))。 %記錄調(diào)度方案各機器的開工時間 s4=zeros(1,pn)。 %記錄調(diào)度方案各工序的開工時間 s2=zeros(1,pn)。 %記錄調(diào)度方案各機器的開工時間 ME=zeros(1,pn)。 %記錄調(diào)度方案各工序的開工時間 PE=zeros(1,pn)。 num=zeros(1,m)。%num=zeros(1,m)。 Y2p=zeros(2*N,pn)。 plotif=0。)end (6)選擇復制 FITNESS=zeros(1,2*N)。) hold on plot(counter,LC2(counter),39。plot(counter,LC1(counter),39。 counter=counter+1。 farm(i,:)=Xp。 Xp(I)= mu2。 mu1=Xp(I)。%變異概率為PmXp=POPU(i,:)。newfarm]。%交叉后的子代存入newfarm for j=1:6 oo(i,j)=length(find(newfarm(i,:)==j))。 A(i,cp(i,4))=c(i)。 d(i)=A(i,cp(i,4))。 A(i,cp(i,2))=a(i)。 b(i)=A(i,cp(i,2))。 cp(i,:)=unidrnd(pn,1,4)。 for i=1:N B(i,:)=farm(Ser(i),:)。%交叉產(chǎn)生的新種群存在其中 Ser=randperm(N)。 endend counter=0。 while length(find(farm(i,:)==gene))=pron(gene) gene=randint(1,1,[1 m])。(3)產(chǎn)生初始種群farm=zeros(N,pn)。OPT_E=zeros(M,pn)。%記錄每個工件的工序數(shù)for i=1:m pron(i)=length(find(W(i,:)~=0))。%收斂曲線1LC2=zeros(1,N)。%m是總工件數(shù)，n是總工序數(shù)Xp=zeros(M,pn)。(2)參數(shù)初始化pn=length(find(W~=0))。提出問題最優(yōu)解編碼和生成染色體群檢測染色體的適應(yīng)度選擇交叉滿足件件？變異 GA流程圖5 用Matlab實現(xiàn)模擬作業(yè)調(diào)度 程序設(shè)計思想及偽代碼文中所設(shè)計的遺傳算法是利用MATLAB語言編寫的，下面為程序的部分偽代碼：(1)遺傳算法參數(shù)(變量聲明)遺傳算法參數(shù)包括：m工件總數(shù)；n工序總數(shù)。按照一定的變異概率和變異方法，生成新的個體。依據(jù)適應(yīng)度選擇再生個體，適應(yīng)度高的個體被選中的概率高，適應(yīng)度低的個體第二章遺傳算法理論基礎(chǔ)可能被淘汰。確定適應(yīng)度函數(shù)并計算個體的適應(yīng)度，判斷是否符合優(yōu)化準則。據(jù)此，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。新一代形成中，根據(jù)適應(yīng)度的大小選擇部分后代，淘汰部分后代，從而保持種群大小是常數(shù)。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機的。這些染色體在后續(xù)迭代中不斷進化，稱為遺傳。種群中的每個個體是問題的一個解，即為“染色體”。從優(yōu)化搜索的角度而言，遺傳操作可使問題 遺傳過程的解，一代又一代地優(yōu)化，并逼進最優(yōu)解。在隨機選擇的染色體內(nèi)隨機交換兩個基因, 形成一個新的染色體即可。一般這樣操作很容易產(chǎn)生不合理的染色體表現(xiàn)型。 交叉算子交叉操作是遺傳算法中關(guān)鍵的一步, 它可以將父代的良好基因通過信息互換而產(chǎn)生更好的子代。遺傳算法中要求適應(yīng)度函數(shù)的取值為非負數(shù)，因此可用下式表示： 選擇算子選擇算子根據(jù)適應(yīng)度的值選擇個體遺傳到下一代群體中，本文采用錦標賽選擇法。 適應(yīng)度函數(shù)在遺傳算法中，適應(yīng)度是個體對生存環(huán)境的適應(yīng)程度，適應(yīng)度高的個體將獲得更多的生存機會。 生成初始種群本文采用的十進制的編碼方式，這里采用隨機產(chǎn)生初始種群的方法。表中第一次出現(xiàn)“2”代表“21”，第三次出現(xiàn)“2”代表“23”。如表 編碼對應(yīng)表工序211131414232222333121343編碼213443223114如第二類工件的編號就是“2”；工件的工序編號則是兩位十進制編號，第二類工件的三道工序分別是“21”、“22”、“23”。其中編碼的方式包括有基于操作的編碼、基于工件的編碼、基于先后表的編碼、基于工件對關(guān)系的編碼和基于機器的編碼等等。 編碼選擇一種合適的染色體表現(xiàn)型是應(yīng)用遺傳算法尋優(yōu)的首要和關(guān)鍵問題。遺傳算法就是對種群重復地進行選擇、交叉、變異等基本遺傳操作，不斷產(chǎn)生出比父代更適應(yīng)環(huán)境的新一代種群，直到滿足要求條件為止。 遺傳算法設(shè)計思想遺傳算法（Genetic Algorithms）是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。則n/m JSP 問題可描述如下：（1）設(shè)m個工件的集合為G，G={Gi︱i=（1，2，……，n）}；（2）設(shè)p臺機器的集合為J，J= {Ji︱i=（1，2，……，p）}；（3）工序（i，j）表示工件Gi的第j道工序，工序（i，j 1）稱為工序（i，j）的前道工序，工序（i，j +1）稱為工序（i，j）的后繼工序，ki表示工件Gi的總工序數(shù)，記k=max（k1，k2，……，km）；（4）矩陣Q=（gij）nxk為執(zhí)行工序的機器序號陣，gi表示執(zhí)行工序（i，j）的機器序號，當jki時，gi =0；（5）矩陣W=（wij）nxk為工序的工時陣，wij表示執(zhí)行工序（i，j）的耗時，當jki時，wi 0，一個矩陣對（Q，W）就可以完全描述一個車間作業(yè)調(diào)度問題；（6）一個調(diào)度被定義為S={(i,j)︱i=1,2……m，j=1，2……ki}，其中（i，j）表示工件i的第j道工序。(5) 不考慮工件加工的優(yōu)先權(quán)，不考慮加工準備時間。4 車間作業(yè)調(diào)度的建模 車間作業(yè)調(diào)度問題描述不失一般性，設(shè)n個作業(yè)m 臺機器的車間作業(yè)調(diào)度問題（表示為：n/m JSP）滿足以下約束條件：（1）每個工件包含若干道工序；（2）各工件必須按工藝路線以指定的次序在機器上加工；（3）任何一個工件的前一道工序加工完成后，方能進行后一道工序的加工，在同一臺機器上一個加工任務(wù)完成之后，方能開始另一個加工任務(wù)。事實上，混亂遺傳算法直接操作的對象既有個體，也有空間結(jié)構(gòu)，這自然使它喪失了只操作個體的經(jīng)典遺傳算法所具有的隱含并行性。(Messy Genetic Algorithm)混亂遺傳算法是由Goldberg提出的，它的目的是解決經(jīng)典遺傳算法中所謂的連接問題，即經(jīng)典遺傳算法很容易破壞定義位置較遠的模式問題。而細胞模型的實施則是在一個單一種群中，通過對經(jīng)典整體性選擇與雜交機制的局部化來達到并行化目的。并行遺傳算法大致分為兩種，一種是島模型(Island Model)，稱為粗粒并行遺傳算法(Coarse Grained PGA)。這在生物學中被稱為為Lamarckian evolution和Baldwin effect。把