RM新时代手机版

遺傳算法解決FJSSP

問(wèn)題建模

圖3

編碼和解碼

本文采用分段編碼法來(lái)對染色體進(jìn)行編碼，染色體由機器選擇部分(MS)和工序選擇部分(OS)兩部分組成，長(cháng)度分別為N，N表示所有工件的所有工序的數量之和，MS和OS均采用間接編碼的方式來(lái)實(shí)現，如圖2所示。假設用i表示某個(gè)工件的序號，則i在OS中第幾次出現就代表是該工件i的第幾道工序。在MS中的數值表示某工件的某道工序所對應的在可選機器集中的第幾臺機器，就像問(wèn)題建模中所描述的，MS中的數值表示的是按先后順序從第一個(gè)工件的第一道工序開(kāi)始至最后一個(gè)工件的最后一個(gè)工件結束所選擇的在可選機器集中的第幾臺機器。所以OS和MS就這樣對應起來(lái)了，具體實(shí)現時(shí)考慮到效率問(wèn)題會(huì )將OS中某個(gè)元素所對應的某一個(gè)工件的某一道工序在MS中的位置和在proDesMatrix[][]中的位置用一個(gè)hashMap一一對應起來(lái)。使用hashMap關(guān)聯(lián)某工件的某工序在MS和proDesMatrix[][]中的位置可大幅降低查找時(shí)間，這對最終大幅降低獲得最優(yōu)解所花費的時(shí)間具有極大的幫助作用。
對染色體的解碼過(guò)程是這樣的：從左到至右遍歷OS序列，由OS序列確定其工件號和工序號，然后由其工件號和工序號經(jīng)由hashMap確定其在MS和proDesMatrix[][]中的位置，由MS中的值確定其在proDesMatrix[][]中的加工機器號和加工時(shí)間。

圖4
初始化種群

首先隨機產(chǎn)生一個(gè)100個(gè)個(gè)體大小的種群，每一個(gè)個(gè)體用一條染色體來(lái)表示。對于每一條染色體，在保證所有工件的所有工序數量都滿(mǎn)足的情況下隨機產(chǎn)生一個(gè)OS序列，在保證某工件工序所對應機器存在的情況下隨機產(chǎn)生一個(gè)MS序列。本算法對傳統的用單一方法生成初始種群的方法進(jìn)行改進(jìn)，以局部搜索、全局搜索和隨機搜索相結合的方式來(lái)產(chǎn)生初始種群，從而保證了初始解的質(zhì)量和種群的基因多樣性，從而大幅降低了獲得可行解所需要的時(shí)間。

適應度值計算

本文的適應度值的取值為各個(gè)工件完成所有加工操作的最大完工時(shí)間Cmax。
求解柔性車(chē)間調度的最短的總調度時(shí)間的難點(diǎn)有以下三點(diǎn)：各個(gè)工件不同的工序之間有嚴格的先后順序，這個(gè)問(wèn)題可以在OS編碼時(shí)被解決，因為染色體序列中各個(gè)工件出現的順序就代表著(zhù)各個(gè)工件的工序序列；每道工序有多臺加工機器可供選擇，這在MS編碼時(shí)被考慮，編碼、交叉和變異的過(guò)程就是對機器進(jìn)行選擇的過(guò)程；同一臺機器某個(gè)時(shí)刻只可以加工一種工件，這個(gè)問(wèn)題可以通過(guò)維護一個(gè)機器數目大小的一維數組來(lái)實(shí)現，數組存儲的值是該機器處理完當前工件后的空閑時(shí)間點(diǎn)。
車(chē)間調度執行的順序是按OS的編碼從左向右執行，如圖2所示，由調度問(wèn)題的執行位置和OS在該位置的值可知要加工工件的工件號i，然后通過(guò)工件號在OS的出現次數獲得該工件所在的工序號j，然后由其工件號和工序號經(jīng)由hashMap確定其在MS和proDesMatrix[][]中的位置，由MS中的值確定其在proDesMatrix[][]中相應位置上的加工機器號和加工時(shí)間，然后更新第i個(gè)工件第j道工序的開(kāi)始時(shí)間為第i個(gè)工件第(j-1)道工序的結束時(shí)間或該工序將要使用機器的最近空閑時(shí)間點(diǎn)的之中的較大者，更新第i個(gè)工件第j道工序的結束時(shí)間為該工序的完工時(shí)間，即開(kāi)始時(shí)間與加工時(shí)間之和，更新該工序所使用機器的最近空閑時(shí)間點(diǎn)為第i個(gè)工件第j道工序的加工完成時(shí)間。如果該工序的完工時(shí)間大于當前的最大完工時(shí)間，更新最大完工時(shí)間的值，直至OS中的所有工序被加工完畢，最終可以獲得完成車(chē)間調度所需的最大完工時(shí)間。最大完工時(shí)間越長(cháng)說(shuō)明越不符合我們的預期，因此，適應度的值反比于最大完工時(shí)間。
選擇

本文將輪盤(pán)賭策略和精英策略相結合的方式來(lái)選擇下一代個(gè)體，適應度越大的個(gè)體被選中的可能性越大。精英策略保證了種群朝著(zhù)更高的質(zhì)量進(jìn)行進(jìn)化，而輪盤(pán)賭策略有效地防止了求解陷入了局部最優(yōu)化的陷阱，兩者相輔相成，加速了種群的迭代和有效解的獲得。

交叉和變異

由于FJSSP編碼的特殊性，其遺傳算子的設計跟JSSP有顯著(zhù)的不同。本文在大量實(shí)驗的基礎上選擇了以下算子：對MS采用的分別為兩點(diǎn)交叉和單點(diǎn)變異算子，對OS則采用了順序交叉和逆轉變異算子。下面就分別簡(jiǎn)要介紹下本文所用到的交叉和變異算子。

1)、變異算子

對OS采用的逆轉變異算子非常簡(jiǎn)單，就是互換OS中不同位置的值。
對MS采用的單點(diǎn)變異要稍復雜些，具體過(guò)程是將MS指定位置中的值更新為某工件工序所對應的可選機器集中加工時(shí)間最短的那臺機器的代號。以圖2中工序O12 為例，其對應基因值為1，表示可選機器集中的第一臺機器M2。而該位置對應的可選加工機器包括M2和M4，如圖1所示，M2和M4的加工時(shí)間分別為5和3，由于M2的加工時(shí)間大于M4的加工時(shí)間，所以該位置基因變異為第二臺可選機器M4的代碼2，否則，則保持1不變。這種變異方法可加速產(chǎn)生最優(yōu)解的速度，降低獲得最有解所耗費的總的運行時(shí)間。

2)、交叉算子

MS的交叉操作采用兩點(diǎn)交叉法，具體過(guò)程是互換兩條染色體的MS部分的某一位置區間的所有基因值。由于MS的特殊設計，從第一個(gè)工件的第一道工序到最后一個(gè)工件的最后一道工序所選擇的機器保證了染色體交叉后仍然是有效的機器選擇序列，這大大地降低了單個(gè)工序在多個(gè)機器中選擇一個(gè)進(jìn)行處理的難度。
OS的交叉操作采用順序交叉法，首先產(chǎn)生范圍在[N,2*N]的兩個(gè)隨機數，而這兩個(gè)隨機數需滿(mǎn)足第一個(gè)隨機數小于第二個(gè)隨機數的條件，產(chǎn)生的兩個(gè)隨機數代表父代染色體要遺傳給子代染色體的染色體序列的起始和結束位置，以圖2中的OS序列為例，在本例中的兩個(gè)隨機數分別為2和3。父代染色體的部分編碼序列被子代繼承：Father1的編碼序列(2 1)被Child1繼承，Father2的編碼序列(1 2)被Child2繼承。Child1:[,2,1,,]，即：繼承的工序分別為工件2的第二個(gè)工序和工件1的第一個(gè)工序。為了獲得Child1染色體的其它工序項：
首先，我們以Father2為模板從第二個(gè)隨機數3所在的位置后面開(kāi)始循環(huán)構造一個(gè)新的染色體序列：(2///1 2 1 2)。然后，我們將已經(jīng)從Father1中繼承的工件序列從新產(chǎn)生的染色體序列中移除(即：工件2的第二個(gè)工序和工件1的第一個(gè)工序)：由(2 X X 1 2)獲得(2 1 2)。最后，填充Child1剩余部分 ：首先從第二個(gè)隨機數所代表的位置后面開(kāi)始填充得到[ , 2, 1, 2, 1]，然后循環(huán)填充得到最終序列[2,2,1,2,1]。同理可求得Child 2的其它工序項。順序交叉的大致步驟如圖3所示。由于這種特殊的設計，OS序列交叉后所獲得的序列仍然是有效的，這極大地擴大了遺傳算法在可行解中的搜索范圍，提高了遺傳算法的搜索能力，對最終獲得最優(yōu)解提供了有力的保證。

圖

停止條件

遺傳算法運行到總調度時(shí)間達到給定下限或者迭代次數達到200次。

實(shí)驗結果

考慮到圖片中文字的可讀性，本文以規格為10*6的經(jīng)典FJSSP測試用例mk01為例將一個(gè)最佳調度以甘特圖的形式展示出來(lái)。具體調度信息如圖4所示，其中，圖中p(i,j)表示工件j在機器i上的加工時(shí)間，i表示機器i，j表示工件j。

圖