基于遺傳算法求解作業(yè)車間調(diào)度問題畢業(yè)論文

《基于遺傳算法求解作業(yè)車間調(diào)度問題畢業(yè)論文》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、t商要錯(cuò)誤!未定義書簽。Abstract錯(cuò)誤!未定義書簽。1緒論11.1嬲鎌11.2作業(yè)車間調(diào)度問題表述11.3車間作業(yè)調(diào)度問題研究的假設(shè)條件及數(shù)學(xué)模型21.3.1車間作業(yè)調(diào)度問題研究的假設(shè)條件21.3.2車間作業(yè)調(diào)度問題的數(shù)學(xué)模型31.4課題研究內(nèi)容及結(jié)構(gòu)安排42遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù)62.1自然進(jìn)化與遺傳算法62.2基本遺傳算法72.2.1遺傳算法的基本思路72.2.2遺傳算法的模式定理72.2.3遺傳算法的收斂性分析92.2.4基本遺傳算法參數(shù)說明102.3遺傳算法的優(yōu)缺點(diǎn)112.3.1遺傳算法的優(yōu)點(diǎn)H2.3.2遺傳算法的缺點(diǎn)112.4遺傳算法的

2、進(jìn)展122.5小結(jié)3用遺傳算法對具體問題的解決與探討15163.1研究過程中的幾個(gè)關(guān)鍵問題163.1.1設(shè)備死鎖現(xiàn)象163.1.2參數(shù)編碼163.1.3初始種群的生成193.1.4個(gè)體的適應(yīng)度函數(shù)203.1.5算法參數(shù)203.1.6遺傳算子的設(shè)計(jì)213.2遺傳算法終止條件243.3遺傳算法解決車間調(diào)度問題的改進(jìn)243.4系統(tǒng)仿真243.5小結(jié)29結(jié)論30致錯(cuò)誤!未定義書簽。參考文獻(xiàn)31附錄321緒論1.1課題來源隨著加入WTO,市場競爭越來越激烈，對制造企業(yè)來說，為了能夠在競爭屮立于不敗，降低成木是不得不面臨的問題，而確保生產(chǎn)車間較高的生產(chǎn)能力和效率，是當(dāng)

3、務(wù)之急。此外，有效的調(diào)度方法己經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)和關(guān)鍵，所以對它的研究具有重要的理論和實(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)和趨勢。所謂生產(chǎn)調(diào)度，即對生產(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ù)、自動化與計(jì)算機(jī)技術(shù)發(fā)展的核心，有效的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用，是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。雖然對其研究已有幾十年的

4、歷史但至今尚未形成一套系統(tǒng)的方法和理論，理論研宄與實(shí)際應(yīng)用之間還存在著較大距離。目前的調(diào)度算法大多只關(guān)心工件的調(diào)度問題，而對其它資源分配問題則研究相對不多，將二者結(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)典

5、的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù)有更強(qiáng)的優(yōu)越性，因?yàn)樗粌H能解決某一特定問題，而且可以適應(yīng)不同的問題形式［2］。1.2作業(yè)車間調(diào)度問題表述作業(yè)車間調(diào)度（job-shop）問題可以表述為：設(shè)有N個(gè)工件在M臺機(jī)器上加工，根據(jù)工件加工工藝的要求，每個(gè)工件使用機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問題的目標(biāo)就是如何選擇加工順序使得總的加工時(shí)間最短最優(yōu)。前提假設(shè)［3］:1.每一臺機(jī)器每次只能加工一個(gè)工件，每一個(gè)工件在機(jī)器上的加工被成為一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序數(shù)不大于設(shè)備數(shù)；4.每道工序必須在指定的某種設(shè)備上加工；5

6、.任何作業(yè)沒有搶先加工的優(yōu)先權(quán)；6.在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件；調(diào)度問題具有相當(dāng)?shù)碾y度，目前調(diào)度問題的理論研宄成果主要在job-shop問題為代表的基于最小完工時(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ī)模的基于單0標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。木文從實(shí)際和理論兩方面進(jìn)行

7、研究和深入，重點(diǎn)研究了現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢的遺傳算法。車間作業(yè)是指利用車間資源（如機(jī)床、刀具、夾具等）完成的某項(xiàng)任務(wù)。在實(shí)際生產(chǎn)中，這項(xiàng)任務(wù)可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工。而在木文中，為了研宄方便，我們將這項(xiàng)任務(wù)限定為加工一批工件。在此基礎(chǔ)上，可對車間作業(yè)調(diào)度問題進(jìn)行一般性的描述:假定有多個(gè)工件，要經(jīng)過多臺機(jī)器加工。一個(gè)工件在一臺機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工吋間稱為該工序的“加工吋間”。用事先給定的“加工路線”表示工件加工時(shí)技術(shù)上的約束，即工件的加工工藝過程。用“加工順序”表示各臺機(jī)器上各個(gè)工件加工的先后順序。車間

8、作業(yè)調(diào)度問題屮，每個(gè)工件都有獨(dú)特的加工路線［5］。它所要解決的問題