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

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