1、. .編號：第六屆計算機仿真大賽參賽作品題號:加工調度問題組別：高年級組 厚玉偉學院： 光電工程聯系：計算機仿真大賽組委會2021年 05月 01日生產調度問題及其優化算法背景及摘要這是一個典型的Job-Shop動態排序問題。目前調度問題的理論研究成果主要集中在以Job-Shop問題為代表的基于最小化完工時間的調度問題上。一個復雜的制造系統不僅可能涉及到成千上萬道車間調度工序，而且工序的變更又可能導致相當大的調度規模。解空間容量巨大，N個工件、M臺機器的問題包含種排列。由于問題的連環嵌套性，使得用圖解方法也變得不切實際。傳統的運籌學方法，即便在單目標優化的靜態調度問題中也難以有效應用。本文給出

2、三個模型。首先通過貪婪法手工求得本問題最優解，既而通過編解碼程序隨機模擬優化方案得出最優解。最后采用現代進化算法中有代表性開展優勢的遺傳算法。文章有針對性地選取遺傳算法關鍵環節的適宜方法，采用MATLAB軟件實現算法模擬，得出優化方案，并與計算機隨機模擬結果加以比較顯示出遺傳算法之優化效果。 對車間調度系列問題的有效解決具有一定參考和借鑒價值。二模型假設1每一時刻，每臺機器只能加工一個工件，且每個工件只能被一臺機器所加工 ，同時加工過程為不連續；2所有機器均同時開工，且工件從機器I 到機器J 的轉移過程時間損耗不計；3各工件必須按工藝路線以指定的次序在機器上加工屢次；4操作允許等待，即前一操作

3、未完成，那么后面的操作需要等待，可用資源有限。三符號說明及初始數據表達分析 - 第i個工件 i=16- 機器順序陣 表示i工件的第 j個操作的機器號- 第j臺機器 j=14- 工件排列陣 表示i機器上第j次加工的工件號 - 加工時間陣 為i工件的第 j個操作的時間周期 - 整個任務完成時間整理數據后得到：= C A B C D 0 0 0 = 8 2 4 24 6 0 0 0 A D B C 0 0 0 0 4 5 3 4 0 0 0 0 C D A B A 0 0 0 3 7 15 20 8 0 0 0 B C D A D C 0 0 7 6 21 1 16 3 0 0 D B C D A

4、C D 0 10 4 8 4 12 6 1 0 A B A C D A C A 1 4 7 3 5 2 5 8 上述二陣直接從題目得出，而那么是我們要求的。關于工件的加工時間表：(表二)產品/工件i:123456總計總凈加工時間周期441653544535247加工工序總數個54567835關于機器的加工時間表：(表三)機器/設備(j):ABCD總計總凈加工時間60427075247加工操作次數10610935分析：由于各產品總凈加工時間和各機器總凈加工時間之中最大值為 75，而總計為247，那么 總時間 C 介于75，247。同時各工件加工繁雜程度不一，各機器的任務量也有輕重之別。合理的調度

5、排序是對于節省時間和資源是必要的。希望最優化答案是75，這樣到達最小值，如果答案是75，那么意味著機器D不連續工作,直至全部加工任務完成。四貪婪法快速求解如果按照一定規那么排序，當多個工件出現“搶占同一機器的局面的時候,我們可以制定如下的工序安排規那么:1. 優先選擇總剩余時間或總剩余操作較多的工件。如果出現總剩余加工時間多者總剩余操作數反而較少的情況時,按照程度具體情況具體分析。2. 機器方面來說,盡量防止等待空閑時間，優先考慮剩余凈加工時間或者剩余加工總次數較多的機器,尤其是機器 D ,即倘假設能夠使機器D不連續工作且其他機器完工時間均不多余75時,那么就可以得到最優解 。首先按照最優化時

6、間為75的設想防止D出現等待，排序后得到升以下具體排列順序。各機器承擔任務表為(其中粗體字為對應工件產品號，括號內為對應時間周期段)：操作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-

7、10)3(11-17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)(表四) (圖一)上圖為加工周期圖甘特圖，標注數字為相應操作的周期，完工時間為第75周期。五計算機隨機模擬編程1編碼：隨機產生生產的工序操作優先順序，進展編碼，如：K= 4 3 5 6 6 2 3 1 41 6 3 5 4 5 3 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 6 5 注：同時作為下文的染色體之用 意思為：工件4優先被考慮進展第一次操作，然后3進展其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次進展。如果前后互相不沖突

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

9、編碼產生一生產加工優先序列，通過解碼過程產生相應加工方案及其總消耗時間C . N次模擬后即可得出解C的概率密度分布情況以及相對最優解N個C的最小值，如80，77等，甚至出現75。4計算機模擬所得數據分析a. 進展100次模擬得出最優解情況： (共運行10次) 82，83，82，84，78，80，81，83，87，82 平均值 82.2，每回耗時約3秒b. 進展1000次模擬得出最優解情況：(共運行10次) 80，79，78，78，79，79，76，80，77，78 平均值 78.4 , 每回耗時25秒c. 進展10000次模擬得出最優解情況：(共運行10次) 76，77，77，75，76，76

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

11、lgorithm作為一種優化算法特別適合于對象模型難于建立、搜索空間非常龐大的復雜問題的優化求解。它和模糊控制技術一樣，雖然在理論上還沒有完善，但是在實踐中已經得到了廣泛的應用。遺傳算法的根本思想是：模仿生物系統“適者生成"的原理，通過選擇、復制、穿插、變異等簡單操作的屢次重復來到達去劣存優的目的，從而獲得問題的優化結果。遺傳算法的實現由兩個局部組成，一是編碼與解碼，二是遺傳操作。其中遺傳操作又包括選擇、復制、穿插、變異等步驟。本文根據實際情況采取了1-6整數編碼。數字1，2，3，4，5，6分別代表6件待加工產品。本文遺傳算法根本流程:通過編碼，解碼程序隨機產生N個有一定數量,如50

12、或100個體構成初始種群a) 從初始中群中選取2個具有最優染色體最有排序方案的個體作為臨時個體父代；b) 如果此2個體中有一個個體通過解碼操作能夠實現最優排序即使總時間為75周期，那么完畢此算法，得到最優解；c) 對2個臨時個體以一定方式(循環穿插)執行染色體穿插變換和變異選擇小概率,互換操作，產生2個新的個體；d) 對父代和子代共4個個體進展選擇，從中選出最正確的2個個體，做為下一代的父代；e) 重復執行第二步(b)操作；f) 如果執行完M步后仍然未得出答案75，那么將目前的最優解作為本算法的最優解答案。1編碼和解碼 同上2穿插變換(crossover) 對2個父代臨時個體進展染色體穿插變換

13、，采用循環穿插方法Cycle crossover CX，如父代染色體為：X：9 2 6 4 7 3 5 8 1和Y：3 4 5 8 1 6 7 2 9，如果隨機選到第二位開場穿插，那么X的2對應Y的4，X的4對應Y的8，X的8對應Y的2，這樣就確定了以上為不變的染色體，其余位置的染色體互換位置，最后得到: 3 2 5 4 1 6 7 8 9, : 9 4 6 8 7 3 5 2 1,實現穿插變換。3變異選擇mutation 采用互換操作SWAP，即隨機交換染色體中兩不同基因的位置。如上面的染色體為：: 3 2 5 4 1 6 7 8 9 。隨機產生變換位置號，如產生隨機數3和5，那么交換數字后

14、得到染色體： 3 2 1 4 5 6 7 8 9， 變異概率取0.1 。4選擇操作selection對父代2個體f1,f2和子代2個體f3,f4進展選擇，通過編碼操作確定具有最優解的2個個體，成為新一代f1和f2 。如此，通過屢次編碼和解碼隨機產生一定數量的個體，選取2個最正確個體進展穿插變換操作，產生2個新個體，然后對4個個體進展選擇，產生下一代，如果某時刻通過解碼操作得出最優解所有解的下限，這里是75周期，那么算法完畢，否那么循環進展，直至預先給定的循環次數到達為止，以最后得到的最優解作為最終最優解。七遺傳算法模擬采用MATLAB工具編程主程序如下：子程序見略% 本程序為主程序，調用以下各

15、分支程序task= 'Wele! Wait a moment please! ',f1=zeros(1,35);f2=zeros(1,35); while f1=f2; % 此步防止初始染色體 f1,f2 一樣，導致以下死循環 minminmax1,s1=chushijie(N); % 種群初始化；基于操作的編碼策略；活動化解碼算法;chushijie(N) 參數 N 為初始種群數 f1=s1 ; minminmax1, % 選取的第一個初始個體 minminmax2,s2=chushijie(N); % 再次種群初始化 f2=s2 ; minminmax2, % 選取的第二個

16、初始個體 end;for e=1:M; % e=1:M 進展 M 次遺傳操作穿插-變異-選擇) D=jiaocha(f1,f2); % 穿插變化循環穿插操作，cycle crossover CX,選取f1; f2; “染色體無需變動局部基因 f3,f4=jiaocha_bianyi(f1,f2,D); % 生成穿插后的“染色體,并進展變異選擇 f3; f4; f1,f2=xuanze(f1,f2,f3,f4); % 選擇：對父代f1,f2和子代f3,f4進展解碼，得出2個f1; f2; 較優個體，成為下一代的父代 minmaxf1,a1,b1=tongbujinzhan(f1); % 求該時刻

17、個體f1的最優時間(因為f1優于f2) if minmaxf1=75; f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, task='Finish! Successful! Best answer! Congratulation! ' , return ; end; end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, if minminmax_last>=90; task='Finish! Action again please!

18、9;,end;if minminmax_last>=80&&minminmax_last<90; task='Finish!' , end;if minminmax_last<80; task='Finish! Successful!', end;八遺傳算法模擬結果首先給出最優方案:在進展某次n=100,m=200的操作后得到模擬最優結果75周期時間：minminmax1 =83minminmax2 =78 二個初始較優個體解f1 =4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5

19、6 4 6 6 4 3 2 2 5 1 1 f1為各工件優先選擇順序排列,即“染色體a1 = 5 35 39 64 0 0 0 0 0 a1,b1為四臺機器空閑周期段 15 24 0 0 0 0 0 0 0 17 53 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0b1 =11 38 42 65 0 0 0 0 0 20 35 0 0 0 0 0 0 0 18 54 68 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0minminmax =75 最終最優解其中機器A空閑時間段為:5-11,35-38,39-42,64-65; 機器B那么為:15-20,24-35;

20、 機器C為:17-18,53-54,65-68;機器D無空閑。以下為:取不同N和M值情況下數據優化過程以及時間上的比較: ( 表五 )NNM第一次運行第二次運行第三次運行第四次運行第五次運行平均運行時間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/111000107-100-7892-101-76101-100-8288-97-8691-93-8

21、78.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-85/10101000101-96-7891-89-8096-104-87105-105-8488-99-789.5(s)10101000099-92-7797-95-7596-104-7689-99-7691-101-7590(s)10010010095-100-8698

22、-90-80104-99-7893-88-8192-99-80/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個隨機解中的最優解,78為經過M=10000代的遺傳(穿插變異選擇)后得到的最終最優解。明顯地發現: M 的增大所產生的優化效果明顯好于N增大產生的優化效果 M 從1-10-100-1

23、000-10000的變化使最優解有從9*-8*-7* 的變化規律， N 的1-10-100的變化那么不明顯。 因此相對于隨機取解, 經過遺傳算法優化之后效果是顯著的。另外對采用遺傳算法前后模擬所得數據進展比較:第一次第二次第三次第四次第五次均值平均時間N=1000 ,M=0 78 79 818079 794 25(S)N=1,N=1,M=1000 80 75 77 7682 78.0 8.5(S) (表六)由上表看來,雖然在均值方面相差不顯著,但是時間上采用遺傳算法之后節約了約三分之二的運行時間,效率顯而易見。九模型優缺點及改進模型優點，采用遺傳算法可對一個理論上無法求盡的NP問題以較有效方法

24、在較短時間內得到較準確解。缺點，采用遺傳算法還不全面，只是一個簡單模型，未考慮收斂性,適配值等，對參數設置與最優解關系研究還不夠深入。 模型本身還具有漏動，仍需改進，較好設想為采用和模擬退火算法的混合遺傳算法，由于時間緊迫，在此就不再深入給出模型及分析了。參考文獻：1 車間調度與遺傳算法 王凌 清華大學2數值計算的算法與分析 X可村 趙英良 科學3Permutation Based GAs and Ordered GreedPeter G. Anderson,4MATLAB6.0 與科學計算 王沫然 電子工業5C程序設計第二版 潭浩強 清華大學 信息014 X 卓 明 2003年8月14日附錄

25、：- 優選. . .word.zl. .子程序一：(種群初始化，得較優個體) function minminmax,ss=chushijie(n) % 種群初始化,以下為編碼和解碼過程，同時對n次選取最優化個體Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ;minminmax=200;for d=1:n; s=0; % 編碼程序：基于操作的編碼策略 k=1; for t=1:35 ; I=randint(1,1,1,6); while

26、 Jm(I,1)=0; I=randint(1,1,1,6); end; s(k)=I; k=k+1; x=1; while x<=7; Jm(I,x)=Jm(I,x+1); x=x+1; end; Jm(I,8)=0; end;Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ;T=8 2 4 24 6 0 0 0;4 5 3 4 0 0 0 0;3 7 15 20 8 0 0 0;7 6 21 1 16 3 0 0;10 4 8

27、 4 12 6 1 0;1 4 7 3 5 2 5 8 ; % 解碼程序：活動化解碼算法 for i=1:6; k(i)=1; end ; for q=1:4; for x=1:9; a(q,x)=0;b(q,x)=0;flag_(q)=0; end; end; for p=1:6; flag(p)=0; end;for i=1:35; q=Jm(s(i),k(s(i); t=T(s(i),k(s(i); z=0; v=0; for x=1:9; if max(flag(s(i),a(q,x)+t<=b(q,x)&&z=0 ; if flag(s(i)<=a(q,x

28、)&&a(q,x)+t=b(q,x); flag(s(i)=b(q,x); for y=x:8; a(q,y)=a(q,y+1);b(q,y)=b(q,y+1); end; z=1 ; elseif flag(s(i)<=a(q,x)&&a(q,x)+t<b(q,x) ; a(q,x)=a(q,x)+t;flag(s(i)=a(q,x);z=1 ; elseif flag(s(i)>a(q,x)&&a(q,x)+t=b(q,x) ; flag(s(i)=b(q,x);b(q,x)=b(q,x)-t;z=1; elseif fla

29、g(s(i)>a(q,x)&&a(q,x)+t<b(q,x); for y=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; if z=0; if flag(s(i)<=flag_(q); flag(s(i)=flag_(q)+t; flag_(q)=flag_(q)+t; elseif flag(s(i)>flag_(q); fo

30、r x=1:9; if a(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;flag_(q)=flag(s(i); end; end; k(s(i)=k(s(i)+1;end;minmax=0; for q=1:4; if minmax<flag_(q); minmax=flag_(q); end;end;if minminmax>minmax ; % 得出初始最優解 minminmax=minmax ;ss=s ;end ;end;子程序二：父代穿插

31、變換function D=jiaocha(f1,f2) % 穿插變化循環穿插操作，CX,選取“染色體無需變動局部基因s=randint(1,1,1,35); while f1(s)=f2(s); s=randint(1,1,1,35);end; for p=1:34; D(p)=0; end; z=0;j=1;D(j)=s;j=j+1; for i=1:35; if f1(i)=f2(s)&&z=0 ; D(j)=i;j=j+1;z=1; end; end; if f2(D(j-1)=f1(s); return; end; for m=1:34; z=0; for i=1:35

32、; if f1(i)=f2(D(j-1) && z=0 ; w=0; for t=3:j; if (i-D(t-1)>0|(i-D(t-1)<0; w=w+1; end; end; if w=j-2; D(j)=i; j=j+1;z=1; end ; end ; end; if f2(D(j-1)=f1(s)&&z=1; return; end; end;end;子程序三：變異選擇，形成子代function f3,f4=jiaocha_bianyi(f1,f2,D) % 生成穿插后的“染色體,并進展變異選擇g2=f1;g1=f2; for i=1:3

33、4; if D(i)>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);if c=1 ; d1=randint(1,1,1,35); d2=randint(1,1,1,35); while d1=d2; d2=randint(1,1,1,35); end; m=f3(d1);f3(d1)=f3(d2);f3(d2)=m;elseif c=2; d1=randint(1,1,1,35); d2=randint(1,1,1,35); while d1=d2; d2=randint(1,1,

34、1,35); end; m=f4(d1);f4(d1)=f4(d2);f4(d2)=m; end;子程序四：四者中選取最優二個體function f1,f2=xuanze(f1,f2,f3,f4) % 對父代f1,f2和子代f3,f4進展解碼，得出2個較優個體，成為下一代的父代min1=0;min2=0;min3=0;min4=0;h=0;g=0;min1=tongbujinzhan(f1);min2=tongbujinzhan(f2);min3=tongbujinzhan(f3);min4=tongbujinzhan(f4);if min1<=min2&&min1<

35、;=min3&&min1<=min4 ; h=f1 ; if min2<=min3&&min2<=min4; g=f2; elseif min3<=min2&&min3<=min4; g=f3; elseif min4<=min2&&min4<=min3; g=f4; end;elseif min2<=min1&&min2<=min3&&min2<=min4 ; h=f2; if min1<=min3&&min1<

36、;=min4 ; g=f1; elseif min3<=min1&&min3<=min4 ; g=f3; elseif min4<=min1&&min4<=min3 ; g=f4; end;elseif min3<=min1&&min3<=min2&&min3<=min4 ; h=f3; if min1<=min2&&min1<=min4 ; g=f1; elseif min2<=min1&&min2<=min4 ; g=f2; el

37、seif min4<=min1&&min4<=min2 ; g=f4; end;elseif min4<=min1&&min4<=min2&&min4<=min3 ; h=f4; if min1<=min2&&min1<=min3 ; g=f1; elseif min2<=min1&&min2<=min3 ; g=f2; elseif min3<=min1&&min3<=min2 ; g=f3; end; end;end; f1=h;f2=g;while f1=f2; minminmax3,s1=chushijie(30); f2=s1;end;子程序五：循環之中，同步求解function minmaxf1,a1,b1=tongbujinzhan(f1) % 求該時刻個體f1的最優時間Jm=3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1