【正文】 老師們嚴(yán)謹(jǐn)?shù)闹螌W(xué)，優(yōu)良的作風(fēng)和敬業(yè)的態(tài)度，為我們樹立了為人師表的典范。在此，沒有考慮產(chǎn)品完工時間對于企業(yè)庫存壓力的影響，實際上，如果產(chǎn)品提前完工，一定會增加企業(yè)的庫存成本或帶來其它方面的影響。Matlab是一個包含大量計算算法的集合，具有強大的計算機數(shù)據(jù)處理能力和出色的圖形處理功能。遺傳算法是一種通用而有效的解決最優(yōu)化問題的方法，它不僅具有并行搜索、魯棒性強等特點，而且遺傳算法由于其結(jié)構(gòu)的開放性，可以更好地綜合多種優(yōu)化方法來獲得更優(yōu)的性能。調(diào)度結(jié)果通過甘特圖的顯示，將調(diào)度結(jié)果圖示化有利于工件在加工前各機器的準(zhǔn)備工作，目標(biāo)就是降低不必要的等待浪費。各代群體平均適應(yīng)值在不斷面的變化，這是由于遺傳算法不定向搜索造成的。 分析結(jié)果①最優(yōu)調(diào)度方案：Xp=[ 4 3 3 5 1 6 1 2 5 3 4 6 2 4 6 3 5 4 5 1 5 3 2 1 6 4 6 1 2 4 2 5 1 2 6 3]由Xp可以得出，1～6（每個工件代碼）各出現(xiàn)6次，即代表每個工件的各道工序都在調(diào)度方案中。 % P 機床數(shù)目%Q mn的矩陣，存儲m個工件n個工序?qū)?yīng)的加工機器Q=[ 3 1 2 4 3 5 。 %收斂曲線1，各代最優(yōu)個體適應(yīng)值的記錄 LC2(counter+1)=meanfitness。 end [fitness index]=sort(FITNESS)。 PE(j)= s2(Xp(j))。 %記錄調(diào)度方案各工序的完工時間 s3=zeros(1,pn)。 %num用于循環(huán)過程記錄工件號出現(xiàn)的次數(shù) for i=1:2*N Xp= POPU(i,:)。.39。 Xp(I1)= mu1。 end end %新舊種群合并 POPU=[farm。 A(i,cp(i,1))=b(i)。%設(shè)置迭代計數(shù)器while counter ~=M (4)交叉newfarm=zeros(N,pn)。end OPT_S=zeros(M,pn)。 P機器總數(shù)；M遺傳算法進(jìn)化代數(shù)：N種群規(guī)模；Pc交叉概率；Pm變異概率；Q機器序號矩陣；W操作時間矩陣；Xp最優(yōu)調(diào)度方案； farm種群。遺傳算法搜索求解的基本步驟是:確定編碼方案并隨機產(chǎn)生種群，種群中個體的數(shù)目一定，每個個體表示為染色體的基因編碼。個體遺傳算子的操作都是在隨機擾動情況下進(jìn)行的。 變異算子變異操作在本問題中相對而言比較簡單。也就是在一個給定的合理的染色體的基礎(chǔ)上，產(chǎn)生兩個隨機數(shù)作為交換位置，再交換兩位置之間的基因，進(jìn)而產(chǎn)生新的染色體。遺傳算法的編碼技術(shù)必須考慮染色體的合法性、可行性、有效性以及問題解空間的表征的完全性。(6) 一個工件同一時間只能在一臺機器上加工，一臺機器同一時間只能加工一個工件，加工的開始時間為O。島模型考慮的是種群的空間結(jié)構(gòu)，而細(xì)胞模型考慮的是一種群中個體的空間結(jié)構(gòu)。在遺傳算法中以各種形式融入模擬退火思想，從而使得遺傳算法在理論上具有全局收斂性，是一個有意義的研究方向。 變異率(記為Pm)定義為種群中變異基因數(shù)中的百分比。⑤變異變異是一種基本運算，它在染色體上自發(fā)地產(chǎn)生隨機的變化。④交叉交叉算子是母體空間到個體空間的映射，記作Tc:S2→S交叉是最主要的遺傳運算，它同時對兩個染色體操作，交叉操作用于結(jié)合來自父染色體和母染色體的特征來產(chǎn)生新的子個體，在解空間中進(jìn)行有效搜索，同時降低對有效模式的破壞概率。根據(jù)求解問題特性來定義反應(yīng)個體對問題環(huán)境適應(yīng)能力和優(yōu)劣程度的測定函數(shù)。①編碼將問題的潛在解用一些參數(shù)表示，這些參數(shù)(基因)排列在一起形成一個特定的編碼(染色體)，代表一個個體，從而將問題的狀態(tài)空間與遺傳算法的碼空間相對應(yīng)，這很大程度上依賴于問題的性質(zhì)，并將影響遺傳操作的設(shè)計。對于優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，遺傳算法對于適應(yīng)度函數(shù)并不要求可導(dǎo)等條件，只要求適應(yīng)度函數(shù)為可加以比較的非負(fù)函數(shù)。4. 基因（Gene）：基因是串中的元素，基因用于表示個體的特征。應(yīng)用遺傳算法時，根據(jù)具體問題的特性，進(jìn)行編碼與適應(yīng)度設(shè)計之后，其余操作按常規(guī)算子自動運行即可，只等最后輸出最優(yōu)解個體，而不必關(guān)心求解的實際過程，所以遺傳算法非常便于處理那些輸入輸出之間因果關(guān)系復(fù)雜的問題。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點:(1)搜索過程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個體。隨著各種特殊調(diào)度問題的攻克和新方法、新設(shè)備的出現(xiàn)，作業(yè)車間調(diào)度研究正在向動態(tài)、敏捷、多重入、多資源、智能化的方向發(fā)展。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的時間里能對復(fù)雜的規(guī)劃問題提供較好的次優(yōu)解，并能對解的次優(yōu)性進(jìn)行定量評估，近年來已成為解決復(fù)雜生產(chǎn)調(diào)度問題的一種重要方法。（7）模擬退火模擬退火法（SA）是將組合優(yōu)化問題與統(tǒng)計力學(xué)的熱平衡問題類比，通過模擬退火過程，可找到全局(或近似)最優(yōu)解。Petri網(wǎng)具有很強地建模能力，對于描述系統(tǒng)的不確定性和隨機性也具有一定地優(yōu)越性，目前Petri網(wǎng)已經(jīng)用于FMS建模和調(diào)度，但尚存在下列問題:l)節(jié)點語義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。（3）基于知識的調(diào)度方法近年來受實際需要的推動，基于知識的智能調(diào)度系統(tǒng)和方法的研究取得了很大的進(jìn)展，基于只是的調(diào)度方法是用專家系統(tǒng)自動產(chǎn)生調(diào)度或輔助人去調(diào)度，它是傳統(tǒng)的調(diào)度方法與基于知識的調(diào)度評價相結(jié)合的方法。調(diào)度的目標(biāo)是將作業(yè)合理地安排到各機床以及合理地使用其它生產(chǎn)資源，并合理安排作業(yè)的加工次序和加工時間，使約束條件被滿足，同時優(yōu)化其中的一些生產(chǎn)性能指標(biāo)。如果車間有足夠多的機床設(shè)備和其它生產(chǎn)資源分配給每個工件或每條工藝加工路線，那么一切都會井然有序，也就不存在調(diào)度問題。(6) 有序加工，無序加工。此外，還有人為的附加因素，如機器負(fù)荷平衡等等約束條件。每個工件又要考慮它的加工時間、安裝時間和操作順序等因素，因而相當(dāng)復(fù)雜，調(diào)度問題往往是通過等式或不等式等約束條件來計算的，屬于典型的NPhard問題。第二章詳細(xì)闡述了車間作業(yè)調(diào)度問題，分析了調(diào)度模型及模型描述，總結(jié)了車間調(diào)度的求解方法。此后，很多學(xué)者就遺傳算法在車間調(diào)度問題方面的應(yīng)用做了大量研究。1954年，Johnson對兩臺機床FlowShop型調(diào)度問題進(jìn)行了研究后，提出了解決車間調(diào)度部分特殊問題的優(yōu)化算法，代表理論研究的開始。由于大量的調(diào)度問題是NP完全問題[13]，近幾年各種智能計算方法逐漸被引入到調(diào)度問題中，如遺傳算法、模擬退火算法等，但是目前尚無有效的求解策略，因此調(diào)度問題的研究也具有重要的理論意義[5]。每個作業(yè)都由一些工序組成，而每個工序則必須由指定的機器加工處理。為了保證生產(chǎn)的高效穩(wěn)定運行，以獲得最大的經(jīng)濟效益，企業(yè)管理者必須能根據(jù)市場上原料供應(yīng)和產(chǎn)品需求的變化進(jìn)行經(jīng)營決策和組織生產(chǎn)，能利用現(xiàn)有的資源做出最有效的調(diào)度方案，使企業(yè)生產(chǎn)獲得最大的綜合經(jīng)濟效益。 contrary to job scheduling of the production process, we describes the classification of scheduling and conventional scheduling methods。調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個加工對象確定具體的加工路線、時間、機器和操作等。車間作業(yè)調(diào)度技術(shù)是生產(chǎn)管理技術(shù)的核心技術(shù)，直接關(guān)系到企業(yè)產(chǎn)品以及服務(wù)的質(zhì)量。此外，用Matlab強大的數(shù)值計算能力和眾多庫函數(shù)來編寫算法，通過仿真實例對算法的求解效果進(jìn)行了測試。當(dāng)前的機械制造企業(yè)采用多元化、多品種、小批量、高柔性生產(chǎn)方式來適應(yīng)激烈的市場競爭。有關(guān)資料表明，在制造過程中95％的時間消耗在非切削過程中。計算機集成制造系統(tǒng)(CIMS)能給企業(yè)帶來巨大的綜合經(jīng)濟效益，因此國內(nèi)、外各大中型企業(yè)都研究與實施計算機集成制造系統(tǒng)。因此，合理的生產(chǎn)調(diào)度是生產(chǎn)系統(tǒng)的高效運行的前提，生產(chǎn)調(diào)度可以保證:生產(chǎn)計劃的有效實施；高效低耗地使用生產(chǎn)資源；均衡生產(chǎn)，減少在制品的資金占用；縮短產(chǎn)品生產(chǎn)周期、確保產(chǎn)品交貨期、降低生產(chǎn)成本，以適應(yīng)多變的市場需求。90年代至今，隨著計算機應(yīng)用技術(shù)的發(fā)展，各種方法在車間調(diào)度問題的研究中得到了充分的發(fā)揮，同時新的研究手段層出不窮，人工智能、人工神經(jīng)網(wǎng)絡(luò)、基因遺傳算法的作業(yè)調(diào)度方法等被廣泛用于Jobshop調(diào)度問題的研究。 本文的研究內(nèi)容本文針對先進(jìn)制造環(huán)境下車間管理與調(diào)度的特點，分析了車間作業(yè)調(diào)度的特點，給出了遺傳算法求解車間作業(yè)調(diào)度的過程。并且分析結(jié)果的可行性，運行時間以及目標(biāo)值。如機器故障、緊急任務(wù)插入、作業(yè)交貨期的變更等一些突發(fā)事件也增加了調(diào)度的難度和隨機性。(3)基于調(diào)度費用和調(diào)度性能的指標(biāo)。生產(chǎn)車間出現(xiàn)調(diào)度問題主要原因是生產(chǎn)資源受到了制約。典型的車間調(diào)度問題包括一個要完成的作業(yè)集(工件集)，每個作業(yè)由一個操作集(工序集)組成，各操作的加工需要生產(chǎn)資源(機器、人員、刀具和輔助資源)，并且必須按一些可行的工藝次序進(jìn)行加工。（2）基于啟發(fā)式規(guī)則的調(diào)度方法最早的近似算法便是基于啟發(fā)式規(guī)則的調(diào)度算法(也稱調(diào)度規(guī)則)，其本質(zhì)是給每一個生產(chǎn)任務(wù)和操作，并賦予優(yōu)先級，優(yōu)先級高的生產(chǎn)任務(wù)和操作優(yōu)先考慮。c)仿真的準(zhǔn)確性很大程度受編程人員的判斷和技巧的限制。在調(diào)度問題的離散圖模型基礎(chǔ)上，啟發(fā)式圖搜索法在調(diào)度領(lǐng)域得到應(yīng)用。該方法已經(jīng)用于解決nowshop調(diào)度問題。③生產(chǎn)計劃與調(diào)度集成策略：生產(chǎn)計劃、調(diào)度的集成研究具有全局優(yōu)化的特征，也符合先進(jìn)制造模式的思想。經(jīng)過幾十年的發(fā)展，遺傳算法已經(jīng)在數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、圖象處理等領(lǐng)域得到成功的應(yīng)用，并顯示出其良好的性能，特別是在求解復(fù)雜優(yōu)化問題上的巨大潛力，使得幾乎所有領(lǐng)域的研究人員都嘗試過遺傳算法在各自專業(yè)領(lǐng)域的應(yīng)用，如:人工生命、神經(jīng)網(wǎng)絡(luò)、組合優(yōu)化、機器學(xué)習(xí)、自適應(yīng)控制、系統(tǒng)辨識等等。(4)對搜索空間沒有任何特殊要求(如連通性、凸性等)，只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其他輔助信息，適應(yīng)范圍更廣。2. 群體（Population）：一定數(shù)量的個體組成了群體，或叫種群。串結(jié)構(gòu)空間對應(yīng)于遺傳學(xué)中的基因型（Genotype）的集合。(Mutation)：在細(xì)胞進(jìn)行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生新的染色體，這些新的染色體表現(xiàn)出新的性狀。實數(shù)編碼直接在解的表現(xiàn)型上進(jìn)行遺傳操作，目前在高維復(fù)雜優(yōu)化問題中得到廣泛應(yīng)用，并取得了較好效果。局部選擇(local selection)。為了便于解釋，下面設(shè)解向量s1= (v1（1），v2(1)，…，vm（1）)和s1=( v1（2），v2（2），…，vm（2）)是兩個父解向量，sz={ s1 s2，…sm }和sw=( s1 ，s2，…sn)是通過雜交獲得的兩個后代。迭代代數(shù)，即算法進(jìn)化代數(shù)，代數(shù)的大小直接關(guān)系到解的質(zhì)量和計算速度。第三種準(zhǔn)則有一定的自適應(yīng)性，例如根據(jù)算法的評價的一些規(guī)則。并行遺傳算法大致分為兩種，一種是島模型(Island Model)，稱為粗粒并行遺傳算法(Coarse Grained PGA)。4 車間作業(yè)調(diào)度的建模 車間作業(yè)調(diào)度問題描述不失一般性，設(shè)n個作業(yè)m 臺機器的車間作業(yè)調(diào)度問題（表示為：n/m JSP）滿足以下約束條件：（1）每個工件包含若干道工序；（2）各工件必須按工藝路線以指定的次序在機器上加工；（3）任何一個工件的前一道工序加工完成后，方能進(jìn)行后一道工序的加工，在同一臺機器上一個加工任務(wù)完成之后，方能開始另一個加工任務(wù)。遺傳算法就是對種群重復(fù)地進(jìn)行選擇、交叉、變異等基本遺傳操作，不斷產(chǎn)生出比父代更適應(yīng)環(huán)境的新一代種群，直到滿足要求條件為止。表中第一次出現(xiàn)“2”代表“21”，第三次出現(xiàn)“2”代表“23”。 交叉算子交叉操作是遺傳算法中關(guān)鍵的一步, 它可以將父代的良好基因通過信息互換而產(chǎn)生更好的子代。種群中的每個個體是問題的一個解，即為“染色體”。新一代形成中，根據(jù)適應(yīng)度的大小選擇部分后代，淘汰部分后代，從而保持種群大小是常數(shù)。按照一定的變異概率和變異方法，生成新的個體。%收斂曲線1LC2=zeros(1,N)。 while length(find(farm(i,:)==gene))=pron(gene) gene=randint(1,1,[1 m])。 cp(i,:)=unidrnd(pn,1,4)。 A(i,cp(i,4))=c(i)。 mu1=Xp(I)。plot(counter,LC1(counter),39。 Y2p=zeros(2*N,pn)。 %記錄調(diào)度方案各機器的開工時間