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

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

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

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

3、產(chǎn)品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8(表一)條件：1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒；2、每臺(tái)設(shè)備在同一時(shí)間只能擔(dān)任一項(xiàng)任務(wù)。（每件產(chǎn)品的每個(gè)工序?yàn)橐粋€(gè)任務(wù)）問(wèn)題：做出生產(chǎn)安排，希望在盡可能短的時(shí)間里，完成所接受的全部任務(wù)。要求：給出每臺(tái)設(shè)備承擔(dān)任務(wù)的時(shí)間表。注：在上面，機(jī)器A，B，C，D即為機(jī)器1，2，3，4，程序中以數(shù)字1，2，3，4表示，說(shuō)明時(shí)則用A

4、，B，C，D12二．模型假設(shè)1．每一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能被一臺(tái)機(jī)器所加工，同時(shí)加工過(guò)程為不間斷；2．所有機(jī)器均同時(shí)開工，且工件從機(jī)器I到機(jī)器J的轉(zhuǎn)移過(guò)程時(shí)間損耗不計(jì)；3．各工件必須按工藝路線以指定的次序在機(jī)器上加工多次；4．操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限。三．符號(hào)說(shuō)明及初始數(shù)據(jù)表達(dá)分析-第i個(gè)工件（i=1…6）-機(jī)器順序陣表示i工件的第j個(gè)操作的機(jī)器號(hào)-第j臺(tái)機(jī)器（j=1…4）-工件排列陣表示i機(jī)器上第j次加工的工件號(hào)-加工時(shí)間陣為i工件的第j個(gè)操作的時(shí)間周期-整個(gè)任務(wù)完成時(shí)間整理

5、數(shù)據(jù)后得到：=[CABCD000]=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA][14735258]上述二陣直接從題目得出，而則是我們要求的。關(guān)于工件的加工時(shí)間表：(表二)產(chǎn)品/工件（i）:123456總計(jì)總凈加工時(shí)間（周期）441653544535247加工工序總數(shù)（個(gè)）54567835關(guān)于機(jī)器的加工時(shí)間表：(表三)機(jī)器/設(shè)備(j):ABCD總計(jì)總凈加工時(shí)間60427075

6、247加工操作次數(shù)10610935分析：由于各產(chǎn)品總凈加工時(shí)間和各機(jī)器總凈加工時(shí)間之中最大值為75，而總計(jì)為247，那么總時(shí)間C介于[75，247]。同時(shí)各工件加工繁雜程度不一，各機(jī)器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對(duì)于節(jié)省時(shí)間和資源是必要的。希望最優(yōu)化答案是75，這樣達(dá)到最小值，如果答案是75，那么意味著機(jī)器D不間斷工作,直至全部加工任務(wù)完成。12四．貪婪法快速求解如果按照一定規(guī)則排序，當(dāng)多個(gè)工件出現(xiàn)“搶占”同一機(jī)器的局面的時(shí)候,我們可以制定如下的工序安排規(guī)則:1.優(yōu)先選擇總剩余時(shí)間或總剩余操作較多的工件。（如果出現(xiàn)總剩余加工時(shí)間多者

7、總剩余操作數(shù)反而較少的情況時(shí),按照程度具體情況具體分析）。2.機(jī)器方面來(lái)說(shuō),盡量避免等待空閑時(shí)間，優(yōu)先考慮剩余凈加工時(shí)間或者剩余加工總次數(shù)較多的機(jī)器,尤其是機(jī)器D,即倘若能夠使機(jī)器D不間斷工作且其他機(jī)器完工時(shí)間均不多余75時(shí),那么就可以得到最優(yōu)解。首先按照最優(yōu)化時(shí)間為75的設(shè)想避免D出現(xiàn)等待，排序后得到升以下具體排列順序。各機(jī)器承擔(dān)任務(wù)表為(其中粗體字為對(duì)應(yīng)工件產(chǎn)品號(hào)，括號(hào)內(nèi)為對(duì)應(yīng)時(shí)間周期段)：操作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

8、-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