兩機無等待流水車間調(diào)度問題與仿真論文

1、<p><b>　　本科畢業(yè)設(shè)計論文</b></p><p>　　題 目：兩機無等待流水車間調(diào)度問題與仿真</p><p>　　專業(yè)名稱 機械設(shè)計制造及其自動化 </p><p>　　學生姓名 </p><p>　　指導教師

2、 </p><p>　　畢業(yè)時間 2014年6月 </p><p>　　畢業(yè) 任務(wù)書</p><p><b>　　一、題目</b></p><p>　　兩機無等待流水車間的調(diào)度與仿真</p><p>　　二、指導思想和目的要求</p><

3、p>　　畢業(yè)設(shè)計（論文）是培養(yǎng)學生自學能力、綜合應(yīng)用能力、獨立工作能力的重要教學實踐環(huán)節(jié)。在畢業(yè)設(shè)計中，應(yīng)獨立承擔一部分比較完整的工程技術(shù)設(shè)計任務(wù)。要求學生發(fā)揮主觀能動性，積極性和創(chuàng)造性，在畢業(yè)設(shè)計中著重培養(yǎng)獨立工作能力和分析解決問題的能力，嚴謹踏實的工作作風，理論聯(lián)系實際，以嚴謹認真的科學態(tài)度，進行有創(chuàng)造性的工作，認真、按時完成任務(wù)。針對兩機無等待流水車間調(diào)度問題, 提出目標函數(shù)最大完工時間最小化的快速算法, 并給出算法的復雜度

4、.分析兩機無等待流水車間調(diào)度問題的排列排序性質(zhì),證明了兩機無等待流水車間調(diào)度問題的可行解只存在于排列排序中,排列排序的最優(yōu)解一定是兩機無等待流水車間調(diào)度問題的最優(yōu)解.最后研究了同時包含普通工件和無等待工件的兩機流水車間調(diào)度問題的復雜性,為進一步研究兩機無等待流水車間調(diào)度問題提供了理論依據(jù)。</p><p><b>　　三、進度和要求</b></p><p>　　第一階

5、段：（共計5周）</p><p>　　第一周及第二周，翻譯并完成教師指定的英文文獻翻譯； </p><p>　　第三周及第五周，對所研究課題有個全面的了解。</p><p>　　第二階段：（共計5周）</p><p>　　完成方案的提出，學習和用已知的方案方法進行實際問題的解決方案的提出和仿真。</p><p>　　第

6、三階段：（共計5周）</p><p><b>　　撰寫論文及評閱。</b></p><p>　　四、主要參考書及參考資料</p><p>　　[1] S.M.Johnson.optimal Two-and Three-Stage Production Scheduling with Set-up Time Included[J]. Naval

7、Research Logistics Quarterly.1954, 1:61-68</p><p>　　[2] Story A.E, Wagner H.M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,1963</p&g

8、t;<p>　　[3] Gavett J.W.Three Heuristic Rules for Sequencing Jobs to a Single Production Facility[J]. Mgmt.Sci.1965,11:B166-176</p><p>　　[4] S.Panwalker,Wafik Iskander.A Survey of Scheduling[J].Ops.R

9、es.1977, 25(1):45-61</p><p>　　[5] Stephen,C.Graves.A Review of Production Scheduling[J].Ops.res.1981,29（4）:646-675</p><p>　　[6] M.S.Fox.ISIS:A Retrospective Intelligent Scheduling.Intelligent Sc

10、heduling,Kaufmann, ed:Michael B.Morgan,1994:3-28</p><p>　　[7] B.Giffler,GL.Thompson.Algorithms for Solving Production Scheduling Problems[J].Ops Res.1960,8:487-503</p><p>　　[8] 董海，梁迪．設(shè)施規(guī)劃與物流分析

11、．北京：機械工業(yè)出版社．2005</p><p>　　[9] Baker K R.A Comparative Study of Flow Shop Algonithms [J].Ops Res.1975(23）:62-73</p><p>　　[10] 王偉玲，馬正元，王玉生．生產(chǎn)調(diào)度問題研究的動態(tài)與趨勢[J]．管理技術(shù)，2005年第5期．</p><p>　　[1

12、1] 鄭璐，顧鑫生，不確定條件下的零等待Flow Shop生產(chǎn)調(diào)度問題[J]．華東理工大學學報2004，30（2）：188-194．</p><p>　　[12] S.Panwalker, Wafik Iskander.A Survey of Scheduling[J].Ops.Res.1977, 25（1）:45-61.</p><p>　　[13] 謝源，謝劍英，鄭小龍．混合有限月蘇下

13、帶模糊交貨期的單機調(diào)度問題的研究[J]．信息與控制2005，34（3）：369-372． </p><p>　　[14] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer and Opreations. Research. 1986, 13:533-549.</p

14、><p>　　[15] 盧冰原，陳華平，顧春生等，模糊環(huán)境下的柔性工作車間調(diào)度模型的研究[J]．運籌與管理．2004，13．</p><p>　　[16] 李福明，朱云龍，尹朝萬等.基于遺傳算法的模糊調(diào)度研究[J].信息與控制．2004，33（6）：703-708</p><p>　　[17] 吳儀，劉民等.JSSP基本約束特點分析及調(diào)度算法[J].清華大學學報(自然科

15、學版)．2004，44(10)：</p><p>　　[18] Kinkpatric S, Gelatt CD, Vecchi M P.Operational by simulated annealing[J].Science.1983, 220:671-680.</p><p>　　[19] 吳梅，陸金桂.遺傳算法的研究進展綜述[J]．機床與液壓．2008，36(3)．</p>

16、;<p>　　[20] 孫卓明，余彬．遺傳算法．計算機時代．2004年，第1期</p><p>　　[21] 陳國良等．遺傳算法及應(yīng)用．北京：人民郵電出版社，1996</p><p>　　學生 薛 偉 指導教師 王 劍 系主任 </p><p><b>　　摘 要</b><

17、/p><p>　　流水車間(Flow Shop)調(diào)度問題無論是在工廠經(jīng)營管理還是在產(chǎn)品制造中都具有廣泛的應(yīng)用，因此對流水車間調(diào)度問題進行研究具有重大的理論意義和實際意義。</p><p>　　本文首先對車間調(diào)度問題國內(nèi)外研究現(xiàn)狀和發(fā)展趨勢進行了系統(tǒng)的闡述。其次，對遺傳算法的基本理論進行了詳細的論述。然后對Flow Shop調(diào)度問題建立數(shù)學模型。再次，在掌握了遺傳算法的基礎(chǔ)之上給出了基于遺傳算法

18、求解Flow Shop調(diào)度問題的編碼方案，遺傳算子的設(shè)計。然后基于遺傳算法對調(diào)度問題進行了實例分析。最后對上述兩種調(diào)度的結(jié)果進行了分析，結(jié)果表明本文提出的方法是有效可行的。</p><p>　　關(guān)鍵詞：生產(chǎn)調(diào)度，流水車間調(diào)度，遺傳算法。</p><p><b>　　ABSTRACT</b></p><p>　　Flow Shop (Flow S

19、hop) 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

20、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

21、 Shop scheduling problem to establish mathe</p><p>　　Key words: production scheduling;Flow shop scheduling;Genetic algorithm;</p><p><b>　　\</b></p><p><b>　　目 錄&

22、lt;/b></p><p><b>　　摘 要I</b></p><p>　　ABSTRACTII</p><p>　　目 錄III</p><p>　　第一章 緒 論1</p><p>　　1.1 引 言1</p><p>　　1

23、.2 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀和存在的問題1</p><p>　　1.2.1 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀1</p><p>　　1.2.2 研究中存在的問題2</p><p>　　1.3 研究意義與目的3</p><p>　　1.4 本文的工作4</p><p>　　第二章 車間調(diào)度問題5</p

24、><p>　　2.1. 車間調(diào)度問題的描述5</p><p>　　2.2 車間調(diào)度問題的特點6</p><p>　　2.3 車間調(diào)度問題的分類6</p><p>　　2.4 Job Shop 與Flow shop 比較7</p><p>　　2.5 調(diào)度問題的研究方法8</p><p>

25、;　　2.6 兩機無等待流水車間調(diào)度13</p><p>　　2.6.1生產(chǎn)周期的計算13</p><p>　　2.6.2生產(chǎn)周期的快速算法14</p><p>　　第三章 遺傳算法16</p><p>　　3.1 遺傳算法的形成與發(fā)展16</p><p>　　3.2 遺傳算法的基本思想17</p&g

26、t;<p>　　3.3 遺傳算法的特點17</p><p>　　3.4 遺傳算法的過程和流程19</p><p>　　3.5 求解調(diào)度問題的遺傳算法22</p><p>　　3.5.1 遺傳算法的設(shè)計步驟22</p><p>　　3.5.2 編碼方式22</p><p>　　3.5.3 適配值函

27、數(shù)24</p><p>　　3.5.4 遺傳算子的設(shè)計24</p><p>　　3.5.5 編碼參數(shù)26</p><p>　　3.5.6 遺傳算子26</p><p>　　3.5.7 算法的終止條件26</p><p>　　第四章 兩機無等待流水車間調(diào)度問題仿真27</p><p>

28、　　4.1 流水車間調(diào)度問題的描述與數(shù)學模型27</p><p>　　4.2 基于Johnson法則的兩機無等待流水車間調(diào)度問題仿真28</p><p>　　4.3 遺傳算法的設(shè)計31</p><p>　　4.3.1 編碼方案31</p><p>　　4.3.2 群體的確定31</p><p>　　4.3.3

29、 適應(yīng)度函數(shù)31</p><p>　　4.3.4 遺傳算子的設(shè)計31</p><p>　　4.4 基于遺傳算法的兩機無等待流水車間調(diào)度問題仿真32</p><p>　　4.5 結(jié)果分析32</p><p>　　第五章 全文總結(jié)33</p><p><b>　　參考文獻34</b><

30、;/p><p><b>　　致 謝36</b></p><p><b>　　畢業(yè)設(shè)計小結(jié)37</b></p><p>　　第一章 緒 論</p><p>　　1.1 引 言</p><p>　　伴隨著用戶對產(chǎn)品需求的快速變化，以及市場競爭的日趨激烈，現(xiàn)代制造企業(yè)需

31、要進行多品種、小批量生產(chǎn)，這種生產(chǎn)方式使生產(chǎn)計劃、組織和控制變得更加復雜。另外，要求企業(yè)對生產(chǎn)過程中所出現(xiàn)的各種信息進行及時反饋和處理，因此，生產(chǎn)調(diào)度問題作為生產(chǎn)管理系統(tǒng)的核心內(nèi)容和關(guān)鍵問題，其研究具有重要的理論和實用價值。企業(yè)要進行改革，結(jié)合企業(yè)的現(xiàn)狀，研究改進遺傳算法在車間調(diào)度的應(yīng)用，從而合理分配企業(yè)資源、提高勞動效率。研究改進遺傳算法在車間調(diào)度的應(yīng)用，從而合理分配企業(yè)資源、提高勞動效率。</p><p>　

32、　1.2 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀和存在的問題</p><p>　　1.2.1 國內(nèi)外車間調(diào)度問題的研究現(xiàn)狀</p><p>　　調(diào)度問題的研究始于20世紀50年代，S.M.Johnson提出了解決n/2/F/Cmax和部分特殊的n/3/F/Cmax問題的算法，這是調(diào)度理論的開始：直至五十年代末期，許多研究成果主要是針對規(guī)模較小的單機和簡單的流水車間的問題，提出了解析優(yōu)化方法，許多研究

33、成果主要是針對規(guī)模較小的單機和簡單的流水車間問題，提出了解析優(yōu)化方法，研究范圍較窄，但是這些研究卻成為經(jīng)典調(diào)度理論的基石。</p><p>　　六十年代，多是利用混合或純整數(shù)規(guī)劃和分支定界法解決一些有代表性的問題，如Story的研究。同時也有人開始嘗試用啟發(fā)式算法研究此問題，如Gavett提出的方法。六十年代末期，經(jīng)典調(diào)度理論體系初步成型。七十年代，人們開始了算法復雜性的研究，多數(shù)調(diào)度問題被證明屬于NP完全問題或

34、NP一難問題，難以找到多項式算法，因此開始關(guān)注啟發(fā)式算法。Panwalkar總結(jié)和歸納出了113條調(diào)度規(guī)則，并對其進行分類。七十年代末期，經(jīng)典調(diào)度理論趨向成熟。</p><p>　　八十年代初期，Stephen等從三個方面對調(diào)度進行了從新考察，對未來發(fā)展做了分析和預測，認為理論與實際的結(jié)合將會成為研究熱點。這個富有挑戰(zhàn)性的課題吸引了機械、計算機、管理等諸多領(lǐng)域的學者，許多跨學科的方法被應(yīng)用到研究中。其中最引人注目

35、的就是以Carnegie-Mellon大學的M.Fox為代表的學者們開展的基于約束傳播的ISIS研究，它標志了人工智能開始真正應(yīng)用與調(diào)度問題。八十年代后期，Giffler等人總結(jié)了生產(chǎn)調(diào)度理論和實際方面的最新研究進展，從七個方面論述了生產(chǎn)調(diào)度的技術(shù)和方法，認為生產(chǎn)調(diào)度無論在理論還是實踐上都已突破了傳統(tǒng)界限。</p><p>　　九十年代至今，各種方法在生產(chǎn)調(diào)度問題的研究中得到了充分的發(fā)揮，同時新的研究手段層出不窮

36、。 而Davis是最早把 GA(GeneticAlgorithm，遺傳算法)應(yīng)用于車間調(diào)度問題的學者之一，他在使用GA求解車間調(diào)度的研究中取得了近似最優(yōu)解。1985年，Davis發(fā)表了關(guān)于把GA成功應(yīng)用于車間調(diào)度問題的論文，充分證明了GA在解決車間調(diào)度問題中的可行性。此后，很多學者就給予遺傳算法的車間調(diào)度方面做了大量研究，發(fā)表了大量卓有成效的論文，對車間調(diào)度這類NP問題的解決提出了具體方案。這些論文中提出了一些具有突破性的新方法，改進并

37、完善了傳統(tǒng)GA車間調(diào)度中的應(yīng)用方法，同時通過在解決一些著名的標準檢測問題(Ben和nark)的過程中取得了最優(yōu)(或接近最優(yōu))解，進一步證明了遺傳算法在解決NP問題方面的有效性。</p><p>　　國內(nèi)對車間調(diào)度的研究起步比較晚，始于90年代。很多企業(yè)由于技術(shù)上的制約，基本上是靠調(diào)度人員的經(jīng)驗進行車間作業(yè)分配和調(diào)度。隨著遺傳算法在車間調(diào)度方面的應(yīng)用熱潮，在這方面也產(chǎn)生了大量的研究成果，不過，研究工作主要集中在清華

38、大學等等CIMS國家重點實驗室，但離形成系統(tǒng)的理論和開發(fā)出成熟的軟件系統(tǒng)還有很長一段距離，因此還在投入大量的人力和物力進行該方面的研究，特別是在開展對車間作業(yè)作業(yè)調(diào)度算法的研究方面，目前尚處在實驗研究階段。</p><p>　　車間調(diào)度問題的高度復雜性和現(xiàn)有計算機條件的局限性決定了不可能一開始就考慮到實際調(diào)度問題中的所有因素，因此，實際研究通常是對車間系統(tǒng)進行簡化和抽象來解決實際問題。正是在這些現(xiàn)有的理論成果上不

39、斷加上約束條件，使得研究問題近似于實際問題?？偠灾?，隨著各種特殊調(diào)度問題的攻克和新方法、新設(shè)備的出現(xiàn)，車間調(diào)度研究正向動態(tài)、敏捷、多資源、智能化的方向發(fā)展。</p><p>　　1.2.2 研究中存在的問題</p><p>　　由于在實際生產(chǎn)過程中會出現(xiàn)諸多不確定因素，而且調(diào)度問題己經(jīng)被證明NP難題，因此尋找具有多項式復雜性的最優(yōu)算法幾乎是不可能的。從目前文獻的研究來看，對于資源分配也沒

40、有提出一個切實可行的解決方案，往往都是從某一方面入手，在若干假設(shè)的基礎(chǔ)上，得出一種理論上的可行解。各種啟發(fā)式方法、諸如基于規(guī)則的算法等，由于能在合理的時間內(nèi)產(chǎn)生比較滿意的調(diào)度，因此廣泛應(yīng)用于實際調(diào)度中，但其往往對所得到的調(diào)度解的次優(yōu)性不能進行評估。因此，有必要探索更好的近似最優(yōu)調(diào)度算法，可以考慮通過增加合理的計算時間來提高解的次優(yōu)性。各種基于統(tǒng)計優(yōu)化的方法，諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問題的新途徑，但與別的優(yōu)化算法

41、類似，也存在著一定程度的枚舉、一般來說收斂到最優(yōu)解較慢，對于判斷解的最優(yōu)性也很困難，在這方面也需要做進一步的研究。</p><p>　　1.3 研究意義與目的</p><p>　　有史以來，有限資源的合理配置和優(yōu)化利用問題始終是人類社會所面臨的最基本經(jīng)濟問題，這個問題貫穿于社會生活的各個方面。從一個國家、社會的宏觀經(jīng)濟運行到具體企業(yè)的微觀經(jīng)濟活動，都要受資源條件的限制。對企業(yè)來說，能否對現(xiàn)

42、有資源進行合理配置和充分利用將直接影響到產(chǎn)品的制造成本，進而成為影響企業(yè)效益的重要因素。企業(yè)資源的合理配置和優(yōu)化利用很大程度上體現(xiàn)在車間一層的生產(chǎn)活動中，所以加強車間層的生產(chǎn)計劃與控制一直在企業(yè)生產(chǎn)經(jīng)營活動中占有十分重要的地位。</p><p>　　車間生產(chǎn)調(diào)度是制造系統(tǒng)生產(chǎn)管理的核心，是生產(chǎn)管理和控制系統(tǒng)實現(xiàn)管理技術(shù)、運籌技術(shù)、優(yōu)化技術(shù)和自動化技術(shù)發(fā)展的核心。及時準確的生產(chǎn)調(diào)度對生產(chǎn)系統(tǒng)的高效運行有著重要的影響

43、。生產(chǎn)管理任務(wù)能否順利的實施與完成，最終要靠合理的生產(chǎn)調(diào)度來保證有效。</p><p>　　實用的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用己成為先進制造技術(shù)實踐的基礎(chǔ)。因此，研究生產(chǎn)調(diào)度問題，不僅具有較大的理論意義，而且具有相當大的實用價值。一方面，生產(chǎn)調(diào)度問題的研究不僅可以推動相關(guān)算法的研究，如遺傳算法、神經(jīng)網(wǎng)絡(luò)、人工智能等，而且還能在此基礎(chǔ)上提出新的算法，這為其他領(lǐng)域類似問題的解決提供了條件和手段；另一方面，一個好的生

44、產(chǎn)調(diào)度方案不僅可以降低生產(chǎn)成本，而且可以提高企業(yè)產(chǎn)品的準時交貨能力，從而增強企業(yè)的競爭力。</p><p>　　隨著科學技術(shù)的發(fā)展，制造行業(yè)的生產(chǎn)規(guī)模變得越來越大，產(chǎn)品越來越多樣化，車間生產(chǎn)情況的復雜性也越來越高。同時，由于加工系統(tǒng)的復雜性和多樣性，目前還沒有一種通用的、全面的方法解決各種生產(chǎn)方式的優(yōu)化調(diào)度問題。制造企業(yè)迫切希望能有一個結(jié)合其自身特點的實用而有效的調(diào)度支持系統(tǒng)，這就需要根據(jù)企業(yè)的實際狀況和生產(chǎn)變化

45、，從以獲得工程滿意解的實際需求出發(fā)，選取調(diào)度目標，應(yīng)用能滿足要求的快速有效的優(yōu)化算法，滿足企業(yè)的實際需求，實現(xiàn)優(yōu)化調(diào)度。</p><p><b>　　1.4 本文的工作</b></p><p>　　第一章 緒論，從課題的研究背景到車間調(diào)度的國內(nèi)外的研究現(xiàn)狀再到車間調(diào)度存在的問題及解決途徑來引出遺傳算法對車間調(diào)度問題研究的重要性。描述了車間調(diào)度問題。進而描述了關(guān)于車間

46、調(diào)度的較常見的幾種研究方法及它們的應(yīng)用領(lǐng)域。</p><p>　　第二章 車間調(diào)度問題綜述，先介紹車間調(diào)度問題其中包括車間調(diào)度問題的描述、特點、分類、job shop與flow shop 比較然后追尋調(diào)度問題研究方法(數(shù)學規(guī)劃法、近似算法、智能搜索算法、模擬退火方法、Multi-agent方法、模糊邏輯、螞蟻調(diào)度算法、神經(jīng)元算法)，從而找到一些解決這些問題的辦法。</p><p>　　第

47、三章 遺傳算法，先介紹遺傳算法的形成與發(fā)展，然后再介紹遺傳算法的基本思想和特點，闡述一下遺傳算法的過程和流程，最后求解調(diào)度問題的遺傳算法其中包括遺傳算法的設(shè)計步驟、編碼方式適配值函數(shù)、遺傳算子的設(shè)計、編碼參數(shù)、遺傳算子和算法的終止條件。</p><p>　　第四章 基于遺傳算法的流水車間調(diào)度問題，首先介紹流水車間的背景，然后對流水車間調(diào)度問題進行描述與建立數(shù)學模型，進行遺傳算法的設(shè)計其中包括編碼方案、群體確定

48、、適應(yīng)度函數(shù)、遺傳算子的設(shè)計，并且進行了仿真。</p><p>　　第二章 車間調(diào)度問題</p><p>　　2.1. 車間調(diào)度問題的描述</p><p>　　生產(chǎn)調(diào)度通常是生產(chǎn)過程的作業(yè)計劃， 例如某機器上工件的加工順序，以及要加工點的工件如何劃分批次。從本質(zhì)上分，調(diào)度問題可以為開環(huán)調(diào)度和閉環(huán)調(diào)度。所謂開環(huán)調(diào)度是指研究工件加工的順序，所有的客戶訂購的產(chǎn)品，在機器

49、上排序生產(chǎn)，不考慮其他的因素，閉環(huán)調(diào)度是指，除了考慮工件的加工順序之外，還要考慮產(chǎn)品批次的大小等。顯然閉環(huán)調(diào)度的復雜性遠遠大于開環(huán)調(diào)度的復雜性，目前對閉環(huán)調(diào)度的處理通常使用近似方法，首先確定批量大小，然后再確定加工順序。</p><p>　　生產(chǎn)調(diào)度的問題基本上可以概述為：對于某一項可分解生產(chǎn)任務(wù)，在特定的約束條件下，分派生產(chǎn)所需要的資源，安排子任務(wù)的生產(chǎn)時間，并對子任務(wù)進行排序，目標是產(chǎn)品的最短的制造時間，或者

50、最低產(chǎn)品成本。其中生產(chǎn)所需要的資源主要包括：人力資源、資金、生產(chǎn)原料、生產(chǎn)設(shè)備等，評價目標好的的指標一般有：產(chǎn)品的生產(chǎn)周期短，總成本低和生產(chǎn)設(shè)備利用率低等。</p><p>　　生產(chǎn)調(diào)度的形式可以描述為：n個工件，m臺機器加工，每一個工件需要在m臺中的一臺或者多臺加工，假設(shè)第i個工件，在第j臺機上加工加工時間為Pij，加工操作位Oij沒一個工件的準備時間為Rij，工件的交貨期為Dij，交貨期是指必須在規(guī)定的時間內(nèi)

51、交貨，每一個工件有相應(yīng)的工藝流程，工件按照工藝的約束在機器上按順序加工。所謂調(diào)度可以看做是，在一定的約束條件下工件如何分配到機器上加工，本質(zhì)上來說調(diào)度就是將工件在機器上排序，其要符合以下兩點要求：</p><p>　　1.符合產(chǎn)品工藝上的約束（可行調(diào)度）；</p><p>　　2.對應(yīng)的執(zhí)行的目標調(diào)度是最優(yōu)的；</p><p>　　生產(chǎn)調(diào)度問題是一類復雜的問題，研究

52、難度非常大，給學者的研究帶來了不小的困難，當前生產(chǎn)調(diào)度的研究還有很多問題沒有解決，很多實際的生產(chǎn)調(diào)度還停留在理論層次，大部分生產(chǎn)調(diào)度的算法研究只做了一些簡單的假設(shè)，過于簡單，與實際的生產(chǎn)差距較大。目前很多企業(yè)的調(diào)度還是靠人工完成，耗費了大量的人力物力，不利于企業(yè)成本的控制。</p><p>　　2.2 車間調(diào)度問題的特點</p><p>　　車間調(diào)度的基本特點是：建模的復雜性，計算的復雜性

53、，動態(tài)的隨機性，多約束性，多目標性。</p><p>　　1.復雜性：車間中工件、機器、緩存和搬運系統(tǒng)之間相互影響、相互作用。每個工件要考慮它的加工時間、安裝時間和操作順序等因素，因而相當復雜。調(diào)度問題是在等式或不等式約束下求指標的優(yōu)化，在計算量上往往是具有NP特性，隨著問題規(guī)模的增大，其計算量急劇增加，使得一些常規(guī)的方法無能為力，對于這一點已經(jīng)證明。</p><p>　　2.隨機性：在實

54、際的作業(yè)車間調(diào)度系統(tǒng)中存在很多隨機的和不確定的因素，環(huán)境是不斷變化的，在運行過程中會遇到多種隨機干擾，比如工件到達時間的不確定性、作業(yè)的加工時間也有一定的隨機性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)偶然事件，如設(shè)備的損壞、修復、作業(yè)交貨期的改變等，故作業(yè)車間調(diào)度過程是一個動態(tài)的隨機過程。</p><p>　　3.多約束性：車間調(diào)度問題中資源的數(shù)量、緩存的容量、工件加工時間以及工件的操作順序等都是約束。此外還有一些人為的因

55、素，如要求各機器上的負荷要平衡等。</p><p>　　4.多目標性：實際的車間調(diào)度問題是多目標的，而且這些目標之間往往是發(fā)生沖突的。調(diào)度目標分為三類：基于作業(yè)交貨期的目標、基于作業(yè)完成時間的目標和基于生產(chǎn)成本的目標。</p><p>　　2.3 車間調(diào)度問題的分類</p><p>　　車間調(diào)度問題的分類，根據(jù)研究的側(cè)重點不同有多種分類方式。</p>

56、<p>　　1．按照資源約束種類和數(shù)量劃分：</p><p>　　(1) 單資源車間調(diào)度(single resource constrained)：只有一種資源制約著車間力。</p><p>　　(2) 雙資源車間調(diào)度(dual resource constrained)：同時有兩種資源制約著車間力。機床設(shè)備往往是制約資源之一，車間有時會缺乏有經(jīng)驗或一技之長的工人，也有可能某種

57、類型的刀具數(shù)量有限，因此這兩種資源可以是機床設(shè)備和工人或刀具。</p><p>　　(3) 多資源車間調(diào)度(multiple resource constrained)：同時有兩種以上的生產(chǎn)所制約著車間的生產(chǎn)能力。這些資源包括員工、機床設(shè)備、機器人、物料運送系統(tǒng)和輔助資源，如貨盤、夾具和刀具等。</p><p>　　單資源車間調(diào)度是雙資源車間調(diào)度的特例，雙資源車間調(diào)度又是多資源車間調(diào)度的特

58、例。所以多資源車間調(diào)度問題是最復雜的一種。</p><p>　　2．按照零件和車間的構(gòu)成劃分：</p><p>　　(1) 流水車間調(diào)度(Flow shop)：在這種車間中，每個零件都有相同的加工路徑。這樣，機床設(shè)備的布局如同流水線一樣，零件一次從流水線的一端進入，最后從另一端流出。</p><p>　　(2) 作業(yè)車間調(diào)度(Job shop)：在這種車間中，機床設(shè)

59、備的布局可以是任意的，因此零件的加工路徑也是任意的，并且各零件的工序內(nèi)容和數(shù)量也是任意的。這是一種最一般的車間調(diào)度形式。</p><p>　　(3) 開放式車間調(diào)度(Open shop)：每個零件的工序之間的加工次序是任意的。零件的加工可以從任何一道工序開始，在任何一道工序結(jié)束。</p><p>　　(4) 單車間調(diào)度(Single shop)：在這種車間中，每個零件只能有一道工序。<

60、;/p><p>　　3．按照零件的加工特點劃分：</p><p>　　(1) 靜態(tài)車間調(diào)度(Static scheduling)：所有的零件在開始調(diào)度時刻已經(jīng)準備間的調(diào)度不考慮零件在加工過程中出現(xiàn)的意外情況，如機床突然損壞、零件的交貨期提前、有更緊迫的零件要求被加工等等。</p><p>　　(2) 動態(tài)車間調(diào)度(Dynamic scheduling)：車間的調(diào)度要求考

61、慮零件在加工的各種意外情況。這種調(diào)度方式要求調(diào)度能隨時相應(yīng)車間能力的變化，在有突發(fā)事件出現(xiàn)后，能立即根據(jù)當時的車間加工能力，對待加工的零件重新展開調(diào)度，以確保在任何時候，都能保持車間的加工性能指標處于最優(yōu)或次優(yōu)狀態(tài)。</p><p>　　2.4 Job Shop 與Flow shop 比較</p><p>　　1.Job Shop 與Flow shop的共性</p><

62、;p>　　Job Shop 與Flow shop調(diào)度問題是目前調(diào)度問題的兩大類型，其目標均是通過科學的調(diào)度，使車間調(diào)度問題最優(yōu)化?；炯s束條件均為：</p><p>　　(1) 同一時刻同一臺機器只能加工一個零件；</p><p>　　(2) 每個工件在某一時候只能在一臺機器上加工，不能中途中斷每一個操作；</p><p>　　(3) 同一個工件的工序之間有先

63、后約束，不同工件的工序之間沒有先后約束；</p><p>　　(4) 不同工件具有相同的優(yōu)先級。</p><p>　　2、Job Shop 與Flow shop的個性</p><p>　　對于上述約束條件，當增加約束條件：每臺機器只有單一加工功能，且各工件中的任意一個工序只能在所有機器中的一臺機器上操作且各工件的技術(shù)約束條件（加工方法、加工時間、加工設(shè)備、加工順序等

64、）相同時，該問題則轉(zhuǎn)化為Flow Shop問題；當增加約束條件：每臺機器只有單一加工功能，各工件中的任意一個工序只能在所有機器中的一臺機器上操作時，該問題轉(zhuǎn)化為Job Shop問題。</p><p>　　Flow shop型問題假設(shè)所有作業(yè)都在同樣的設(shè)備上加工，并有一致的加工操作和加工順序；Job shop是最一般的調(diào)度類型，不同的作業(yè)具有不同的加工操作和加工順序，并不限制作業(yè)的加工設(shè)備?，F(xiàn)代車間調(diào)度類型往往是

65、job shop型的，本文的研究就是針對 job shop型的調(diào)度問題展開。</p><p>　　2.5 調(diào)度問題的研究方法</p><p>　　生產(chǎn)調(diào)度問題的研究最初集中在整數(shù)規(guī)劃、仿真和簡單的規(guī)劃等方法上，這些方法不是調(diào)度結(jié)果不理想，就是難以解決復雜的問題。 隨著機器數(shù)和工件數(shù)的增加，調(diào)度方案呈指數(shù)增長，怎樣才能盡快地得到最優(yōu)調(diào)度方案，這一問題吸引了國內(nèi)外許多學者和實際生產(chǎn)調(diào)度人員的關(guān)

66、注，提出了很多的解決方法。近年來，在生產(chǎn)調(diào)度領(lǐng)域出現(xiàn)了許多新的優(yōu)化方法，比如神經(jīng)網(wǎng)絡(luò)法、模擬退火法、遺傳算法等，使得生產(chǎn)調(diào)度問題的研究方法走向了多元化。</p><p>　　1．精確算法一數(shù)學規(guī)劃法</p><p>　　數(shù)學規(guī)劃法主要是通過對車間調(diào)度問題建立一個整數(shù)規(guī)劃模型，采用枚舉方法尋求調(diào)度問題的最優(yōu)解。數(shù)學規(guī)劃方法往往采用基于枚舉思想的分枝定界法或動態(tài)規(guī)劃算法進行求解。分枝定界法基本

67、思想是先求出對調(diào)度整數(shù)規(guī)劃模型所對應(yīng)的線性規(guī)劃問題的最優(yōu)解，如果解不能滿足調(diào)度問題的整數(shù)條件，則對應(yīng)的線性規(guī)劃問題的最優(yōu)解必是調(diào)度問題的目標函數(shù)值的上界，而調(diào)度問題的任意可行解的目標函數(shù)值則是其最優(yōu)解的下界，然后將對應(yīng)的線性規(guī)劃問題的可行域分成子域，通過不斷減少上界和增大下界，最終尋找到最優(yōu)解。分枝定界法的實現(xiàn)方法是動態(tài)構(gòu)造一個表示調(diào)度問題所有可行解的樹，通過對樹的搜索尋找調(diào)度問題的最優(yōu)解。分枝定界法只適合于小規(guī)模的調(diào)度問題，并且對實際

68、問題比較敏感，因此限制了它在調(diào)度問題上的應(yīng)用。動態(tài)規(guī)劃方法的優(yōu)點是任務(wù)分配和排序的全局性比較好，所有的選擇同時進行，因此可以保證求解問題的全局優(yōu)化。但是，動態(tài)規(guī)劃方法是一種精確求解方法，它需要對調(diào)度問題進行統(tǒng)一的建模，任何參數(shù)的變化會使得算法的重用性很差，因此，對于復雜多變的生產(chǎn)調(diào)度來說，單一的數(shù)學規(guī)劃模型不能覆蓋所有的因素，存在求解空間大和計算困難等問題。</p><p><b>　　2．近似算法&l

69、t;/b></p><p>　　由于數(shù)學規(guī)劃法的局限性，從20世紀70年代開始出現(xiàn)了啟發(fā)式算法，這些算法基本上是在一些信息和規(guī)則的啟發(fā)下進行推理和計算，從而獲得調(diào)度問題的近似最優(yōu)解。啟發(fā)式搜索方法的優(yōu)點是利用了面向特定問題的知識和經(jīng)驗，因而可以產(chǎn)生好的解決方案，求解時間也可以接受。而對于如何提高搜索效率并減少內(nèi)存使用以解決規(guī)模較大的問題，還需要進一步探索。啟發(fā)式算法主要有：</p><p

70、>　　(1) 基于啟發(fā)式規(guī)則的調(diào)度算法</p><p>　　啟發(fā)式規(guī)則的調(diào)度算法也稱調(diào)度規(guī)則，是最早的近似算法。其本質(zhì)是給每一個生產(chǎn)任務(wù)和操作賦予優(yōu)先級，優(yōu)先級高的生產(chǎn)任務(wù)和操作優(yōu)先考慮。由于其具有簡單、易于實現(xiàn)、計算復雜度低的特點，調(diào)度規(guī)則在調(diào)度問題上得到廣泛的應(yīng)用，同時不斷有新的調(diào)度規(guī)則產(chǎn)生。Panwalkar等人總結(jié)了113條規(guī)則，并將它們分為三類：簡單規(guī)則、復合規(guī)則、式規(guī)則，其中屬于簡單規(guī)則有30多

71、條，如先進先出、最短加工時間、交付期最早等經(jīng)常使用的規(guī)則，其它規(guī)則基本上是簡單規(guī)則的組合或加權(quán)組合；另外，調(diào)度規(guī)則經(jīng)過適當?shù)慕M合和變形后，往往可以得到很好的調(diào)度效果。調(diào)度規(guī)則的缺點在于其精確度不夠高。隨著計算機運算速度的飛速提高，人們希望尋找新的近似調(diào)度方法，以合理的額外計算時間代價，換得比單純啟發(fā)式規(guī)則所得到的調(diào)度更好的調(diào)度。</p><p>　　(2) 啟發(fā)式圖搜索法</p><p>

72、　　啟發(fā)式圖搜索法主要有寬度優(yōu)先、深度優(yōu)先、Beam搜索及A或者A}算法等。啟發(fā)式圖搜索法的缺點在于計算復雜度較高，如A*算法的計算復雜度為D(2n-1)(n為搜索圖中結(jié)點數(shù))，在調(diào)度問題的離散圖中結(jié)點數(shù)為nxm。對于此類方法如何提高搜索效率、減少內(nèi)存使用，以能解決比較大的規(guī)模的問題，還需要進一步探索。</p><p>　　(3) 拉格朗日松弛算法</p><p>　　LR算法由于其在可行

73、的時間里能對復雜的規(guī)劃問題提供較好的最優(yōu)解，并能對解的最優(yōu)性進行定量評估，近年來已成為解決復雜生產(chǎn)調(diào)度問題的重要方法。但不可避免的是，LR算法存在搜索效率低，可行調(diào)度的構(gòu)造有待于進一步研究等問題。</p><p><b>　　3．智能搜索算法</b></p><p>　　計算智能是通過神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)、進化計算的有機融合而形成的新的科學方法，也是智能理論和技術(shù)發(fā)展的

74、嶄新階段。</p><p><b>　　(1) 遺傳算法</b></p><p>　　遺傳算法(genetic algorithm簡稱GA)是一種嶄新的并行優(yōu)化搜索方法。它是模仿物群體進化過程的一種優(yōu)化算法，給定一組初始解作為一個群體，通過選擇、交叉和變異等遺傳操作來搜索最優(yōu)解。遺傳算法對求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并根據(jù)適應(yīng)

75、性進行選擇，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機會，經(jīng)過反復迭代，直到達到某種形式的收斂。遺傳算法尤其適用于處理傳統(tǒng)搜索方法難以解決的復雜的非線性問題，可廣泛用于組合優(yōu)化、機器學習和規(guī)劃設(shè)計等領(lǐng)域。</p><p>　　遺傳算法已經(jīng)成為一種比較通用的優(yōu)化算法，主要原因是編碼技術(shù)和遺傳操作比較簡單，優(yōu)化不受限制性條件的約束。但遺傳算法也有明顯的不足之處：對于大規(guī)模的組合優(yōu)化問題，由于搜索空間大，搜索時

76、間較長，往往會出現(xiàn)早熟收斂的情況；對初始種群很敏感，初始種群選擇不好會影響解的質(zhì)量和算法效率。為了進一步改進遺傳算法，人們主要從兩方面入手：一是對遺傳算法本身進行改進；二是與其它算法結(jié)合，取長補短。</p><p>　　(2) 禁忌搜索算法</p><p>　　對于復雜的組合優(yōu)化問題，禁忌搜索也是一種通過鄰域搜索以獲取最優(yōu)解的方法。算法的基本過程如下：它從一個可行解S出發(fā)，產(chǎn)生的領(lǐng)域，如果

77、F為目標函數(shù)，選取所有領(lǐng)域中使F(si)為最優(yōu)的狀態(tài)作為下一個狀態(tài)，并把這一移動的反向移動存入一個稱為禁忌移動(Ta bu Move)的表中。列在表中的移動在以后若干步內(nèi)不允許再產(chǎn)生，這樣可免搜索退回去。每搜索一次，更新一次禁忌移動表。由于禁忌移動表的限制，有可能跳出局部極小，從而提高了算法的運行效率。可見，禁忌搜索算法的基本要素是初始解、移動、鄰域和禁忌表。禁忌搜索算法沒有自然性的終止條件，對求解的問題，目標函數(shù)和搜索空間沒有任何特殊

78、的要求，計算速度較快。因此，它在調(diào)度問題上有著廣泛的應(yīng)用前景。</p><p>　　(3) 人工神經(jīng)網(wǎng)絡(luò)</p><p>　　“人工神經(jīng)網(wǎng)絡(luò)"是一種模擬人腦神經(jīng)系統(tǒng)的結(jié)構(gòu)和功能，運用大量的處理部件經(jīng)廣泛互連而組成的網(wǎng)絡(luò)系統(tǒng)。Hop field應(yīng)用神經(jīng)網(wǎng)絡(luò)方法求解旅行商問題獲得成功，從而為組合優(yōu)化問題求解開辟了新的途徑。人工神經(jīng)網(wǎng)絡(luò)的優(yōu)點是：具有很強的分布式存儲能力和很大的存儲空間

79、，具有自學習能力，再者容錯性好，特有的高維空間使多體效應(yīng)更加復雜和顯著，易于分類。但是，人工神經(jīng)網(wǎng)絡(luò)在實際生產(chǎn)中的應(yīng)用不是很多，而且存在學習效率比較差、難以表達符號知識、計算速度比較慢和精度低等缺點，這些都需要進一步改進。特別是對于求解大規(guī)模問題有一定難度。目前，神經(jīng)網(wǎng)絡(luò)優(yōu)化應(yīng)用于生產(chǎn)調(diào)度中，主要有三種方式：一是利用其并行計算能力，求解優(yōu)化調(diào)度；二是利用其自學習能力，從優(yōu)化軌跡中提取調(diào)度知識；三是用神經(jīng)網(wǎng)絡(luò)來描述調(diào)度約束或調(diào)度策略，以實

80、現(xiàn)對生產(chǎn)過程的可行或次優(yōu)調(diào)度。</p><p>　　(4) 模擬退火方法</p><p>　　模擬退火算法(SA)來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f,溫度T演化成控制參數(shù)t，即得到解組

81、合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解一計算目標函數(shù)差一接受或舍棄一的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程．模擬退火方法已經(jīng)應(yīng)用到許多領(lǐng)域。模擬退火算法顯示出了求解優(yōu)化問題的強大威力，它可以突破局域搜索的限制，轉(zhuǎn)移到代價較高的解答，而且如果選擇參數(shù)得當，會在很快的時間內(nèi)收斂。但是，模擬退火算法在實際應(yīng)用中往往不能產(chǎn)生較優(yōu)的

82、結(jié)果，而且各個參數(shù)選擇起來比較困難，如果選擇不得當，就會使得計算時間很長，而且可能得不到好的結(jié)果，模擬退火算法和其它算法結(jié)合使用會得到很好的效果，如和遺傳算法、人工神經(jīng)網(wǎng)絡(luò)結(jié)合等。</p><p>　　(5) Multi-agent方法</p><p>　　多代理通過一系列分散的智能單元(Agent)間進行協(xié)調(diào)來解決問題，這些單元有各的目標和自治的行為，并且可以有子單元，但是沒有一個單元能

83、夠解決全局問題，因而它們之間必須進行協(xié)調(diào)。每個Agent至少應(yīng)有以下三個組成部分：</p><p>　　1).知識庫。包含Agent執(zhí)行其功能所必需的知識和數(shù)據(jù)。</p><p>　　2).控制功能。根據(jù)環(huán)境狀態(tài)及與其它Agent間的相互作用，從知識庫中提取知識來完成調(diào)度功能。</p><p>　　3).通訊功能。用來與其它Agent和環(huán)境之間進行信息傳遞。<

84、/p><p>　　Multi-agent特別適合解決復雜問題，尤其是那些經(jīng)典方法無法解決的單元間有大互作用的問題。</p><p><b>　　(6) 模糊邏輯</b></p><p>　　1965年，美國控制論專家Zadeh教授首先提出模糊集合的概念，發(fā)表了開創(chuàng)性論文糊集合論。他提出模糊數(shù)學的核心思想就是運用數(shù)學手段，仿效人腦思維，對復雜事物進行

85、模糊處理。1973年，Zadeh教授又提出模糊邏輯的理論，并積極倡導將模糊理人工智能方向發(fā)展。模糊集理論對于建模和求解車間調(diào)度問題是非常有用的，因為它就具有許多模糊特征，比如不確定的加工次數(shù)、不確定的約束數(shù)量以及不確定的加工時間等</p><p>　　(7) 螞蟻調(diào)度算法</p><p>　　螞蟻選擇路徑的原則是依據(jù)信息素隨機選擇，即信息素多的路徑被選擇的可能性較大，若有一只螞蟻隨機地選擇

86、了最短或較短的路徑，那么，它能較早地回來并在該路徑上留下信息素。在一定時間內(nèi)，這條路徑上就有較多的信息素，從而吸引其它螞蟻也選擇這條路徑。由于它們會較早地留下信息素，最短路徑上的信息素量就會越來越多，這種正反饋使得該路徑的吸引力會越來越強，另一方面，信息素隨時間揮發(fā)，較長的路徑由于信息素難以得到加強，信息素的量會越來越少，最終被完全廢棄。螞蟻在選擇路徑的過程中，留下信息素來表示自己的“試錯一結(jié)果；利用環(huán)境實現(xiàn)非直接通信，使得群體能區(qū)分不

87、同解的優(yōu)劣；利用隨機選擇特性，使得整個蟻群能夠跳出局部最優(yōu)；利用信息素的揮發(fā)特性來淘汰劣質(zhì)解。</p><p><b>　　(8) 神經(jīng)元算法</b></p><p>　　人工神經(jīng)元網(wǎng)絡(luò)的早期研究始于二十世紀四十年代，以1943年美國生理學家W.S．McCullocn和數(shù)學家W.A．Pitts提出的二值神經(jīng)元模型為代表。人工神經(jīng)網(wǎng)絡(luò)的用人工神經(jīng)元相互連接組成一個計算網(wǎng)

88、絡(luò)，并行高效地求解問題。它的主要特點是能夠?qū)W習，通過給網(wǎng)絡(luò)提供一定的訓練樣本，然后根據(jù)網(wǎng)絡(luò)的實際輸出與希望輸出之間的偏差，利用某種方法逐步修改各人工神經(jīng)元之間的連接權(quán)，形成求解某些問題的能力。從二十世紀八十年代末期開始，人工神經(jīng)網(wǎng)絡(luò)被用來求解調(diào)度問題。它的主要缺點是效率受訓練影響很大，并且在問題規(guī)模較大時，計算速度慢，結(jié)構(gòu)參數(shù)難以確定。</p><p>　　2.6 兩機無等待流水車間調(diào)度</p>&

89、lt;p>　　無等待流水車間（no-wait flow shop，NWFS）調(diào)度問題是一類十分重要的調(diào)度問題，它廣泛存在于煉鋼、食品加工、化工和制藥等領(lǐng)域。已經(jīng)證明機床數(shù)量大于2的NWFS是強NP難題。NWFS可描述為：給定m臺機床和n個工件，所有工件在各機床上的加工順序均相同。同時約定，一個工件在某一時刻只能夠在一臺機床上加工，一臺機床在某一時刻只能夠加工一個工件。由于技術(shù)條件的限制，同一工件的加工必須連續(xù)完成，即同一工件的相鄰

90、工序之間沒有等待時間。各工序的加工時間已知。問題是如何安排生產(chǎn)，在滿足上述要求的條件下得到最小生產(chǎn)周期。</p><p>　　2.6.1生產(chǎn)周期的計算</p><p>　　由于同一工件的工序必須連續(xù)生產(chǎn)的限制，計算NWFS的生產(chǎn)周期不同于一般流水車間調(diào)度問題。文獻[3]給出了NWFS生產(chǎn)周期的計算公式：令為工件i在機床k上的加工時間，為一個調(diào)度，為相鄰兩工件i-1和i的開工時間之差（如圖1

91、-1)所示）；則為</p><p>　　圖1-1 兩工件的NWFS調(diào)度和流水車間調(diào)度</p><p><b>　　的生產(chǎn)周期為</b></p><p>　　上述和的算法復雜度分別為O(m2)、O(nm2)。</p><p>　　2.6.2生產(chǎn)周期的快速算法</p><p>　　結(jié)合問題特征，可簡化

92、的計算。如圖1所示，兩個工件的NWFS和流水車間調(diào)度問題有相同的生產(chǎn)周期。因此，可先按照流水車間調(diào)度問題求得生產(chǎn)周期，再根據(jù)連續(xù)生產(chǎn)的要求從后向前依次求得NWFS的各工序開工時間，進而得到。令、分別為工序的開工、完工時間，求的算法如下：</p><p>　　，；令y從2到m，分別計算，</p><p>　　，；令y從2到m，分別計算，。</p><p>　　令y從m

93、-1到1，分別調(diào)整，。</p><p>　　上述算法的復雜度為O(m)。若將得到的代入式（2），容易求得生產(chǎn)周期，其復雜度為O(nm)。因為共有個，為了提高算法效率，可預先求出所有。這樣，在計算生產(chǎn)周期時，就可視為常數(shù)。同樣，可看作常數(shù)。于是，式（2）的復雜度就可降低為O(n)。</p><p><b>　　第三章 遺傳算法</b></p><p&

94、gt;　　3.1 遺傳算法的形成與發(fā)展</p><p>　　遺傳算法起源于對生物系統(tǒng)所進行的計算機模擬研究。早在本世紀40年代，就有學者開始研究如何利用計算機進行生物模擬的技術(shù)。進入60年代后，美國Michigan大學的Holland教授受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進化機制的適合于復雜系統(tǒng)優(yōu)化計算的自適應(yīng)概率優(yōu)化技術(shù)——遺傳算法。70年代初，Holland提出了遺傳算法的基本定理——模式

95、定理（Schema Theorem），從而奠定了遺傳算法的理論基礎(chǔ)。1975年，Holland出版了其開創(chuàng)性的著作《自然和人工系統(tǒng)中的自適應(yīng)性（Adaptation in Natural and Artificial Systems）》。</p><p>　　同年，De Jong基于遺傳算法的思想在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，他推薦了在大多數(shù)優(yōu)化問題中都較適用的遺傳算法的參數(shù)，還定義了評價遺傳算法

96、性能的在線指標和離線指標。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進行歸納總結(jié)，出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法（Genetic Algorithms in Search,Optimization and Machine Learning）》,從而形成了遺傳算法的基本框架。</p><p>　　1991年，Davis編輯出版了《遺傳算法手冊（Handbook of Genetic Algo

97、rithms）》一書，此書為推廣和普及遺傳算法的應(yīng)用起到了重要的指導作用。1992年，Koza將遺傳算法應(yīng)用于計算機程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程（Genetic Programming，簡稱GP）的概念。</p><p>　　正是由于80年代中期，遺傳算法研究的蓬勃發(fā)展，吸引了大批的科學研究者和工程技術(shù)人員從事該領(lǐng)域的研究和開發(fā)應(yīng)用工作。</p><p>　　盡管遺傳算法本身在

98、理論和應(yīng)用方法上仍有許多待進一步研究的問題，但它的應(yīng)用非常廣泛，尤其適合于處理傳統(tǒng)搜索方法難以解決的高度復雜的非線性問題。它在在函數(shù)優(yōu)化、組合優(yōu)化問題求解、生產(chǎn)調(diào)度問題、自動控制、模式識別、信息處理、規(guī)劃設(shè)計、機器學習、圖像處理、機器人學、人工生命、遺傳編程等領(lǐng)域的應(yīng)用中已展現(xiàn)出其優(yōu)越性和魅力，從而也確定了它在21世紀的智能計算機技術(shù)的關(guān)鍵地位。</p><p>　　3.2 遺傳算法的基本思想</p>

99、<p>　　遺傳算法和傳統(tǒng)的搜索算法不同，它從一組隨機產(chǎn)生的初始解，稱為“種群(Population)”開始搜索過程。種群中的每個個體是問題的一個解，稱為“染色體(Chromosome)”。在遺傳算法中最重要的概念是染色體，染色體通常是一串數(shù)據(jù)(或數(shù)組)，用來作為優(yōu)化問題的解的代碼，其本身不一定是解.這些染色體在后續(xù)迭代中不斷進化，稱為遺傳。在每一代中用“適應(yīng)值(Fitness)”來測量染色體的好壞。生成的下一代染色體稱為

100、后代(Oring)。后代是由前一代染色體通過交叉(Crossover)或者變異(Mutation)運算形成的。新一代形成中，根據(jù)適應(yīng)值的大小選擇部分后代，淘汰部分后代，從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高。據(jù)此，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解</p><p>　　遺傳算法的基本步驟是：</p><p>　　1.確定問題的編碼方案。

101、由于GA通常不直接作用于問題的解空間，而是利用解的某種編碼表示來進行進化，因此選擇合理的編碼機制對算法質(zhì)量和效率有很大影響。</p><p>　　2.確定適應(yīng)度函數(shù)。由于GA通?；谶m應(yīng)度進行遺傳操作，因此合理的適應(yīng)度能夠?qū)⒏鱾€體的優(yōu)劣程度得以體現(xiàn)，并適應(yīng)算法的進化過程。</p><p>　　3.算法參數(shù)的選取。通常包括種群數(shù)目、交叉概率、變異概率、進化代數(shù)等。</p>&l

102、t;p>　　4.遺傳算子的設(shè)計。通常包括初始化、選擇、交叉、變異和替換操作等。</p><p>　　5.確定算法的終止條件。終止準則應(yīng)根據(jù)所求解問題的性質(zhì)，在優(yōu)化質(zhì)量和效率方面作合理均衡或側(cè)重。</p><p>　　3.3 遺傳算法的特點</p><p>　　遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法

103、是基于一個單一的度量函數(shù)(評估函數(shù))的梯度或較高次統(tǒng)計，以產(chǎn)生一個確定性的試驗解序列，遺傳算法不依賴于梯度信息，而是通過模擬自然進化過程來搜索最優(yōu)解，它利用某種編碼技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進化過程。遺傳算法通過有組織地、隨機地信息交換來重新組合那些適應(yīng)性好的串，生成新的串的群體。遺傳算法的特點有以下幾點：</p><p>　　1.自組織、自適應(yīng)和自學習性(智能性)。應(yīng)用遺傳算法求解

104、問題時，在編碼方式、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略為“適者生存，不適者被淘汰”，因而適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，再通過基因重組和基因突變等操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。進化算法的這種自組織、自適應(yīng)特征，使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特征和規(guī)律的能力。自然選擇消除了算法設(shè)計過程中的一個最大的障礙，即需要事先描述問題的全部特點，并要說明針對問題的不同

105、特點算法應(yīng)采取的措施。因此，利用遺傳算法的方法，我們可以解決那些復雜的非結(jié)構(gòu)化問題。</p><p>　　2.并行搜索特性。遺傳算法按并行方式搜索一個種群數(shù)目的所有點，而不是單點。它的并行性表現(xiàn)在兩個方面，一是遺傳算法是內(nèi)在并行的(inherent Parallelism)，即遺傳算法本身非常適合大規(guī)模并行搜索操作。最簡單的并行方式是讓幾百甚至數(shù)千臺計算機各自進行獨立種群的演化計算，運行過程中甚至不進行任何通信(

106、獨立的種群之間若有少量的通信一般會帶來更好的結(jié)果)，等到運算結(jié)束時才通過比較、選擇最佳個體。這種并行處理方式對并行系統(tǒng)結(jié)構(gòu)沒有什么限制和要求，可以說，遺傳算法適合在目前所有的并行機或分布式系統(tǒng)上進行并行處理，而且對并行效率沒有太大影響。二是遺傳算法的內(nèi)含并行(implicitparallelism)。由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內(nèi)的多個區(qū)域，并相互交流信息。使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模n成比例的