本科畢業設計論文 題 目 ： 兩機無等待流水車間調度問題與仿真 專業名稱 機械設計制造及其自動化 學生姓名 指導教師 畢業時間 2014 年 6 月 西北工業大學明德學院本科畢業設計論文 畢業 任務書 一、題目 兩機無等待流水車間的調度與仿真 二、指導思想和目的要求 畢業設計（論文）是培養學生自學能力、 綜合應用能力、獨立工作能力的重要教學實踐環節。在畢業設計中，應獨立承擔一部分比較完整的工程技術設計任務。要求學生發揮主觀能動性，積極性和創造性，在畢業設計中著重培養獨立工作能力和分析解決問題的能力，嚴謹踏實的工作作風，理論聯系實際，以嚴謹認真的科學態度，進行有創造性的工作，認真、按時完成任務。針對兩機無等待流水車間調度問題 , 提出目標函數最大完工時間最小化的快速算法 , 并給出算法的復雜度 .分析兩機無等待流水車間調度問題的排列排序性質 ,證明了兩機無等待流水車間調度問題的可行解只存在于排列排序中 ,排列排序的最優 解一定是兩機無等待流水車間調度問題的最優解 .最后研究了同時包含普通工件和無等待工件的兩機流水車間調度問題的復雜性 ,為進一步研究兩機無等待流水車間調度問題提供了理論依據。 三、進度和要求 第一階段：（共計 5 周） 第一周及第二周，翻譯并完成教師指定的英文文獻翻譯； 第三周及第五周，對所研究課題有個全面的了解。 第二階段：（共計 5 周） 完成方案的提出，學習和用已知的方案方法進行實際問題的解決方案的提出和仿真。 第三階段：（共計 5 周 ） 撰寫論文及評閱。 四、主要參考書及參考資料 1 S.M.Johnson.optimal Two-and Three-Stage Production Scheduling with Set-up Time IncludedJ. Naval Research Logistics Quarterly.1954, 設計 論文 西北工業大學明德學院本科畢業設計論文 1:61-68 2 Story A.E, Wagner H.M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,1963 3 Gavett J.W.Three Heuristic Rules for Sequencing Jobs to a Single Production FacilityJ. Mgmt.Sci.1965,11:B166-176 4 S.Panwalker,Wafik Iskander.A Survey of SchedulingJ.Ops.Res.1977, 25(1):45-61 5 Stephen,C.Graves.A Review of Production SchedulingJ.Ops.res.1981,29（ 4） :646-675 6 M.S.Fox.ISIS:A Retrospective Intelligent Scheduling.Intelligent Scheduling,Kaufmann, ed:Michael B.Morgan,1994:3-28 7 B.Giffler,GL.Thompson.Algorithms for Solving Production Scheduling ProblemsJ.Ops Res.1960,8:487-503 8 董海，梁迪設施規劃與物流分析北京：機械工業出版社 2005 9 Baker K R.A Comparative Study of Flow Shop Algonithms J.Ops Res.1975(23） :62-73 10 王偉玲，馬正元，王玉生生產調度問題研究的動態與趨勢 J管理技術， 2005 年第 5 期 11 鄭璐，顧鑫生，不確定條件下的零等待 Flow Shop 生產調度問題 J華東理工大學學報 2004， 30（ 2）： 188-194 12 S.Panwalker, Wafik Iskander.A Survey of SchedulingJ.Ops.Res.1977, 25（ 1） :45-61. 13 謝源，謝劍英，鄭小龍混合有限月蘇下帶模糊交貨期的單機調度問題的研究 J信息與控制 2005， 34（ 3）： 369-372 14 Glover F. Future paths for integer programming and links to artificial intelligenceJ. Computer and Opreations. Research. 1986, 13:533-549. 15 盧冰原，陳華平，顧春生等，模糊環境下的柔性工作車間調度模型的 西北工業大學明德學院本科畢業設計論文 研究 J運籌與管理 2004， 13 16 李福明，朱云龍，尹朝萬等 .基于遺傳算法的模糊調度研究 J.信息與控制 2004， 33（ 6）： 703-708 17 吳儀，劉民等 .JSSP 基本約束特點分析及調度算法 J.清華大學學報(自然科學版 ) 2004， 44(10)： 18 Kinkpatric S, Gelatt CD, Vecchi M P.Operational by simulated annealingJ.Science.1983, 220:671-680. 19 吳梅，陸金桂 .遺傳算法的研究進展綜述 J機床與液壓 2008， 36(3) 20 孫卓明，余彬遺傳算法計算機時代 2004 年，第 1 期 21 陳國良等遺傳算法及應用北京：人民郵電出版社， 1996 學生 薛 偉 指導教師 王 劍 系主任 西北工業大學明德學院本科畢業設計論文 I 摘 要 流水車間 (Flow Shop)調度問題無論是在工廠經營管理還是在產品制造中都具有廣泛的應用，因此對流水車間調度問題進行研究具有重大的理論意義和實際意義。 本文首先對車間調度問題國內外研究現狀和發展趨勢進行了系統的闡述。其次，對遺傳算法的基本理論進行了詳細的論述。然后對 Flow Shop 調度問題建立數學模型。再次，在掌握了遺傳算法的基礎之上給出了基于遺傳算法求解 Flow Shop 調度問題的編碼方案，遺傳算子的設計。然后基于遺傳算法對調度問題進行了實例分析。最后對上述兩種調度的結果進行了分析， 結果表明本文提出的方法是有效可行的。 關鍵詞： 生產調度 ， 流水車間調度 ， 遺傳算法 。西北工業大學明德學院本科畢業設計論文 II ABSTRACT Flow Shop (Flow Shop) scheduling problem in both factory management and has wide application in the product manufacturing, so the study of Flow Shop scheduling problem is of great theoretical significance and practical significance.This article first to the workshop scheduling problem research status and development trend at home and abroad systematically in this paper.Secondly, the basic theory of genetic algorithm in detail in this paper.Then the Flow Shop scheduling problem to establish mathematical model.Again, in the mastery of the genetic algorithm based on genetic algorithm is given based on the Flow Shop scheduling problem of coding scheme, the design of genetic operators.Then based on the genetic algorithm for scheduling problems on the instance analysis.Finally, the results of the two kinds of scheduling are analyzed, the results show that the proposed method is effective and feasible. Key words: production scheduling；Flow shop scheduling；Genetic algorithm； 西北工業大學明德學院本科畢業設計論文 III 目 錄 摘 要 . I ABSTRACT . II 目 錄 . III 第一章 緒 論 . 1 1.1 引 言 . 1 1.2 國內外車間調度問題的研究現狀和存在的問題 . 1 1.2.1 國內外車間調度問題的研究現狀 . 1 1.2.2 研究中存在的問題 . 2 1.3 研究意義與目的 . 3 1.4 本文的工作 . 4 第二章 車間調度問題 . 5 2.1. 車間調度問題的描述 . 5 2.2 車間調度問題的特點 . 6 2.3 車間調度問題的分類 . 6 2.4 Job Shop 與 Flow shop 比較 . 7 2.5 調度問題的研究方法 . 8 2.6 兩機無等待流水車間調度 . 13 2.6.1 生產周期的計算 . 13 2.6.2 生產周期的快速算法 . 14 第三章 遺傳算法 . 16 3.1 遺傳算法的形成與發展 . 16 3.2 遺傳算法的基本思想 . 17 3.3 遺傳算 法的特點 . 17 3.4 遺傳算法的過程和流程 . 19 3.5 求解調度問題的遺傳算法 . 22 西北工業大學明德學院本科畢業設計論文 IV 3.5.1 遺傳算法的設計步驟 . 22 3.5.2 編碼方式 . 22 3.5.3 適配值函數 . 24 3.5.4 遺傳算子的設計 . 24 3.5.5 編碼參數 . 26 3.5.6 遺傳算子 . 26 3.5.7 算法的終止條件 . 26 第四章 兩機無等待流水車間調度問題仿真 . 27 4.1 流水車間調度問題的描述與數學模型 . 27 4.2 基于 Johnson 法則的兩機無等待流水車間調度問題仿真 . 28 4.3 遺傳算法的設計 . 31 4.3.1 編碼方案 . 31 4.3.2 群體的確定 . 31 4.3.3 適 應度函數 . 31 4.3.4 遺傳算子的設計 . 31 4.4 基于遺傳算法的兩機無等待流水車間調度問題仿真 . 32 4.5 結果分析 . 32 第五章 全文總結 . 33 參考文獻 . 34 致 謝 . 36 畢業設計小結 . 37 西北工業大學明德學院本科畢業設計論文 1 第一章 緒 論 1.1 引 言 伴隨著用戶對產品需求的快速變化，以及市場競爭的日趨激烈，現代制造企業需要進行多品種、小批量生產，這種生產方式使生產計劃、組織和控制變得更加復雜。另外，要求企業對生產過程中所出現的各種信息進行及時反饋和處理，因此，生產調度問題作為生產管理系統的核心內容和關鍵問題，其研究具有重要的理論和實用價值。企業要進行改革，結合企業的現狀，研究改進遺傳算法在 車間調度的應用，從而合理分配企業資源、提高勞動效率。研究改進遺傳算法在車間調度的應用，從而合理分配企業資源、提高勞動效率。 1.2 國內外車間調度問題的研究現狀和存在的問題 1.2.1 國內外車間調度問題的研究現狀 調度問題的研究始于 20 世紀 50 年代， S.M.Johnson 提出了解決 n/2/F/Cmax和部分特殊的 n/3/F/Cmax 問題的算法，這 是 調度理論的開始：直至五十年代末期，許多研究成果主要是針對規模較小的單機和簡單的流水車間的問題，提出了解析優化方法，許多研究成果主要是針對規模較小的單機和簡單的流 水車間問題，提出了解析優化方法，研究范圍較窄，但是這些研究卻成為經典調度理論的基石。 六十年代，多是利用混合或純整數規劃和分支定界法解決一些有代表性的問題，如 Story 的研究。同時也有人開始嘗試用啟發式算法研究此問題，如 Gavett提出的方法。六十年代末期，經典調度理論體系初步成型。七十年代，人們開始了算法復雜性的研究，多數調度問題被證明屬于 NP 完全問題或 NP 一難問題，難以找到多項式算法，因此開始關注啟發式算法。 Panwalkar 總結和歸納出了 113條調度規則，并對其進行分類。七十年代末期，經典調度理論趨向 成熟。 八十年代初期， Stephen 等從三個方面對調度進行了從新考察，對未來發展做了分析和預測，認為理論與實際的結合將會成為研究熱點。這個富有挑戰性的課題吸引了機械、計算機、管理等諸多領域的學者，許多跨學科的方法被應用到西北工業大學明德學院本科畢業設計論文 2 研究中。其中最引人注目的就是以 Carnegie-Mellon 大學的 M.Fox 為代表的學者們開展的基于約束傳播的 ISIS 研究，它標志了人工智能開始真正應用與調度問題。八十年代后期， Giffler 等人總結了生產調度理論和實際方面的最新研究進展，從七個方面論述了生產調度的技術和方法，認為生產調度無 論在理論還是實踐上都已突破了傳統界限。 九十年代至今，各種方法在生產調度問題的研究中得到了充分的發揮，同時新的研究手段層出不窮。 而 Davis 是最早把 GA(GeneticAlgorithm，遺傳算法 )應用于車間調度問題的學者之一，他在使用 GA 求解車間調度的研究中取得了近似最優解。 1985 年， Davis 發表了關于把 GA 成功應用于車間調度問題的論文，充分證明了 GA 在解決車間調度問題中的可行性。此后，很多學者就給予遺傳算法的車間調度方面做了大量研究，發表了大量卓有成效的論文，對車間調度這類NP 問題的解決提出了具 體方案。這些論文中提出了一些具有突破性的新方法，改進并完善了傳統 GA 車間調度中的應用方法，同時通過在解決一些著名的標準檢測問題 (Ben 和 nark)的過程中取得了最優 (或接近最優 )解，進一步證明了遺傳算法在解決 NP 問題方面的有效性。 國內對車間調度的研究起步比較晚，始于 90 年代。很多企業由于技術上的制約，基本上是靠調度人員的經驗進行車間作業分配和調度。隨著遺傳算法在車間調度方面的應用熱潮，在這方面也產生了大量的研究成果，不過，研究工作主要集中在清華大學等等 CIMS 國家重點實驗室，但離形成系統的理論和開發出成熟 的軟件系統還有很長一段距離，因此還在投入大量的人力和物力進行該方面的研究，特別是在開展對車間作業作業調度算法的研究方面，目前尚處在實驗研究階段。 車間調度問題的高度復雜性和現有計算機條件的局限性決定了不可能一開始就考慮到實際調度問題中的所有因素，因此，實際研究通常是對車間系統進行簡化和抽象來解決實際問題。正是在這些現有的理論成果上不斷加上約束條件，使得研究問題近似于實際問題。總而言之，隨著各種特殊調度問題的攻克和新方法、新設備的出現，車間調度研究正向動態、敏捷、多資源、智能化的方向發展。 1.2.2 研究中 存在的問題 由于在實際生產過程中會出現諸多不確定因素，而且調度問題己經被證明西北工業大學明德學院本科畢業設計論文 3 NP 難題，因此尋找具有多項式復雜性的最優算法幾乎是不可能的。從目前文獻的研究來看，對于資源分配也沒有提出一個切實可行的解決方案，往往都是從某一方面入手，在若干假設的基礎上，得出一種理論上的可行解。各種啟發式方法、諸如基于規則的算法等，由于能在合理的時間內產生比較滿意的調度，因此廣泛應用于實際調度中，但其往往對所得到的調度解的次優性不能進行評估。因此，有必要探索更好的近似最優調度算法，可以考慮通過增加合理的計算時間來提高解的次優性。各 種基于統計優化的方法，諸如模擬退火法、遺傳算法等，提供了一種解決調度優化問題的新途徑，但與別的優化算法類似，也存在著一定程度的枚舉、一般來說收斂到最優解較慢，對于判斷解的最優性也很困難，在這方面也需要做進一步的研究。 1.3 研究意義與目的 有史以來，有限資源的合理配置和優化利用問題始終是人類社會所面臨的最基本經濟問題，這個問題貫穿于社會生活的各個方面。從一個國家、社會的宏觀經濟運行到具體企業的微觀經濟活動，都要受資源條件的限制。對企業來說，能否對現有資源進行合理配置和充分利用將直接影響到產品的制造成本，進 而成為影響企業效益的重要因素。企業資源的合理配置和優化利用很大程度上體現在車間一層的生產活動中，所以加強車間層的生產計劃與控制一直在企業生產經營活動中占有十分重要的地位。 車間生產調度是制造系統生產管理的核心，是生產管理和控制系統實現管理技術、運籌技術、優化技術和自動化技術發展的核心。及時準確的生產調度對生產系統的高效運行有著重要的影響。生產管理任務能否順利的實施與完成，最終要靠合理的生產調度來保證有效。 實用的調度方法和優化技術的研究與應用己成為先進制造技術實踐的基礎。因此，研究生產調度問題，不僅具有較大 的理論意義，而且具有相當大的實用價值。一方面，生產調度問題的研究不僅可以推動相關算法的研究，如遺傳算法、神經網絡、人工智能等，而且還能在此基礎上提出新的算法，這為其他領域類似問題的解決提供了條件和手段；另一方面，一個好的生產調度方案不僅可以降低生產成本，而且可以提高企業產品的準時交貨能力，從而增強企業的競爭力。 隨著科學技術的發展，制造行業的生產規模變得越來越大，產品越來越多樣西北工業大學明德學院本科畢業設計論文 4 化，車間生產情況的復雜性也越來越高。同時，由于加工系統的復雜性和多樣性，目前還沒有一種通用的、全面的方法解決各種生產方式的優化調度問 題。制造企業迫切希望能有一個結合其自身特點的實用而有效的調度支持系統，這就需要根據企業的實際狀況和生產變化，從以獲得工程滿意解的實際需求出發，選取調度目標，應用能滿足要求的快速有效的優化算法，滿足企業的實際需求，實現優化調度。 1.4 本文的工作 第一章 緒論，從課題的研究背景到車間調度的國內外的研究現狀再到車間調度存在的問題及解決途徑來引出遺傳算法對車間調度問題研究的重要性。描述了車間調度問題。進而描述了關于車間調度的較常見的幾種研究方法及它們的應用領域。 第二章 車間調度問題綜述，先介紹車間調度問題 其中包括車間調度問題的描述、特點、分類、 job shop 與 flow shop 比較然后追尋調度問題研究方法 (數學規劃法、近似算法、智能搜索算法、模擬退火方法、 Multi-agent 方法、模糊邏輯、螞蟻調度算法、神經元算法 )，從而找到一些解決這些問題的辦法。 第三章 遺傳算法，先介紹遺傳算法的形成與發展，然后再介紹遺傳算法的基本思想和特點，闡述一下遺傳算法的過程和流程，最后求解調度問題的遺傳算法其中包括遺傳算法的設計步驟、編碼方式適配值函數、遺傳算子的設計、編碼參數、遺傳算子和算法的終止條件。 第四章 基 于遺傳算法的流水車間調度問題，首先介紹流水車間的背景，然后對流水車間調度問題進行描述與建立數學模型，進行遺傳算法的設計其中包括編碼方案、群體確定、適應度函數、遺傳算子的設計 ， 并且進行了仿真。 西北工業大學明德學院本科畢業設計論文 5 第二章 車間調度問題 2.1. 車間調度問題的描述 生產調度通常是生產過程的作業計劃， 例如某機器上工件的加工順序，以及要加工點的工件如何劃分批次。從本質上分，調度問題可以為開環調度和閉環調度。所謂開環調度是指研究工件加工的順序，所有的客戶訂購的產品，在機器上排序生產，不考慮其他的因素，閉環調度是指， 除了考慮工件的加工順序之外，還要考慮產品批次的大小等。顯然閉環調度的復雜性遠遠大于開環調度的復雜性，目前對閉環調度的處理通常使用近似方法，首先確定批量大小，然后再確定加工順序。 生產調度的問題基本上可以概述為：對于某一項可分解生產任務，在特定的約束條件下，分派生產所需要的資源，安排子任務的生產時間，并對子任務進行排序，目標是產品的最短的制造時間，或者最低產品成本。其中生產所需要的資源主要包括：人力資源、資金、生產原料、生產設備等，評價目標好的的指標一般有：產品的生產周期短，總成本低和生產設備利用率低等。 生 產調度的形式可以描述為： n 個工件， m 臺機器加工，每一個工件需要在m臺中的一臺或者多臺加工，假設第 i個工件 ni1 ，在第 j臺機上加工 mj 1加工時間為 Pij，加工操作位 Oij 沒一個工件的準備時間為 Rij，工件的交貨期為 Dij，交貨期是指必須在規定的時間內交貨，每一個工件有相應的工藝流程，工件按照工藝的約束在機器上按順序加工。所謂調度可以看做是，在一定的約束條件下工件如何分配到機器上加工，本質上來說調度就是將工件在機器上排序，其要符合以 下兩點要求： 1.符合產品工藝上的約束（可行調度）； 2.對應的執行的目標調度是最優的； 生產調度問題是一類復雜的問題，研究難度非常大，給學者的研究帶來了不小的困難，當前生產調度的研究還有很多問題沒有解決，很多實際的生產調度還西北工業大學明德學院本科畢業設計論文 6 停留在理論層次，大部分生產調度的算法研究只做了一些簡單的假設，過于簡單，與實際的生產差距較大。目前很多企業的調度還是靠人工完成，耗費了大量的人力物力，不利于企業成本的控制。 2.2 車間調度問題的特點 車間調度的基本特點是：建模的復雜性，計算的復雜性，動態的隨機性，多約束性，多目標性。 1.復雜性：車間中工件、機器、緩存和搬運系統之間相互影響、相互作用。每個工件要考慮它的加工時間、安裝時間和操作順序等因素，因而相當復雜。調度問題是在等式或不等式約束下求指標的優化，在計算量上往往是具有 NP 特性，隨著問題規模的增大，其計算量急劇增加，使得一些常規的方法無能為力，對于這一點已經證明。 2.隨機性：在實際的作業車間調度系統中存在很多隨機的和不確定的因素，環境是不斷變化的，在運行過程中會遇到多種隨機干擾，比如工件到達時間的不確定性、作業的加工時間也有一定的隨機性，而且生產系統中常出現一些突發偶然事 件，如設備的損壞、修復、作業交貨期的改變等，故作業車間調度過程是一個動態的隨機過程。 3.多約束性：車間調度問題中資源的數量、緩存的容量、工件加工時間以及工件的操作順序等都是約束。此外還有一些人為的因素，如要求各機器上的負荷要平衡等。 4.多目標性：實際的車間調度問題是多目標的，而且這些目標之間往往是發生沖突的。調度目標分為三類：基于作業交貨期的目標、基于作業完成時間的目標和基于生產成本的目標。 2.3 車間調度問題的分類 車間調度問題的分類，根據研究的側重點不同有多種分類方式。 1按照資源約束種類和數 量劃分 ： (1) 單資源車間調度 (single resource constrained)：只有一種資源制約著車間力。 (2) 雙資源車間調度 (dual resource constrained)：同時有兩種資源制約著車間力。機床設備往往是制約資源之一，車間有時會缺乏有經驗或一技之長的西北工業大學明德學院本科畢業設計論文 7 工人，也有可能某種類型的刀具數量有限，因此這兩種資源可以是機床設備和工人或刀具。 (3) 多資源車間調度 (multiple resource constrained)：同時有兩種以上的生產所制約著車間的生產能力。這些資源包括員 工、機床設備、機器人、物料運送系統和輔助資源，如貨盤、夾具和刀具等。 單資源車間調度是雙資源車間調度的特例，雙資源車間調度又是多資源車間調度的特例。所以多資源車間調度問題是最復雜的一種。 2按照零件和車間的構成劃分 ： (1) 流水車間調度 (Flow shop)：在這種車間中，每個零件都有相同的加工路徑。這樣，機床設備的布局如同流水線一樣，零件一次從流水線的一端進入，最后從另一端流出。 (2) 作業車間調度 (Job shop)：在這種車間中，機床設備的布局可以是任意的，因此零件的加工路徑也是任意的，并且各零 件的工序內容和數量也是任意的。這是一種最一般的車間調度形式。 (3) 開放式車間調度 (Open shop)：每個零件的工序之間的加工次序是任意的。零件的加工可以從任何一道工序開始，在任何一道工序結束。 (4) 單車間調度 (Single shop)：在這種車間中，每個零件只能有一道工序。 3按照零件的加工特點劃分 ： (1) 靜態車間調度 (Static scheduling)：所有的零件在開始調度時刻已經準備間的調度不考慮零件在加工過程中出現的意外情況，如機床突然損壞、零件的交貨期提前、有更緊迫的零件要求被加 工等等。 (2) 動態車間調度 (Dynamic scheduling)：車間的調度要求考慮零件在加工的各種意外情況。這種調度方式要求調度能隨時相應車間能力的變化，在有突發事件出現后，能立即根據當時的車間加工能力，對待加工的零件重新展開調度，以確保在任何時候，都能保持車間的加工性能指標處于最優或次優狀態。 2.4 Job Shop 與 Flow shop 比較 1.Job Shop 與 Flow shop 的共性 Job Shop 與 Flow shop 調度問題是目前調度問題的兩大類型，其目標均是通過科學的調度，使 車間調度問題最優化。基本約束條件均為： 西北工業大學明德學院本科畢業設計論文 8 (1) 同一時刻同一臺機器只能加工一個零件； (2) 每個工件在某一時候只能在一臺機器上加工，不能中途中斷每一個操作； (3) 同一個工件的工序之間有先后約束，不同工件的工序之間沒有先后約束； (4) 不同工件具有相同的優先級。 2、 Job Shop 與 Flow shop 的個性 對于上述約束條件，當增加約束條件：每臺機器只有單一加工功能，且各工件中的任意一個工序只能在所有機器中的一臺機器上操作且各工件的技術約束條件（加工方法、加工時間、加工設備、加工順序等）相同時，該 問題則轉化為Flow Shop 問題；當增加約束條件：每臺機器只有單一加工功能，各工件中的任意一個工序只能在所有機器中的一臺機器上操作時，該問題轉化為 Job Shop 問題。 Flow shop 型問題假設所有作業都在同樣的設備上加工，并有一致的加工操作和加工順序； Job shop 是最一般的調度類型，不同的作業具有不同的加工操作和加工順序，并不限制作業的加工設備?，F代車間調度類型往往是 job shop型的，本文的研究就是針對 job shop 型的調度問題展開。 2.5 調度問題的研究方法 生產調度問題的研究最初 集中在整數規劃、仿真和簡單的規劃等方法上，這些方法不是調度結果不理想，就是難以解決復雜的問題。 隨著機器數和工件數的增加，調度方案呈指數增長，怎樣才能盡快地得到最優調度方案，這一問題吸引了國內外許多學者和實際生產調度人員的關注，提出了很多的解決方法。近年來，在生產調度領域出現了許多新的優化方法，比如神經網絡法、模擬退火法、遺傳算法等，使得生產調度問題的研究方法走向了多元化。 1精確算法一數學規劃法 數學規劃法主要是通過對車間調度問題建立一個整數規劃模型，采用枚舉方法尋求調度問題的最優解。數學規劃方法往往采 用基于枚舉思想的分枝定界法或動態規劃算法進行求解。分枝定界法基本思想是先求出對調度整數規劃模型所對應的線性規劃問題的最優解，如果解不能滿足調度問題的整數條件，則對應的線西北工業大學明德學院本科畢業設計論文 9 性規劃問題的最優解必是調度問題的目標函數值的上界，而調度問題的任意可行解的目標函數值則是其最優解的下界，然后將對應的線性規劃問題的可行域分成子域，通過不斷減少上界和增大下界，最終尋找到最優解。分枝定界法的實現方法是動態構造一個表示調度問題所有可行解的樹，通過對樹的搜索尋找調度問題的最優解。分枝定界法只適合于小規模的調度問題，并且對實際問題比較 敏感，因此限制了它在調度問題上的應用。動態規劃方法的優點是任務分配和排序的全局性比較好，所有的選擇同時進行，因此可以保證求解問題的全局優化。但是，動態規劃方法是一種精確求解方法，它需要對調度問題進行統一的建模，任何參數的變化會使得算法的重用性很差，因此，對于復雜多變的生產調度來說，單一的數學規劃模型不能覆蓋所有的因素，存在求解空間大和計算困難等問題。 2近似算法 由于數學規劃法的局限性，從 20 世紀 70 年代開始出現了啟發式算法，這些算法基本上是在一些信息和規則的啟發下進行推理和計算，從而獲得調度問題的近似最 優解。啟發式搜索方法的優點是利用了面向特定問題的知識和經驗，因而可以產生好的解決方案，求解時間也可以接受。而對于如何提高搜索效率并減少內存使用以解決規模較大的問題，還需要進一步探索。啟發式算法主要有： (1) 基于啟發式規則的調度算法 啟發式規則的調度算法也稱調度規則，是最早的近似算法。其本質是給每一個生產任務和操作賦予優先級，優先級高的生產任務和操作優先考慮。由于其具有簡單、易于實現、計算復雜度低的特點，調度規則在調度問題上得到廣泛的應用，同時不斷有新的調度規則產生。 Panwalkar 等人總結了 113 條規 則，并將它們分為三類：簡單規則、復合規則、式規則，其中屬于簡單規則有 30 多條，如先進先出、最短加工時間、交付期最早等經常使用的規則，其它規則基本上是簡單規則的組合或加權組合；另外，調度規則經過適當的組合和變形后，往往可以得到很好的調度效果。調度規則的缺點在于其精確度不夠高。隨著計算機運算速度的飛速提高，人們希望尋找新的近似調度方法，以合理的額外計算時間代價，換得比單純啟發式規則所得到的調度更好的調度。 (2) 啟發式圖搜索法 啟發式圖搜索法主要有寬度優先、深度優先、 Beam 搜索及 A 或者 A算法等。西北工業大學明德學院本科畢業設計論文 10 啟發式圖搜 索法的缺點在于計算復雜度較高，如 A*算法的計算復雜度為D(2n-1)(n 為搜索圖中結點數 )，在調度問題的離散圖中結點數為 nxm。對于此類方法如何提高搜索效率、減少內存使用，以能解決比較大的規模的問題，還需要進一步探索。 (3) 拉格朗日松弛算法 LR 算法由于其在可行的時間里能對復雜的規劃問題提供較好的最優解，并能對解的最優性進行定量評估，近年來已成為解決復雜生產調度問題的重要方法。但不可避免的是， LR 算法存在搜索效率低，可行調度的構造有待于進一步研究等問題。 3智能搜索算法 計算智能是通過神經網絡、模糊系 統、進化計算的有機融合而形成的新的科學方法，也是智能理論和技術發展的嶄新階段。 (1) 遺傳算法 遺傳算法 (genetic algorithm 簡稱 GA)是一種嶄新的并行優化搜索方法。它是模仿物群體進化過程的一種優化算法，給定一組初始解作為一個群體，通過選擇、交叉和變異等遺傳操作來搜索最優解。遺傳算法對求解問題本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并根據適應性進行選擇，使適應性好的染色體比適應性差的染色體有更多的繁殖機會，經過反復迭代，直到達到某種形式的收斂。遺傳算法尤其適用于處理傳統 搜索方法難以解決的復雜的非線性問題，可廣泛用于組合優化、機器學習和規劃設計等領域。 遺傳算法已經成為一種比較通用的優化算法，主要原因是編碼技術和遺傳操作比較簡單，優化不受限制性條件的約束。但遺傳算法也有明顯的不足之處：對于大規模的組合優化問題，由于搜索空間大，搜索時間較長，往往會出現早熟收斂的情況；對初始種群很敏感，初始種群選擇不好會影響解的質量和算法效率。為了進一步改進遺傳算法，人們主要從兩方面入手：一是對遺傳算法本身進行改進；二是與其它算法結合，取長補短。 (2) 禁忌搜索算法 對于復雜的組合優化問題， 禁忌搜索也是一種通過鄰域搜索以獲取最優解的方法。算法的基本過程如下：它從一個可行解 S 出發，產生的領域，如果 F 為目西北工業大學明德學院本科畢業設計論文 11 標函數，選取所有領域中使 F(si)為最優的狀態作為下一個狀態，并把這一移動的反向移動存入一個稱為禁忌移動 (Ta bu Move)的表中。列在表中的移動在以后若干步內不允許再產生，這樣可免搜索退回去。每搜索一次，更新一次禁忌移動表。由于禁忌移動表的限制，有可能跳出局部極小，從而提高了算法的運行效率。可見，禁忌搜索算法的基本要素是初始解、移動、鄰域和禁忌表。禁忌搜索算法沒有自然性的終止條件，對求解的問 題，目標函數和搜索空間沒有任何特殊的要求，計算速度較快。因此，它在調度問題上有著廣泛的應用前景。 (3) 人工神經網絡 “ 人工神經網絡 是一種模擬人腦神經系統的結構和功能，運用大量的處理部件經廣泛互連而組成的網絡系統。 Hop field 應用神經網絡方法求解旅行商問題獲得成功，從而為組合優化問題求解開辟了新的途徑。人工神經網絡的優點是：具有很強的分布式存儲能力和很大的存儲空間，具有自學習能力，再者容錯性好，特有的高維空間使多體效應更加復雜和顯著，易于分類。但是，人工神經網絡在實際生產中的應用不是很多，而且存在 學習效率比較差、難以表達符號知識、計算速度比較慢和精度低等缺點，這些都需要進一步改進。特別是對于求解大規模問題有一定難度。目前，神經網絡優化應用于生產調度中，主要有三種方式：一是利用其并行計算能力，求解優化調度；二是利用其自學習能力，從優化軌跡中提取調度知識；三是用神經網絡來描述調度約束或調度策略，以實現對生產過程的可行或次優調度。 (4) 模擬退火方法 模擬退火算法 (SA)來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個 溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。用固體退火模擬組合優化問題，將內能 E 模擬為目標函數值 f,溫度 T 演化成控制參數 t，即得到解組合優化問題的模擬退火算法：由初始解 i 和控制參數初值 t開始，對當前解重復 “ 產生新解一計算目標函數差一接受或舍棄一的迭代，并逐步衰減 t 值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程模擬退火方法已經應用到許多領域。模擬退火算法顯示出了求解優化問題的強大威力，它可以突破局域搜索的限制，轉移到西北工業大學明德學院本科畢業設計論文 12 代價較高的解答，而且如果選擇參數得當 ，會在很快的時間內收斂。但是，模擬退火算法在實際應用中往往不能產生較優的結果，而且各個參數選擇起來比較困難，如果選擇不得當，就會使得計算時間很長，而且可能得不到好的結果，模擬退火算法和其它算法結合使用會得到很好的效果，如和遺傳算法、人工神經網絡結合等。 (5) Multi-agent 方法 多代理通過一系列分散的智能單元 (Agent)間進行協調來解決問題，這些單元有各的目標和自治的行為，并且可以有子單元，但是沒有一個單元能夠解決全局問題，因而它們之間必須進行協調。每個 Agent 至少應有以下三個組成部分： 1).知識庫。包含 Agent 執行其功能所必需的知識和數據。 2).控制功能。根據環境狀態及與其它 Agent 間的相互作用，從知識庫中提取知識來完成調度功能。 3).通訊功能。用來與其它 Agent 和環境之間進行信息傳遞。 Multi-agent 特別適合解決復雜問題，尤其是那些經典方法無法解決的單元間有大互作用的問題。 (6) 模糊邏輯 1965 年，美國控制論專家 Zadeh 教授首先提出模糊集合的概念，發表了開創性論文糊集合論。他提出模糊數學的核心思想就是運用數學手段，仿效人腦思維，對復雜事物進行模糊處理。 1973 年， Zadeh 教授又提出模糊邏輯的理論，并積極倡導將模糊理人工智能方向發展。模糊集理論對于建模和求解車間調度問題是非常有用的，因為它就具有許多模糊特征，比如不確定的加工次數、不確定的約束數量以及不確定的加工時間等 (7) 螞蟻調度算法 螞蟻選擇路徑的原則是依據信息素隨機選擇，即信息素多的路徑被選擇的可能性較大，若有一只螞蟻隨機地選擇了最短或較短的路徑，那么，它能較早地回來并在該路徑上留下信息素。在一定時間內，這條路徑上就有較多的信息素，從而吸引其它螞蟻也選擇這條路徑。由于它們會較早地留下信息素，最短路徑上的信息 素量就會越來越多，這種正反饋使得該路徑的吸引力會越來越強，另一方面，信息素隨時間揮發，較長的路徑由于信息素難以得到加強，信息素的量會越來越西北工業大學明德學院本科畢業設計論文 13 少，最終被完全廢棄。螞蟻在選擇路徑的過程中，留下信息素來表示自己的 “ 試錯一結果；利用環境實現非直接通信，使得群體能區分不同解的優劣；利用隨機選擇特性，使得整個蟻群能夠跳出局部最優；利用信息素的揮發特性來淘汰劣質解。 (8) 神經元算法 人工神經元網絡的早期研究始于二十世紀四十年代，以 1943 年美國生理學家 W.S McCullocn 和數學家 W.A Pitts 提出的二值神經元 模型為代表。人工神經網絡的用人工神經元相互連接組成一個計算網絡，并行高效地求解問題。它的主要特點是能夠學習，通過給網絡提供一定的訓練樣本，然后根據網絡的實際輸出與希望輸出之間的偏差，利用某種方法逐步修改各人工神經元之間的連接權，形成求解某些問題的能力。從二十世紀八十年代末期開始，人工神經網絡被用來求解調度問題。它的主要缺點是效率受訓練影響很大，并且在問題規模較大時，計算速度慢，結構參數難以確定。 2.6 兩機無等待流水車間調度 無等待流水車間（ no-wait flow shop， NWFS）調度問題是一類十分重要的調度問題，它廣泛存在于煉鋼、食品加工、化工和制藥等領域。已經證明機床數量大于 2 的 NWFS 是強 NP 難題。 NWFS 可描述為：給定 m 臺機床和 n 個工件，所有工件在各機床上的加工順序均相同。同時約定，一個工件在某一時刻只能夠在一臺機床上加工，一臺機床在某一時刻只能夠加工一個工件。由于技術條件的限制，同一工件的加工必須連續完成，即同一工件 的 相鄰工序之間沒有等待時間。各 工序的加工時間已知。問題是如何安排生產， 在 滿足上述要求的 條件下 得到最小生產周期。 2.6.1 生 產周期的計算 由于同一工件的工序必須連續生產的限制，計算 NWFS 的生產周期不同于一般流水車間調度問題。文獻 3給出了 NWFS 生產周期的計算公式：令 kip, 為工件i 在機床 k 上的加工時間， ,.,1,.,1 nii 為一個調度， iid ,1 為相鄰兩工件 i-1和 i 的開工時間之差（如圖 1-1)所示）；則 iid ,1 為 西北工業大學明德學院本科畢業設計論文 14 iidi - 1 , i12機 床時 間 ti - 1i - 1 ii12機 床時 間 ti - 1i - 1生 產 周 期生 產 周 期a ) N W F S 調 度 b ) 流 水 車 間 調 度 圖 1-1 兩工件的 NWFS 調度和流水車間調度 ,m a xm a x 1,111,1,12,1 ikqqikqqimkii pppd 的生產周期為 ni mk knii pdf 2 1 ,1)( 上述iid ,1和 )(f 的算法復雜度分別為 O(m2)、 O(nm2)。 2.6.2 生產周期的快速算法 結合問題特征，可簡化iid ,1的計算。如圖 1 所示，兩個工件的 NWFS 和流水車間調度 問題有相同的生產周期。因此，可先按照流水車間調度問題求得生產周期，再根據連續生產的要求從后向前依次求得 NWFS 的 各工序開工時間，進而得到iid ,1。令yxs,、yxc,分別為工 序yxo,的開工 、 完工時間，求iid ,1的算法如下： 1. 01,1 is，1,11,1 ii pc； 令 y從 2到 m，分別計算1,1,1 yiyi cs，yiyiyi psc ,1,1,1 2. 1,11, ii cs，1,1,1, iii psc ；令 y 從 2 到 m，分別計算 ,m ax ,11, yiyiyi ccs ，yjyjyj psc , 。 3. 令 y 從 m-1 到 1，分別調整1, yiyi sc，iyyiyi pcs ,。 4. 1,11,1 iiii ssd 上述算 法的復雜度為 O(m)。 若 將得到的iid ,1代入式（ 2），容易求得生產周1-1 1-2 西北工業大學明德學院本科畢業設計論文 15 mk knp1 ,期，其復雜度為 O(nm)。 因為iid ,1共有 )1( nn 個，為了 提高算法效率 ，可 預 先求出所有iid ,1。 這樣， 在計算生產周期時，iid ,1就可視為常數。同樣， 可看作常數 。 于是 ， 式（ 2）的復雜度就可降 低 為 O(n)。 西北工業大學明德學院本科畢業設計論文 16 第三章 遺傳算法 3.1 遺傳算法的形成與發展 遺傳算法起源于對生物系統所進行的計算機模擬研究。早在本世紀 40 年代，就有學者開始研究如何利用計算機進行生物模擬的技術。進入 60 年代后，美國Michigan 大學的 Holland 教授受到這種生物模擬技術的啟發，創造出了一種基于生物遺傳和進化機制的適合于復雜系統優化計算的自適應概率優化技術 遺傳算法。 70 年代初， Holland 提出了遺傳算法的基本定理 模式定理（ Schema Theorem），從而奠定了遺傳算法的理論基礎。 1975 年， Holland 出版了 其開創性的著作自然和人工系統中的自適應性（ Adaptation in Natural and Artificial Systems）。 同年， De Jong 基于遺傳算法的思想在計算機上進行了大量的純數值函數優化計算實驗，他推薦了在大多數優化問題中都較適用的遺傳算法的參數，還定義了評價遺傳算法性能的在線指標和離線指標。在一系列研究工作的基礎上， 80年代由 Goldberg 進行歸納總結，出版了專著搜索、優化和機器學習中的遺傳算法（ Genetic Algorithms in Search,Optimization and Machine Learning） ,從而形成了遺傳算法的基本框架。 1991 年， Davis 編輯出版了遺傳算法手冊（ Handbook of Genetic Algorithms）一書，此書為推廣和普及遺傳算法的應用起到了重要的指導作用。1992 年， Koza 將遺傳算法應用于計算機程序的優化設計及自動生成，提出了遺傳編程（ Genetic Programming，簡稱 GP）的概念。 正是由于 80 年代中期，遺傳算法研究的蓬勃發展，吸引了大批的科學研究者和工程技術人員從事該領域的研究和開發應用工作。 盡管遺傳算法本身在理論和應用方法上仍有許多待進一步研究的問題，但它的應用非常廣泛，尤其適合于處理傳統搜索方法難以解決的高度復雜的非線性問題。它在在函數優化、組合優化問題求解、生產調度問題、自動控制、模式識別、信息處理、規劃設計、機器學習、圖像處理、機器人學、人工生命、遺傳編程等西北工業大學明德學院本科畢業設計論文 17 領域的應用中已展現出其優越性和魅力，從而也確定了它在 21 世紀的智能計算機技術的關鍵地位。 3.2 遺傳算法的基本思想 遺傳算法和傳統的搜索算法不同，它從一組隨機產生的初始解，稱為 “ 種群(Population)” 開始搜索過程。種群中的 每個個體是問題的一個解，稱為 “ 染色體 (Chromosome)” 。在遺傳算法中最重要的概念是染色體，染色體通常是一串數據 (或數組 )，用來作為優化問題的解的代碼，其本身不一定是解 .這些染色體在后續迭代中不斷進化，稱為遺傳。在每一代中用 “ 適應值 (Fitness)” 來測量染色體的好壞。生成的下一代染色體稱為后代 (Oring)。后代是由前一代染色體通過交 叉 (Crossover)或者變異 (Mutation)運算形成的。新一代形成中，根據適應值的大小選擇部分后代，淘汰部分后代，從而保持種群大小是常數。適值高的染色體被選中 的概率較高。據此，經過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優解或次優解 遺傳算法的基本步驟是 ： 1.確定問題的編碼方案。由于 GA 通常不直接作用于問題的解空間，而是利用解的某種編碼表示來進行進化，因此選擇合理的編碼機制對算法質量和效率有很大影響。 2.確定適應度函數。由于 GA 通常基于適應度進行遺傳操作，因此合理的適應度能夠將各個體的優劣程度得以體現，并適應算法的進化過程。 3.算法參數的選取。通常包括種群數目、交叉概率、變異概率、進化代數等。 4.遺傳算子的設計。通常包括初始化、選擇、交叉 、變異和替換操作等。 5.確定算法的終止條件。終止準則應根據所求解問題的性質，在優化質量和效率方面作合理均衡或側重。 3.3 遺傳算法的特點 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，它與傳統的算法不同，大多數古典的優化算法是基于一個單一的度量函數 (評估函數 )的梯度或較高次統計，以產生一個確定性的試驗解序列，遺傳算法不依賴于梯度信息，而是通過模擬自然進化過程來搜索最優解，它利用某種編碼技術，作用于稱為染色體的數字串，模擬由這些串組成的群體的進化過程。遺傳算法通過有組西北工業大學明德學院本科畢業設計論文 18 織地、隨機地信息交換來 重新組合那些適應性好的串，生成新的串的群體。遺傳算法的特點有以下幾點 ： 1.自組織、自適應和自學習性 (智能性 )。應用遺傳算法求解問題時，在編碼方式、適應度函數及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略為 “ 適者生存，不適者被淘汰 ” ，因而適應度大的個體具有更適應環境的基因結構，再通過基因重組和基因突變等操作，就可能產生更適應環境的后代。進化算法的這種自組織、自適應特征，使它同時具有能根據環境變化來自動發現環境的特征和規律的能力。自然選擇消除了算法設計過程中的一個最大的障 礙，即需要事先描述問題的全部特點，并要說明針對問題的不同特點算法應采取的措施。因此，利用遺傳算法的方法，我們可以解決那些復雜的非結構化問題。 2.并行搜索特性。遺傳算法按并行方式搜索一個種群數目的所有點，而不是單點。它的并行性表現在兩個方面，一是遺傳算法是內在并行的 (inherent Parallelism)，即遺傳算法本身非常適合大規模并行搜索操作。最簡單的并行方式是讓幾百甚至數千臺計算機各自進行獨立種群的演化計算，運行過程中甚至不進行任何通信 (獨立的種群之間若有少量的通信一般會帶來更好的結果 )，等到運算 結束時才通過比較、選擇最佳個體。這種并行處理方式對并行系統結構沒有什么限制和要求，可以說，遺傳算法適合在目前所有的并行機或分布式系統上進行并行處理，而且對并行效率沒有太大影響。二是遺傳算法的內含并行(implicitparallelism)。由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內的多個區域，并相互交流信息。使用這種搜索方式，雖然每次只執行與種群規模 n 成比例的計算，但實質上已進行了大約 O(n3)次有效搜索，這是使遺傳算法能以較少的計算獲得較大的收益。遺傳算法僅用適應度函數的數值評估基因個體 ，并在此基礎上進行遺傳操作。所以遺傳算法不僅不受函數連續可微的約束，而且其定義域可以任意設定。遺傳算法具有可擴展性，易于同別的技術混合使用。 3.遺傳算法對給定問題，可以產生許多的潛在解，最終選擇可以由使用者確定。 由以上結論可知，遺傳算法模擬自然界生物優勝劣汰的進化過程，在迭代處理過程中，群體一代一代的得以優化并逐漸逼近最優解。但為什么通過選擇、交叉和變異這三種簡單的算子就能夠體現出其他算法不具有的自適應 和 全局優化西北工業大學明德學院本科畢業設計論文 19 能力呢 ?為此，科學工作者做了許多深入細致的理論研究工作，目前主要有以下幾個方面 : 1.模式處 理 模式 (Schema)是一個描述字符串集的模板，該字符集中的串的某些位置上存在相似性。引入模式概念后可以發現，遺傳算法所操作的串實際上隱藏著多個模式，一個模式可以隱含在多個串中，不同的串之間通過模式而相互聯系。遺傳算法進行群體搜索的過程可看作是隱含的對模式的抽樣過程，通過遺傳操作將較短的低階模式的信息結合起來形成高階模式。最終搜索到最優解。所以串的運算實質上是模式的運算，通過對模式在選擇、交叉和變異作用下的變化分析導出模式定理。 2.遺傳算法收斂性研究 遺傳算法可以實現均衡的收縮，并且在許多復雜問題的求解 中往往能得到滿意的結果，但是該算法的優化收斂性仍需研究分析。近年來，關于遺傳算法收斂性的研究取得了突破性進展， Goldberg 和 Segrest 首先是用馬爾可夫鏈模型分析了遺傳算法收斂性， Joe S.(1995)等用有限馬爾可夫鏈證明了標準遺傳算法理論上不具備優化收斂性 ；同時還證明了若對遺傳算法作一定的改進，即不按比例進行選擇，而是保留當前的最佳值，則此改進后的遺傳算法最終能夠收斂到最優解。羅志軍等 (2000)論證了遺傳算法過程是一個齊次有限馬爾可夫鏈，巧妙地構造 GA 的馬爾可夫鏈的狀態空間，并對其轉移概率矩陣 進行極限分析。 3.4 遺傳算法的過程和流程 1.主要步驟 標準遺傳算法的主要步驟如下： (1).隨機產生一組初始個體構成初始種群，個體數目一定，每個個體表示染色體的基因編碼，定義調度問題的適應度函數，并評價每一個體的適配值(fitness value)。 (2).判斷算法收斂準則是否滿足，若滿足則輸出搜索結果；否則執行以下步驟。 (3).根據適配值大小以一定方式執行復制操作。 (4).按交叉概率 pc 執行交叉操作。 西北工業大學明德學院本科畢業設計論文 20 (5).按變異概率 pm 執行變異操作。 (6).返回步驟 (2)。 2.基本流程 標準遺傳算法的 流程圖描述，如圖 3.1 所示。 其中涉及如下： (1).算法收斂準則 算法收斂準則一般依據問題的不同有不同的確定方式。例如，可以采用以下的準則之一作為判斷的條件： 1)種群中個體的最大適應度超過預先設定值； 2)種群中個體的平均適應度超過預先設定值； 3)世代數超過預先設定值。 (2).選擇操作 選擇操作通常采用比例選擇，即復制概率正比于個體的適配值，如此意味著適配值高的個體在下一代中復制自身的概率大，從而提高了種群的平均適配值根據群體中每個個體變量的目標函數的值或一定概率值進行選擇和淘汰，利用其中的優良個體 進行繁殖，因此，在遺傳算法中，其優良個性可以一直保持下去。常用的選擇操作有： 1).比例選擇：也叫賭輪選擇，它的基本思想是各個個體的被選中的概率和其適應度大小成比例。 2).最佳個體保留選擇：它的思想是先按賭輪選擇機制執行遺傳算法的選擇功能，然后把群體中適應度最高的個體不進行交叉和變異而直接復制到下一代中。這樣可以保證進化過程中某一代的最優解可不被交叉和變異操作破壞，但是容易出現早熟現象。另外還有排序選擇、錦標賽選擇、 EP 選擇等方法。 西北工業大學明德學院本科畢業設計論文 21 隨 機 產 生 初 始 種 群并 計 算 個 體 適 配 值算 法 收 斂 準 則是 否 滿 足執 行 復 制 操 作r a n d o m 0 , 1 pc?輸 出 搜 索 結 果執 行 交 叉 操 作r a n d o m 0 , 1 0。在復雜問題的優化時，往往需要構造合適的評價函數，使其 適應 GA 進行優化。 )()f JMTMJM （ （ 3-1） 3.5.4 遺傳算子的設計 遺傳算子優勝劣汰是設計 GA 的基本思想，它應在選擇、交叉、變異等遺傳算子中得以體現，并考慮到對算法效率與性能的影響。 1.選擇復制 復制操作是為了避免有效基因的損失，使高性能的個體得以更大的概率生存，從而提高全局收斂性和計算效率。最常用的方法是比例復制和基于排名的復制，前者以正比于個體適配值的概率來選擇相應的個體，后者則基于個體在種群中的 排名來選擇相應的個體。至于種群的替換，采納的方案可以是部分個體的替換，也可以是整個群體的替換。 2.交叉算子 (1).交叉方法 1： 首先選取父代染色體 1 和 2，隨機產生一個與染色體長度相同的向量，該向西北工業大學明德學院本科畢業設計論文 25 量由數字 1、 2 組成。向量定義了從父代 1 和父代 2 中選取基因的順序。從一個父代上選取 1 個基因并從另一個父代上消除對應的基因，并且將該基因加到子代上去；重復該步驟直到兩父代染色體為空并且子代染色體包含所有的基因。 父代 1 ： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索引： 1 1 2 1 1 2 3 3 2 2 3 隨機產生的數字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 1 結果： 子代 1： 3 2 1 4 1 2 1 2 3 4 3； 子代 2： 1 4 3 2 2 2 3 1 1 4 3 (2).交叉方法 2： 從父代染色體中任意選取一個子串，然后把該子串插入到父代 2 中子串中第一個基因出現的位置，然后從得到的染色體中刪掉子串索引所對應的所有基因。 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 隨機產生的數字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 2 結果： 子代 1： 4 3 2 2 1 2 3 1 1 4 3； 子代 2： 3 2 2 1 2 4 3 1 1 4 3 (3).交叉方法 3： 從父代染色體 1 中任意選取一個子串，先從染色體 2 中刪掉子串索引所對應的所有基因，然后把該子串插入到父代 2 中子串在父代 1 中出現的位置。 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 隨機產生的數字： 1 1 2 2 2 2 2 1 1 1 1 交叉方法 3 結果： 子代 1： 4 3 2 2 2 3 1 1 1 4 3 ； 子代 2： 3 4 3 1 2 2 1 2 1 4 3 (4).交叉方法 4： 從父代染色體 1 中任意選取一個子串，然后把該子串插入到父代 2 中子串在父代 1 中出現的位 置，從染色體 2 中刪掉子串索引所對應的所有基因 父代 1： 3 2 4 2 2 3 1 1 1 4 3； 父代 2： 1 4 1 3 2 2 1 2 4 3 3 索 引： 1 1 1 2 3 2 1 2 3 2 3； 索 引： 1 1 2 1 1 2 3 3 2 2 3 隨機產生的數字： 1 1 2 2 2 2 1 1 1 西北工業大學明德學院本科畢業設計論文 26 交叉方法 4 結果： 子代 1： 4 3 2 3 1 1 2 2 1 4 3 ； 子代 2： 3 4 2 2 1 2 3 1 1 4 3 3.5.5 編碼參數 種群數目是影響算法優化性能和效率的因素之一。 通 常，種群太小則不能提供足夠的采樣點，以至算法性能很差，甚至得不到問題的可行解 ； 種群太大時盡管可增加優化信息以阻止早熟收斂的發生，但無疑會增加計算量，從而使收斂時間太長。當然，在優化過程中種群數目是允許變化的。 交叉概率用于控制交叉操作的頻率表。概率太大時，種群中串的更新很快，進而會使高適配值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前。 當交叉操作產生的后代適配值不在進化且沒有達到最優時，就意味著算法的早 熟 收斂。這種現象的根源在于有效基因的缺損。 變異操作一定程度上 克 服了這種情況 ，有利于增加種群的多樣性。 變異概率是加大種群多樣性的重要因素?；诙M制編碼的 GA 中，通常一個較低的變異率足以防止整個群體中任意位置的基因一直保持不變。但是，概率太小則不會產生新個體，概率太大則是 GA 成為隨 機 搜索。 3.5.6 遺傳算子 優勝劣汰是設計 GA 的基本思想，它應在的選擇、交叉、變異等遺傳算子中得以體現，并考慮到算法效率與性能影響。 復制操作是為了避免有效基因的損失，使高性能的個體得以更大的概率生存，從而提高全局收斂性和計算效率最常用的方法是比例復制和基于排名的復制，前者以正比于個體是配置的概率來 選擇相應的個體，后者則基于個體在中群眾的排名來選擇相應的個體。至于種群的替換，采納的方案可以是部分個體的替換，換也可以是整個群體的替換。 3.5.7 算法的終止條件 GA 的收斂理論說明了 GA 以概率 1 收斂的極限性質，因此我們要追尋的是提高算法的收斂速度，這與算法操作設計和參數選取有關。然而，實際應用 GA 時是不允許讓它無停的發展下去的，而且通常問題的最優解也未必知道，因此需要有一定的條件來終止算法的進程。 西北工業大學明德學院本科畢業設計論文 27 第四章 兩機無等待流水車間調度問題 仿真 流水車間 (Flow shop)調度問題 , 也稱為同序作業調度問題 ，它是車間調度中的一個重要論題，它無論是在離散制造工業還是在流程工業中都具有廣泛的應用，具有一定的代表性。 4.1 流水車間調度問題的描述與數學模型 流水車間調度問題一般可以描述為 n 個工件要在 m 臺機器上加工，每個工件需要經過 m 道工序，每道工序要求不同的機器 n， n 個工件在 m 臺機器上的加工順序相同。工件在機器上的加工時間是給定的，設為 tij(i l， ， n； j l， ，m)。問題的目標是確定 n 個工件在每臺機器上的最優加工順序，使最大流程時間達到最小。 對該問題常常作如下假設： (1).每個工件在機器上的加工順序 是給定的； (2).每臺機器同時只能加工一個工件； (3).一個工件不能同時在不同的機器上加工； (4).工序不能預定； (5).工序的準備時間與順序無關，且包含在加工時間中； (6).工件在每臺機器上的加工順序相同，且是確定的。 令 c(ji， k)表示工件 ji 在機器 k 上的加工完工時間， j1， j2， jn 表示工件的調度，那么對于無限中間存儲方式， n 個工件、 m 臺機器的流水車間調度問題的完工時間可表示為 )4-4( ,2；,2；)1,(),(m ax ),()3-4( ,2；)1,()1,()2-4( ,2；)1,c(),c(1)-(4 1,)1,(11111111mknitkjckjckjc nitjcjc mktkjkjtjckjiiijiikjjii 最大流程時間為： 西北工業大學明德學院本科畢業設計論文 28 ）（ 5-4 ),(m a x mjcc n 調度目標就是確定 j1,j2,jn 使得 Cmax 最小。 4.2 基于 Johnson 法則的 兩機無等待流水車間調度問題 仿真 首先說明 Johnson 法則：如果作業 i 和 j 滿足 m i n , m i n , i j j ib a b a，則作業 i 和 j 滿足 Johnson 不等式。如果不滿足，則交換作業 i 和 j 的加工順序，作業 i 和 j 滿足 Johnson 不等式。由此可知，任意兩個滿足 Johnson 法則的調度具有相同的加工時間?，F在，流水線問題轉化為求滿足 Johnson 法則的調度問題。 可以證明，應 用 Johnson 法則的算法是本問題的一個最優算法。 算法的大致步驟如下： ia ， ib 分別為第 i 個作業在機器 1M 、 2M 上的作 業時間。先取 1 | iiN i a b， 2 | iiN i a b.，然后將 1N 中作業按照 ia 的非遞減順序排序，將 2N 中作業按照 ib 的非遞增順序排序。之后將 1N 中作業接著構成滿足2N 中作業 Johnson 法則的調度算法。 具體實現時，可以通過完善比較函數，而將 n 個作業通過一次排序即可得到滿足的 Johnson 法則的調度順序。 圖 4-1 仿真程序代碼 西北工業大學明德學院本科畢業設計論文 29 圖 4-2 仿真程序代碼 圖 4-3 仿真程序代碼 西北工業大學明德學院本科畢業設計論文 30 圖 4-4 仿真程序代碼 圖 4-5 仿真程序 西北工業大學明德學院本科畢業設計論文 31 4.3 遺傳算法的設計 4.3.1 編碼方案 由于遺傳算法不能直接處理生產調度問題的參數，所以必須通過編碼將它們表示成遺傳空間中由基因按一定結構組成的染色體。流水車間調度用工件的順序來表示染色體。所以我們采用十進制基于工件的編碼，通過對 9 個工件的流水車間調度問題，假設工件的加工順序是 J1， J2， J3， J4， J5， J6， J7， J8， J9則可將其編碼為 R1， 2， 3， 4， 5， 6， 7， 8， 9。 4.3.2 群體的確定 初始群體由各個基因，即工件的加工排列隨機生成 20 個染色體，即隨機 產生 20 個初始調度方案，以后各子代群體由所有父代和交叉變異所產生的新染色體按照適應度函數值由大到小進行排列，并選擇前 20 個染色體進行作為子代，這樣就可以確保子代在交叉變異過程中，始終向著最優的方案演變。 4.3.3 適應度函數 一般將目標函數作為適應度函數，這里用最大加工時間的倒數作為適應度函數。由此計算每個染色體的適應值大小。 令 Cmax 表示染色體 i 的最大加工完成時間，那么適應度函數為： 6)-(4 1)(m a xCiF 4.3.4 遺傳算子的設計 1.對于選擇運算，選用基于排名的方法，將群 體中每個染色體按照適應度從大到小進行排列。然后按照某種規則給每個染色體分配選擇概率。例如群體大小為 20，排名前 16 的選中進行以后的運算，排名后 4 位則不進行以后的運算。 2.交叉運算使用交叉方法 1。 3.變異運算使用逆序變異算子。 4.運行參數的確定： M：群體大小。取 M 20； T：終止代數。取 T 2； Pc：交叉概率。取 Pc 0.5； 西北工業大學明德學院本科畢業設計論文 32 Pm：變異概率。取 Pm 0.01。 4.4 基于遺傳算法的兩機無等待流水車間調度問題仿真 圖 4-6 4.5 結果分析 由以上的演示可以看出，優秀的父代經過交叉變異后產生 會產生更加優秀的后代，也可能產生不良的后代，因此，將所有父代和新產生的染色體組合成一個大于父代群體大小的中間群體，并依據適應度進行重新排列，并選擇靠前的作為子代，這樣就保證了子代群體是優于父代群體的，并隨著交叉變異的代數越多而子代群體越趨向于優化。 西北工業大學明德學院本科畢業設計論文 33 第五章 全文總結 本文以流水車間的調度作為研究對象，以遺傳算法為基礎，分別對一般流水車間和具有可跨工位操作的流水車間兩種生產車間計劃調度進行了系統的研究。在理論研究的基礎上完成了基于遺傳算法的調度的算法設計，展示了算法的實現過程并對調度結果進行分析。本 論文的主要工作總結如下： 1.闡述了車間調度問題國內外研究現狀，探討了車間調度的問題以及可能的解決途徑。 2.對車間調度問題進行了簡單的描述的，對車間調度問題的復雜性進行了探討。將靜態和動態車間調度，作業車間調度和流水車間調度進行了區別。最后對車間調度方法進行了總結。接著簡單介紹了遺傳算法的形成與發展，基本思路和操作步驟。詳細介紹了遺傳算法中常用的一些編碼方式，交叉變異方法，查詢到了常用參數范圍和對算法的終止條件進行了簡單理解。 3.對一般流水車間問題進行了描述和數學建模，針對流水車間調度問題，對遺傳算法進 行了設計，選擇出最優的調度方案。 盡管調度問題的研究己經取得了很多的成果，但是這些成果與實際的調度問題之間都存在一定的差距，尚不能很好地解決復雜的實際生產調度問題。要更好地解決實際的復雜調度問題，需研究更加有效的調度優化方法以及研究解決實際調度問題的合理有效的調