【正文】 ME=zeros(1,pn)。 s3(Q(Xp(j),num(Xp(j))))=max(s1(Xp(j)),s4(Q(Xp(j),num(Xp(j)))))。 Y2p(i,:)=PE。 %記錄最佳個(gè)體和收斂曲線 minfitness=min(fitness)。 % N 種群規(guī)模(取偶數(shù))Pc=。 2 4 2 1 5 3 ]。由圖不難看出，最優(yōu)個(gè)體適應(yīng)值在進(jìn)化代數(shù)10左右的時(shí)候已經(jīng)開(kāi)始收斂。例如,第一臺(tái)機(jī)床加工的第一道工序是“5” ,可以得知第五類工件的第一個(gè)工件。由于程序比較簡(jiǎn)單，運(yùn)行時(shí)間很短，所以程序比較合理。該模型是基于實(shí)際生產(chǎn)調(diào)度情況得到。仍然存在需要進(jìn)一步探討和研究之處，具體如下：可以探索將遺傳算法與其它領(lǐng)域搜索算法，如模擬退火算法、神經(jīng)網(wǎng)絡(luò)方法等結(jié)合，是否能獲得更佳的效果。在這次設(shè)計(jì)的撰寫過(guò)程中，我得到了侯老師的精心指導(dǎo)。作為一個(gè)本科生，由于經(jīng)驗(yàn)和知識(shí)的匱乏，如果沒(méi)有導(dǎo)師的督促指導(dǎo)以及周圍同學(xué)們的支持，很難獨(dú)立完成畢業(yè)設(shè)計(jì)。遺傳算法作為一種非確定性的模擬自然算法，為作業(yè)車間調(diào)度等復(fù)雜系統(tǒng)的優(yōu)化提供了一種新的方法，并且已經(jīng)取得了很多的成果。遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，它在解決生產(chǎn)車間作業(yè)調(diào)度問(wèn)題時(shí)，具有明顯的優(yōu)勢(shì)。程序是我運(yùn)行時(shí)間也與計(jì)算機(jī)的CPU有關(guān)，所以要提高程序的運(yùn)行時(shí)間要從兩個(gè)方面入手，即計(jì)算機(jī)和程序本身。④： 基于機(jī)器的甘特圖圖4標(biāo)明了工序和機(jī)床的分配關(guān)系,其間還標(biāo)明各工序在對(duì)應(yīng)機(jī)器上的操作時(shí)間。本調(diào)度問(wèn)題的評(píng)價(jià)指標(biāo)是尋求最短生產(chǎn)周期，根據(jù)輸出的Xp，再結(jié)合Q、W矩陣可以計(jì)算出最短的加工周期（目標(biāo)函數(shù)值）: Tmin=63。 2 1 3 4 5 4 。 endend 分析結(jié)果的可行性、運(yùn)行時(shí)間以及目標(biāo)函數(shù)值 仿真輸出結(jié)果①在仿真的過(guò)程中，輸入如下參數(shù)：M=100。OPT_E(counter+1,:)=Y2p(index(1),:)。 Y3p(i,j)=Q(Xp(j),num(Xp(j)))。 s1(Xp(j))=max(s2(Xp(j)),s4(Q(Xp(j),num(Xp(j)))))。 %記錄調(diào)度方案各工序的開(kāi)工時(shí)間 PE=zeros(1,pn)。 plotif=0。 counter=counter+1。%變異概率為PmXp=POPU(i,:)。 d(i)=A(i,cp(i,4))。 for i=1:N B(i,:)=farm(Ser(i),:)。(3)產(chǎn)生初始種群farm=zeros(N,pn)。%m是總工件數(shù)，n是總工序數(shù)Xp=zeros(M,pn)。依據(jù)適應(yīng)度選擇再生個(gè)體，適應(yīng)度高的個(gè)體被選中的概率高，適應(yīng)度低的個(gè)體第二章遺傳算法理論基礎(chǔ)可能被淘汰。遺傳操作進(jìn)行的高效有向的搜索而不是如一般隨機(jī)搜索方法所進(jìn)行的無(wú)向搜索。從優(yōu)化搜索的角度而言，遺傳操作可使問(wèn)題 遺傳過(guò)程的解，一代又一代地優(yōu)化，并逼進(jìn)最優(yōu)解。遺傳算法中要求適應(yīng)度函數(shù)的取值為非負(fù)數(shù)，因此可用下式表示： 選擇算子選擇算子根據(jù)適應(yīng)度的值選擇個(gè)體遺傳到下一代群體中，本文采用錦標(biāo)賽選擇法。如表 編碼對(duì)應(yīng)表工序211131414232222333121343編碼213443223114如第二類工件的編號(hào)就是“2”；工件的工序編號(hào)則是兩位十進(jìn)制編號(hào)，第二類工件的三道工序分別是“21”、“22”、“23”。 遺傳算法設(shè)計(jì)思想遺傳算法（Genetic Algorithms）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。事實(shí)上，混亂遺傳算法直接操作的對(duì)象既有個(gè)體，也有空間結(jié)構(gòu)，這自然使它喪失了只操作個(gè)體的經(jīng)典遺傳算法所具有的隱含并行性。這在生物學(xué)中被稱為為L(zhǎng)amarckian evolution和Baldwin effect。2. 終止規(guī)則遺傳算法的終止準(zhǔn)則通常有三種，一種是將某一個(gè)固定的最大代數(shù)作為停止算法的標(biāo)準(zhǔn)。Vl=[l0010011]在給定點(diǎn)變異后變?yōu)?V1*=[10011011]在遺傳操作中需注意的幾點(diǎn)問(wèn)題:1. 參數(shù)及其選取種群規(guī)模記為Pop_Size，即種群中個(gè)體(染色體)的個(gè)數(shù)。實(shí)數(shù)編碼遺傳算法的交叉操作類似于二進(jìn)制編碼遺傳算法。通常有以下的算法可供選擇:輪盤賭選擇(roulette wheel selection)記種群規(guī)模為n，個(gè)體Vi的適值為(fvi)，則個(gè)體Vi被選擇的概率為然后，根據(jù)這些概率構(gòu)造一個(gè)轉(zhuǎn)輪，旋轉(zhuǎn)轉(zhuǎn)輪n次，每次選一個(gè)染色體加入新的種群。實(shí)數(shù)編碼將問(wèn)題的解用一個(gè)實(shí)數(shù)來(lái)表示。(crossover) ：有性生殖生物在繁殖下一代時(shí)兩個(gè)同源染色體之間通過(guò)交叉而重組，即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。5. 串結(jié)構(gòu)空間 SS：在串中，基因任意組合所構(gòu)成的串的集合。由于遺傳算法是自然遺傳學(xué)與計(jì)算機(jī)科學(xué)相互結(jié)合滲透的產(chǎn)物，因此在遺傳算法中借用了許多自然進(jìn)化的概念。(3)遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，從而增加了其搜索過(guò)程的靈活性。由于它具有這些特點(diǎn)，從上世紀(jì)80年代以來(lái)，遺傳算法成為信息科學(xué)和運(yùn)籌優(yōu)化領(lǐng)域的一個(gè)研究熱點(diǎn)，并在數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、圖像處理等多個(gè)領(lǐng)域得到廣泛應(yīng)用，被認(rèn)為是21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。②實(shí)時(shí)或動(dòng)態(tài)重調(diào)度策略：車間制造過(guò)程的隨機(jī)性、不確定性需要不斷地進(jìn)行重調(diào)度，以處理突發(fā)的事件。由于模擬退火法能以一定的概率接受差的能量值，因而有可能跳出局部極小，但它的收斂速度較慢，很難用于實(shí)時(shí)動(dòng)態(tài)調(diào)度環(huán)境。3)很難對(duì)高級(jí)的調(diào)度規(guī)則建模。該方法不可避免存在以下問(wèn)題:a)缺乏理論意義。采用數(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)度問(wèn)題。生產(chǎn)的柔性體現(xiàn)在設(shè)備的使用和設(shè)備的安排兩個(gè)方面，設(shè)備使用的柔性是指設(shè)備可用于多個(gè)零件的多道工序加工，設(shè)備安排的柔性是指工件的設(shè)備加工路徑，而不是固定或預(yù)先確定的。每一臺(tái)機(jī)器在每個(gè)時(shí)間只能加工某個(gè)工件的某道工序，只能在上道工序加工完成才能開(kāi)始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。按照不同的分類標(biāo)準(zhǔn)，可分為6種類型:(l)開(kāi)環(huán)車間和閉環(huán)車間。(2)動(dòng)態(tài)隨機(jī)性調(diào)度中存在很多隨機(jī)性和不確定性。第四章將實(shí)際的車間作業(yè)問(wèn)題抽象成數(shù)學(xué)模型，并且設(shè)計(jì)遺傳算法的基本算子以及操作。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，國(guó)內(nèi)也掀起了一股應(yīng)用遺傳算法研究車間作業(yè)調(diào)度問(wèn)題的熱潮。大量的研究促使車間調(diào)度領(lǐng)域取得了豐碩的成果，產(chǎn)生了很多重要的調(diào)度方法。制造系統(tǒng)生產(chǎn)管理的核心就是車間生產(chǎn)調(diào)度，生產(chǎn)管理任務(wù)順利實(shí)施與完成，最終要靠合理的生產(chǎn)調(diào)度來(lái)保證。然而，當(dāng)前的產(chǎn)品的加工工藝復(fù)雜度相當(dāng)高，在調(diào)度任務(wù)規(guī)模較大且動(dòng)態(tài)多變的環(huán)境中，手工調(diào)度表現(xiàn)的非常低效甚至無(wú)法實(shí)現(xiàn)調(diào)度。在這種生產(chǎn)模式下如何進(jìn)行組織管理，包括如何組織動(dòng)態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計(jì)劃、如何進(jìn)行調(diào)度是企業(yè)面臨的主要問(wèn)題?，F(xiàn)代科學(xué)技術(shù)的快速發(fā)展和客戶對(duì)產(chǎn)品的個(gè)性化需求越來(lái)越高，這給傳統(tǒng)制造加工業(yè)帶來(lái)了巨大的挑戰(zhàn)和機(jī)遇。本文主要研究了制造車間作業(yè)調(diào)度問(wèn)題。中北大學(xué)2012屆畢業(yè)設(shè)計(jì)說(shuō)明書摘 要在現(xiàn)今的經(jīng)濟(jì)全球化制造時(shí)代，客戶化的產(chǎn)品需求要求更短的產(chǎn)品生命周期。作業(yè)車間調(diào)度問(wèn)題是一個(gè)典型的NP—hard問(wèn)題，是最困難的組合優(yōu)化問(wèn)題之一。 we use chromosome coding, genetic operators and genetic algorithm to solve the scheduling problem. In addition, using the Matlab numerical puting power and number of library functions to write the algorithm to test the effects of algorithm by simulation examples. Examples show that The program algorithm is better, equipment of organizing production resource utilization, The algorithm has a strong guiding significance for the actual production of the workshop.Keywords: Job Scheduling, Genetic Algorithm, MATLAB目 錄1 緒論 1 課題研究背景及意義 1 問(wèn)題的提出 1 課題的現(xiàn)實(shí)與理論意義 1 國(guó)內(nèi)外研究現(xiàn)狀綜述 3 本文的研究?jī)?nèi)容 42 車間作業(yè)調(diào)度算法 5 調(diào)度問(wèn)題特點(diǎn)與分類 5 車間作業(yè)調(diào)度問(wèn)題描述 5 調(diào)度問(wèn)題優(yōu)化算法 63 求解調(diào)度問(wèn)題的遺傳算法 10 遺傳算法求解調(diào)度問(wèn)題的優(yōu)越性 10 遺傳算法簡(jiǎn)介 11 遺傳算法概述 11 遺傳算法基本過(guò)程 12 遺傳算法執(zhí)行策略 154 車間作業(yè)調(diào)度的建模 17 車間作業(yè)調(diào)度問(wèn)題描述 17 遺傳算法設(shè)計(jì)思想 18 編碼 18 生成初始種群 19 適應(yīng)度函數(shù) 19 選擇算子 19 交叉算子 19 變異算子 19 遺傳算法流程 195 用Matlab實(shí)現(xiàn)模擬作業(yè)調(diào)度 22 程序設(shè)計(jì)思想及偽代碼 22 分析結(jié)果的可行性、運(yùn)行時(shí)間以及目標(biāo)函數(shù)值 26 仿真輸出結(jié)果 26 分析結(jié)果 276 結(jié)論與展望 30參考文獻(xiàn) 32致 謝 34第 II 頁(yè) 共 II 頁(yè)1 緒論 課題研究背景及意義 問(wèn)題的提出隨著科學(xué)技術(shù)、經(jīng)濟(jì)全球化和信息技術(shù)的迅猛發(fā)展，生產(chǎn)企業(yè)面臨著多變的商業(yè)環(huán)境［1］。對(duì)于中小型企業(yè)來(lái)敏捷制造就是先進(jìn)的生產(chǎn)模式，生產(chǎn)調(diào)度方案的優(yōu)劣是敏捷制造的標(biāo)志。以前大部分企業(yè)主要依靠經(jīng)驗(yàn)豐富的工人手工安排調(diào)度計(jì)劃，在調(diào)度問(wèn)題比較簡(jiǎn)單的情況下還是可行的。具體就是針對(duì)一項(xiàng)可分析的工作（如產(chǎn)品制造），探討盡可能滿足約束條件（如交貨期、工藝路線、資源情況）的前提下，通過(guò)下達(dá)生產(chǎn)指令，安排其組成部分（操作哪些資源）、其加工時(shí)間及加工的先后順序，以達(dá)到合理利用產(chǎn)品制造資源，獲得產(chǎn)品制造時(shí)間和成本的最優(yōu)化[14] ，提高企業(yè)經(jīng)濟(jì)效益的目的。由于車間調(diào)度問(wèn)題的復(fù)雜性，各種不同的具體問(wèn)題往往有不同的解決方法。國(guó)內(nèi)對(duì)于車間調(diào)度問(wèn)題的研究起步比較晚，基本上是靠調(diào)度人員的經(jīng)驗(yàn)進(jìn)行車間作業(yè)分配和調(diào)度。重點(diǎn)研究了遺傳算法在車間作業(yè)調(diào)度優(yōu)化中的操作過(guò)程，包括了編碼方式、種群大小、交叉方式與概率、變異方法與概率等參數(shù)的選擇。在現(xiàn)有計(jì)算條件下，一般優(yōu)化方法對(duì)于車間調(diào)度問(wèn)題是低效甚至是無(wú)能為力的。如基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時(shí)間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)等。 車間作業(yè)調(diào)度問(wèn)題描述一般車間調(diào)度問(wèn)題可以描述為:n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件分為k道工序，每道工序可在不同的機(jī)器上加工。因此，需要在庫(kù)存成本與切換加工次數(shù)頻率之間尋求一個(gè)動(dòng)態(tài)的平衡。這類方法從理論上來(lái)說(shuō)是能求得最優(yōu)解，但通常由于計(jì)算復(fù)雜性原因，不能獲得真正的實(shí)用。（4）仿真調(diào)度方法由于制造系統(tǒng)的復(fù)雜性，很難用一個(gè)精確的解析模型來(lái)進(jìn)行描述分析，而通過(guò)對(duì)仿真模型的運(yùn)行收集數(shù)據(jù)，就能對(duì)實(shí)際系統(tǒng)進(jìn)行性能，狀態(tài)方面的分析，從而能對(duì)系統(tǒng)采用合適的控制調(diào)度方法。Petri網(wǎng)是基于FMS中作業(yè)的加工流程建模，當(dāng)作業(yè)需求或工藝稍微變動(dòng)，必須改模型結(jié)構(gòu)。模擬退火法可以用于具有最小MakesPan指標(biāo)的FlowShop排序問(wèn)題。由于調(diào)度問(wèn)題的復(fù)雜性，其研究策略主要形成了以下幾種：①分解與成組策略：利用分解生產(chǎn)計(jì)劃或GT的調(diào)度策略可以大大降低問(wèn)題的計(jì)算復(fù)雜性和規(guī)模，求得調(diào)度問(wèn)題的較優(yōu)解，同時(shí)優(yōu)化系統(tǒng)的一些性能指標(biāo)。它基于自然界生物進(jìn)化過(guò)程中優(yōu)勝劣汰、自然選擇、適者生存和物種遺傳的思想來(lái)搜索求解空間最優(yōu)解，是一種多參數(shù)、多群體同時(shí)進(jìn)行的優(yōu)化方法，其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息，它尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜非線性問(wèn)題。這使的遺傳算法能以較少的計(jì)算獲得較大的收