基于基因遺傳算法flow_shop調(diào)度問(wèn)題研究與分析學(xué)士學(xué)位論文

1、<p><b>　　摘 要</b></p><p>　　流水車間(Flow Shop)調(diào)度問(wèn)題無(wú)論是在工廠經(jīng)營(yíng)管理還是在產(chǎn)品制造中都具有廣泛的應(yīng)用，因此對(duì)流水車間調(diào)度問(wèn)題進(jìn)行研究具有重大的理論意義和實(shí)際意義。</p><p>　　本文首先對(duì)車間調(diào)度問(wèn)題國(guó)內(nèi)外研究現(xiàn)狀和發(fā)展趨勢(shì)進(jìn)行了系統(tǒng)的闡述。其次，對(duì)遺傳算法的基本理論進(jìn)行了詳細(xì)的論述。然后對(duì)Flow Sho

2、p調(diào)度問(wèn)題和具有跨工位的車間調(diào)度問(wèn)題建立數(shù)學(xué)模型。再次，在掌握了遺傳算法的基礎(chǔ)之上給出了基于遺傳算法求解Flow Shop調(diào)度問(wèn)題和跨工位車間調(diào)度問(wèn)題的編碼方案，遺傳算子的設(shè)計(jì)。然后，以生產(chǎn)周期最短為目標(biāo)，基于遺傳算法對(duì)上述兩種調(diào)度問(wèn)題進(jìn)行了實(shí)例分析，通過(guò)甘特圖給出了調(diào)度結(jié)果。最后對(duì)上述兩種調(diào)度的結(jié)果進(jìn)行了分析，結(jié)果表明本文提出的方法是有效可行的。</p><p>　　關(guān)鍵詞：生產(chǎn)調(diào)度；流水車間調(diào)度；遺傳算法；跨

3、工位操作 </p><p><b>　　Abstract</b></p><p>　　Flow shop scheduling problem (FSP) is widely used in the factory management and manufacturing, hence, there is great practical significance an

4、d theoretical value to study FSP.</p><p>　　Firstly, the current situation and development trend of domestic and foreign research about the shop scheduling problem is described. Secondly, the basic theory of

5、genetic algorithm is discussed in detail. Then the mathematical models are constructed for flow shop scheduling problem and multi-station shop scheduling problem. Again, the presented coding scheme and genetic operator a

6、re gived based on genetic algorithm to solve flow shop scheduling problems with multi-station. Then, in the producti</p><p>　　Keywords: Production scheduling; Flow shop; Genetic algorithm; multi-station oper

7、ations</p><p><b>　　目 錄</b></p><p><b>　　摘 要I</b></p><p>　　ABSTRACTII</p><p><b>　　1 緒 論1</b></p><p><b>　　1.1 引

8、言1</b></p><p>　　1.2 國(guó)內(nèi)外車間調(diào)度問(wèn)題的研究現(xiàn)狀和存在的問(wèn)題1</p><p>　　1.2.1 國(guó)內(nèi)外車間調(diào)度問(wèn)題的研究現(xiàn)狀1</p><p>　　1.2.2 研究中存在的問(wèn)題3</p><p>　　1.3 研究意義與目的3</p><p>　　1.4 本文的工作

9、4</p><p>　　2 車間調(diào)度問(wèn)題綜述6</p><p>　　2.1 車間調(diào)度問(wèn)題6</p><p>　　2.1.1 車間調(diào)度問(wèn)題的描述6</p><p>　　2.1.2 車間調(diào)度問(wèn)題的特點(diǎn)6</p><p>　　2.1.3 車間調(diào)度問(wèn)題的分類7</p><p>　　2

10、.1.4 Job Shop 與Flow shop 比較8</p><p>　　2.2 調(diào)度問(wèn)題的研究方法9</p><p>　　3 遺傳算法14</p><p>　　3.1 遺傳算法的形成與發(fā)展14</p><p>　　3.2 遺傳算法的基本思想14</p><p>　　3.3 遺傳算法的特點(diǎn)1

11、5</p><p>　　3.4 遺傳算法的過(guò)程和流程17</p><p>　　3.5 求解FSP調(diào)度問(wèn)題的遺傳算法19</p><p>　　3.5.1 遺傳算法的設(shè)計(jì)步驟19</p><p>　　3.5.2 編碼方式19</p><p>　　3.5.3 適配值函數(shù)21</p><

12、p>　　3.5.4 遺傳算子的設(shè)計(jì)22</p><p>　　3.5.5 編碼參數(shù)23</p><p>　　3.5.6 遺傳算子24</p><p>　　3.5.7 算法的終止條件24</p><p>　　4 基于遺傳算法的流水車間調(diào)度問(wèn)題25</p><p>　　4.1 流水車間調(diào)度問(wèn)題的描

13、述與數(shù)學(xué)模型25</p><p>　　4.2 遺傳算法的設(shè)計(jì)26</p><p>　　4.2.1 編碼方案26</p><p>　　4.2.2 群體的確定26</p><p>　　4.2.3 適應(yīng)度函數(shù)26</p><p>　　4.2.4 遺傳算子的設(shè)計(jì)26</p><p>

14、;　　4.3 基于遺傳算法的實(shí)例求解演示27</p><p>　　4.4 結(jié)果分析45</p><p>　　5 具有跨工位操作的車間調(diào)度問(wèn)題46</p><p>　　5.1 跨工位數(shù)學(xué)模型47</p><p>　　5.2 遺傳算法的設(shè)計(jì)48</p><p>　　5.2.1 編碼方案48</

15、p><p>　　5.2.2 群體的確定48</p><p>　　5.2.3 適應(yīng)度函數(shù)49</p><p>　　5.2.4 遺傳算子的設(shè)計(jì)49</p><p>　　5.3 實(shí)例描述50</p><p>　　5.4 結(jié)果分析68</p><p><b>　　結(jié) 論69&

16、lt;/b></p><p><b>　　致 謝70</b></p><p><b>　　參考文獻(xiàn)71</b></p><p><b>　　附錄A73</b></p><p><b>　　附錄B84</b></p><p&

17、gt;<b>　　1 緒 論</b></p><p><b>　　1.1 引言</b></p><p>　　近幾十年來(lái)，隨著科學(xué)技術(shù)的發(fā)展，各類生產(chǎn)過(guò)程已經(jīng)發(fā)生了顯著的變化，其主要的特征是生產(chǎn)規(guī)模的大型化和生成過(guò)程的連續(xù)化。在激烈的市場(chǎng)競(jìng)爭(zhēng)中，為了保證生產(chǎn)的高效穩(wěn)定運(yùn)行，已獲得最大的經(jīng)濟(jì)效益，需要在管理策略上進(jìn)行改革，僅憑經(jīng)驗(yàn)的管理已經(jīng)不符合

18、現(xiàn)在化生產(chǎn)的要求，計(jì)算機(jī)集成制造系統(tǒng)(CIMS)因運(yùn)而生。管理自動(dòng)化是CIMS得分系統(tǒng)，是現(xiàn)代制造業(yè)的重要組成部分，計(jì)算機(jī)輔助生產(chǎn)計(jì)劃、生產(chǎn)調(diào)度與控制是管理自動(dòng)化的核心技術(shù)，是CIMS功能結(jié)構(gòu)模型中不可缺少的一個(gè)層次，無(wú)論是理論研究，還是應(yīng)用系統(tǒng)的開(kāi)發(fā)都受到廣大學(xué)者和企業(yè)界認(rèn)識(shí)的關(guān)注，成為學(xué)術(shù)界的熱門(mén)研究課題本課題。</p><p>　　同時(shí)，伴隨著用戶對(duì)產(chǎn)品需求的快速變化，以及市場(chǎng)競(jìng)爭(zhēng)的日趨激烈，現(xiàn)代制造企業(yè)需

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

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

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

22、題被證明屬于NP完全問(wèn)題或NP一難問(wèn)題，難以找到多項(xiàng)式算法，因此開(kāi)始關(guān)注啟發(fā)式算法。Panwalkar總結(jié)和歸納出了113條調(diào)度規(guī)則，并對(duì)其進(jìn)行分類[4]。七十年代末期，經(jīng)典調(diào)度理論趨向成熟。</p><p>　　八十年代初期，Stephen等[5]從三個(gè)方面對(duì)調(diào)度進(jìn)行了從新考察，對(duì)未來(lái)發(fā)展做了分析和預(yù)測(cè)，認(rèn)為理論與實(shí)際的結(jié)合將會(huì)成為研究熱點(diǎn)。這個(gè)富有挑戰(zhàn)性的課題吸引了機(jī)械、計(jì)算機(jī)、管理等諸多領(lǐng)域的學(xué)者，許多跨學(xué)

23、科的方法被應(yīng)用到研究中。其中最引人注目的就是以Carnegie-Mellon大學(xué)的M.Fox[6]為代表的學(xué)者們開(kāi)展的基于約束傳播的ISIS研究，它標(biāo)志了人工智能開(kāi)始真正應(yīng)用與調(diào)度問(wèn)題。八十年代后期，Giffler[7] 等人總結(jié)了生產(chǎn)調(diào)度理論和實(shí)際方面的最新研究進(jìn)展，從七個(gè)方面論述了生產(chǎn)調(diào)度的技術(shù)和方法，認(rèn)為生產(chǎn)調(diào)度無(wú)論在理論還是實(shí)踐上都已突破了傳統(tǒng)界限。<

24、/p><p>　　九十年代至今，各種方法在生產(chǎn)調(diào)度問(wèn)題的研究中得到了充分的發(fā)揮，同時(shí)新的研究手段層出不窮。 而Davis[8]是最早把 GA(GeneticAlgorithm，遺傳算法)應(yīng)用于車間調(diào)度問(wèn)題的學(xué)者之一，他在使用GA求解車間調(diào)度的研究中取得了近似最優(yōu)解。1985年，Davis發(fā)表了關(guān)于把GA成功應(yīng)用于車間調(diào)度問(wèn)題的論文，充分證明了GA在解決車間調(diào)度問(wèn)題中的可行性。此后，很多學(xué)者就給予遺傳算法的車間調(diào)度方面

25、做了大量研究，發(fā)表了大量卓有成效的論文，對(duì)車間調(diào)度這類NPhard問(wèn)題的解決提出了具體方案。這些論文中提出了一些具有突破性的新方法，改進(jìn)并完善了傳統(tǒng)GA車間調(diào)度中的應(yīng)用方法，同時(shí)通過(guò)在解決一些著名的標(biāo)準(zhǔn)檢測(cè)問(wèn)題(Benc知rnark)的過(guò)程中取得了最優(yōu)(或接近最優(yōu))解，進(jìn)一步證明了遺傳算法在解決NP問(wèn)題方面的有效性。</p><p>　　國(guó)內(nèi)對(duì)車間調(diào)度的研究起步比較晚，始于90年代。很多企業(yè)由于技術(shù)上的制約，基本

26、上是靠調(diào)度人員的經(jīng)驗(yàn)進(jìn)行車間作業(yè)分配和調(diào)度。隨著遺傳算法在車間調(diào)度方面的應(yīng)用熱潮，在這方面也產(chǎn)生了大量的研究成果，不過(guò)，研究工作主要集中在清華大學(xué)等等CIMS國(guó)家重點(diǎn)實(shí)驗(yàn)室，但離形成系統(tǒng)的理論和開(kāi)發(fā)出成熟的軟件系統(tǒng)還有很長(zhǎng)一段距離，因此還在投入大量的人力和物力進(jìn)行該方面的研究，特別是在開(kāi)展對(duì)車間作業(yè)作業(yè)調(diào)度算法的研究方面，目前尚處在實(shí)驗(yàn)研究階段。</p><p>　　車間調(diào)度問(wèn)題的高度復(fù)雜性和現(xiàn)有計(jì)算機(jī)條件的局限

27、性決定了不可能一開(kāi)始就考慮到實(shí)際調(diào)度問(wèn)題中的所有因素，因此，實(shí)際研究通常是對(duì)車間系統(tǒng)進(jìn)行簡(jiǎn)化和抽象來(lái)解決實(shí)際問(wèn)題。正是在這些現(xiàn)有的理論成果上不斷加上約束條件，使得研究問(wèn)題近似于實(shí)際問(wèn)題。總而言之，隨著各種特殊調(diào)度問(wèn)題的攻克和新方法、新設(shè)備的出現(xiàn)，車間調(diào)度研究正向動(dòng)態(tài)、敏捷、多資源、智能化的方向發(fā)展。</p><p>　　1.2.2 研究中存在的問(wèn)題</p><p>　　由于在實(shí)際生產(chǎn)過(guò)程

28、中會(huì)出現(xiàn)諸多不確定因素，而且調(diào)度問(wèn)題己經(jīng)被證明NP難題，因此尋找具有多項(xiàng)式復(fù)雜性的最優(yōu)算法幾乎是不可能的。從目前文獻(xiàn)的研究來(lái)看，對(duì)于資源分配也沒(méi)有提出一個(gè)切實(shí)可行的解決方案，往往都是從某一方面入手，在若干假設(shè)的基礎(chǔ)上，得出一種理論上的可行解。各種啟發(fā)式方法、諸如基于規(guī)則的算法等，由于能在合理的時(shí)間內(nèi)產(chǎn)生比較滿意的調(diào)度，因此廣泛應(yīng)用于實(shí)際調(diào)度中，但其往往對(duì)所得到的調(diào)度解的次優(yōu)性不能進(jìn)行評(píng)估。因此，有必要探索更好的近似最優(yōu)調(diào)度算法，可以考慮

29、通過(guò)增加合理的計(jì)算時(shí)間來(lái)提高解的次優(yōu)性。各種基于統(tǒng)計(jì)優(yōu)化的方法，諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問(wèn)題的新途徑，但與別的優(yōu)化算法類似，也存在著一定程度的枚舉、一般來(lái)說(shuō)收斂到最優(yōu)解較慢，對(duì)于判斷解的最優(yōu)性也很困難，在這方面也需要做進(jìn)一步的研究。</p><p>　　在調(diào)度問(wèn)題的理論研究中，大多數(shù)還是集中在針對(duì)經(jīng)典的調(diào)度問(wèn)題設(shè)計(jì)優(yōu)化算法，而經(jīng)典調(diào)度問(wèn)題與實(shí)際相差較大，尤其在目前環(huán)境下，車間調(diào)度問(wèn)題將是

30、一個(gè)研究的重點(diǎn)和進(jìn)一步研究的方向，而目前對(duì)于這方面研究的文獻(xiàn)相對(duì)來(lái)說(shuō)較少。在實(shí)際車間調(diào)度中，車間計(jì)劃與車間調(diào)度往往是分層進(jìn)行的，但這可能造成計(jì)劃在實(shí)際調(diào)度中的不可行問(wèn)題，如何將計(jì)劃與調(diào)度結(jié)合考慮，以求總體的優(yōu)化也是需要進(jìn)一步研究的。</p><p>　　1.3 研究意義與目的</p><p>　　有史以來(lái)，有限資源的合理配置和優(yōu)化利用問(wèn)題始終是人類社會(huì)所面臨的最基本經(jīng)濟(jì)問(wèn)題，這個(gè)問(wèn)題貫穿

31、于社會(huì)生活的各個(gè)方面。從一個(gè)國(guó)家、社會(huì)的宏觀經(jīng)濟(jì)運(yùn)行到具體企業(yè)的微觀經(jīng)濟(jì)活動(dòng)，都要受資源條件的限制。對(duì)企業(yè)來(lái)說(shuō)，能否對(duì)現(xiàn)有資源進(jìn)行合理配置和充分利用將直接影響到產(chǎn)品的制造成本，進(jìn)而成為影響企業(yè)效益的重要因素。企業(yè)資源的合理配置和優(yōu)化利用很大程度上體現(xiàn)在車間一層的生產(chǎn)活動(dòng)中，所以加強(qiáng)車間層的生產(chǎn)計(jì)劃與控制一直在企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)中占有十分重要的地位。</p><p>　　車間生產(chǎn)調(diào)度是制造系統(tǒng)生產(chǎn)管理的核心，是生產(chǎn)管

32、理和控制系統(tǒng)實(shí)現(xiàn)管理技術(shù)、運(yùn)籌技術(shù)、優(yōu)化技術(shù)和自動(dòng)化技術(shù)發(fā)展的核心。及時(shí)準(zhǔn)確的生產(chǎn)調(diào)度對(duì)生產(chǎn)系統(tǒng)的高效運(yùn)行有著重要的影響。生產(chǎn)管理任務(wù)能否順利的實(shí)施與完成，最終要靠合理的生產(chǎn)調(diào)度來(lái)保證有效。</p><p>　　實(shí)用的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用己成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)。因此，研究生產(chǎn)調(diào)度問(wèn)題，不僅具有較大的理論意義，而且具有相當(dāng)大的實(shí)用價(jià)值。一方面，生產(chǎn)調(diào)度問(wèn)題的研究不僅可以推動(dòng)相關(guān)算法的研究，如遺傳算法

33、、神經(jīng)網(wǎng)絡(luò)、人工智能等，而且還能在此基礎(chǔ)上提出新的算法，這為其他領(lǐng)域類似問(wèn)題的解決提供了條件和手段；另一方面，一個(gè)好的生產(chǎn)調(diào)度方案不僅可以降低生產(chǎn)成本，而且可以提高企業(yè)產(chǎn)品的準(zhǔn)時(shí)交貨能力，從而增強(qiáng)企業(yè)的競(jìng)爭(zhēng)力。</p><p>　　隨著科學(xué)技術(shù)的發(fā)展，制造行業(yè)的生產(chǎn)規(guī)模變得越來(lái)越大，產(chǎn)品越來(lái)越多樣化，車間生產(chǎn)情況的復(fù)雜性也越來(lái)越高。同時(shí)，由于加工系統(tǒng)的復(fù)雜性和多樣性，目前還沒(méi)有一種通用的、全面的方法解決各種生產(chǎn)方

34、式的優(yōu)化調(diào)度問(wèn)題。制造企業(yè)迫切希望能有一個(gè)結(jié)合其自身特點(diǎn)的實(shí)用而有效的調(diào)度支持系統(tǒng)，這就需要根據(jù)企業(yè)的實(shí)際狀況和生產(chǎn)變化，從以獲得工程滿意解的實(shí)際需求出發(fā)，選取調(diào)度目標(biāo)，應(yīng)用能滿足要求的快速有效的優(yōu)化算法，滿足企業(yè)的實(shí)際需求，實(shí)現(xiàn)優(yōu)化調(diào)度。</p><p>　　1.4 本文的工作</p><p>　　緒論，從課題的研究背景到車間調(diào)度的國(guó)內(nèi)外的研究現(xiàn)狀再到車間調(diào)度存在的問(wèn)題及解決途徑來(lái)引出

35、遺傳算法對(duì)車間調(diào)度問(wèn)題研究的重要性。描述了車間調(diào)度問(wèn)題。進(jìn)而描述了關(guān)于車間調(diào)度的較常見(jiàn)的幾種研究方法及它們的應(yīng)用領(lǐng)域。</p><p>　　車間調(diào)度問(wèn)題綜述，先介紹車間調(diào)度問(wèn)題其中包括車間調(diào)度問(wèn)題的描述、特點(diǎn)、分類、job shop與flow shop 比較然后追尋調(diào)度問(wèn)題研究方法(數(shù)學(xué)規(guī)劃法、近似算法、智能搜索算法、模擬退火方法、Multi-agent方法、模糊邏輯、螞蟻調(diào)度算法、神經(jīng)元算法)，從而找到一些解決

36、這些問(wèn)題的辦法。</p><p>　　第三章遺傳算法，先介紹遺傳算法的形成與發(fā)展，然后再介紹遺傳算法的基本思想和特點(diǎn)，闡述一下遺傳算法的過(guò)程和流程，最后求解FSP調(diào)度問(wèn)題的遺傳算法其中包括遺傳算法的設(shè)計(jì)步驟、編碼方式適配值函數(shù)、遺傳算子的設(shè)計(jì)、編碼參數(shù)、遺傳算子和算法的終止條件。</p><p>　　第四章基于遺傳算法的流水車間調(diào)度問(wèn)題，首先介紹流水車間的背景，然后對(duì)流水車間調(diào)度問(wèn)題進(jìn)行描

37、述與建立數(shù)學(xué)模型，進(jìn)行遺傳算法的設(shè)計(jì)其中包括編碼方案、群體確定、適應(yīng)度函數(shù)、遺傳算子的設(shè)計(jì)最后根據(jù)實(shí)例按照上邊的步驟得到甘特圖和一些數(shù)據(jù)求解進(jìn)行分析。</p><p>　　第五章具有跨工位操作的車間調(diào)度問(wèn)題，先介紹跨工位的背景，對(duì)后對(duì)跨工位流水車間調(diào)度問(wèn)題進(jìn)行描述，然后對(duì)跨工位進(jìn)行定義并寫(xiě)出數(shù)學(xué)模型，然后進(jìn)行遺傳算法的設(shè)計(jì)，其中包括其中包括編碼方案、群體確定、適應(yīng)度函數(shù)、遺傳算子的設(shè)計(jì)最后根據(jù)實(shí)例按照上邊的步驟先

38、畫(huà)出甘特圖和求出一些數(shù)據(jù)后求解并且進(jìn)行分析。</p><p>　　結(jié)論，本文以流水車間的調(diào)度作為研究對(duì)象，以遺傳算法為基礎(chǔ)，分別對(duì)一般流水車間和具有可跨工位操作的流水車間兩種生產(chǎn)車間計(jì)劃調(diào)度進(jìn)行了系統(tǒng)的研究。在理論研究的基礎(chǔ)上完成了基于遺傳算法的FSP調(diào)度的算法設(shè)計(jì)，展示了算法的實(shí)現(xiàn)過(guò)程并對(duì)調(diào)度結(jié)果進(jìn)行分析。</p><p>　　2 車間調(diào)度問(wèn)題綜述</p><p&g

39、t;　　2.1 車間調(diào)度問(wèn)題</p><p>　　2.1.1 車間調(diào)度問(wèn)題的描述</p><p>　　從廣義上講，調(diào)度是一種對(duì)資源的分配。車間調(diào)度是對(duì)一個(gè)可用的加工機(jī)器集在時(shí)間上進(jìn)行加工任務(wù)集分配，以滿足一個(gè)性能指標(biāo)集。調(diào)度的目標(biāo)是將作業(yè)合理地安排到各機(jī)器，并合理安排作業(yè)的加工次序和加工開(kāi)始時(shí)間，使約束條件得到滿足，同時(shí)優(yōu)化一些性能指標(biāo)。</p><p>　　車

40、間調(diào)度問(wèn)題一般可以描述為:n個(gè)工件在m臺(tái)機(jī)器上加工，一個(gè)工件分為m道工序，每個(gè)工序可以在若干臺(tái)機(jī)器上加工。每一臺(tái)機(jī)器在每個(gè)時(shí)刻只能加工某個(gè)工件的某道工序，只能在上道工序加工完成后才能開(kāi)始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。</p><p>　　車間調(diào)度問(wèn)題的決策內(nèi)容包括分配決策(工件的加工順序)和時(shí)間決策(工件各工序的加工時(shí)間)以及路徑?jīng)Q策(工件工序的加工設(shè)備的分配)。</p>&

41、lt;p>　　車間調(diào)度問(wèn)題的特點(diǎn)是多個(gè)工件在有限的機(jī)器上加工，每臺(tái)機(jī)器在切換不同工件生產(chǎn)時(shí)需要一定的準(zhǔn)備時(shí)間。切換加工次數(shù)增加有利于減少工件的庫(kù)存，但導(dǎo)致生產(chǎn)率下降。因此，需要在庫(kù)存成本和工件切換加工頻率之間取得平衡。生產(chǎn)的柔性體現(xiàn)在設(shè)備使用和設(shè)備安排兩個(gè)方面，設(shè)備使用的柔性是指設(shè)備可用于多個(gè)零件的多個(gè)工序的加工;設(shè)備安排的柔性是指工件的設(shè)備加工路徑不是固定和預(yù)先確定的，具有可選的路徑，可以通過(guò)將若干設(shè)備組織為一條或者多條生產(chǎn)線加

42、工一種工件，使得該工件的生產(chǎn)率最大。</p><p>　　車間調(diào)度問(wèn)題的另一類研究集中于柔性制造系統(tǒng)(FMS)，F(xiàn)MS有一系列NC數(shù)控設(shè)備組成，NC能夠單獨(dú)加工多個(gè)工件，在選擇了待加工工件后，所需刀具必須分配到該設(shè)備的工具集中。FMS問(wèn)題包括:工件選擇分配、設(shè)備分組、生產(chǎn)率確定和設(shè)備負(fù)荷、刀具分配等問(wèn)題，它的約束包括設(shè)備工具集的容量限制、設(shè)備可用時(shí)間和設(shè)備負(fù)荷等。</p><p>　　2.

43、1.2 車間調(diào)度問(wèn)題的特點(diǎn)</p><p>　　車間調(diào)度的基本特點(diǎn)是：建模的復(fù)雜性，計(jì)算的復(fù)雜性，動(dòng)態(tài)的隨機(jī)性，多約束性，多目標(biāo)性。</p><p>　　(1) 復(fù)雜性：車間中工件、機(jī)器、緩存和搬運(yùn)系統(tǒng)之間相互影響、相互作用。每個(gè)工件要考慮它的加工時(shí)間、安裝時(shí)間和操作順序等因素，因而相當(dāng)復(fù)雜。調(diào)度問(wèn)題是在等式或不等式約束下求指標(biāo)的優(yōu)化，在計(jì)算量上往往是具有NP特性，隨著問(wèn)題規(guī)模的增大，其

44、計(jì)算量急劇增加，使得一些常規(guī)的方法無(wú)能為力，對(duì)于這一點(diǎn)已經(jīng)證明。</p><p>　　(2) 隨機(jī)性：在實(shí)際的作業(yè)車間調(diào)度系統(tǒng)中存在很多隨機(jī)的和不確定的因素，環(huán)境是不斷變化的，在運(yùn)行過(guò)程中會(huì)遇到多種隨機(jī)干擾，比如工件到達(dá)時(shí)間的不確定性、作業(yè)的加工時(shí)間也有一定的隨機(jī)性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)偶然事件，如設(shè)備的損壞、修復(fù)、作業(yè)交貨期的改變等，故作業(yè)車間調(diào)度過(guò)程是一個(gè)動(dòng)態(tài)的隨機(jī)過(guò)程。</p><

45、;p>　　(3)多約束性：車間調(diào)度問(wèn)題中資源的數(shù)量、緩存的容量、工件加工時(shí)間以及工件的操作順序等都是約束。此外還有一些人為的因素，如要求各機(jī)器上的負(fù)荷要平衡等。</p><p>　　(4) 多目標(biāo)性：實(shí)際的車間調(diào)度問(wèn)題是多目標(biāo)的，而且這些目標(biāo)之間往往是發(fā)生沖突的。調(diào)度目標(biāo)分為三類：基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時(shí)間的目標(biāo)和基于生產(chǎn)成本的目標(biāo)。</p><p>　　2.1.3 車

46、間調(diào)度問(wèn)題的分類</p><p>　　車間調(diào)度問(wèn)題的分類，根據(jù)研究的側(cè)重點(diǎn)不同有多種分類方式。</p><p>　　1．按照資源約束種類和數(shù)量劃分</p><p>　　(1) 單資源車間調(diào)度(single resource constrained)：只有一種資源制約著車間力。</p><p>　　(2) 雙資源車間調(diào)度(dual resour

47、ce constrained)：同時(shí)有兩種資源制約著車間力。機(jī)床設(shè)備往往是制約資源之一，車間有時(shí)會(huì)缺乏有經(jīng)驗(yàn)或一技之長(zhǎng)的工人，也有可能某種類型的刀具數(shù)量有限，因此這兩種資源可以是機(jī)床設(shè)備和工人或刀具。</p><p>　　(3) 多資源車間調(diào)度(multiple resource constrained)：同時(shí)有兩種以上的生產(chǎn)所制約著車間的生產(chǎn)能力。這些資源包括員工、機(jī)床設(shè)備、機(jī)器人、物料運(yùn)送系統(tǒng)和輔助資源，如貨

48、盤(pán)、夾具和刀具等。</p><p>　　單資源車間調(diào)度是雙資源車間調(diào)度的特例，雙資源車間調(diào)度又是多資源車間調(diào)度的特例。所以多資源車間調(diào)度問(wèn)題是最復(fù)雜的一種。</p><p>　　2．按照零件和車間的構(gòu)成劃分</p><p>　　(1) 流水車間調(diào)度(Flow shop)：在這種車間中，每個(gè)零件都有相同的加工路徑。這樣，機(jī)床設(shè)備的布局如同流水線一樣，零件一次從流水線的

49、一端進(jìn)入，最后從另一端流出。</p><p>　　(2) 作業(yè)車間調(diào)度(Job shop)：在這種車間中，機(jī)床設(shè)備的布局可以是任意的，因此零件的加工路徑也是任意的，并且各零件的工序內(nèi)容和數(shù)量也是任意的。這是一種最一般的車間調(diào)度形式。</p><p>　　(3) 開(kāi)放式車間調(diào)度(Open shop)：每個(gè)零件的工序之間的加工次序是任意的。零件的加工可以從任何一道工序開(kāi)始，在任何一道工序結(jié)束。

50、</p><p>　　(4) 單車間調(diào)度(Single shop)：在這種車間中，每個(gè)零件只能有一道工序。</p><p>　　3．按照零件的加工特點(diǎn)劃分</p><p>　　(1) 靜態(tài)車間調(diào)度(Static scheduling)：所有的零件在開(kāi)始調(diào)度時(shí)刻已經(jīng)準(zhǔn)備間的調(diào)度不考慮零件在加工過(guò)程中出現(xiàn)的意外情況，如機(jī)床突然損壞、零件的交貨期提前、有更緊迫的零件要求被

51、加工等等。</p><p>　　(2) 動(dòng)態(tài)車間調(diào)度(Dynamic scheduling)：車間的調(diào)度要求考慮零件在加工的各種意外情況。這種調(diào)度方式要求調(diào)度能隨時(shí)相應(yīng)車間能力的變化，在有突發(fā)事件出現(xiàn)后，能立即根據(jù)當(dāng)時(shí)的車間加工能力，對(duì)待加工的零件重新展開(kāi)調(diào)度，以確保在任何時(shí)候，都能保持車間的加工性能指標(biāo)處于最優(yōu)或次優(yōu)狀態(tài)。</p><p>　　2.1.4 Job Shop 與Flow

52、shop 比較</p><p>　　1、Job Shop 與Flow shop的共性</p><p>　　Job Shop 與Flow shop調(diào)度問(wèn)題是目前調(diào)度問(wèn)題的兩大類型，其目標(biāo)均是通過(guò)科學(xué)的調(diào)度，使車間調(diào)度問(wèn)題最優(yōu)化?；炯s束條件均為：</p><p>　　(1) 同一時(shí)刻同一臺(tái)機(jī)器只能加工一個(gè)零件；</p><p>　　(2) 每個(gè)

53、工件在某一時(shí)候只能在一臺(tái)機(jī)器上加工，不能中途中斷每一個(gè)操作；</p><p>　　(3) 同一個(gè)工件的工序之間有先后約束，不同工件的工序之間沒(méi)有先后約</p><p><b>　　束；</b></p><p>　　(4) 不同工件具有相同的優(yōu)先級(jí)。</p><p>　　2、Job Shop 與Flow shop的個(gè)性&l

54、t;/p><p>　　對(duì)于上述約束條件，當(dāng)增加約束條件：每臺(tái)機(jī)器只有單一加工功能，且各工件中的任意一個(gè)工序只能在所有機(jī)器中的一臺(tái)機(jī)器上操作且各工件的技術(shù)約束條件（加工方法、加工時(shí)間、加工設(shè)備、加工順序等）相同時(shí)，該問(wèn)題則轉(zhuǎn)化為Flow Shop問(wèn)題；當(dāng)增加約束條件：每臺(tái)機(jī)器只有單一加工功能，各工件中的任意一個(gè)工序只能在所有機(jī)器中的一臺(tái)機(jī)器上操作時(shí)，該問(wèn)題轉(zhuǎn)化為Job Shop問(wèn)題。</p><p&

55、gt;　　Flow shop型問(wèn)題假設(shè)所有作業(yè)都在同樣的設(shè)備上加工，并有一致的加工操作和加工順序；Job shop是最一般的調(diào)度類型，不同的作業(yè)具有不同的加工操作和加工順序，并不限制作業(yè)的加工設(shè)備?，F(xiàn)代車間調(diào)度類型往往是 job shop型的，本文的研究就是針對(duì) job shop型的調(diào)度問(wèn)題展開(kāi)。</p><p>　　2.2 調(diào)度問(wèn)題的研究方法</p><p>　　生產(chǎn)調(diào)度問(wèn)題的研究最初

56、集中在整數(shù)規(guī)劃、仿真和簡(jiǎn)單的規(guī)劃等方法上，這些方法不是調(diào)度結(jié)果不理想，就是難以解決復(fù)雜的問(wèn)題[9]。 隨著機(jī)器數(shù)和工件數(shù)的增加，調(diào)度方案呈指數(shù)增長(zhǎng)，怎樣才能盡快地得到最優(yōu)調(diào)度方案，這一問(wèn)題吸引了國(guó)內(nèi)外許多學(xué)者和實(shí)際生產(chǎn)調(diào)度人員的關(guān)注，提出了很多的解決方法。近年來(lái)，在生產(chǎn)調(diào)度領(lǐng)域出現(xiàn)了許多新的優(yōu)化方法，比如神經(jīng)網(wǎng)絡(luò)法、模擬退火法、遺傳算法等，使得生產(chǎn)調(diào)度問(wèn)題的研究方法走向了多元化[10]。</p><p>　　1．

57、精確算法一數(shù)學(xué)規(guī)劃法</p><p>　　數(shù)學(xué)規(guī)劃法主要是通過(guò)對(duì)車間調(diào)度問(wèn)題建立一個(gè)整數(shù)規(guī)劃模型，采用枚舉方法尋求調(diào)度問(wèn)題的最優(yōu)解。數(shù)學(xué)規(guī)劃方法往往采用基于枚舉思想的分枝定界法或動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。分枝定界法基本思想是先求出對(duì)調(diào)度整數(shù)規(guī)劃模型所對(duì)應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解，如果解不能滿足調(diào)度問(wèn)題的整數(shù)條件，則對(duì)應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解必是調(diào)度問(wèn)題的目標(biāo)函數(shù)值的上界，而調(diào)度問(wèn)題的任意可行解的目標(biāo)函數(shù)值則是其最優(yōu)解的

58、下界，然后將對(duì)應(yīng)的線性規(guī)劃問(wèn)題的可行域分成子域，通過(guò)不斷減少上界和增大下界，最終尋找到最優(yōu)解[11]。分枝定界法的實(shí)現(xiàn)方法是動(dòng)態(tài)構(gòu)造一個(gè)表示調(diào)度問(wèn)題所有可行解的樹(shù)，通過(guò)對(duì)樹(shù)的搜索尋找調(diào)度問(wèn)題的最優(yōu)解。分枝定界法只適合于小規(guī)模的調(diào)度問(wèn)題，并且對(duì)實(shí)際問(wèn)題比較敏感，因此限制了它在調(diào)度問(wèn)題上的應(yīng)用。動(dòng)態(tài)規(guī)劃方法的優(yōu)點(diǎn)是任務(wù)分配和排序的全局性比較好，所有的選擇同時(shí)進(jìn)行，因此可以保證求解問(wèn)題的全局優(yōu)化。但是，動(dòng)態(tài)規(guī)劃方法是一種精確求解方法，它需要對(duì)

59、調(diào)度問(wèn)題進(jìn)行統(tǒng)一的建模，任何參數(shù)的變化會(huì)使得算法的重用性很差，因此，對(duì)于復(fù)雜多變的生產(chǎn)調(diào)度來(lái)說(shuō)，單一的數(shù)學(xué)規(guī)劃模型不能覆蓋所有的因素，存在求解空間大和計(jì)算困難等問(wèn)題。</p><p><b>　　2．近似算法</b></p><p>　　由于數(shù)學(xué)規(guī)劃法的局限性，從20世紀(jì)70年代開(kāi)始出現(xiàn)了啟發(fā)式算法，這些算法基本上是在一些信息和規(guī)則的啟發(fā)下進(jìn)行推理和計(jì)算，從而獲得調(diào)度

60、問(wèn)題的近似最優(yōu)解。啟發(fā)式搜索方法的優(yōu)點(diǎn)是利用了面向特定問(wèn)題的知識(shí)和經(jīng)驗(yàn)，因而可以產(chǎn)生好的解決方案，求解時(shí)間也可以接受。而對(duì)于如何提高搜索效率并減少內(nèi)存使用以解決規(guī)模較大的問(wèn)題，還需要進(jìn)一步探索。啟發(fā)式算法主要有：</p><p>　　(1) 基于啟發(fā)式規(guī)則的調(diào)度算法</p><p>　　啟發(fā)式規(guī)則的調(diào)度算法也稱調(diào)度規(guī)則，是最早的近似算法。其本質(zhì)是給每一個(gè)生產(chǎn)任務(wù)和操作賦予優(yōu)先級(jí)，優(yōu)先級(jí)高的

61、生產(chǎn)任務(wù)和操作優(yōu)先考慮。由于其具有簡(jiǎn)單、易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低的特點(diǎn)，調(diào)度規(guī)則在調(diào)度問(wèn)題上得到廣泛的應(yīng)用，同時(shí)不斷有新的調(diào)度規(guī)則產(chǎn)生。Panwalkar等人總結(jié)了113條規(guī)則[12]，并將它們分為三類：簡(jiǎn)單規(guī)則、復(fù)合規(guī)則、式規(guī)則，其中屬于簡(jiǎn)單規(guī)則有30多條，如先進(jìn)先出、最短加工時(shí)間、交付期最早等經(jīng)常使用的規(guī)則，其它規(guī)則基本上是簡(jiǎn)單規(guī)則的組合或加權(quán)組合；另外，調(diào)度規(guī)則經(jīng)過(guò)適當(dāng)?shù)慕M合和變形后，往往可以得到很好的調(diào)度效果。調(diào)度規(guī)則的缺點(diǎn)在于其

62、精確度不夠高。隨著計(jì)算機(jī)運(yùn)算速度的飛速提高，人們希望尋找新的近似調(diào)度方法，以合理的額外計(jì)算時(shí)間代價(jià)，換得比單純啟發(fā)式規(guī)則所得到的調(diào)度更好的調(diào)度。</p><p>　　(2) 啟發(fā)式圖搜索法</p><p>　　啟發(fā)式圖搜索法主要有寬度優(yōu)先、深度優(yōu)先、Beam搜索及A或者A}算法等。啟發(fā)式圖搜索法的缺點(diǎn)在于計(jì)算復(fù)雜度較高，如A*算法的計(jì)算復(fù)雜度為D(2n-1)(n為搜索圖中結(jié)點(diǎn)數(shù))，在調(diào)度問(wèn)

63、題的離散圖中結(jié)點(diǎn)數(shù)為nxm。對(duì)于此類方法如何提高搜索效率、減少內(nèi)存使用，以能解決比較大的規(guī)模的問(wèn)題，還需要進(jìn)一步探索。</p><p>　　(3) 拉格朗日松弛算法</p><p>　　LR算法由于其在可行的時(shí)間里能對(duì)復(fù)雜的規(guī)劃問(wèn)題提供較好的最優(yōu)解，并能對(duì)解的最優(yōu)性進(jìn)行定量評(píng)估，近年來(lái)已成為解決復(fù)雜生產(chǎn)調(diào)度問(wèn)題的重要方法。但不可避免的是，LR算法存在搜索效率低，可行調(diào)度的構(gòu)造有待于進(jìn)一步研

64、究等問(wèn)題。</p><p><b>　　3．智能搜索算法</b></p><p>　　計(jì)算智能是通過(guò)神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)、進(jìn)化計(jì)算的有機(jī)融合而形成的新的科學(xué)方法，也是智能理論和技術(shù)發(fā)展的嶄新階段。</p><p><b>　　(1) 遺傳算法</b></p><p>　　遺傳算法(genetic al

65、gorithm簡(jiǎn)稱GA)是一種嶄新的并行優(yōu)化搜索方法。它是模仿物群體進(jìn)化過(guò)程的一種優(yōu)化算法，給定一組初始解作為一個(gè)群體，通過(guò)選擇、交叉和變異等遺傳操作來(lái)搜索最優(yōu)解。遺傳算法對(duì)求解問(wèn)題本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并根據(jù)適應(yīng)性進(jìn)行選擇，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)，經(jīng)過(guò)反復(fù)迭代，直到達(dá)到某種形式的收斂。遺傳算法尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜的非線性問(wèn)題，可廣泛用于組合優(yōu)化、

66、機(jī)器學(xué)習(xí)和規(guī)劃設(shè)計(jì)等領(lǐng)域。</p><p>　　遺傳算法已經(jīng)成為一種比較通用的優(yōu)化算法，主要原因是編碼技術(shù)和遺傳操作比較簡(jiǎn)單，優(yōu)化不受限制性條件的約束。但遺傳算法也有明顯的不足之處：對(duì)于大規(guī)模的組合優(yōu)化問(wèn)題，由于搜索空間大，搜索時(shí)間較長(zhǎng)，往往會(huì)出現(xiàn)早熟收斂的情況；對(duì)初始種群很敏感，初始種群選擇不好會(huì)影響解的質(zhì)量和算法效率。為了進(jìn)一步改進(jìn)遺傳算法，人們主要從兩方面入手：一是對(duì)遺傳算法本身進(jìn)行改進(jìn)；二是與其它算法結(jié)合

67、，取長(zhǎng)補(bǔ)短。</p><p>　　(2) 禁忌搜索算法</p><p>　　對(duì)于復(fù)雜的組合優(yōu)化問(wèn)題，禁忌搜索也是一種通過(guò)鄰域搜索以獲取最優(yōu)解的方法。算法的基本過(guò)程如下：它從一個(gè)可行解S出發(fā)，產(chǎn)生的領(lǐng)域，如果F為目標(biāo)函數(shù)，選取所有領(lǐng)域中使F(si)為最優(yōu)的狀態(tài)作為下一個(gè)狀態(tài)，并把這一移動(dòng)的反向移動(dòng)存入一個(gè)稱為禁忌移動(dòng)(Ta bu Move)的表中。列在表中的移動(dòng)在以后若干步內(nèi)不允許再產(chǎn)生，這

68、樣可免搜索退回去。每搜索一次，更新一次禁忌移動(dòng)表。由于禁忌移動(dòng)表的限制，有可能跳出局部極小，從而提高了算法的運(yùn)行效率?？梢?jiàn)，禁忌搜索算法的基本要素是初始解、移動(dòng)、鄰域和禁忌表。禁忌搜索算法沒(méi)有自然性的終止條件，對(duì)求解的問(wèn)題，目標(biāo)函數(shù)和搜索空間沒(méi)有任何特殊的要求，計(jì)算速度較快。因此，它在調(diào)度問(wèn)題上有著廣泛的應(yīng)用前景。</p><p>　　(3) 人工神經(jīng)網(wǎng)絡(luò)</p><p>　　“人工神經(jīng)網(wǎng)

69、絡(luò)"是一種模擬人腦神經(jīng)系統(tǒng)的結(jié)構(gòu)和功能，運(yùn)用大量的處理部件經(jīng)廣泛互連而組成的網(wǎng)絡(luò)系統(tǒng)。Hop field應(yīng)用神經(jīng)網(wǎng)絡(luò)方法求解旅行商問(wèn)題獲得成功，從而為組合優(yōu)化問(wèn)題求解開(kāi)辟了新的途徑。人工神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)是：具有很強(qiáng)的分布式存儲(chǔ)能力和很大的存儲(chǔ)空間，具有自學(xué)習(xí)能力，再者容錯(cuò)性好，特有的高維空間使多體效應(yīng)更加復(fù)雜和顯著，易于分類。但是，人工神經(jīng)網(wǎng)絡(luò)在實(shí)際生產(chǎn)中的應(yīng)用不是很多，而且存在學(xué)習(xí)效率比較差、難以表達(dá)符號(hào)知識(shí)、計(jì)算速度比較慢和

70、精度低等缺點(diǎn)，這些都需要進(jìn)一步改進(jìn)。特別是對(duì)于求解大規(guī)模問(wèn)題有一定難度。目前，神經(jīng)網(wǎng)絡(luò)優(yōu)化應(yīng)用于生產(chǎn)調(diào)度中，主要有三種方式：一是利用其并行計(jì)算能力，求解優(yōu)化調(diào)度；二是利用其自學(xué)習(xí)能力，從優(yōu)化軌跡中提取調(diào)度知識(shí)；三是用神經(jīng)網(wǎng)絡(luò)來(lái)描述調(diào)度約束或調(diào)度策略，以實(shí)現(xiàn)對(duì)生產(chǎn)過(guò)程的可行或次優(yōu)調(diào)度。</p><p>　　(4) 模擬退火方法</p><p>　　模擬退火算法(SA)來(lái)源于固體退火原理，將固

71、體加溫至充分高，再讓其徐徐冷卻加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解一計(jì)算目標(biāo)函數(shù)差一接受或舍棄一的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡

72、羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程．模擬退火方法已經(jīng)應(yīng)用到許多領(lǐng)域。模擬退火算法顯示出了求解優(yōu)化問(wèn)題的強(qiáng)大威力，它可以突破局域搜索的限制，轉(zhuǎn)移到代價(jià)較高的解答，而且如果選擇參數(shù)得當(dāng)，會(huì)在很快的時(shí)間內(nèi)收斂。但是，模擬退火算法在實(shí)際應(yīng)用中往往不能產(chǎn)生較優(yōu)的結(jié)果，而且各個(gè)參數(shù)選擇起來(lái)比較困難，如果選擇不得當(dāng)，就會(huì)使得計(jì)算時(shí)間很長(zhǎng)，而且可能得不到好的結(jié)果，模擬退火算法和其它算法結(jié)合使用會(huì)得到很好的效果，如和遺傳算法、人工神經(jīng)網(wǎng)絡(luò)結(jié)合等[13]

73、。</p><p>　　(5) Multi-agent方法</p><p>　　多代理通過(guò)一系列分散的智能單元(Agent)間進(jìn)行協(xié)調(diào)來(lái)解決問(wèn)題，這些單元有各的目標(biāo)和自治的行為，并且可以有子單元，但是沒(méi)有一個(gè)單元能夠解決全局問(wèn)題，因而它們之間必須進(jìn)行協(xié)調(diào)。每個(gè)Agent至少應(yīng)有以下三個(gè)組成部分[14]：</p><p>　　知識(shí)庫(kù)。包含Agent執(zhí)行其功能所必需的知

74、識(shí)和數(shù)據(jù)。</p><p>　　控制功能。根據(jù)環(huán)境狀態(tài)及與其它Agent間的相互作用，從知識(shí)庫(kù)中提取知識(shí)來(lái)完成調(diào)度功能。</p><p>　　通訊功能。用來(lái)與其它Agent和環(huán)境之間進(jìn)行信息傳遞。</p><p>　　Multi-agent特別適合解決復(fù)雜問(wèn)題，尤其是那些經(jīng)典方法無(wú)法解決的單元間有大互作用的問(wèn)題。</p><p><b&

75、gt;　　(6) 模糊邏輯</b></p><p>　　1965年，美國(guó)控制論專家Zadeh教授首先提出模糊集合的概念，發(fā)表了開(kāi)創(chuàng)性論文糊集合論[15]。他提出模糊數(shù)學(xué)的核心思想就是運(yùn)用數(shù)學(xué)手段，仿效人腦思維，對(duì)復(fù)雜事物進(jìn)行模糊處理。1973年，Zadeh教授又提出模糊邏輯的理論，并積極倡導(dǎo)將模糊理人工智能方向發(fā)展。模糊集理論[16]對(duì)于建模和求解車間調(diào)度問(wèn)題是非常有用的，因?yàn)樗途哂性S多模糊特征，比

76、如不確定的加工次數(shù)、不確定的約束數(shù)量以及不確定的加工時(shí)間等</p><p>　　(7) 螞蟻調(diào)度算法</p><p>　　螞蟻選擇路徑的原則是依據(jù)信息素隨機(jī)選擇，即信息素多的路徑被選擇的可能性較大，若有一只螞蟻隨機(jī)地選擇了最短或較短的路徑，那么，它能較早地回來(lái)并在該路徑上留下信息素。在一定時(shí)間內(nèi)，這條路徑上就有較多的信息素，從而吸引其它螞蟻也選擇這條路徑。由于它們會(huì)較早地留下信息素，最短路

77、徑上的信息素量就會(huì)越來(lái)越多，這種正反饋使得該路徑的吸引力會(huì)越來(lái)越強(qiáng)，另一方面，信息素隨時(shí)間揮發(fā)，較長(zhǎng)的路徑由于信息素難以得到加強(qiáng)，信息素的量會(huì)越來(lái)越少，最終被完全廢棄。螞蟻在選擇路徑的過(guò)程中，留下信息素來(lái)表示自己的“試錯(cuò)一結(jié)果；利用環(huán)境實(shí)現(xiàn)非直接通信，使得群體能區(qū)分不同解的優(yōu)劣；利用隨機(jī)選擇特性，使得整個(gè)蟻群能夠跳出局部最優(yōu)；利用信息素的揮發(fā)特性來(lái)淘汰劣質(zhì)解。</p><p><b>　　(8) 神經(jīng)元

78、算法</b></p><p>　　人工神經(jīng)元網(wǎng)絡(luò)的早期研究始于二十世紀(jì)四十年代，以1943年美國(guó)生理學(xué)家W.S．McCullocn和數(shù)學(xué)家W.A．Pitts提出的二值神經(jīng)元模型為代表。人工神經(jīng)網(wǎng)絡(luò)的用人工神經(jīng)元相互連接組成一個(gè)計(jì)算網(wǎng)絡(luò)，并行高效地求解問(wèn)題[17]。它的主要特點(diǎn)是能夠?qū)W習(xí)，通過(guò)給網(wǎng)絡(luò)提供一定的訓(xùn)練樣本，然后根據(jù)網(wǎng)絡(luò)的實(shí)際輸出與希望輸出之間的偏差，利用某種方法逐步修改各人工神經(jīng)元之間的連接

79、權(quán)，形成求解某些問(wèn)題的能力。從二十世紀(jì)八十年代末期開(kāi)始，人工神經(jīng)網(wǎng)絡(luò)被用來(lái)求解調(diào)度問(wèn)題[18]。它的主要缺點(diǎn)是效率受訓(xùn)練影響很大，并且在問(wèn)題規(guī)模較大時(shí)，計(jì)算速度慢，結(jié)構(gòu)參數(shù)難以確定。</p><p><b>　　3 遺傳算法</b></p><p>　　3.1 遺傳算法的形成與發(fā)展</p><p>　　遺傳算法[19]起源于對(duì)生物系統(tǒng)所進(jìn)行

80、的計(jì)算機(jī)模擬研究。美國(guó)Michigan大學(xué)的Holland教授及其學(xué)生們受到生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化的自適應(yīng)概率優(yōu)化技術(shù)一遺傳算法。Holland教授用遺傳算法的思想對(duì)自然和人工自適應(yīng)系統(tǒng)進(jìn)行了研究，提出了遺傳算法的基本定理一模式定理(Schema Theorem)，并于1975年出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著《Adaptation Natural and artif

81、icial Systems》。80年代，Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)，開(kāi)創(chuàng)了遺傳算法的機(jī)器學(xué)習(xí)的新概念。1987年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，他發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個(gè)體編碼上使用雙倍體的編碼方法。</p><p>　　1975年，DeJ0ng基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹(shù)立了

82、遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。1989年，Goldberg出版了《Genetic Algorithm in search，optimization and Machine Leaking》一書(shū)，該書(shū)系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面完整地論述了遺傳算法的基本原理及其應(yīng)用。1991年，Oavis出版了《Handbook of Genetic Algorithm》一書(shū)，介紹了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)

83、濟(jì)中的大量實(shí)例。1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程(Genetic Programming簡(jiǎn)稱GP)的概念[20]。從遺傳算法的整個(gè)發(fā)展看，70年代是興起階段，80年代是發(fā)展階段，90年代是高潮階段。遺傳算法作為一浙江工業(yè)大學(xué)碩士學(xué)位論文種實(shí)用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù)，發(fā)展極為迅速，己引起國(guó)內(nèi)外學(xué)者的高度重視[21]。</p><p>　　3.2 遺傳算法的基本

84、思想</p><p>　　遺傳算法是建立在自然選擇和群體遺傳學(xué)機(jī)理基礎(chǔ)上的隨機(jī)、迭代、進(jìn)化，具有廣泛適用性的搜索方法，所有的自然種類都是適應(yīng)環(huán)境而得以生存，這一自然適應(yīng)性是遺傳算法的主旋律，遺傳算法結(jié)合了達(dá)爾文適者生存和隨機(jī)信息交換，前者消除了解中不適應(yīng)因素，后者利用了原有解己有的知識(shí)，從而有力地加快了搜索過(guò)程。</p><p>　　遺傳算法和傳統(tǒng)的搜索算法不同，它從一組隨機(jī)產(chǎn)生的初始解，

85、稱為“種群(Population)”開(kāi)始搜索過(guò)程。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解，稱為“染色體(Chromosome)”。在遺傳算法中最重要的概念是染色體，染色體通常是一串?dāng)?shù)據(jù)(或數(shù)組)，用來(lái)作為優(yōu)化問(wèn)題的解的代碼，其本身不一定是解.這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。在每一代中用“適應(yīng)值(Fitness)”來(lái)測(cè)量染色體的好壞。生成的下一代染色體稱為后代(Ofspring)。后代是由前一代染色體通過(guò)交又(Crossover)或者變

86、異(Mutation)運(yùn)算形成的。新一代形成中，根據(jù)適應(yīng)值的大小選擇部分后代，淘汰部分后代，從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高。據(jù)此，經(jīng)過(guò)若干代之后，算法收斂于最好的染色體，它很可能就是問(wèn)題的最優(yōu)解或次優(yōu)解</p><p>　　遺傳算法的基本步驟是:</p><p>　　1、確定問(wèn)題的編碼方案。由于GA通常不直接作用于問(wèn)題的解空間，而是利用解的某種編碼表示來(lái)進(jìn)行進(jìn)化，因

87、此選擇合理的編碼機(jī)制對(duì)算法質(zhì)量和效率有很大影響。</p><p>　　2、確定適應(yīng)度函數(shù)。由于GA通?；谶m應(yīng)度進(jìn)行遺傳操作，因此合理的適應(yīng)度能夠?qū)⒏鱾€(gè)體的優(yōu)劣程度得以體現(xiàn)，并適應(yīng)算法的進(jìn)化過(guò)程。</p><p>　　3、算法參數(shù)的選取。通常包括種群數(shù)目、交叉概率、變異概率、進(jìn)化代數(shù)等。</p><p>　　4、遺傳算子的設(shè)計(jì)。通常包括初始化、選擇、交叉、變異和替換

88、操作等。</p><p>　　5、確定算法的終止條件。終止準(zhǔn)則應(yīng)根據(jù)所求解問(wèn)題的性質(zhì)，在優(yōu)化質(zhì)量和效率方面作合理均衡或側(cè)重。</p><p>　　3.3 遺傳算法的特點(diǎn)</p><p>　　遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于一個(gè)單一的度量函數(shù)(評(píng)估函數(shù))的梯度或較高次統(tǒng)計(jì)，以產(chǎn)生一個(gè)確定性的

89、試驗(yàn)解序列，遺傳算法不依賴于梯度信息，而是通過(guò)模擬自然進(jìn)化過(guò)程來(lái)搜索最優(yōu)解，它利用某種編碼技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進(jìn)化過(guò)程。遺傳算法通過(guò)有組織地、隨機(jī)地信息交換來(lái)重新組合那些適應(yīng)性好的串，生成新的串的群體。遺傳算法的特點(diǎn)有以下幾點(diǎn):</p><p>　　(1) 自組織、自適應(yīng)和自學(xué)習(xí)性(智能性)。應(yīng)用遺傳算法求解問(wèn)題時(shí)，在編碼方式、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過(guò)程中獲

90、得的信息自行組織搜索。由于基于自然的選擇策略為“適者生存，不適者被淘汰”，因而適應(yīng)度大的個(gè)體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，再通過(guò)基因重組和基因突變等操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。進(jìn)化算法的這種自組織、自適應(yīng)特征，使它同時(shí)具有能根據(jù)環(huán)境變化來(lái)自動(dòng)發(fā)現(xiàn)環(huán)境的特征和規(guī)律的能力。自然選擇消除了算法設(shè)計(jì)過(guò)程中的一個(gè)最大的障礙，即需要事先描述問(wèn)題的全部特點(diǎn)，并要說(shuō)明針對(duì)問(wèn)題的不同特點(diǎn)算法應(yīng)采取的措施。因此，利用遺傳算法的方法，我們可以解決那些復(fù)雜的

91、非結(jié)構(gòu)化問(wèn)題。</p><p>　　(2) 并行搜索特性。遺傳算法按并行方式搜索一個(gè)種群數(shù)目的所有點(diǎn)，而不是單點(diǎn)。它的并行性表現(xiàn)在兩個(gè)方面，一是遺傳算法是內(nèi)在并行的(inherent Parallelism)，即遺傳算法本身非常適合大規(guī)模并行搜索操作。最簡(jiǎn)單的并行方式是讓幾百甚至數(shù)千臺(tái)計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算，運(yùn)行過(guò)程中甚至不進(jìn)行任何通信(獨(dú)立的種群之間若有少量的通信一般會(huì)帶來(lái)更好的結(jié)果)，等到運(yùn)算結(jié)束時(shí)

92、才通過(guò)比較、選擇最佳個(gè)體。這種并行處理方式對(duì)并行系統(tǒng)結(jié)構(gòu)沒(méi)有什么限制和要求，可以說(shuō)，遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理，而且對(duì)并行效率沒(méi)有太大影響。</p><p>　　二是遺傳算法的內(nèi)含并行(implicitparallelism)。由于遺傳算法采用種群的方式組織搜索，因而可同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域，并相互交流信息。使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模n成比例的計(jì)算，但實(shí)質(zhì)上已進(jìn)行

93、了大約O(n3)次有效搜索，這是使遺傳算法能以較少的計(jì)算獲得較大的收益。</p><p>　　3、遺傳算法僅用適應(yīng)度函數(shù)的數(shù)值評(píng)估基因個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作。所以遺傳算法不僅不受函數(shù)連續(xù)可微的約束，而且其定義域可以任意設(shè)定。</p><p>　　4、遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合使用。</p><p>　　5、遺傳算法對(duì)給定問(wèn)題，可以產(chǎn)生許多的潛在

94、解，最終選擇可以由使用者確定。</p><p>　　由以上結(jié)論可知，遺傳算法模擬自然界生物優(yōu)勝劣汰的進(jìn)化過(guò)程，在迭代處理過(guò)程中，群體一代一代的得以優(yōu)化并逐漸逼近最優(yōu)解。但為什么通過(guò)選擇、交叉和變異這三種簡(jiǎn)單的算子就能夠體現(xiàn)出其他算法不具有的自適應(yīng)、魯棒性和全局優(yōu)化能力呢?為此，科學(xué)工作者做了許多深入細(xì)致的理論研究工作，目前主要有以下幾個(gè)方面:</p><p><b>　　模式處理

95、</b></p><p>　　模式(Schema)是一個(gè)描述字符串集的模板，該字符集中的串的某些位置上存在相似性。引入模式概念后可以發(fā)現(xiàn)，遺傳算法所操作的串實(shí)際上隱藏著多個(gè)模式，一個(gè)模式可以隱含在多個(gè)串中，不同的串之間通過(guò)模式而相互聯(lián)系。遺傳算法進(jìn)行群體搜索的過(guò)程可看作是隱含的對(duì)模式的抽樣過(guò)程，通過(guò)遺傳操作將較短的低階模式的信息結(jié)合起來(lái)形成高階模式。最終搜索到最優(yōu)解。所以串的運(yùn)算實(shí)質(zhì)上是模式的運(yùn)算，通

96、過(guò)對(duì)模式在選擇、交叉和變異作用下的變化分析導(dǎo)出模式定理。</p><p><b>　　遺傳算法收斂性研究</b></p><p>　　遺傳算法可以實(shí)現(xiàn)均衡的收縮，并且在許多復(fù)雜問(wèn)題的求解中往往能得到滿意的結(jié)果，但是該算法的優(yōu)化收斂性仍需研究分析。近年來(lái)，關(guān)于遺傳算法收斂性的研究取得了突破性進(jìn)展，Goldberg和Segrest首先是用馬爾可夫鏈模型分析了遺傳算法收斂性

97、，Joe S.(1995)等用有限馬爾可夫鏈證明了標(biāo)準(zhǔn)遺傳算法理論上不具備優(yōu)化收斂性;同時(shí)還證明了若對(duì)遺傳算法作一定的改進(jìn)，即不按比例進(jìn)行選擇，而是保留當(dāng)前的最佳值，則此改進(jìn)后的遺傳算法最終能夠收斂到最優(yōu)解。羅志軍等(2000)論證了遺傳算法過(guò)程是一個(gè)齊次有限馬爾可夫鏈，巧妙地構(gòu)造GA的馬爾可夫鏈的狀態(tài)空間，并對(duì)其轉(zhuǎn)移概率矩陣進(jìn)行極限分析。</p><p>　　3.4 遺傳算法的過(guò)程和流程</p>

98、<p><b>　　1、主要步驟</b></p><p>　　標(biāo)準(zhǔn)遺傳算法的主要步驟如下：</p><p>　　(1) 隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群，個(gè)體數(shù)目一定，每個(gè)個(gè)體表示染色體的基因編碼，定義調(diào)度問(wèn)題的適應(yīng)度函數(shù)，并評(píng)價(jià)每一個(gè)體的適配值(fitness value)。</p><p>　　(2) 判斷算法收斂準(zhǔn)則是否滿足，

99、若滿足則輸出搜索結(jié)果；否則執(zhí)行以下步驟。</p><p>　　(3) 根據(jù)適配值大小以一定方式執(zhí)行復(fù)制操作。</p><p>　　(4) 按交叉概率pc執(zhí)行交叉操作。</p><p>　　(5) 按變異概率pm執(zhí)行變異操作。</p><p>　　(6) 返回步驟(2)。</p><p><b>　　2、基本流

100、程</b></p><p>　　標(biāo)準(zhǔn)遺傳算法的流程圖描述，如圖3.1所示。</p><p><b>　　其中涉及如下：</b></p><p>　　(1) 算法收斂準(zhǔn)則</p><p>　　算法收斂準(zhǔn)則一般依據(jù)問(wèn)題的不同有不同的確定方式。例如，可以采用以下的準(zhǔn)則之一作為判斷的條件：1)種群中個(gè)體的最大適應(yīng)度超

101、過(guò)預(yù)先設(shè)定值；2)種群中個(gè)體的平均適應(yīng)度超過(guò)預(yù)先設(shè)定值；3)世代數(shù)超過(guò)預(yù)先設(shè)定值。</p><p><b>　　(2) 選擇操作</b></p><p>　　選擇操作通常采用比例選擇，即復(fù)制概率正比于個(gè)體的適配值，如此意味著適配值高的個(gè)體在下一代中復(fù)制自身的概率大，從而提高了種群的平均適配值根據(jù)群體中每個(gè)個(gè)體變量的目標(biāo)函數(shù)的值或一定概率值進(jìn)行選擇和淘汰，利用其中的優(yōu)良

102、個(gè)體進(jìn)行繁殖，因此，在遺傳算法中，其優(yōu)良個(gè)性可以一直保持下去。常用的選擇操作有：</p><p>　　(1) 比例選擇：也叫賭輪選擇，它的基本思想是各個(gè)個(gè)體的被選中的概率和其適應(yīng)度大小成比例。</p><p>　　(2) 最佳個(gè)體保留選擇：它的思想是先按賭輪選擇機(jī)制執(zhí)行遺傳算法的選擇功能，然后把群體中適應(yīng)度最高的個(gè)體不進(jìn)行交叉和變異而直接復(fù)制到下一代中。這樣可以保證進(jìn)化過(guò)程中某一代的最優(yōu)解

103、可不被交叉和變異操作破壞，但是容易出現(xiàn)早熟現(xiàn)象。另外還有排序選擇、錦標(biāo)賽選擇、EP 選擇等方法。</p><p>　　圖3.1 遺傳算法基本流程</p><p><b>　　(3) 交叉操作</b></p><p>　　交叉操作通過(guò)交換兩父代個(gè)體的部分信息構(gòu)成后代個(gè)體，使得后代繼承父代的有效模式，從而有助于產(chǎn)生優(yōu)良個(gè)體。在交叉重組的過(guò)程中要避免

104、基因代碼差異較小的個(gè)體進(jìn)行交叉，防止“近親結(jié)合”，產(chǎn)生不良個(gè)體。</p><p>　　常見(jiàn)的幾種交叉操作有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉、均勻交叉、算術(shù)交叉等方法。</p><p><b>　　(4) 變異操作</b></p><p>　　變異操作通過(guò)隨機(jī)改變個(gè)體中某些基因而產(chǎn)生新個(gè)體，有助于增加種群的多樣性，避免早熟收斂。</p><

105、;p>　　常見(jiàn)的幾種變異操作有：點(diǎn)變異、均勻變異、正態(tài)變異、非一致性變異等方法。</p><p>　　遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過(guò)交叉和變異這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合，是指當(dāng)群體在進(jìn)行中陷于搜索空間中某個(gè)局部最優(yōu)而靠交叉不能擺脫時(shí)，通過(guò)變異操作可有助于跳出局部最優(yōu)解。所謂相互競(jìng)

106、爭(zhēng)，是指當(dāng)通過(guò)交叉已形成所期望的積木塊時(shí)，變異操作有可能破壞這些積木塊。因此交叉和變異操作要有效地配合使用。</p><p>　　3.5 求解FSP調(diào)度問(wèn)題的遺傳算法</p><p>　　3.5.1 遺傳算法的設(shè)計(jì)步驟</p><p>　　通常遺傳算法的設(shè)計(jì)是按以下步驟進(jìn)行的：</p><p>　　確定問(wèn)題的編碼方案。</p>

107、<p><b>　　確定適配值函數(shù)。</b></p><p><b>　　遺傳算子的設(shè)計(jì)。</b></p><p>　　算法參數(shù)的選取。主要包括種群數(shù)目、交叉與變異概率、進(jìn)化代數(shù)等。</p><p>　　確定算法的終止條件。</p><p>　　3.5.2 編碼方式</p>