基于.遺傳算法求解作業(yè)車間調(diào)度問題-生產(chǎn)運作實踐

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

1、生產(chǎn)運作實踐大作業(yè)24目錄目錄0問題一：基于遺傳算法求解作業(yè)車間調(diào)度問題21．問題介紹21.1作業(yè)車間調(diào)度問題表述21.2作業(yè)車間調(diào)度問題研究的假設條件21.3車間作業(yè)調(diào)度問題的數(shù)學模型32.基本遺傳算法42.1遺傳算法的基本思路42.2基本遺傳算法參數(shù)說明43.用遺傳算法對具體問題的解決53.1參數(shù)編碼53.2初始種群的生成63.3個體的適應度函數(shù)63.4遺傳算子的設計73.5遺傳算法終止條件84．模型的求解85．結(jié)論總結(jié)106.附錄10問題二：郵政運輸網(wǎng)絡中的郵路規(guī)劃和郵車調(diào)度181.問題描述182.

2、模型建立182.1模型的基本假設182.2符號說明192.3模型分析202.4模型的建立203.模型的求解213.1求解思路213.2求解算法2224問題一：基于遺傳算法求解作業(yè)車間調(diào)度問題1．問題介紹1.1作業(yè)車間調(diào)度問題表述作業(yè)車間是指利用車間資源完成的某項任務，在實際生產(chǎn)中，這項任務可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工，為了研究方便，我們將這項任務限定為加工一批工件。在此基礎(chǔ)上，可對作業(yè)車間調(diào)度問題進行一般性的描述:假定有N個工件，要經(jīng)過M臺機器加工,一個工件在一臺機器上的加工程序稱為一道

3、“工序”，相應的加工時間稱為該工序的“加工時間”,用事先給定的“加工路線”表示工件加工時技術(shù)上的約束，即工件的加工工藝過程,用“加工順序”表示各臺機器上各個工件加工的先后順序。在車間作業(yè)調(diào)度問題中，每個工件都有獨特的加工路線，我們要解決的問題就是如何分配N個零件在M個機器上的加工順序以使得總的加工時間最短。1.2作業(yè)車間調(diào)度問題研究的假設條件在研究一般的作業(yè)車間調(diào)度問題中往往需要明確兩類重要假設條件:1.工藝路徑約束:工件的任一工序必須在其前道工序完成后才能開始，并保證同一工件不會同時在兩臺機器上加工，反

4、映了工件不同工序間的時序關(guān)系;2.資源獨占性約束:任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關(guān)系。根據(jù)上面以及求解方便，我們做出以下具體假設：1.每一臺機器每次只能加工一個工件，每一個工件在機器上的加工被成為一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序數(shù)不大于設備數(shù)；4.每道工序必須在指定的某種設備上加工，所有機器處理的加工類型均不同；5.在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件；6.不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的

5、；7.工序允許等待，即前一個工序未完成，則后面工序需要等待；8.工件的加工時間事先給定，且在整個加工過程中保持不變。1.3車間作業(yè)調(diào)度問題的數(shù)學模型24建立車間作業(yè)調(diào)度問題的數(shù)學模型，是我們研究該問題的出發(fā)點，同時也為其后的研究奠定了基礎(chǔ)。假設有n個工件，要在m臺機器上加工，每個工件有Pi道工序，每臺機器上總共要加工Lj道工序。我們定義以下基本數(shù)學符號［6］：J:所有工件的集合，；M:所有機器的集合，；：工件Ji的工序集合，；P:所有工序的集合，此為矩陣。P（i，j）表示i工件的第j道工序。，表示i工件的

6、所有工序按優(yōu)先順序的排列。不足，那么其空余的位置用0填滿。（1.1）:機器順序陣，此為矩陣。（i，j）表示i工件的第j道工序的機器號，表示i工件的所有工序按優(yōu)先順序加工的各機器號的排列。注意:如果某工件的工序數(shù)不足，那么其空余的位置用0填滿。（1.2）T:加工時間陣，此為矩陣。T(i,j)表示工件i的第j道工序在（i，j）上的加工時間。同樣地，如果某工件的工序數(shù)不足，那么其空余的位置用0填滿。（1.3）：工件排列陣，此為矩陣。表示在i機器上排在第j位24加工的工件號，表示i機器上依次加工的各工件的排列。同

7、上，如果某工件的工序數(shù)不足，那么其空余的位置用0填滿。事實上，工件排列陣就是調(diào)度的一種表示形式。由此，我們可以給出一般性的車間作業(yè)調(diào)度數(shù)學模型的定義:如果對應于一個確定的，滿足或。即使得目標函數(shù)取值最小(或最大)，且與相容，則稱為車間作業(yè)調(diào)度問題在此目標函數(shù)下的最優(yōu)解。2.基本遺傳算法遺傳算法是一種基于自然群體遺傳演化機制的高效探索算法，由美國學者Holland于1975年首先提出來的，通過模擬達爾文的遺傳選擇和自然淘汰的生物進化過程來求解。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編

8、碼成符號串形式，對群體反復進行基于遺傳學的操作（遺傳，交叉和變異），根據(jù)預定的目標適應度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。2.1遺傳算法的基本思路1.首先確定問題的求解空間；2.將求解空間中的每一個點進行編碼，并從求解空間中任選N個點組成初始群體；3.計算當前群體中每個個體的適應度函數(shù)值，然后運用選擇、交叉、變異