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

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臺機器的問題包含（N!）M種排列。由于問題的連環(huán)嵌套性，使得用圖解方法也變得不切實際。傳統(tǒng)的運籌學(xué)方法，即便在單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。本文給出三個模型。首先通過貪婪法手工求得本問題最優(yōu)

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

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

4、從機器I到機器J的轉(zhuǎn)移過程時間損耗不計;3 .各工件必須按工藝路線以指定的次序在機器上加工多次；4 .操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限.符號說明及初始數(shù)據(jù)表達分析(i=1.6)JM(i,j)表示i工件的第j個操作的機器號(j=1,4)Mj(i,j)表示i機器上第j次加工的工件號T(i,j)為i工件的第j個操作的時間周期C-整個任務(wù)完成時間整理數(shù)據(jù)后得到:T=8242460004534000037152080007621116300104841261014735258上述二陣直接從題目得出，而M則是我們要求的。J關(guān)于工件的加工時間表：(表二)產(chǎn)品/工件(i):1

5、23456總計Ji總凈加工時間(周期)441653544535247Ji加工工序總數(shù)(個)54567835關(guān)于機器的加工時間表：(表三)機器/設(shè)備(j)：ABCD總計Mj總凈加工時間60427075247Mj加工操作次數(shù)10610935分析：由于各產(chǎn)品總凈加工時間和各機器總凈加工時間之中最大值為75,而總計為247,那么總時間C介于75,247。同時各工件加工繁雜程度不一，各機器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對于節(jié)省時間和資源是必要的。希望最優(yōu)化答案是75,這樣達到最小值，如果答案是75,那么意味著機器D不間斷工作,直至全部加工任務(wù)完成。Ji-第i個工件JM-機器順序陣Mj-第j臺機器

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

7、避免D出現(xiàn)等待，排序后得到開以下具體排列順序。各機器承擔(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)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-

8、17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)（表四）（圖一）上圖為加工周期圖（甘特圖），標(biāo)注數(shù)字為相應(yīng)操作的周期，完工時間為第75周期A機器B機器C機器D機器1020304050607080五.計算機隨機模擬（編程）1.編碼：隨機產(chǎn)生生產(chǎn)的工序操作優(yōu)先順序，進行編碼，如：K=43566231416354536641551326224415665（注：同時作為下文的染色體之用）意思為：工件4優(yōu)先被考慮進行第一次操作，然后3進行其第一步操作，然后5操作，6操作，冉6操作其第二步工序，依次進行。如果前后互相不沖突，則可同時在不同機器

9、上操作。通過排列組合得出，總共有類似K的排列序列2父1023多種！當(dāng)然,這其中只對應(yīng)解75,247,意味著有大量排列序列對應(yīng)同一加工方案， 而大量加工方案又對應(yīng)同一時間解。2 .解碼：即對編碼進行翻譯，產(chǎn)生具體可操作工序安排方案，這里采用活動化解碼算法。例如工件2第i步操作（記為JM（2,i）,且在機器A上進行）被安排在工件3第j步操作（記為JM（3,j）后面進行，那么如果安排好JM（3,j）后，只要JM（2,i）在工件2已經(jīng)排序好的操作之后進行，那么操作JM（2,i）可插入到機器A處最前可安置的時間段進行。在這里，一個編碼序列對應(yīng)一個加工方案，而一個加工方案可對應(yīng)一個或多個編碼序列，這就是二

10、者之關(guān)系。3 .編程：通過一組隨機編碼產(chǎn)生一生產(chǎn)加工優(yōu)先序列，通過解碼過程產(chǎn)生相應(yīng)加工方案及其總耗費時間C.N次模擬后即可得出解C的概率密度分布情況以及相對最優(yōu)解 （N個C的最小值，如80,77等，甚至出現(xiàn)75）。4.計算機模擬所得數(shù)據(jù)分析a.進行100次模擬得出最優(yōu)解情況：（共運行10次）82,83,82,84,78,80,81,83,87,82平均值82.2,每回耗時約3秒b.進行1000次模擬得出最優(yōu)解情況：（共運行10次）80,79,78,78,79,79,76,80,77,78平均值78.4,每回耗時25秒c.進行10000次模擬得出最優(yōu)解情況：（共運行10次）76,77,77,75

11、,76,76,77,76,76,77平均值76.3,每回耗時4分鐘d.模擬1000000次得到的解C的概率密度分布情況為：（如圖二所示）（注：75處為17次（概率為17/1000000=1/58823）,76處為40次，77處167次）結(jié)論：如果想將2父1023中排序序列以平均出現(xiàn)一次的可能性進行模擬，即運行2父1023次，計算機需運行將近150萬億年！當(dāng)然，我們沒有這個必要，因為我們只需要運行數(shù)萬次，就很可能得到最優(yōu)解75,（在隨機模擬1000000次后出現(xiàn)17次75,那么意味著概率大約17/1000000=1/58823,另外76處為40次，77處167次）。六.遺傳算法模型建立和步驟解法

12、遺傳算法（GeneticAlgorithm）作為一種優(yōu)化算法特別適合于對象模型難于建立、搜索空間非常龐大的復(fù)雜問題的優(yōu)化求解。它和模糊控制技術(shù)一樣，雖然在理論上還沒有完善，但是在實踐中已經(jīng)得到了廣泛的應(yīng)用。遺傳算法的基本思想是：模仿生物系統(tǒng)適者生成”的原理，通過選擇、復(fù)制、交叉、變異等簡單操作的多次重復(fù)來達到去劣存優(yōu)的目的，從而獲得問題的優(yōu)化結(jié)果。遺傳算法的實現(xiàn)由兩個部分組成，一是編碼與解碼，二是遺傳操作。其中遺傳操作又包括選擇、復(fù)制、交叉、變異等步驟。本文根據(jù)實際情況采取了1-6整數(shù)編碼。數(shù)字1,2,3,4,5,6分別代表6件待加工產(chǎn)品。本文遺傳算法基本流程：通過編碼，解碼程序隨機產(chǎn)生N個（

13、有一定數(shù)量，如50或100）個體構(gòu)成初始種群a）從初始中群中選取2個具有最優(yōu)染色體（最有排序方案）的個體作為臨時個體（父代）；b）如果此2個體中有一個個體通過解碼操作能夠?qū)崿F(xiàn)最優(yōu)排序（即使總時間為75周期），那么結(jié)束此算法，得到最優(yōu)解；c）對2個臨時個體以一定方式（循環(huán)交叉）執(zhí)行染色體交叉變換和變異選擇（小概率，互換操作），產(chǎn)生2個新的個體；d）對父代和子代共4個個體進行選擇，從中選出最佳的2個個體，做為下一代的父代；e）重復(fù)執(zhí)行第二步（b）操作；f）如果執(zhí)行完M步后仍然未得出答案75,那么將目前的最優(yōu)解作為本算法的最優(yōu)解答案。1.編碼和解碼(同上)2 .交叉變換(crossover)對2個父

14、代臨時個體進行染色體交叉變換，采用循環(huán)交叉方法(CyclecrossoverCX),如父代染色體為：X:926473581和Y:345816729,如果隨機選到第二位開始交叉，那么X的2對應(yīng)Y的4,X的4對應(yīng)Y的8,X的8對應(yīng)Y的2,這樣就確定了以上為不變的染色體，其余位置的染色體互換位置，最后得到X:325416789,、:946873521,實現(xiàn)交叉變換。3 .變異選擇(mutation)采用互換操作(SWAP,即隨機交換染色體中兩不同基因的位置。如上面的染色體為：X:325416789。隨機產(chǎn)生變換位置號，如產(chǎn)生隨機數(shù)3和5,那么交換數(shù)字后得到染色體：321456789,變異概率取0.1

15、。4 .選擇操作(selection)對父代2個體f1,f2和子代2個體f3,f4進行選擇，通過編碼操作確定具有最優(yōu)解的2個個體，成為新一代f1和f2。如此，通過多次編碼和解碼隨機產(chǎn)生一定數(shù)量的個體，選取2個最佳個體進行交叉變換操作，產(chǎn)生2個新個體，然后對4個個體進行選擇，產(chǎn)生下一代，如果某時刻通過解碼操作得出最優(yōu)解(所有解的下限，這里是75周期)，那么算法結(jié)束，否則循環(huán)進行，直至預(yù)先給定的循環(huán)次數(shù)達到為止，以最后得到的最優(yōu)解作為最終最優(yōu)解。七.遺傳算法模擬(采用主程序如下：(子程序見略)%本程序為主程序，調(diào)用以下各分支程序task=Welcome!Waitamomentplease!-Wri

16、ter:f1=zeros(1,35);f2=zeros(1,35);whilef1=f2;%minminmax1,s1=chushijie(N)；%f1=s1;minminmax1,%minminmax2,s2=chushijie(N);%f2=s2;minminmax2,%end;fore=1:M%e=1:MD=jiaocha(f1,f2);%f1;f2;f3,f4=jiaocha_bianyi(f1,f2,D);%f3;f4;MATLAB:具編程)孫卓明，信息 014,此步避免初始染色體f1,f2相同， 導(dǎo)致以下死循環(huán)種群初始化；基于操作的編碼策略；活動化解碼算法;chushijie(N)

17、參數(shù) N為初始種群數(shù)選取的第一個初始個體再次種群初始化選取的第二個初始個體進行 M 次遺傳操作(交叉-變異-選擇)交叉變化(循環(huán)交叉操作，cyclecrossoverCX),選取“染色體”無需變動部分基因生成交叉后的“染色體”，并進行變異選擇選擇：又父代 f1,f2 和子代 f3,f4 進行解碼，得出 2 個較優(yōu)個體，成為下一代的父代f1,f2=xuanze(f1,f2,f3,f4);%f1;f2;minmaxf1,a1,b1=tongbujinzhan(f1);%ifminmaxf1=75;求該時刻個體 f1 的最優(yōu)時間（因為 f1 優(yōu)于 f2）f1,a1,b1,minminmax1,min

18、minmax2,minminmax_last=minmaxf1,task=Finish!Successful!Bestanswer!Congratulation!,return;end;end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,ifminminmax_last=90;task=Finish!Actionagainplease!,end;ifminminmax_last=80&minminmax_last90;task=Finish!,end;ifminminmax_last80;task=Finish!Succ

19、essful!,end;八.遺傳算法模擬結(jié)果首先給出最優(yōu)方案：在進行某次n=100,m=200的操作后得到模擬最優(yōu)結(jié)果75周期時間：minminmax1=83minminmax2=78(二個初始較優(yōu)個體解)f1=45663136456132545315264564664322511(f1為各工件優(yōu)先選擇順序排列，即“染色體”)a1=535396400000(a1,b1為四臺機器空閑周期段)15240000000175365000000000000000b1=113842650000020350000000185468000000000000000minminmax=75(最終最優(yōu)解)其中機器A

20、空閑時間段為：5-11,35-38,39-42,64-65;機器B則為:15-20,24-35;機器C為:17-18,53-54,65-68;機器D無空閑。以下為：取不同N和M值情況下數(shù)據(jù)優(yōu)化過程以及時間上的比較：（表五）NNMA 次運行第二次運行第三次運行第四次運行第五次運行平均運行時間111104-114-9898-105-9392-93-92100-132-9586-86-84/1110106-97-86108-100-89102-87-8799-90-9088-104-84/1110094-81-8181-102-7891-105-91101-84-8090-101-90/111000

21、107-100-7892-101-76101-100-8288-97-8691-93-878.5(s)111000088-105-77103-81-7789-99-84107-104-7893-105-7880(s)10101090-108-90104-91-83104-100-9395-98-87105-106-87/101010098-96-9693-99-9088-90-80105-92-8091-95-85r/10101000101-96-7891-89-8096-104-87105-105-8488-99-789.5(s)10101000099-92-7797-95-7596-104

22、-7689-99-7691-101-7590(s)10010010095-100-8698-90-80104-99-7893-88-8192-99-80r/1001001000109-98-8591-100-82100-99-77114-101-8496-110-7611(s)1001001000096-101-78101-86-76101-97-8099-110-7699-111-77100(s)說明：以最后一行第一次運行“96-101-78”為例,96和101分別為2次N取100時得到的100*2個隨機解中的最優(yōu)解,78為經(jīng)過M=10000弋的遺傳（交叉變異選擇）后得到的最終最優(yōu)解。明顯地

23、發(fā)現(xiàn)：M的增大所產(chǎn)生的優(yōu)化效果明顯好于N增大產(chǎn)生的優(yōu)化效果M從1-10-100-1000-10000的變化使最優(yōu)解有從9*-8*-7*的變化規(guī)律，N的1-10-100的變化則不明顯。因此相對于隨機取解，經(jīng)過遺傳算法優(yōu)化之后效果是顯著的。另外對采用遺傳算法前后模擬所得數(shù)據(jù)進行比較%L、次第二次第三次第四次第五次均值平均時間N=1000,M=0r787981:8079r79.4r25(S)N=1,N=1,M=1000807577768278.08.5(S)（表六）由上表看來，雖然在均值方面相差不顯著，但是時間上采用遺傳算法之后節(jié)約了約三分之二的運行時間，效率顯而易見。九,模型優(yōu)缺點及改進模型優(yōu)點，

24、采用遺傳算法可對一個理論上無法求盡的NP問題以較有效方法在較短時間內(nèi)得到較精確解。缺點，采用遺傳算法還不全面，只是一個簡單模型，未考慮收斂性，適配值等，對參數(shù)設(shè)置與最優(yōu)解關(guān)系研究還不夠深入。模型本身還具有漏動，仍需改進，較好設(shè)想為采用和模擬退火算法的混合遺傳算法，由于時間緊迫，在此就不再深入給出模型及分析了。參考文獻：1.車間調(diào)度與遺傳算法王凌清華大學(xué)出版社2,數(shù)值計算的算法與分析張可村趙英良科學(xué)出版社3.PermutationBasedGAsandOrderedGreedPeterG.Anderson,4.MATLAB6.0與科學(xué)計算王沫然電子工業(yè)出版社5.C程序設(shè)計（第二版）潭浩強清華大學(xué)

25、出版社信息014孫卓明2003年8月14日本文網(wǎng)上下載地址（個人主頁）:http:附錄:子程序一：(種群初始化，得較優(yōu)個體)functionminminmax,ss=chushijie(n)%種群初始化，以下為編碼和解碼過程，同時對 n 次選取最優(yōu)化個體Jm=31234000;14230000;34121 000;23414300;42341340;12 134131;minminmax=200;ford=1:n;s=0;%編碼程序：基于操作的編碼策略k=1;fort=1:35;I=randint(1,1,1,6);whileJm(I,1)=0;I=randint(1,1,1,6);end;s

26、(k)=I;k=k+1;x=1;whilex=7;Jm(I,x)=Jm(I,x+1);x=x+1;end;Jm(I,8)=0;end;Jm=31234000;14230000;34121 000;23414300;42341340;12 134131;T=824246000;45340000;3715208000;7621116300;1048412610;14735258;%解碼程序：活動化解碼算法fori=1:6;k(i)=1;end;forq=1:4;forx=1:9;a(q,x)=0;b(q,x)=0;flag_(q)=0;end;end;forp=1:6;flag(p)=0;end;

27、fori=1:35;q=Jm(s(i),k(s(i);t=T(s(i),k(s(i);z=0;v=0;forx=1:9;ifmax(flag(s(i),a(q,x)+t=b(q,x)&z=0;ifflag(s(i)=a(q,x)&a(q,x)+t=b(q,x);flag(s(i)=b(q,x);fory=x:8;a(q,y)=a(q,y+1);b(q,y)=b(q,y+1);end;z=1;elseifflag(s(i)=a(q,x)&a(q,x)+ta(q,x)&a(q,x)+t=b(q,x)flag(s(i)=b(q,x);b(q,x)=b(q,x)-t;z

28、=1;elseifflag(s(i)a(q,x)&a(q,x)+tb(q,x);fory=8:x+2;a(q,y)=a(q,y-1);b(q,y)=b(q,y-1);end;b(q,x+1)=b(q,x);b(q,x)=flag(s(i);a(q,x+1)=flag(s(i)+t;flag(s(i)=a(q,x+1);z=1;end;end;end;ifz=0;ifflag(s(i)flag_(q);forx=1:9;ifa(q,x)=0&v=0;a(q,x)=flag_(q);b(q,x)=flag(s(i);v=1;end;end;flag(s(i)=flag(s(i)+t

29、;flag_(q)=flag(s(i);end;end;k(s(i)=k(s(i)+1;end;minmax=0;forq=1:4;ifminmaxminmax;%得出初始最優(yōu)解minminmax=minmax;ss=s;end;end;z=0;fori=1:35;iff1(i)=f2(D(j-1)&z=0;w=0;fort=3:j;if(i-D(t-1)0|(i-D(t-1)0;g1(D(i)=f1(D(i);g2(D(i)=f2(D(i);end;end;f3=g1;f4=g2;c=randint(1,1,1,100);ifc=1;d1=randint(1,1,1,35);d2=r

30、andint(1,1,1,35);whiled1=d2;d2=randint(1,1,1,35);end;m=f3(d1);f3(d1)=f3(d2);f3(d2)=m;elseifc=2;d1=randint(1,1,1,35);d2=randint(1,1,1,35);whiled1=d2;d2=randint(1,1,1,35);end;m=f4(d1);f4(d1)=f4(d2);f4(d2)=m;end;子程序四：(四者中選取最優(yōu)二個體)functionf1,f2=xuanze(f1,f2,f3,f4)%對父代 f1,f2 和子代 f3,f4 進行解碼，得出 2 個較優(yōu)個體，成為下一

31、代的父代min1=0;min2=0;min3=0;min4=0;h=0;g=0;min1=tongbujinzhan(f1);min2=tongbujinzhan(f2);min3=tongbujinzhan(f3);min4=tongbujinzhan(f4);ifmin1=min2&min1=min3&min1=min4;h=f1;ifmin2=min3&min2=min4;g=f2;elseifmin3=min2&min3=min4;g=f3;elseifmin4=min2&min4=min3;g=f4;end;elseifmin2=min1&am

32、p;min2=min3&min2=min4;h=f2;ifmin1=min3&min1=min4;g=f1;elseifmin3=min1&min3=min4;g=f3;elseifmin4=min1&min4=min3;g=f4;end;elseifmin3=min1&min3=min2&min3=min4;h=f3;ifmin1=min2&min1=min4;g=f1;elseifmin2=min1&min2=min4;g=f2;elseifmin4=min1&min4=min2;g=f4;end;elseifmin4=min1&min4=min2&min4=min3;h=f4;ifmin1=min2&min1=min3;g=f1;elseifmin2=min1&min2=min3;g=f2;elseifmin3=min1&min3=min2;g=f3;end;end;end;f1=h;