matlab生產(chǎn)調(diào)度問題及其優(yōu)化算法.doc

《matlab生產(chǎn)調(diào)度問題及其優(yōu)化算法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、生產(chǎn)調(diào)度問題及其優(yōu)化算法（采用遺傳算法與MATLAB編程）信息014孫卓明二零零三年八月十四日生產(chǎn)調(diào)度問題及其優(yōu)化算法背景及摘要這是一個典型的Job-Shop動態(tài)排序問題。目前調(diào)度問題的理論研究成果主要集中在以Job-Shop問題為代表的基于最小化完工時間的調(diào)度問題上。一個復(fù)雜的制造系統(tǒng)不僅可能涉及到成千上萬道車間調(diào)度工序，而且工序的變更又可能導(dǎo)致相當(dāng)大的調(diào)度規(guī)模。解空間容量巨大，N個工件、M臺機(jī)器的問題包含種排列。由于問題的連環(huán)嵌套性，使得用圖解方法也變得不切實際。傳統(tǒng)的運(yùn)籌學(xué)方法，即便在單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。本文給出三個模型。首先通過貪婪法手工求得本

2、問題最優(yōu)解，既而通過編解碼程序隨機(jī)模擬優(yōu)化方案得出最優(yōu)解。最后采用現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢的遺傳算法。文章有針對性地選取遺傳算法關(guān)鍵環(huán)節(jié)的適宜方法，采用MATLAB軟件實現(xiàn)算法模擬，得出優(yōu)化方案，并與計算機(jī)隨機(jī)模擬結(jié)果加以比較顯示出遺傳算法之優(yōu)化效果。對車間調(diào)度系列問題的有效解決具有一定參考和借鑒價值。一．問題重述某重型機(jī)械廠產(chǎn)品都是單件性的，其中有一車間共有A，B，C，D四種不同設(shè)備，現(xiàn)接受6件產(chǎn)品的加工任務(wù)，每件產(chǎn)品接受的程序在指定的設(shè)備上加工，其工序與加工周期如下表：（S-設(shè)備號、T-周期）工序產(chǎn)品12345678STSTSTSTSTSTSTST1C8A2B4C

3、24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8(表一)條件：1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒；2、每臺設(shè)備在同一時間只能擔(dān)任一項任務(wù)。（每件產(chǎn)品的每個工序為一個任務(wù)）問題：做出生產(chǎn)安排，希望在盡可能短的時間里，完成所接受的全部任務(wù)。要求：給出每臺設(shè)備承擔(dān)任務(wù)的時間表。注：在上面，機(jī)器A，B，C，D即為機(jī)器1，2，3，4，程序中以數(shù)字1，2，3，4表示，說明時則用A，B，C，D二．模型假設(shè)1．每一時刻，每臺機(jī)器只能加工一個工件，且每個工件只能被一臺機(jī)器所加工，同時

4、加工過程為不間斷；2．所有機(jī)器均同時開工，且工件從機(jī)器I到機(jī)器J的轉(zhuǎn)移過程時間損耗不計；3．各工件必須按工藝路線以指定的次序在機(jī)器上加工多次；4．操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限。三．符號說明及初始數(shù)據(jù)表達(dá)分析-第i個工件（i=1…6）-機(jī)器順序陣表示i工件的第j個操作的機(jī)器號-第j臺機(jī)器（j=1…4）-工件排列陣表示i機(jī)器上第j次加工的工件號-加工時間陣為i工件的第j個操作的時間周期-整個任務(wù)完成時間整理數(shù)據(jù)后得到：=[CABCD000]=[824246000][ADBC0000][45340000][CDABA000][37152080

5、00][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA][14735258]上述二陣直接從題目得出，而則是我們要求的。關(guān)于工件的加工時間表：(表二)產(chǎn)品/工件（i）:123456總計總凈加工時間（周期）441653544535247加工工序總數(shù)（個）54567835關(guān)于機(jī)器的加工時間表：(表三)機(jī)器/設(shè)備(j):ABCD總計總凈加工時間60427075247加工操作次數(shù)10610935分析：由于各產(chǎn)品總凈加工時間和各機(jī)器總凈加工時間之中最大值為75，而總計為247，那么總時間C介于[75，247]。同時各工件加工繁雜

6、程度不一，各機(jī)器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對于節(jié)省時間和資源是必要的。希望最優(yōu)化答案是75，這樣達(dá)到最小值，如果答案是75，那么意味著機(jī)器D不間斷工作,直至全部加工任務(wù)完成。四．貪婪法快速求解如果按照一定規(guī)則排序，當(dāng)多個工件出現(xiàn)“搶占”同一機(jī)器的局面的時候,我們可以制定如下的工序安排規(guī)則:1.優(yōu)先選擇總剩余時間或總剩余操作較多的工件。（如果出現(xiàn)總剩余加工時間多者總剩余操作數(shù)反而較少的情況時,按照程度具體情況具體分析）。2.機(jī)器方面來說,盡量避免等待空閑時間，優(yōu)先考慮剩余凈加工時間或者剩余加工總次數(shù)較多的機(jī)器,尤其是機(jī)器D,即倘若能夠使機(jī)器D不間斷工作且其他機(jī)器完

7、工時間均不多余75時,那么就可以得到最優(yōu)解。首先按照最優(yōu)化時間為75的設(shè)想避免D出現(xiàn)等待，排序后得到升以下具體排列順序。各機(jī)器承擔(dān)任務(wù)表為(其中粗體字為對應(yīng)工件產(chǎn)品號，括號內(nèi)為對應(yīng)時間周期段)：操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6(1)2(2-5)1(12-13)6(14-20)3(21-35)4(36)5(43-54)6(55-56)3(57-64)6(66-73)B4(1-7)6(8-11)5(12-15)1(16-19)3(36-55)2(56-58)C3(1-3)1(4-11)