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

1、生產(chǎn)調(diào)度問題及其優(yōu)化算法（采用遺傳算法與MATLAB編程）信息014 孫卓明二零零三年八月十四日生產(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)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。本文給出三個(gè)模型。首先通過貪婪法手工求得本問題最優(yōu)解，既而通

2、過編解碼程序隨機(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à)值。一問題重述 某重型機(jī)械廠產(chǎn)品都是單件性的，其中有一車間共有A，B，C，D四種不同設(shè)備，現(xiàn)接受6件產(chǎn)品的加工任務(wù)，每件產(chǎn)品接受的程序在指定的設(shè)備上加工，其工序與加工周期如下表：（S-設(shè)備號(hào)、T-周期）工序產(chǎn)品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7

3、A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8 ( 表一 )條件：1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒； 2、每臺(tái)設(shè)備在同一時(shí)間只能擔(dān)任一項(xiàng)任務(wù)。（每件產(chǎn)品的每個(gè)工序?yàn)橐粋€(gè)任務(wù)）問題：做出生產(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表示，說明時(shí)則用A，B，C，D二模型假設(shè)1每一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能被一臺(tái)機(jī)器所加工 ，同時(shí)加工過程為不間斷；2所有機(jī)器均同時(shí)開工，且工

4、件從機(jī)器I 到機(jī)器J 的轉(zhuǎn)移過程時(shí)間損耗不計(jì)；3各工件必須按工藝路線以指定的次序在機(jī)器上加工多次；4操作允許等待，即前一操作未完成，則后面的操作需要等待，可用資源有限。三符號(hào)說明及初始數(shù)據(jù)表達(dá)分析 - 第i個(gè)工件 （i=16）- 機(jī)器順序陣 表示i工件的第 j個(gè)操作的機(jī)器號(hào)- 第j臺(tái)機(jī)器 （j=14）- 工件排列陣 表示i機(jī)器上第j次加工的工件號(hào) - 加工時(shí)間陣 為i工件的第 j個(gè)操作的時(shí)間周期 - 整個(gè)任務(wù)完成時(shí)間整理數(shù)據(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

5、 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 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 上述二陣直接從題目得出，而則是我們要求的。關(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ī)器總

6、凈加工時(shí)間之中最大值為 75，而總計(jì)為247，那么 總時(shí)間 C 介于75，247。同時(shí)各工件加工繁雜程度不一，各機(jī)器的任務(wù)量也有輕重之別。合理的調(diào)度排序是對(duì)于節(jié)省時(shí)間和資源是必要的。希望最優(yōu)化答案是75，這樣達(dá)到最小值，如果答案是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í)間或

7、者剩余加工總次數(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-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

8、-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(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75) (表四) (圖一) 上圖為加工周期圖（甘特圖），標(biāo)注數(shù)字為相應(yīng)操作的周期，完工時(shí)間為第75周期。五計(jì)算機(jī)隨機(jī)模擬（編程）1編碼：隨機(jī)產(chǎn)生生產(chǎn)的工序操作優(yōu)先順序，進(jìn)行編碼，如：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 （注

9、：同時(shí)作為下文的染色體之用） 意思為：工件4優(yōu)先被考慮進(jìn)行第一次操作，然后3進(jìn)行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次進(jìn)行。如果前后互相不沖突，則可同時(shí)在不同機(jī)器上操作。通過排列組合得出，總共有類似K的排列序列 2多種！當(dāng)然，這其中只對(duì)應(yīng)解 75，247，意味著有大量排列序列對(duì)應(yīng)同一加工方案，而大量加工方案又對(duì)應(yīng)同一時(shí)間解。2解碼： 即對(duì)編碼進(jìn)行翻譯，產(chǎn)生具體可操作工序安排方案，這里采用活動(dòng)化解碼算法。例如工件2第i步操作（記為（2，i），且在機(jī)器A上進(jìn)行）被安排在工件3第j步操作（記為JM（3,j）后面進(jìn)行，那么如果安排好（3,j）后，只要（2，i）在工件2已經(jīng)排序好的

10、操作之后進(jìn)行，那么操作（2，i）可插入到機(jī)器A處最前可安置的時(shí)間段進(jìn)行。在這里，一個(gè)編碼序列對(duì)應(yīng)一個(gè)加工方案，而一個(gè)加工方案可對(duì)應(yīng)一個(gè)或多個(gè)編碼序列，這就是二者之關(guān)系。3編程： 通過一組隨機(jī)編碼產(chǎn)生一生產(chǎn)加工優(yōu)先序列，通過解碼過程產(chǎn)生相應(yīng)加工方案及其總耗費(fèi)時(shí)間C . N次模擬后即可得出解C的概率密度分布情況以及相對(duì)最優(yōu)解（N個(gè)C的最小值，如80，77等，甚至出現(xiàn)75）。4計(jì)算機(jī)模擬所得數(shù)據(jù)分析a. 進(jìn)行100次模擬得出最優(yōu)解情況： (共運(yùn)行10次) 82，83，82，84，78，80，81，83，87，82 平均值 82.2，每回耗時(shí)約3秒b. 進(jìn)行1000次模擬得出最優(yōu)解情況：(共運(yùn)行10次

11、) 80，79，78，78，79，79，76，80，77，78 平均值 78.4 , 每回耗時(shí)25秒c. 進(jìn)行10000次模擬得出最優(yōu)解情況：(共運(yùn)行10次) 76，77，77，75，76，76，77，76，76，77 平均值 76.3, 每回耗時(shí)4分鐘 d. 模擬1000000次得到的解C的概率密度分布情況為： （如圖二所示）( 圖二 ) （注：75處為17次（概率為17/1000000=1/58823），76處為40次，77處167次）結(jié)論：如果想將2中排序序列以平均出現(xiàn)一次的可能性進(jìn)行模擬，即運(yùn)行2次，計(jì)算機(jī)需運(yùn)行將近150萬億年！當(dāng)然，我們沒有這個(gè)必要，因?yàn)槲覀冎恍枰\(yùn)行數(shù)萬次，就很可

12、能得到最優(yōu)解75，（在隨機(jī)模擬1000000次后出現(xiàn)17次75，那么意味著概率大約17/1000000=1/58823，另外76處為40次，77處167次）。六遺傳算法模型建立和步驟解法遺傳算法（Genetic Algorithm）作為一種優(yōu)化算法特別適合于對(duì)象模型難于建立、搜索空間非常龐大的復(fù)雜問題的優(yōu)化求解。它和模糊控制技術(shù)一樣，雖然在理論上還沒有完善，但是在實(shí)踐中已經(jīng)得到了廣泛的應(yīng)用。遺傳算法的基本思想是：模仿生物系統(tǒng)“適者生成"的原理，通過選擇、復(fù)制、交叉、變異等簡(jiǎn)單操作的多次重復(fù)來達(dá)到去劣存優(yōu)的目的，從而獲得問題的優(yōu)化結(jié)果。遺傳算法的實(shí)現(xiàn)由兩個(gè)部分組成，一是編碼與解碼，二是

13、遺傳操作。其中遺傳操作又包括選擇、復(fù)制、交叉、變異等步驟。 本文根據(jù)實(shí)際情況采取了1-6整數(shù)編碼。數(shù)字1，2，3，4，5，6分別代表6件待加工產(chǎn)品。本文遺傳算法基本流程:通過編碼，解碼程序隨機(jī)產(chǎn)生N個(gè)（有一定數(shù)量,如50或100）個(gè)體構(gòu)成初始種群a) 從初始中群中選取2個(gè)具有最優(yōu)染色體（最有排序方案）的個(gè)體作為臨時(shí)個(gè)體（父代）；b) 如果此2個(gè)體中有一個(gè)個(gè)體通過解碼操作能夠?qū)崿F(xiàn)最優(yōu)排序（即使總時(shí)間為75周期），那么結(jié)束此算法，得到最優(yōu)解；c) 對(duì)2個(gè)臨時(shí)個(gè)體以一定方式(循環(huán)交叉)執(zhí)行染色體交叉變換和變異選擇（小概率,互換操作），產(chǎn)生2個(gè)新的個(gè)體；d) 對(duì)父代和子代共4個(gè)個(gè)體進(jìn)行選擇，從中選出最

14、佳的2個(gè)個(gè)體，做為下一代的父代；e) 重復(fù)執(zhí)行第二步(b)操作；f) 如果執(zhí)行完M步后仍然未得出答案75，那么將目前的最優(yōu)解作為本算法的最優(yōu)解答案。1編碼和解碼 （同上）2交叉變換(crossover) 對(duì)2個(gè)父代臨時(shí)個(gè)體進(jìn)行染色體交叉變換，采用循環(huán)交叉方法（Cycle crossover CX），如父代染色體為：X：9 2 6 4 7 3 5 8 1和Y：3 4 5 8 1 6 7 2 9，如果隨機(jī)選到第二位開始交叉，那么X的2對(duì)應(yīng)Y的4，X的4對(duì)應(yīng)Y的8，X的8對(duì)應(yīng)Y的2，這樣就確定了以上為不變的染色體，其余位置的染色體互換位置，最后得到: 3 2 5 4 1 6 7 8 9, : 9 4

15、 6 8 7 3 5 2 1,實(shí)現(xiàn)交叉變換。3變異選擇（mutation） 采用互換操作（SWAP），即隨機(jī)交換染色體中兩不同基因的位置。如上面的染色體為：: 3 2 5 4 1 6 7 8 9 。隨機(jī)產(chǎn)生變換位置號(hào)，如產(chǎn)生隨機(jī)數(shù)3和5，那么交換數(shù)字后得到染色體： 3 2 1 4 5 6 7 8 9， 變異概率取0.1 。4選擇操作（selection） 對(duì)父代2個(gè)體f1,f2和子代2個(gè)體f3,f4進(jìn)行選擇，通過編碼操作確定具有最優(yōu)解的2個(gè)個(gè)體，成為新一代f1和f2 。 如此，通過多次編碼和解碼隨機(jī)產(chǎn)生一定數(shù)量的個(gè)體，選取2個(gè)最佳個(gè)體進(jìn)行交叉變換操作，產(chǎn)生2個(gè)新個(gè)體，然后對(duì)4個(gè)個(gè)體進(jìn)行選擇，產(chǎn)

16、生下一代，如果某時(shí)刻通過解碼操作得出最優(yōu)解（所有解的下限，這里是75周期），那么算法結(jié)束，否則循環(huán)進(jìn)行，直至預(yù)先給定的循環(huán)次數(shù)達(dá)到為止，以最后得到的最優(yōu)解作為最終最優(yōu)解。七遺傳算法模擬（采用MATLAB工具編程）主程序如下：（子程序見略）% 本程序?yàn)橹鞒绦?，調(diào)用以下各分支程序task= 'Welcome! Wait a moment please! - Writer: 孫 卓 明 ,信息 014',f1=zeros(1,35);f2=zeros(1,35); while f1=f2; % 此步避免初始染色體 f1,f2 相同，導(dǎo)致以下死循環(huán) minminmax1,s1=chus

17、hijie(N); % 種群初始化；基于操作的編碼策略；活動(dòng)化解碼算法;chushijie(N) 參數(shù) N 為初始種群數(shù) f1=s1 ; minminmax1, % 選取的第一個(gè)初始個(gè)體 minminmax2,s2=chushijie(N); % 再次種群初始化 f2=s2 ; minminmax2, % 選取的第二個(gè)初始個(gè)體 end;for e=1:M; % e=1:M 進(jìn)行 M 次遺傳操作（交叉-變異-選擇) D=jiaocha(f1,f2); % 交叉變化（循環(huán)交叉操作，cycle crossover CX）,選取f1; f2; “染色體”無需變動(dòng)部分基因 f3,f4=jiaocha_b

18、ianyi(f1,f2,D); % 生成交叉后的“染色體”,并進(jìn)行變異選擇 f3; f4; f1,f2=xuanze(f1,f2,f3,f4); % 選擇：對(duì)父代f1,f2和子代f3,f4進(jìn)行解碼，得出2個(gè)f1; f2; 較優(yōu)個(gè)體，成為下一代的父代 minmaxf1,a1,b1=tongbujinzhan(f1); % 求該時(shí)刻個(gè)體f1的最優(yōu)時(shí)間(因?yàn)閒1優(yōu)于f2) if minmaxf1=75; f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, task='Finish! Successful! Best answer!

19、Congratulation! ' , return ; end; end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1, if minminmax_last>=90; task='Finish! Action again please!',end;if minminmax_last>=80&&minminmax_last<90; task='Finish!' , end;if minminmax_last<80; task='Finish!

20、Successful!', end;八遺傳算法模擬結(jié)果首先給出最優(yōu)方案:在進(jìn)行某次n=100,m=200的操作后得到模擬最優(yōu)結(jié)果75周期時(shí)間：minminmax1 =83 minminmax2 =78 （二個(gè)初始較優(yōu)個(gè)體解）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 6 4 6 6 4 3 2 2 5 1 1 （f1為各工件優(yōu)先選擇順序排列,即“染色體”）a1 = 5 35 39 64 0 0 0 0 0 （a1,b1為四臺(tái)機(jī)器空閑周期段） 15 24 0 0 0 0 0 0 0 17 53 65 0 0 0 0 0 0 0

21、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 （最終最優(yōu)解）其中機(jī)器A空閑時(shí)間段為:5-11,35-38,39-42,64-65; 機(jī)器B則為:15-20,24-35; 機(jī)器C為:17-18,53-54,65-68;機(jī)器D無空閑。以下為:取不同N和M值情況下數(shù)據(jù)優(yōu)化過程以及時(shí)間上的比較: ( 表五 )NNM第一次運(yùn)行第二次運(yùn)行第三次運(yùn)行第四次運(yùn)行第五次運(yùn)行平均運(yùn)行時(shí)間111104-114-9898-105-9392

22、-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-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/10101009

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

24、-97-8099-110-7699-111-77100(s)說明: 以最后一行第一次運(yùn)行 “96-101-78”為例,96和101分別為2次N取100時(shí)得到的100*2個(gè)隨機(jī)解中的最優(yōu)解,78為經(jīng)過M=10000代的遺傳(交叉變異選擇)后得到的最終最優(yōu)解。明顯地發(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的變化則不明顯。 因此相對(duì)于隨機(jī)取解, 經(jīng)過遺傳算法優(yōu)化之后效果是顯著的。另外對(duì)采用遺傳算法前后模擬所得數(shù)據(jù)進(jìn)行比較:第一次第二次第三次第四次第五次均值平均時(shí)

25、間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) (表六)由上表看來,雖然在均值方面相差不顯著,但是時(shí)間上采用遺傳算法之后節(jié)約了約三分之二的運(yùn)行時(shí)間,效率顯而易見。九模型優(yōu)缺點(diǎn)及改進(jìn)模型優(yōu)點(diǎn)，采用遺傳算法可對(duì)一個(gè)理論上無法求盡的NP問題以較有效方法在較短時(shí)間內(nèi)得到較精確解。缺點(diǎn)，采用遺傳算法還不全面，只是一個(gè)簡(jiǎn)單模型，未考慮收斂性,適配值等，對(duì)參數(shù)設(shè)置與最優(yōu)解關(guān)系研究還不夠深入。 模型本身還具有漏動(dòng)，仍需改進(jìn)，較好設(shè)想為采用和模擬退火算法的混合遺傳算法，由于時(shí)間緊迫，在此就不再深入給出模型及分

26、析了。參考文獻(xiàn)：1 車間調(diào)度與遺傳算法 王凌 清華大學(xué)出版社2數(shù)值計(jì)算的算法與分析 張可村 趙英良 科學(xué)出版社3Permutation Based GAs and Ordered Greed Peter G. Anderson,4MATLAB6.0 與科學(xué)計(jì)算 王沫然 電子工業(yè)出版社5C程序設(shè)計(jì)（第二版） 潭浩強(qiáng) 清華大學(xué)出版社 信息014 孫 卓 明 2003年8月14日 本文網(wǎng)上下載地址(個(gè)人主頁): 附錄：子程序一：(種群初始化，得較優(yōu)個(gè)體) function minminmax,ss=chushijie(n) % 種群初始化,以下為編碼和解碼過程，同時(shí)對(duì)n次選取最優(yōu)化個(gè)體Jm=3 1

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

28、; 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 4 12 6 1 0;1 4 7 3 5 2 5 8 ; % 解碼程序：活動(dòng)化解碼算法 for i=1:6; k(i)=1; end ; for q=1:4; for x=1:9; a(q,x)=0;b(q,x)=0;fl

29、ag_(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)&&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

30、(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 flag(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);

31、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); for 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)

32、=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 ; % 得出初始最優(yōu)解 minminmax=minmax ;ss=s ;end ;end;子程序二：（父代交叉變換）function D=jiaocha(f1,f2) % 交叉變化（循環(huán)交叉操作，CX）,選取“染色體”無需變動(dòng)部分基因s=randint(1,1,1,35); while f1(s)=f2(s); s=randint

33、(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; 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

34、 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) % 生成交叉后的“染色體”,并進(jìn)行變異選擇g2=f1;g1=f2; for i=1:34; 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=r

35、andint(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,1,35); end; m=f4(d1);f4(d1)=f4(d2);f4(d2)=m; end; 子程序四：（四者中選取最優(yōu)二個(gè)體）function f1,f2=xuanze(f1,f2,f3,f4) %

36、對(duì)父代f1,f2和子代f3,f4進(jìn)行解碼，得出2個(gè)較優(yōu)個(gè)體，成為下一代的父代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<=min3&&min1<=min4 ; h=f1 ; if min2<=min3&&min2<=min4; g=f2; elseif min3<

37、=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<=min4 ; g=f1; elseif min3<=min1&&min3<=min4 ; g=f3; elseif min4<=min1&&min4

38、<=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; elseif min4<=min1&&min4<=min2 ; g=f4; end;elseif min4<=min1&&min4<=min2&

39、;&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;子程序五：（循環(huán)之中，同步求解）function minmaxf1,a1,b1=tongbujinzhan(f1) % 求該時(shí)刻個(gè)體f1的最優(yōu)時(shí)間Jm=3 1 2 3 4 0 0 0 ;1