【正文】 多余的運(yùn)算。6 結(jié)論與展望如今，制造業(yè)環(huán)境不斷變化，企業(yè)間競爭日趨激烈，對于生產(chǎn)調(diào)度問題的研究就具有非常重要的現(xiàn)實(shí)意義?；旌纤惴ㄊ悄壳把芯寇囬g調(diào)度問題的一個(gè)重要發(fā)展趨勢，它不僅僅使用一種調(diào)度算法，而是在實(shí)際系統(tǒng)中使用組合優(yōu)化方法通過與其它各種優(yōu)化算法相互借鑒相互溶合，以彌補(bǔ)各自的缺點(diǎn)，發(fā)揮各自的優(yōu)勢。最后感謝中北大學(xué)大學(xué)四年來對我的培養(yǎng)。在以后的各種工程中可以同樣利用Matlab來建模、仿真和計(jì)算。由于程序比較簡單，所以運(yùn)行時(shí)間短暫。在安排各工件的工序時(shí)，必須保證該工件的該工序前道工序已經(jīng)加工完畢，這樣調(diào)度結(jié)果可行性得以驗(yàn)證。if counter=2 if LC1(counter+1)=LC1(counter) farm=farm1(1:N,:)。 ME(j)=s4(Q(Xp(j),num(Xp(j))))。 %num用于循環(huán)過程記錄工件號(hào)出現(xiàn)的次數(shù) PS=zeros(1,pn)。 end end farm(pos(1),:)=X。 c(i)=A(i,cp(i,3))。OPT_M=zeros(M,pn)。若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)向第三步。 遺傳算法流程在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個(gè)體按照它們對環(huán)境適應(yīng)度(適應(yīng)度評(píng)估)施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。本文采用基于工序的編碼，利用十進(jìn)制直接的表達(dá)方式。在混亂遺傳算法中，個(gè)體由其每個(gè)分量的位置與取值共同表示，位置可以不按次序排列，也并不是所有分量都在個(gè)體的表示中出現(xiàn)。若變異率太低，一些有用的基因就不能進(jìn)入選擇，若太高，既隨機(jī)的變化太多，那么后代就可能失去雙親繼承下來的好特性，這樣算法就會(huì)失去從過去的搜索中學(xué)習(xí)的能力。單點(diǎn)交叉即首先在雙親的染色體上隨機(jī)地選一個(gè)交叉位置，將交換位置的右段互相交換，從而形成兩個(gè)新的后代。二進(jìn)制編碼將問題的解用一個(gè)二進(jìn)制0和1字符串來表示，十進(jìn)制編碼將問題的解用一個(gè)十進(jìn)制串來表示。它們的值稱為等位基因（Alleles）。這使的遺傳算法能以較少的計(jì)算獲得較大的收益。由于調(diào)度問題的復(fù)雜性，其研究策略主要形成了以下幾種：①分解與成組策略：利用分解生產(chǎn)計(jì)劃或GT的調(diào)度策略可以大大降低問題的計(jì)算復(fù)雜性和規(guī)模，求得調(diào)度問題的較優(yōu)解，同時(shí)優(yōu)化系統(tǒng)的一些性能指標(biāo)。Petri網(wǎng)是基于FMS中作業(yè)的加工流程建模，當(dāng)作業(yè)需求或工藝稍微變動(dòng)，必須改模型結(jié)構(gòu)。這類方法從理論上來說是能求得最優(yōu)解，但通常由于計(jì)算復(fù)雜性原因，不能獲得真正的實(shí)用。 車間作業(yè)調(diào)度問題描述一般車間調(diào)度問題可以描述為:n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件分為k道工序，每道工序可在不同的機(jī)器上加工。在現(xiàn)有計(jì)算條件下，一般優(yōu)化方法對于車間調(diào)度問題是低效甚至是無能為力的。國內(nèi)對于車間調(diào)度問題的研究起步比較晚，基本上是靠調(diào)度人員的經(jīng)驗(yàn)進(jìn)行車間作業(yè)分配和調(diào)度。具體就是針對一項(xiàng)可分析的工作（如產(chǎn)品制造），探討盡可能滿足約束條件（如交貨期、工藝路線、資源情況）的前提下，通過下達(dá)生產(chǎn)指令，安排其組成部分（操作哪些資源）、其加工時(shí)間及加工的先后順序，以達(dá)到合理利用產(chǎn)品制造資源，獲得產(chǎn)品制造時(shí)間和成本的最優(yōu)化[14] ，提高企業(yè)經(jīng)濟(jì)效益的目的。對于中小型企業(yè)來敏捷制造就是先進(jìn)的生產(chǎn)模式，生產(chǎn)調(diào)度方案的優(yōu)劣是敏捷制造的標(biāo)志。作業(yè)車間調(diào)度問題是一個(gè)典型的NP—hard問題，是最困難的組合優(yōu)化問題之一。本文主要研究了制造車間作業(yè)調(diào)度問題。在這種生產(chǎn)模式下如何進(jìn)行組織管理，包括如何組織動(dòng)態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計(jì)劃、如何進(jìn)行調(diào)度是企業(yè)面臨的主要問題。制造系統(tǒng)生產(chǎn)管理的核心就是車間生產(chǎn)調(diào)度，生產(chǎn)管理任務(wù)順利實(shí)施與完成，最終要靠合理的生產(chǎn)調(diào)度來保證。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，國內(nèi)也掀起了一股應(yīng)用遺傳算法研究車間作業(yè)調(diào)度問題的熱潮。(2)動(dòng)態(tài)隨機(jī)性調(diào)度中存在很多隨機(jī)性和不確定性。每一臺(tái)機(jī)器在每個(gè)時(shí)間只能加工某個(gè)工件的某道工序，只能在上道工序加工完成才能開始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。采用數(shù)學(xué)規(guī)劃的方法，表達(dá)清晰，易于在計(jì)算機(jī)上求解，但生產(chǎn)環(huán)境具有很多不確定的因素，存在建模不確定性和求解空間太大，造成計(jì)算困難，特別是不能反映特定調(diào)度領(lǐng)域的自然結(jié)構(gòu)，所以很難應(yīng)用經(jīng)驗(yàn)知識(shí)去處理調(diào)度問題。3)很難對高級(jí)的調(diào)度規(guī)則建模。②實(shí)時(shí)或動(dòng)態(tài)重調(diào)度策略：車間制造過程的隨機(jī)性、不確定性需要不斷地進(jìn)行重調(diào)度，以處理突發(fā)的事件。(3)遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。5. 串結(jié)構(gòu)空間 SS：在串中，基因任意組合所構(gòu)成的串的集合。實(shí)數(shù)編碼將問題的解用一個(gè)實(shí)數(shù)來表示。實(shí)數(shù)編碼遺傳算法的交叉操作類似于二進(jìn)制編碼遺傳算法。2. 終止規(guī)則遺傳算法的終止準(zhǔn)則通常有三種，一種是將某一個(gè)固定的最大代數(shù)作為停止算法的標(biāo)準(zhǔn)。事實(shí)上，混亂遺傳算法直接操作的對象既有個(gè)體，也有空間結(jié)構(gòu)，這自然使它喪失了只操作個(gè)體的經(jīng)典遺傳算法所具有的隱含并行性。如表 編碼對應(yīng)表工序211131414232222333121343編碼213443223114如第二類工件的編號(hào)就是“2”；工件的工序編號(hào)則是兩位十進(jìn)制編號(hào)，第二類工件的三道工序分別是“21”、“22”、“23”。從優(yōu)化搜索的角度而言，遺傳操作可使問題 遺傳過程的解，一代又一代地優(yōu)化，并逼進(jìn)最優(yōu)解。依據(jù)適應(yīng)度選擇再生個(gè)體，適應(yīng)度高的個(gè)體被選中的概率高，適應(yīng)度低的個(gè)體第二章遺傳算法理論基礎(chǔ)可能被淘汰。(3)產(chǎn)生初始種群farm=zeros(N,pn)。 d(i)=A(i,cp(i,4))。 counter=counter+1。 %記錄調(diào)度方案各工序的開工時(shí)間 PE=zeros(1,pn)。 Y3p(i,j)=Q(Xp(j),num(Xp(j)))。 endend 分析結(jié)果的可行性、運(yùn)行時(shí)間以及目標(biāo)函數(shù)值 仿真輸出結(jié)果①在仿真的過程中，輸入如下參數(shù)：M=100。本調(diào)度問題的評(píng)價(jià)指標(biāo)是尋求最短生產(chǎn)周期，根據(jù)輸出的Xp，再結(jié)合Q、W矩陣可以計(jì)算出最短的加工周期（目標(biāo)函數(shù)值）: Tmin=63。程序是我運(yùn)行時(shí)間也與計(jì)算機(jī)的CPU有關(guān)，所以要提高程序的運(yùn)行時(shí)間要從兩個(gè)方面入手，即計(jì)算機(jī)和程序本身。遺傳算法作為一種非確定性的模擬自然算法，為作業(yè)車間調(diào)度等復(fù)雜系統(tǒng)的優(yōu)化提供了一種新的方法，并且已經(jīng)取得了很多的成果。仍然存在需要進(jìn)一步探討和研究之處，具體如下：可以探索將遺傳算法與其它領(lǐng)域搜索算法，如模擬退火算法、神經(jīng)網(wǎng)絡(luò)方法等結(jié)合，是否能獲得更佳的效果。由于程序比較簡單，運(yùn)行時(shí)間很短，所以程序比較合理。由圖不難看出，最優(yōu)個(gè)體適應(yīng)值在進(jìn)化代數(shù)10左右的時(shí)候已經(jīng)開始收斂。 % N 種群規(guī)模(取偶數(shù))Pc=。 Y2p(i,:)=PE。 %記錄調(diào)度方案各機(jī)器的開工時(shí)間 ME=zeros(1,pn)。plot(counter,LC1(counter),39。 A(i,cp(i,4))=c(i)。 while length(find(farm(i,:)==gene))=pron(gene) gene=randint(1,1,[1 m])。按照一定的變異概率和變異方法，生成新的個(gè)體。種群中的每個(gè)個(gè)體是問題的一個(gè)解，即為“染色體”。表中第一次出現(xiàn)“2”代表“21”，第三次出現(xiàn)“2”代表“23”。4 車間作業(yè)調(diào)度的建模 車間作業(yè)調(diào)度問題描述不失一般性，設(shè)n個(gè)作業(yè)m 臺(tái)機(jī)器的車間作業(yè)調(diào)度問題（表示為：n/m JSP）滿足以下約束條件：（1）每個(gè)工件包含若干道工序；（2）各工件必須按工藝路線以指定的次序在機(jī)器上加工；（3）任何一個(gè)工件的前一道工序加工完成后，方能進(jìn)行后一道工序的加工，在同一臺(tái)機(jī)器上一個(gè)加工任務(wù)完成之后，方能開始另一個(gè)加工任務(wù)。第三種準(zhǔn)則有一定的自適應(yīng)性，例如根據(jù)算法的評(píng)價(jià)的一些規(guī)則。為了便于解釋，下面設(shè)解向量s1= (v1（1），v2(1)，…，vm（1）)和s1=( v1（2），v2（2），…，vm（2）)是兩個(gè)父解向量，sz={ s1 s2，…sm }和sw=( s1 ，s2，…sn)是通過雜交獲得的兩個(gè)后代。實(shí)數(shù)編碼直接在解的表現(xiàn)型上進(jìn)行遺傳操作，目前在高維復(fù)雜優(yōu)化問題中得到廣泛應(yīng)用，并取得了較好效果。串結(jié)構(gòu)空間對應(yīng)于遺傳學(xué)中的基因型（Genotype）的集合。(4)對搜索空間沒有任何特殊要求(如連通性、凸性等)，只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其他輔助信息，適應(yīng)范圍更廣。③生產(chǎn)計(jì)劃與調(diào)度集成策略：生產(chǎn)計(jì)劃、調(diào)度的集成研究具有全局優(yōu)化的特征，也符合先進(jìn)制造模式的思想。在調(diào)度問題的離散圖模型基礎(chǔ)上，啟發(fā)式圖搜索法在調(diào)度領(lǐng)域得到應(yīng)用。（2）基于啟發(fā)式規(guī)則的調(diào)度方法最早的近似算法便是基于啟發(fā)式規(guī)則的調(diào)度算法(也稱調(diào)度規(guī)則)，其本質(zhì)是給每一個(gè)生產(chǎn)任務(wù)和操作，并賦予優(yōu)先級(jí)，優(yōu)先級(jí)高的生產(chǎn)任務(wù)和操作優(yōu)先考慮。生產(chǎn)車間出現(xiàn)調(diào)度問題主要原因是生產(chǎn)資源受到了制約。如機(jī)器故障、緊急任務(wù)插入、作業(yè)交貨期的變更等一些突發(fā)事件也增加了調(diào)度的難度和隨機(jī)性。 本文的研究內(nèi)容本文針對先進(jìn)制造環(huán)境下車間管理與調(diào)度的特點(diǎn)，分析了車間作業(yè)調(diào)度的特點(diǎn)，給出了遺傳算法求解車間作業(yè)調(diào)度的過程。因此，合理的生產(chǎn)調(diào)度是生產(chǎn)系統(tǒng)的高效運(yùn)行的前提，生產(chǎn)調(diào)度可以保證:生產(chǎn)計(jì)劃的有效實(shí)施；高效低耗地使用生產(chǎn)資源；均衡生產(chǎn)，減少在制品的資金占用；縮短產(chǎn)品生產(chǎn)周期、確保產(chǎn)品交貨期、降低生產(chǎn)成本，以適應(yīng)多變的市場需求。有關(guān)資料表明，在制造過程中95％的時(shí)間消耗在非切削過程中。此外，用Matlab強(qiáng)大的數(shù)值計(jì)算能力和眾多庫函數(shù)來編寫算法，通過仿真實(shí)例對算法的求解效果進(jìn)行了測試。調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個(gè)加工對象確定具體的加工路線、時(shí)間、機(jī)器和操作等。為了保證生產(chǎn)的高效穩(wěn)定運(yùn)行，以獲得最大的經(jīng)濟(jì)效益，企業(yè)管理者必須能根據(jù)市場上原料供應(yīng)和產(chǎn)品需求的變化進(jìn)行經(jīng)營決策和組織生產(chǎn)，能利用現(xiàn)有的資源做出最有效的調(diào)度方案，使企業(yè)生產(chǎn)獲得最大的綜合經(jīng)濟(jì)效益。由于大量的調(diào)度問題是NP完全問題[13]，近幾年各種智能計(jì)算方法逐漸被引入到調(diào)度問題中，如遺傳算法、模擬退火算法等，但是目前尚無有效的求解策略，因此調(diào)度問題的研究也具有重要的理論意義[5]。此后，很多學(xué)者就遺傳算法在車間調(diào)度問題方面的應(yīng)用做了大量研究。每個(gè)工件又要考慮它的加工時(shí)間、安裝時(shí)間和操作順序等因素，因而相當(dāng)復(fù)雜，調(diào)度問題往往是通過等式或不等式等約束條件來計(jì)算的，屬于典型的NPhard問題。(6) 有序加工，無序加工。調(diào)度的目標(biāo)是將作業(yè)合理地安排到各機(jī)床以及合理地使用其它生產(chǎn)資源，并合理安排作業(yè)的加工次序和加工時(shí)間，使約束條件被滿足，同時(shí)優(yōu)化其中的一些生產(chǎn)性能指標(biāo)。Petri網(wǎng)具有很強(qiáng)地建模能力，對于描述系統(tǒng)的不確定性和隨機(jī)性也具有一定地優(yōu)越性，目前Petri網(wǎng)已經(jīng)用于FMS建模和調(diào)度，但尚存在下列問題:l)節(jié)點(diǎn)語義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的時(shí)間里能對復(fù)雜的規(guī)劃問題提供較好的次優(yōu)解，并能對解的次優(yōu)性進(jìn)行定量評(píng)估，近年來已成為解決復(fù)雜生產(chǎn)調(diào)度問題的一種重要方法。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點(diǎn):(1)搜索過程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個(gè)體。4. 基因（Gene）：基因是串中的元素，基因用于表示個(gè)體的特征。①編碼將問題的潛在解用一些參數(shù)表示，這些參數(shù)(基因)排列在一起形成一個(gè)特定的編碼(染色體)，代表一個(gè)個(gè)體，從而將問題的狀態(tài)空間與遺傳算法的碼空間相對應(yīng)，這很大程度上依賴于問題的性質(zhì)，并將影響遺傳操作的設(shè)計(jì)。④交叉交叉算子是母體空間到個(gè)體空間的映射，記作Tc:S2→S交叉是最主要的遺傳運(yùn)算，它同時(shí)對兩個(gè)染色體操作，交叉操作用于結(jié)合來自父染色體和母染色體的特征來產(chǎn)生新的子個(gè)體，在解空間中進(jìn)行有效搜索，同時(shí)降低對有效模式的破壞概率。 變異率(記為Pm)定義為種群中變異基因數(shù)中的百分比。島模型考慮的是種群的空間結(jié)構(gòu)，而細(xì)胞模型考慮的是一種群中個(gè)體的空間結(jié)構(gòu)。遺傳算法的編碼技術(shù)必須考慮染色體的合法性、可行性、有效性以及問題解空間的表征的完全性。 變異算子變異操作在本問題中相對而言比較簡單。遺傳算法搜索求解的基本步驟是:確定編碼方案并隨機(jī)產(chǎn)生種群，種群中個(gè)體的數(shù)目一定，每個(gè)個(gè)體表示為染色體的基因編碼。end OPT_S=zeros(M,pn)。 A(i,cp(i,