【正文】 ......................................................................... 11 遺傳算法的缺點(diǎn) ............................................................................................. 11 遺傳算法的進(jìn)展 ....................................................................................................... 12 小結(jié) ........................................................................................................................... 15 3 用遺傳算法對(duì)具體問題的解決與探討 .................................................................. 16 研究過程中的幾個(gè)關(guān)鍵問題 ................................................................................... 16 設(shè)備死鎖現(xiàn)象 ................................................................................................. 16 參數(shù)編碼 ......................................................................................................... 16 初始種群的生成 ............................................................................................. 19 個(gè)體的適應(yīng)度函數(shù) ......................................................................................... 20 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 VI 頁(yè) 算法參數(shù) ......................................................................................................... 20 遺傳算子的設(shè)計(jì) ............................................................................................. 21 遺傳算法終止條件 ................................................................................................... 24 遺傳算法解決車間調(diào)度問題的改進(jìn) ....................................................................... 24 系統(tǒng)仿真 ................................................................................................................... 24 小結(jié) ........................................................................................................................... 29 結(jié) 論 ....................................................................................................................................... 30 致 謝 ....................................................................................................................................... 31 參考文獻(xiàn) ................................................................................................................................ 32 附 錄 ....................................................................................................................................... 33 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 1 頁(yè) 1 緒論 課題來源 隨著加入 WTO，市場(chǎng)競(jìng)爭(zhēng)越來越激烈，對(duì)制造企業(yè)來說，為了能夠在競(jìng)爭(zhēng)中立于不敗，降低成本是不得不面臨的問題，而確保生產(chǎn)車間較高的生產(chǎn)能力和效率，是當(dāng)務(wù)之急。此外，有效的調(diào)度方法已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)和關(guān)鍵，所以對(duì)它的研究具有重要的理論和實(shí)用價(jià)值。 當(dāng)前科學(xué)技術(shù)正進(jìn)入多學(xué)科互相交叉、互相滲透、互相影響的時(shí)代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進(jìn)是其中一個(gè) 典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個(gè)顯著特點(diǎn)。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨勢(shì)。 所謂生產(chǎn)調(diào)度，即對(duì)生產(chǎn)過程進(jìn)行作業(yè)計(jì)劃，作為一個(gè)關(guān)鍵模塊，是整個(gè)先進(jìn)生產(chǎn)制造系統(tǒng)實(shí)現(xiàn)管理技術(shù)、運(yùn)籌方法、優(yōu)化技術(shù)、自動(dòng)化與計(jì)算機(jī)技術(shù)發(fā)展的核心，有效的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用，是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。 雖然對(duì)其研究已有幾十年的 歷史 但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實(shí)際應(yīng)用之間還存在著較大距離。目前的調(diào)度算法大多只關(guān)心工件的調(diào)度問題，而對(duì)其它資源分配問題則研究相對(duì)不多，將二者 結(jié)合起來研究應(yīng)該是值得注意的問題，目前已有不少學(xué)者開始關(guān)注該問題。 由于一般車間調(diào)度問題的復(fù)雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。由于遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法 ［ 1］ 。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題。一些學(xué)者們經(jīng)過大量的實(shí)踐證明了 遺傳算法在解決作業(yè)車間調(diào)度問題上 比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù) 有更強(qiáng)的 優(yōu)越 性，因?yàn)樗粌H能解決某一特定問題，而且可以適應(yīng)不同的問 題形式 ［ 2］ 。 作業(yè) 車間調(diào)度問題表述 作業(yè)車間調(diào)度（ jobshop）問題可以表述為：設(shè)有 N個(gè)工件在 M臺(tái)機(jī)器上加工，根據(jù)工件加工工藝的要求，每個(gè)工件使用 機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問題的目標(biāo)就是如何選擇加工順序使得總的加工時(shí)間最短最優(yōu)。 前提假設(shè) ［ 3］ ： 1. 每一臺(tái)機(jī)器每次只能加工一個(gè)工件，每一個(gè)工件在機(jī)器上的加工被成為一道工 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 2 頁(yè) 序。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序數(shù)不大于設(shè)備數(shù)； 4. 每道工序必須在指定的某種設(shè)備上加工； 5. 任何作業(yè)沒有搶先加工的優(yōu)先權(quán) ； 6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件； 調(diào)度問題具有相當(dāng)?shù)碾y度，目前調(diào)度問題的理論研究成果主要在 jobshop 問題為代表的基于最小完工時(shí)間的調(diào)度問題上。 求解調(diào)度問題的方法稱為調(diào)度優(yōu)化算法。它可分為精確求解方法和近視求解方法。其中精確求解方法包括解析方法、窮舉方法（包括分支定界）等；近似求解方法包括基于規(guī)則的構(gòu)造性方法、鄰域搜索算法（如進(jìn)化遺傳算法，模擬退火算法）以及人工智能方法（如神經(jīng)網(wǎng)絡(luò)） ［ 4］ 等。而傳統(tǒng)的運(yùn)籌學(xué)方法，即便在較大規(guī)模的基于單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用 。本文從實(shí)際和理論兩方面進(jìn)行研究和深入，重點(diǎn)研究了現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢(shì)的遺傳算法 。 車間作業(yè)是指利用車間資源 (如機(jī)床、刀具、夾具等 )完成的某項(xiàng)任務(wù)。在實(shí)際生產(chǎn)中，這項(xiàng)任務(wù)可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工。而在本文中，為了研究方便，我們將這項(xiàng)任務(wù)限定為加工一批工件。在此基礎(chǔ)上，可對(duì)車間作業(yè)調(diào)度問題進(jìn)行一般性的描述 :假定有多個(gè)工件，要經(jīng)過多臺(tái)機(jī)器加工。一個(gè)工件在一臺(tái)機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工時(shí)間稱為該工序的“加工時(shí)間”。用事先給定的“加工路線”表示工件加工時(shí)技術(shù)上的約束 ，即工件的加工工藝過程。用“加工順序”表示各臺(tái)機(jī)器上各個(gè)工件加工的先后順序。車間作業(yè)調(diào)度問題中，每個(gè)工件都有獨(dú)特的加工路線 ［ 5］ 。它所要解決的問題就是確定每臺(tái)機(jī)器上不同工件的加工順序，以及每個(gè)工件的所有工序的起始加工時(shí)間，以最優(yōu)化某個(gè)性能指標(biāo)。 車間作業(yè)調(diào)度問題研究的假設(shè)條件及數(shù)學(xué)模型 車間作業(yè)調(diào)度問題研究的假設(shè)條件 在研究一般的車間作業(yè)調(diào)度問題中往往需要明確兩類重要假設(shè)條件 : :工件的任一工序必須在其前道工序完成后才能開始，并保證同一工件不會(huì)同時(shí)在兩臺(tái)機(jī)器上 加工，反映了工件不同工序間的時(shí)序關(guān)系 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 3 頁(yè) (機(jī)器 )獨(dú)占性約束 :任一臺(tái)機(jī)器每次只能加工一個(gè)工件，且一旦開工就不能中斷，反映了加工隊(duì)列中工件間的時(shí)序關(guān)系。 此外，還有一些輔助假設(shè)條件，如下 : 1. 各工件經(jīng)過其準(zhǔn)備時(shí)間后可開始加工 。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的 。 3. 工序允許等待，即前一個(gè)工序未完成，則后面工序需要等待 。 4. 所有機(jī)器處理的加工類型均不同 。 5. 工件的加工時(shí)間事先給定，且在整個(gè)加工過程中保持不變 。 6. 緩沖區(qū)容量為無窮大。 車間作業(yè) 調(diào)度問題的數(shù)學(xué)模型 建立車間作業(yè)調(diào)度問題的數(shù)學(xué)模型，是我們研究該問題的出發(fā)點(diǎn)，同時(shí)也為其后的研 究奠定了基礎(chǔ)。 假設(shè)有 n個(gè)工件，要在 m臺(tái)機(jī)器上加工，每個(gè)工件有 Pi 道工序，每臺(tái)機(jī)器上總共要加工 Lj 道工序。我們定義以下基本數(shù)學(xué)符號(hào) ［ 6］ ： J:所有工件的集合， 12{ , , }nJ J J J? ； M:所有機(jī)器的集合， 12{ , , }mM M M M? ； ijP： 工件 Ji 的工序集合， 12{ , , }i i i i ij j j j pP P P P?； P:所有工序的集合，此為 12m ax{ , , }nn P P P? 矩陣。 P（ i， j） 表 示 i工件的第 j 道工序。 ( , )ijPi P??，表示 i 工件的所有工序按優(yōu)先順序的排列。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 1 11 1 1 111121 2 ( 1 )110 0 000in n n n iiiP PPj j j Pj j j p j PPPPP P PPP P P P?????????????? （ ） MJ :機(jī)器順序陣， 此為 12m ax{ , , }nn P P P? 矩陣。 MJ （ i， j）表示 i工件的第 j 道工序的機(jī)器號(hào)， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機(jī)器號(hào)的排列。注意 : 如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0填滿 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 4 頁(yè) 1 11 2 1 1111 2 1 ( 1 )1 1100 000ijPjjjpj j n j Pn n n iiiP PPP P PMP P P PPPPM M MJM M M M?????????????? （ ） T:加工時(shí)間陣，此為 12m ax{ , , }nn P P P? 矩陣。 T(i, j)表示工件 i的第 j 道工序在