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

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

1、編號(hào)：第六屆計(jì)算機(jī)仿真大賽參賽作品題號(hào):加工調(diào)度問題組別：高年級(jí)組作者：厚玉偉學(xué)院：光電工程聯(lián)系電話：18716321594計(jì)算機(jī)仿真大賽組委會(huì)2012年05月01日13生產(chǎn)調(diào)度問題及其優(yōu)化算法背景及摘要這是一個(gè)典型的Job-Shop動(dòng)態(tài)排序問題。目前調(diào)度問題的理論研究成果主要集中在以Job-Shop問題為代表的基于最小化完工時(shí)間的調(diào)度問題上。一個(gè)復(fù)雜的制造系統(tǒng)不僅可能涉及到成千上萬道車間調(diào)度工序，而且工序的變更又可能導(dǎo)致相當(dāng)大的調(diào)度規(guī)模。解空間容量巨大，N個(gè)工件、M臺(tái)機(jī)器的問題包含種排列。由于問題的連環(huán)嵌套性，使得用圖解方法也變得不切實(shí)際。傳統(tǒng)的運(yùn)籌學(xué)方法，即便在單目標(biāo)優(yōu)化的

2、靜態(tài)調(diào)度問題中也難以有效應(yīng)用。本文給出三個(gè)模型。首先通過貪婪法手工求得本問題最優(yōu)解，既而通過編解碼程序隨機(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)度系列問題的有效解決具有一定參考和借鑒價(jià)值。13二．模型假設(shè)1．每一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能被一臺(tái)機(jī)器所加工，同時(shí)加工過程為不間斷；2．所有機(jī)器均同時(shí)開工，且工件從機(jī)器I到機(jī)器J的轉(zhuǎn)移過程時(shí)間損耗不計(jì)；3．各工件必須按工藝路

3、線以指定的次序在機(jī)器上加工多次；4．操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限。三．符號(hào)說明及初始數(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í)間整理數(shù)據(jù)后得到：=[CABCD000]=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA]

4、[14735258]上述二陣直接從題目得出，而則是我們要求的。關(guān)于工件的加工時(shí)間表：(表二)產(chǎn)品/工件（i）:123456總計(jì)總凈加工時(shí)間（周期）441653544535247加工工序總數(shù)（個(gè)）54567835關(guān)于機(jī)器的加工時(shí)間表：(表三)機(jī)器/設(shè)備(j):ABCD總計(jì)總凈加工時(shí)間60427075247加工操作次數(shù)10610935分析：由于各產(chǎn)品總凈加工時(shí)間和各機(jī)器總凈加工時(shí)間之中最大值為1375，而總計(jì)為247，那么總時(shí)間C介于[75，247]。同時(shí)各工件加工繁雜程度不一，各機(jī)器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對(duì)于節(jié)省時(shí)間和資源是必要的。希望最優(yōu)化答案是75，這樣達(dá)到最

5、小值，如果答案是75，那么意味著機(jī)器D不間斷工作,直至全部加工任務(wù)完成。四．貪婪法快速求解如果按照一定規(guī)則排序，當(dāng)多個(gè)工件出現(xiàn)“搶占”同一機(jī)器的局面的時(shí)候,我們可以制定如下的工序安排規(guī)則:1.優(yōu)先選擇總剩余時(shí)間或總剩余操作較多的工件。（如果出現(xiàn)總剩余加工時(shí)間多者總剩余操作數(shù)反而較少的情況時(shí),按照程度具體情況具體分析）。2.機(jī)器方面來說,盡量避免等待空閑時(shí)間，優(yōu)先考慮剩余凈加工時(shí)間或者剩余加工總次數(shù)較多的機(jī)器,尤其是機(jī)器D,即倘若能夠使機(jī)器D不間斷工作且其他機(jī)器完工時(shí)間均不多余75時(shí),那么就可以得到最優(yōu)解。首先按照最優(yōu)化時(shí)間為75的設(shè)想避免D出現(xiàn)等待，排序后得到升以下具體排列順序

6、。各機(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-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)4(12-17)5(18-25)6(26-28)1(29-52)5(55-60)6(61-65)2(66-69)4(70-72)D5(1-10)3(11-17)4(18-38)5(3

7、9-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)(表四)(圖一)上圖為加工周期圖（甘特圖），標(biāo)注數(shù)字為相應(yīng)操作的周期，完工時(shí)間為第75周期。13五．計(jì)算機(jī)隨機(jī)模擬（編程）1．編碼：隨機(jī)產(chǎn)生生產(chǎn)的工序操作優(yōu)先順序，進(jìn)行編碼，如：K=[43566231416354536641551326224415665]（注：同時(shí)作為下文的染色體之用）意思為：工件4優(yōu)先被考慮進(jìn)行第一次操作，然后3進(jìn)行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次進(jìn)行。如果前后