一種基于改進(jìn)遺傳算法的車間調(diào)度問題研究

1、一種基于改良遺傳算法的車間調(diào)度問題研究論文導(dǎo)讀:：作業(yè)車間調(diào)度是一類求解困難的組合優(yōu)化問題，本文在考慮遺傳算法早熟收斂問題結(jié)合模擬退火算法局部最優(yōu)時(shí)能概率性跳出的特性，最終使算法能夠趨于全局最優(yōu)。在次根底上，將遺傳算法和模擬退火算法相結(jié)合，提出了一種基于遺傳和模擬退火的混合算法，并用實(shí)例對(duì)該算法進(jìn)行了仿真研究。結(jié)果說明，該算法有教好的收斂精度，是可行的，與傳統(tǒng)的算法相比擬，有明顯的優(yōu)越性。論文關(guān)鍵詞：遺傳算法，車間調(diào)度，模擬退火1. 引言作業(yè)車間調(diào)度：機(jī)器先于機(jī)器加工工件，工件先于工件在機(jī)床上加工模擬退火，式中，其中，式(1)表示目標(biāo)函數(shù)，式(2)(3)(4)表示工藝約束條件決定的各工件的各操

2、作的先后加工順序以及加工各個(gè)工件的各機(jī)器的先后順序。式中，符號(hào)和分別為工件在機(jī)器上的完成時(shí)間和加工時(shí)間。3用改良遺傳算法(MGA)求解3.1編碼方式如何將所研究問題的解轉(zhuǎn)換為由編碼形式表達(dá)的染色體是遺傳算法的關(guān)鍵問題【2】。對(duì)JSSP問題，遺傳算法的編碼常見的有以下幾種：基于工序(或操作)的編碼、基于工件的編碼、基于先后表的編碼、基于工件對(duì)關(guān)系的編碼、基于優(yōu)先規(guī)那么的編碼、基于機(jī)器的編碼、基于完成時(shí)間的編碼、隨機(jī)鍵編碼、基于析取圖的編碼【3】。這些編碼方法都存在這樣或者那樣的缺乏，鑒于以上車間調(diào)度問題編碼方法所存在的問題，提出一個(gè)既能保證后代的合法性，又能表征全部解空間，解碼又相對(duì)簡單的編碼方

3、法很有必要。本文考慮一個(gè)基于工序(或操作)的編碼方法用來保證搜索空間是一個(gè)完整的解空間，并且任何操作者的所有交換可對(duì)應(yīng)于適宜調(diào)度，對(duì)于每個(gè)基因?qū)?yīng)一道工序，代表該工序在進(jìn)行調(diào)度操作時(shí)的處理優(yōu)先級(jí)，對(duì)于n個(gè)工件m臺(tái)機(jī)器的調(diào)度問題，一個(gè)染色體由個(gè)基因組成?？紤]3個(gè)工件和2臺(tái)機(jī)器問題的機(jī)器加工次序矩陣：以及加工的時(shí)間矩陣：假設(shè)一個(gè)任意基于操作的解分別為s = (1，3，2，2，1，3)， 其中1，2和3分別代表工件1，2和3論文開題報(bào)告范例。通過一個(gè)半活動(dòng)解碼過程，工件的加工次序?qū)τ跈C(jī)器1對(duì)應(yīng)3-2-1，對(duì)于機(jī)器2對(duì)應(yīng)1-2-3。它們對(duì)應(yīng)的makespan(工件完工時(shí)間)為7的甘特圖如圖所示：Fig

4、ure 1. Halfactivities scheduling correspond to tmakespan圖1 半活動(dòng)調(diào)度對(duì)應(yīng)的makespan我們認(rèn)為，活動(dòng)調(diào)度編碼是半自主調(diào)度編碼的一個(gè)子集，因此，最優(yōu)調(diào)度方案必須是一個(gè)活動(dòng)調(diào)度編碼對(duì)應(yīng)的工件完工時(shí)間【4】?；顒?dòng)調(diào)度編碼的應(yīng)用可以在下一個(gè)操作之前檢查可能的空白的間隔時(shí)間所在最后位置模擬退火，并且在最后操作之前填補(bǔ)前一個(gè)空白間隔時(shí)間直到最后一個(gè)操作轉(zhuǎn)化為半活動(dòng)調(diào)度，導(dǎo)致makespan的長度可以變得更短。 因此，Gantt圖(圖1)被改變?yōu)槿缦铝袌D2所示，同時(shí)，對(duì)應(yīng)的makespan 為6 (最優(yōu)值)。Figure 2. Activiti

5、esscheduling correspond to tmakespan圖2 活動(dòng)碼調(diào)度對(duì)應(yīng)的makespan3.2解碼算法染色體只包含數(shù)字編碼。在解碼時(shí)首先要把基因與工序?qū)?yīng)起來，即把優(yōu)先級(jí)賦給對(duì)應(yīng)的工序。設(shè)：包含t個(gè)已調(diào)度工序的局部調(diào)度；階段t可調(diào)度工序的集合對(duì)應(yīng)給定的。解碼步驟如下：步驟1：令t=0，開始為空的局部調(diào)度。初始的包括無緊前工序的所有工序。步驟2：比擬中所有工序的調(diào)度優(yōu)先級(jí)，把具有最大優(yōu)先級(jí)的工序(假設(shè)為，其上道工序的結(jié)束時(shí)刻為)盡可能早的參加到中，即從時(shí)刻開始對(duì)該工序所對(duì)應(yīng)機(jī)器上各加工空閑依次判斷能否將此工件插入加工。假設(shè)能，那么在空閑中插入加工，并修改該機(jī)器上的加工隊(duì)列；

6、否那么，把該工序參加到該機(jī)器加工隊(duì)列的末尾，構(gòu)造一個(gè)新的局部調(diào)度。步驟3：按如下步驟更新數(shù)據(jù)集：從中刪除工序，通過在中增加工序的直接后續(xù)工序構(gòu)造，t=t+1。步驟4：返回步驟2直至構(gòu)造一個(gè)完整的調(diào)度，由此得到的調(diào)度為活動(dòng)調(diào)度。3.3交叉，變異算子交叉是最主要的遺傳運(yùn)算，遺傳算法的性能在很大程度上取決于采用的交叉運(yùn)算的性能，根據(jù)賭輪盤法【6】從父代群體中選擇雙親，采用單點(diǎn)順序交叉法生成后代。變異算子采用互換變異操作，隨機(jī)從染色體中選擇兩個(gè)基因進(jìn)行互換。3.4選擇算子選擇是遺傳算法的推動(dòng)力，采用擴(kuò)大的采樣空間，從雙親和后代種群中選擇個(gè)最優(yōu)的個(gè)體作為下一代的雙親。并且增加記憶操作，把截止當(dāng)前的最優(yōu)解

7、記錄下來，在下次迭代中，假設(shè)最優(yōu)解優(yōu)于該值，那么替代之。運(yùn)算結(jié)束時(shí)輸出該值，即為尋得的最優(yōu)解。3.5初始溫度確實(shí)定溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一，初始溫度高模擬退火，那么搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響【7】。初始溫度可以用估計(jì)，其中為充分大的數(shù)，為目標(biāo)函數(shù)的最壞情況和最好情況的差值，實(shí)際計(jì)算可以選等值，此時(shí)對(duì)應(yīng)的0.9048,0.9512,0.9900等，已經(jīng)到達(dá)充分大的要求，這里取為所有工件所有工序加工時(shí)間之和；為所有工件中所需加工時(shí)間最長的工件的加工時(shí)間，這是目標(biāo)函數(shù)的兩個(gè)可以估計(jì)的上

8、下界，由此確定的初始溫度可以保證是足夠大的。3.6計(jì)算過程車間調(diào)度問題是最小化問題，可以通過下邊的方法直接將目標(biāo)函數(shù)轉(zhuǎn)化成適應(yīng)度函數(shù)： 計(jì)算步驟如下：步驟1：初始化種群數(shù)目，交叉概率，變異概率，退火速率，輸入機(jī)器順序矩陣,，加工時(shí)間矩陣，計(jì)算初始溫度。步驟2：隨機(jī)產(chǎn)生個(gè)個(gè)體構(gòu)成初始群體，并進(jìn)行解碼。令最優(yōu)值為當(dāng)前種群的最優(yōu)個(gè)體，。步驟3：判斷當(dāng)前溫度是否小于給定的終止溫度，假設(shè)是，結(jié)束；否那么轉(zhuǎn)步驟4論文開題報(bào)告范例。步驟4：對(duì)種群進(jìn)行交叉操作。步驟5：對(duì)所有個(gè)體進(jìn)行變異操作。步驟6：對(duì)所有各個(gè)個(gè)體都進(jìn)行定步長抽樣的模擬退火操作，對(duì)舊個(gè)體采用swap方式產(chǎn)生新個(gè)體，以概率接受后代。步驟7：保存

9、原種群和產(chǎn)生的新種群中個(gè)最好個(gè)體，及時(shí)更新。步驟8：令，然后進(jìn)行退火操作，并返回步驟3。步驟9：輸出結(jié)果，并結(jié)束計(jì)算。4. 實(shí)驗(yàn)結(jié)果與分析為了測(cè)試上述所提出算法的性能，本文選取了Brandimarte基準(zhǔn)問題和經(jīng)典的Benchmarks基準(zhǔn)問題模擬退火， Brandimarte基準(zhǔn)問題包括工件數(shù)分別為6，10，20，機(jī)器數(shù)為6，10，5的3個(gè)問題實(shí)例，Benchmarks基準(zhǔn)問題包括工件數(shù)從10到30之間，機(jī)器數(shù)從5到15之間的8個(gè)問題實(shí)例在不同的范圍的相同條件下的幾個(gè)測(cè)試參數(shù)基準(zhǔn)被選擇，現(xiàn)采用文獻(xiàn)中提到的MT06， MT10和MT20的MGA的表現(xiàn)，和文獻(xiàn)中提到的LA01、LA06、LA11

10、、LA16、LA21、LA26、LA31和LA36的LA類問題。Table 1. Comparison of the MGA, SA, GA resulting dataof experiment表1 比擬MGA,SA,GA的計(jì)算結(jié)果 問題 n,m MGA SA GA MT06 6,6 55 55 55 MT10 10,10 930 939 997 MT20 20,5 1165 1227 1247 LA01 10,5 666 666 666 LA06 15,5 926 926 926 LA11 20,5 1222 1222 1222 LA16 10,10 945 979 979 LA21 15

11、,10 1058 1083 1156 LA26 20,10 1218 1253 1328 LA31 30,10 1784 1784 1836 LA36 15,15 1291 1321 1384 在同樣的參數(shù)和終止標(biāo)準(zhǔn)的執(zhí)行下，改良遺傳算法(MGA)、簡單遺傳算法(GA)與模擬退火算法(SA)之間的計(jì)算結(jié)果見表1，從表1的結(jié)果來看改良遺傳算法(MGA)的結(jié)果優(yōu)于簡單遺傳算法(GA)與模擬退火算法(SA)。5.結(jié)束語車間調(diào)度問題已經(jīng)證明為NP問題，難以找到能夠求得最優(yōu)解確實(shí)定性調(diào)度算法。又由于遺傳算法的優(yōu)良特性，因此，采用遺傳算法對(duì)車間調(diào)度問題進(jìn)行求解已成為求解該類問題的趨勢(shì)。本文提出的基于混合遺

12、傳算法的調(diào)度算法，同時(shí)融入模擬退火算法賦予搜索過程一種時(shí)變且最終趨于零的概率跳躍性，防止陷入局部最優(yōu)并最終趨于全局最優(yōu)。仿真實(shí)驗(yàn)說明了該改良遺傳算法是可行的、有效的、具有較好的搜索能力。參考文獻(xiàn):【1】GERVEY M R,JOHSON D S,SOTHI R.The complexity offlowshop and jobshop scheduling.Mathematics and OperationsResearch1976(1):117-129【2】R. Cheng, M. Gen and Y. Tsujimura, A tutorialsurvey of jobshop sched

13、uling problems using genetic algorithms I.Representation;, Computers and Industrial Engineering, 1976(30):983997【3】D. E. Goldberg, Genetic Algorithms in Search,Optimization and Machine Learning, Addison Wesley, New York, 1989.【4】L. Wang and D. Z. Zheng, An effective hybridoptimization strategy for j

14、ob-shop scheduling problems;, Computers andOperations Research, 28, pp. 585596, 2001.【5】G. Shi, A genetic algorithm applied to a classicjob-shop scheduling problem;, International Journal of Systems Science, 28(1),pp.2532, 1997.【6】Srinivas M,Patnaik L M.G enetic algorithm s:asurvey.C om puter,1994,2

15、7(6):1726.【7】B. Hajek, Cooling schedules for optimalannealing;, Mathematics of Operations Research, 13(2), pp. 311329, 1988J. F. Muth and G. Thompson, Industrial scheduling,Prentice Hall, Englewood Cliffs, NJ, 1963.S. Lawrence, Resource constrained projectscheduling: an experimental investigation of heurist