求解作業(yè)車間調(diào)度的改進遺傳算法.doc

求解作業(yè)車間調(diào)度問題的改進遺傳算法摘 要：本論文中，我們提出了一種解決job-shop調(diào)度問題的新遺傳算，這個提出的方法在建立分區(qū)塊假設(shè)和模式定理基礎(chǔ)之上，用基于作業(yè)的表示，提出了一種新的交叉方法。通過篩選排序目標值短，適配高的模式作為遺傳算子，此交叉方法可以有效轉(zhuǎn)換父代重要的排序信息從而達到全局優(yōu)化。用C+編碼產(chǎn)生的基于機器的仿真結(jié)果表明我們遺傳算子是強有效的而且適合車間作業(yè)調(diào)度問題。我們的方法要比之前的以GA為基礎(chǔ)的方法要更有效。關(guān)鍵詞：車間作業(yè)調(diào)度，遺傳算法 ，模式定理，建立分塊假設(shè)B.1 引言車間作業(yè)調(diào)度問題是眾所周知的最難的排序問題之一，其算法需要大量的計算步驟，其步驟也會隨著問題的大小呈指數(shù)增長。該問題通過決定各工件在機器上的加工順序來使作業(yè)時間最小化，該作業(yè)時間就是完成所有工件所需要的時間。盡管JSP調(diào)度問題的最優(yōu)解可以通過統(tǒng)計技術(shù)（分支定界法和數(shù)學規(guī)劃法）來得到，這些方法對于即使是中等規(guī)模的問題也需要過高的計算量。Davis L.是第一個提出將遺傳算法應用到解決JSP 問題中的，那是在1985年，最近，用遺傳算法來求解JSP問題比以前有了進一步的發(fā)展，工件的加工順序由遺傳編碼來確定，然后用過濾束搜索方法來解決這個問題。到目前為止，已經(jīng)有許多研究者提出了基于遺傳算法的解決方法。由于Davis 已經(jīng)展示了將遺傳算法應用到調(diào)度問題中，所以有很多研究者在致力于研究這一主題。他們中的一些人用這種交叉方法設(shè)計的有效的作業(yè)或操作討論了流水車間調(diào)度問題或者是排序問題像旅行商問題：邊緣重組算子和基于位置的交叉。其他人致力與介紹具體問題的代表性模式，因此提出了比傳統(tǒng)遺傳算子更為復雜的算子來解決動態(tài)計劃和機器的JSP調(diào)度問題。不管怎么樣，都不可能來公正的比較這些基于遺傳算法的方法，因為這些方法都是跟具體問題相匹配的。1991年，Nakanoetal 將常規(guī)遺傳算法應用到眾所周知的個工件的JSP調(diào)度問題中，他們選擇的二進制基因型包含了工件在每臺機器上加工順序信息和傳統(tǒng)的二進制交叉和變異，但是需要一個修復機制來糾正遺傳操作后的不合法調(diào)度。Fangetal 也成功的將遺傳算法應用到解決JSP調(diào)度問題，是由基于常規(guī)交叉變異的方法的一個變種的父代排序而來的有效調(diào)度，它們的性能增強主要是因為基于目標的基因變異，它們交叉和變異的切入點是由基因在種群中的差異來決定的。然而這些基因表示是有多余的，因而存在假性競爭。不管怎樣，遺傳算法能夠讓我們迅速得到高質(zhì)量的解決方法而且很容易的同其他搜索技術(shù)進行比較。盡管遺傳算法能夠使我們獲得比其他方法更快更好的解決方法，一些方法已經(jīng)被運用于解決車間作業(yè)問題，但是在遺傳計算法和其他具體的方法之間還存在一些代溝，本文中位置轉(zhuǎn)換認為是一個主要的搜索引擎。為了能夠把遺傳算法成功的運用于解決車間作業(yè)調(diào)度問題，應該達到些列標準。1完整性，任何解決方法都應該有編碼。2 安全性，每個遺傳算法的編碼都應該有相對應的調(diào)試方法3 簡潔性，編碼和提哦啊是方法應該是一對一。4 持續(xù)性，正如兒童遺傳父母的特點。 本文中我們運用以操作為基礎(chǔ)展現(xiàn)編碼，介紹一種改進的部分調(diào)度交換交叉，它基于模式定理和建設(shè)作為交叉算子塊假說。通過選擇短的，適合階段模式的一串操作，這個位置轉(zhuǎn)換可以保存這樣的特點。以上述標準看來，這種編碼或位置轉(zhuǎn)換非常有效，并且這是通過實驗在理論和實際操作上都證明了其有效性。B.2 模式定理和建立分塊假說為了分析遺傳算法的操作，本文介紹了該模式的概念。這個模式可以定義為包含所有類似字符的串，它們是包含在一個種群中的高適應值的染色體中的，這個種群中，不相似的字符用 * 表示，下面的這個方程就是我們所知道的模式定理，它給出了這個模式下一代預計大小的下界。mH(i+1) =H(i) mH(i)1-PC (1-Pm)n/ (i)式中：mH(i+1)：模式在i+1帶的樣本數(shù)；mH(i)：模式在i+1帶的樣本數(shù)；H(i)：包含的染色體在第代的平均適配值；Pc：交叉概率；：染色體長度；ld：計算而來的模式中字符長度最大值，如果交叉取代了定義的最大長度，那么模式被打亂的概率就會增加。Pm：變異概率；n：模式的順序，它的大小是等于模式中定義的字符的。這里1-Pm代表個體不發(fā)生變異的概率，這個命題可以歸納為：如果H(i) (i)，模式被選擇到下一代的概率高，這就意味著上述平均適配值的模式被選擇來復制的概率就高。因此，可以作出結(jié)論短的排序，高于平均水平的適配值的模式將在后代樣本中增加。這些隊列短的高與平均適配值的模式就被叫做建立分塊，建立分塊假說表明遺傳算法通過這些分塊并置來搜索鄰近的最優(yōu)解。B.3 遺傳算法B.3.1 遺傳概述本文采用的是有YasuhiroM eta提出的基于工序的表達法，這種表達法將調(diào)度用一系列工序來編碼，每一個基因代表一個工件，染色體可以直接解碼為一個調(diào)度。一個染色體由個基因組成，每一個基因表示一個工件，每一個基因根據(jù)工件機器加工順序表按顯示的順序進行調(diào)度。例如：對于表B.1，假設(shè)有一個染色體2,1,3,3,1,2,2,1,3,第一個基因2表示工件2的第一道工序，第二個基因2表示工件1的第一道工序，第三個基因3表示工件3的第1道工序，根據(jù)表格1所示的工件機器加工順序表，如圖B.1所示，這個調(diào)度安排為：J2的第一道工序在M1上加工時間為1，完工時間是12.表B.1 工件機器加工安排工件加工順序123加工時間J1332J2153J3323機器順序J1M1M2M3J2M1M3M2J3M2M1M3 圖B.1 一個可行調(diào)度B.3.2 適配值函數(shù)在每一次迭代過程中，都要用適配手段來評價當代個體。這些評價函數(shù)有大量的特征。在優(yōu)化問題應用中，適配值是通過原目標函數(shù)來計算的，在本論文中，每一個體的適配值是通過下面的相關(guān)調(diào)度的總運行時間（周程時間）來評價的f(Si) = ft(j)式中ft(j)工件j的完工時間。B.3.3 交叉本文中，我們根據(jù)模式定理和建立分塊假說改進了局部調(diào)度的交換交叉，這是由Gen和Cheng提出的。這個改進的交叉算子總結(jié)如下：（1）在父代1中隨機選擇一個位置，第二個選擇的基因位置和第一個基因的相同，兩個基因之間塊的長度最短，然后局部調(diào)度就由這些基因組成。（2）產(chǎn)生局部調(diào)度2，重復步驟（1）得到父代2.（3）交換局部調(diào)度產(chǎn)生子代1和子代2.（4）給子代1和子代2找出遺漏的和浪費的基因。（5）通過隨機刪除浪費的基因和插入遺漏的基因來使子代1和子代2合法化，對于高于局部調(diào)度的調(diào)度盡力讓它的順序保持與調(diào)度順序相近。例如：父代1=32 1 23 4 1 2 4 4 1 3 4 1 2 3父代2=4 1 32 1 3 4 1 23 4 2 1 2 3 4子代1=32 1 3 4 1 23 4 1 2 4 4 1 3 4 1 2 3子代2=4 1 32 1 23 4 2 1 2 3 4合法的后代：子代13 1 42 1 3 4 1 23 4 1 2 4 3 2子代24 32 1 23 4 2 1 2 3 4 4 3 1B.3.4 變異盡管交叉在盡力提高后代的適配值，現(xiàn)有解決方存在法使后代匯集的可能。有一個避免機制就是變異，它以微小的概率在相同的個體中隨機變化，我們把變異算子定義如下：在個體中隨機產(chǎn)生在兩個位置然后交換它們的基因，如果這兩個基因是相同的，則重新選擇新的位置。例如：父代1p1=1 2 43 2 1 4 2 2 3 1 41 4 3 3子代1=1 2 44 2 1 4 2 2 3 1 31 4 3 3B.4 數(shù)值試驗為了研究本文所述方法的有效行，文字研究和比較了之前的方法。在試驗只能夠，算法通過C+來進行編碼，遺傳算法的所有參數(shù)按以下所示：種群大小500，變異概率0.15，交叉概率0.7，表B.2展示了傳統(tǒng)方法和本文所述方法的調(diào)度結(jié)果。對每一個問題，本文所述的方法能夠立即得到最優(yōu)調(diào)度。MT10的調(diào)度甘特圖如圖B.2所示。表B.2 本文所述方法和其他方法