一種調(diào)度問題新的遺傳算法的設(shè)計與應(yīng)用.pdf

1、西安電子科技大學學位論文獨創(chuàng)性(或創(chuàng)新性)聲明秉承學校嚴謹?shù)膶W分和優(yōu)良的科學道德本人聲明所呈交的論文是我個人在導師指導下進行的研究工作及取得的研究成果盡我所知除了文中特別加以標注和致謝中所羅列的內(nèi)容以外論文中不包含其它人已經(jīng)發(fā)表或撰寫過的研究成果；也不包含為獲得西安電子科技大學或其它教育機構(gòu)的學位或證書而使用過的材料與我一同工作的同志對本研究所做的任何貢獻均已在論文中做了明確的說明并表示了謝意申請學位論文與資料若有不實之處本人承擔一切的

2、法律責任本人簽名：章玉瘟贛日期齟理：堡：￡!西安電子科技大學關(guān)于論文使用授權(quán)的說明本人完全了解西安電子科技大學有關(guān)保留和使用學位論文的規(guī)定即：研究生在校攻讀學位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學學校有權(quán)保留送交論文的復印件允許查閱和借閱論文；學?？梢怨颊撐牡膫悴炕虿糠謨?nèi)容可以允許采用影印、縮印或其它復制手段保存論文同時本人保證畢業(yè)后結(jié)合學位論文研究課題撰寫的文章一律署名單位為西安電子科技大學(保密的論文在解密后遵守此規(guī)定)本

3、學位論文屬于保密在一年解密后適用本授權(quán)書本人簽名：垃絲逐日期逝。么!z2導師簽名：鴨彳日期絲絲：生：絲㈨IIIIIIIIlllllIIIllIII1Y1865199摘要調(diào)度問題在計算機學科、管理學科和控制論學科等很多學科都有重要而廣泛的應(yīng)用，大多數(shù)調(diào)度問題通常都是非常難解的NP完全問題，對它們構(gòu)造有效算法十分困難，對小規(guī)模的問題，通常使用啟發(fā)式方法求出他們的近似最優(yōu)解，而對比較大規(guī)模的問題，還沒有十分有效的算法。因此對他們進行研究不僅有

4、重要的科學意義，而且有重要而廣泛的應(yīng)用價值。flowshop調(diào)度問題是如下的一類調(diào)度問題：設(shè)有m臺機器，n個零件(也稱為任務(wù)或工件)，每個工件都要依次經(jīng)過m臺機器進行加工，所有工件在每臺機器上均要按照一定的順序進行加工，本文考慮同順序的flow—shop調(diào)度問題，即所有工件在每一臺機器上的加工順序都相同，則問題為，當給定n個工件在每臺機器上的加工時間，如何確定n個工件在每臺機器上的加工順序才能使得加工完所有工件所用的時間最短當機器的臺數(shù)

5、多于兩臺時，在一般條件下，目前還沒有有效的求解方法。論文對這種調(diào)度問題進行了研究，主要工作如下：首先，在對問題進行全面分析的基礎(chǔ)上，給出了加工完所有工件所用時間的數(shù)學表達式，在此基礎(chǔ)上，建立了此問題的一個全局最優(yōu)化模型：加工時間極小化的優(yōu)化模型，該模型為一個極小極大優(yōu)化模型；其次，針對問題的特點和結(jié)構(gòu)，給出了適合此問題調(diào)度方案的編碼方法，并定義了適應(yīng)度函數(shù)；進一步，設(shè)計了一個新的雜交算子和變異算子，在此基礎(chǔ)上，設(shè)計了求解同順序flows

6、hop調(diào)度問題極小極大優(yōu)化模型的一個新的遺傳算法。最后，對一個企業(yè)的實際調(diào)度問題建立了同順序flowshop調(diào)度問題的極小極大優(yōu)化模型，對此模型用所提算法進行了求解，所得方案將企業(yè)每月加班加點每天不停生產(chǎn)也難以完成任務(wù)的狀況改進到每月只需265天的時間便可完成任務(wù)，該調(diào)度方案極大地改進了企業(yè)目前所用的方案，可以滿足企業(yè)的要求。另外，對5個試驗問題也進行了數(shù)值模擬，結(jié)果表明了算法的可行性和有效性。關(guān)鍵詞：Flowshop調(diào)度遺傳算法進化計