合作型協同進化遺傳算法求解分布式柔性作業車間調度問題＊

董博文 王有遠

（①南昌航空大學飛行器工程學院，江西 南昌 330063；②南昌航空大學工業工程研究所，江西 南昌 330063；③南昌市航空復雜系統與智能科學重點實驗室，江西 南昌 330063）

隨著經濟全球化發展，許多制造企業由集中式制造向分布式制造轉變，生產制造不再局限于在單一工廠進行，而是多工廠協同制造。生產調度在分布式制造中進一步延伸，在機械加工等制造場景中，產生了分布式柔性作業車間調度問題（distributed flexible job shop scheduling problem，DFJSP）。DFJSP屬于NP（難問題），對其進行優化有助于縮短制造期、提高機器利用率，因此其研究具有重要的學術意義和應用價值。

國內外學者對DFJSP 進行了相關研究。Chan F T S 等[1]最早研究了DFJSP，提出了一種基于支配基因的遺傳算法，對問題解空間進行了完全編碼；Giovanni L D 等[2]使用不完全編碼方式，只編碼了工廠分配和工序排序信息，通過解碼確定機器選擇，提出一種改進遺傳算法（IGA）求解DFJSP；Lu P H 等[3]和Wu M C 等[4]分別使用工件序列（GA_JS）和工序序列（GA_OP）一維編碼，設計啟發式規則進行解碼；Marzouki B 等[5-6]使用分散禁忌搜索（DTSMA）和化學反應優化算法（CRO）求解DFJSP；吳銳等[7]提出一種改進人工蜂群算法，引入基于關鍵路徑的局部搜索算子提高算法局部搜索能力；吳秀麗等[8]設計了一種改進差分進化算法（IDESAA），利用模擬退火提高算法的局部搜索能力；孟磊磊等[9]提出了一種混合蛙跳算法（HSFLA），結合變鄰域搜索提高算法的局部搜索能力；Li X Y 等[10]使用工廠分配和工序排序雙層編碼，提出一種改進灰狼優化算法（IGWO），使用基于關鍵工廠和關鍵路徑的鄰域搜索策略。

上述研究主要通過在部分解空間搜索來降低對DFJSP 的求解難度，隨著問題規模增大解空間急劇擴大，算法全局搜索能力不足，尋優能力變差。本文提出一種合作型協同進化遺傳算法（cooperative co-evolutionary genetic algorithm，CCGA）求 解DFJSP，利用分而治之的思想將問題分解為多個低維子問題，使用隨機協同機制促進子種群協同進化以提高算法全局搜索能力。為彌補協同進化全局搜索能力強而局部開發能力弱的缺點，使用基于關鍵工廠的多重局部擾動策略，提高算法的局部開發能力。通過對公共基準算例進行測試并與其他算法對比，驗證了所提算法的有效性。

1 分布式柔性作業車間調度問題

DFJSP 描述如下：給定n個待加工工件J={J1,J2,···,Ji,···,Jn}，需要將其分配給q個工廠U={U1,U2,···,Ul,···,Uq}加工。工件i有ni個工序Ji={Oi1,Oi2,···,Oij,···,Oini}，若工件i分配到工廠l加工，則該工件所有工序均在該工廠內加工。工廠l有ml臺機器 Ml={Ml1,Ml2,···,Mlk,···,Mlml}，可加工工序Oij的機器集合為每臺機器在同一時刻最多只能加工一個工序，任一工件在任一時刻只能在一臺機器上加工。工序一旦開始加工便不能中斷，同一工件的所有工序需滿足優先約束。所有工廠、機器和工件都在0 時刻可用，加工時間在不同工廠以及機器上可能不同。DFJSP 的目標是將工件分配給工廠、選擇加工工序的機器和確定各機器上的加工順序，使得調度的最大完工時間最短。DFJSP 的數學模型可參考Meng L 等[11]歸納的4 種主要模型。

2 合作型協同進化遺傳算法求解DFJSP

2.1 編碼與解碼

為使算法在解空間的較優區域搜索，采用工廠分配和工序排序解耦編碼方式，在解碼時基于機器負荷確定機器選擇。一個DFJSP 實例見表1，表中“-”表示該工序無法在該機器加工。該實例的一個編碼方案如圖1 所示，工廠分配編碼FA 長度與工件數相同，第i個基因表示工件i所分配的工廠，如第1 個基因表示工件J1分配到工廠2。工序排序編碼OS 長度與總工序數相同，使用工件號編碼，工件號出現的次數表示第幾個工序，如第4 個基因為3，第二次出現，表示為工序O32。

圖1 DFJSP 實例的一個編碼方案

表1 DFJSP 實例

染色體解碼依OS 順序依次解碼，根據FA 編碼確定工序所在工廠，進而確定可用機器集。選擇最大完工時間最小的機器，當具有相同的最大完工時間時，選擇加工時間短的機器，若加工時間也相同，則隨機選擇。在將工序分配給機器時，使用貪心策略，將工序安排在盡可能早地符合要求的機器空閑中，使得完工時間最小。圖1 所示的第一個基因表示工序O21，根據FA 可知工件J2分配到工廠1，對應有兩臺機器M11和M12可加工，工時分別為1和2，顯然在機器M11上的完工時間比在M12上短，因此選擇機器M11加工工序O21。圖1 編碼方案對應的調度甘特圖如圖2 所示。

圖2 編碼方案對應的調度甘特圖

2.2 協同機制

CCGA 的思想是將問題分解為多個子問題，分而治之。子問題之間的協同機制是CCGA 的一個關鍵因素，子種群中個體的適應度評估需要與其他子種群中的個體協作。常見的協同機制包括最優個體協同選擇、最差個體協同選擇、隨機個體協同選擇等。為提高算法全局搜索能力，使用隨機個體協同機制，以盡可能多地搜索解空間。對于工廠分配子種群中的一個個體Pi，隨機選擇工序排序子種群中的一個個體，組合成完整染色體，通過解碼得到的最大完工時間即為Pi的適應度，工序排序子種群中的個體適應度評估類似。

2.3 種群初始化與進化算子

初始種群的質量對于算法迭代搜索有一定的影響，好的初始種群能夠幫助算法找到更優解。為提高初始種群質量，隨機生成OS 部分編碼，使用Lu P H 等[3]提出的基于工廠負荷的工廠分配方法確定FA 部分編碼。

選擇算子用于模擬適者生存的原則，能夠幫助種群向最優個體收斂，使用三元錦標賽進行選擇，以平衡隨機協同機制收斂速度慢的影響。

交叉有助于增加種群多樣性，工廠分配編碼使用單點交叉，工序排序編碼使用兩點順序交叉[4]，如圖3 所示。兩個交叉點將個體分為3 段，子代C1保留父代P1的第一段和第三段，在父代P2中刪除這些基因，剩余部分即為C1第二段。這樣能保證得到的子代依然是可行解，且最大限度繼承父代的編碼信息。子代C2使用類似的方法產生。

圖3 工序排序兩點順序交叉

變異能在一定程度上避免算法陷入局部最優解，使用逆轉變異算子對FA 與OS 進行變異，即任意選取兩點，逆轉兩點之間的基因順序。

2.4 多重局部擾動策略

DFJSP 中完工時間最大的工廠稱為關鍵工廠，關鍵工廠中具備最大完工時間的路徑稱為關鍵路徑，關鍵路徑上的工序稱為關鍵工序。只有關鍵工廠和關鍵路徑發生變化，才可能打破原有調度得到更優解。CCGA 將問題分解為多個子問題，分而治之，優勢是能夠更加充分搜索解空間，缺點是局部開發能力較差。為提高所提算法的局部開發能力，設計如下6 個鄰域擾動算子。

鄰域1：將關鍵工廠中的一個工件分配到完工時間最小的工廠中。

鄰域2：將關鍵工廠的工序分成k段，每一段第一個基因與其他基因交換。

鄰域3：將關鍵工廠的工序分成k段，重排k段的順序。

鄰域4：隨機選擇一個關鍵工序，與關鍵工廠的其他工序交換。

鄰域5：隨機選擇一個關鍵工序，插入到關鍵工廠工序序列的某個位置。

鄰域6：對于關鍵工廠中關鍵路徑，采用移動一個工序的鄰域搜索方法。

鄰域2 和3 改編自Zhu J 等[12]提出的部分成對交換和簡單插入，將均勻分為k段改為隨機點位分段。鄰域4 和5 改編自Valente J M S 等[13]提出的鄰近非鄰近交換和插入，將隨機選擇一個工序改為選擇一個關鍵工序。鄰域6 為Mastrolilli M 等[14]針對FJSP 提出的移動一個關鍵工序鄰域結構。

多重局部擾動過程如下：

Step1：隨機選擇一個鄰域擾動算子。

Step2：根據鄰域結構生成一個新解。

Step3：若新解優于原解，以新解為中心返回Step1，否則返回Step2，直到鄰域結構全部搜索完。

為提高計算效率，設定只有當新個體適應度不超過最優解d時才進行多重局部擾動，同時為避免進化后期種群收斂造成大量個體滿足上述要求導致計算量增大，設定每個種群最多15%的個體能夠進行多重局部擾動，且增加選擇概率，rand＜ 0.5時才進行多重局部擾動，提高局部搜索的均勻性。

2.5 算法整體框架

CCGA 算法偽代碼如算法1（圖4），4～10 行表示工廠分配子種群和工序排序子種群分別進化；11～23 行表示使用隨機協同策略評估個體適應度，并對滿足條件的個體進行多重局部擾動；26～28 行表示在算法陷入局部最優時引入隨機個體，提高種群多樣性繼續搜索，以幫助算法跳出局部最優。

圖4 CCGA 算法偽代碼

3 實驗驗證

采用De Giovanni L 和Pezzella F[2]基 于23 個FJSP 基 準（la01-la20、mt06、mt10 和mt20）拓 展到2/3/4 工廠情形下生成的69 個DFJSP 基準驗證CCGA 的有效性。使用Matlab R2020b 編程，取種群規模N=200、最大迭代次數G=150、交叉概率Pc=0.95、變異概率Pm=0.01、局部擾動比例參數d=0.2，每個基準獨立運行30 次。

3.1 多重局部擾動策略有效性驗證

為驗證多重局部擾動策略的有效性，使用2 工廠下的23 個基準進行對比實驗，對比結果見表2。

表2 CCGA-non 與CCGA 對比實驗

表2 中CCGA 表示帶多重局部擾動策略，CCGAnon 表示不帶多重局部擾動策略，Cm表示所求得的最好的最大完工時間，AVG 表示平均最大完工時間。23 個基準中有10 個基準（la06-la09、la11-la15、mt20）CCGA 求得的最優解和平均值都比CCGAnon 好，剩余13 個基準所求得的最優解相同，其中CCGA 在基準la10 和la19 上的平均值比CCGAnon 好。使用Minitab 19.1 對兩個算法在23 個基準上求得的最優值和平均值進行Wilcoxon 符號秩檢驗，置信區間為95%，得到p值為0.006 和0.003，均小于0.05，說明CCGA 在統計意義上顯著優于CCGA-non，即多重局部擾動策略是有效的。

3.2 CCGA 算法有效性驗證

將CCGA 與其他求解DFJSP 的算法進行比較，所求得的最優解對比結果見表3 和表4，表中最后一行為使用Wilcoxon 符號秩檢驗得到p值，最后一列帶“*”號表示CCGA 找到基準下界。在2 工廠情形時，所有算法在la01～la05、la16～la20、mt06以及mt10 基準上均能找到下界。剩余11 個基準中，CCGA 求得的最優解均優于IGA、DTSMA、CRO和GA_JS，且Wilcoxon 符號秩檢驗得到p值均小于0.05，證明CCGA 優于IGA、DTSMA、CRO 和GA_JS 這4 個算法。對于GA_OP 和IDESAA，CCGA分別在3 個和4 個基準上找到更優，Wilcoxon 符號秩檢驗得到p值均大于0.05，說明GA_OP 和IDESAA在統計意義上與CCGA 無顯著差異。對于IGWO和HSFLA，求解結果和p值均表明其優于CCGA。

表4 CCGA 和其他算法計算結果對比（3 工廠）

在3 工廠實驗中，由于生產資源增加，但是生產任務沒有變化，因此比較容易找到最優解。從表4 可以看出，CCGA 在3 工廠情形下求解結果比IGA、DTSMA、CRO、GA_JS 和GA_OP 要好。與剩余算法求解結果主要在基準la13、la15 和mt20上不同，Wilcoxon 符號秩檢驗p值均大于0.05，表明CCGA 與這些算法在統計意義上沒有顯著差異。

4 工廠情形時可用生產資源進一步增加，CCGA和GA_JS、GA_OP、IDESAA、IGWO、HSFLA 均能找到23 個基準的最優解，在此不再列出實驗結果。從以上結果分析可知，CCGA 在求解DFJSP 時是有效的。圖5 所示為2 工廠情形時基準la08 的最優調度甘特圖。

圖5 2 工廠情形la08 基準調度甘特圖

4 結語

本文提出了一種合作型協同進化遺傳算法求解DFJSP，利用分而治之的思想提高全局搜索能力，并設計多重局部擾動策略提高算法的局部開發能力。在公共基準上的實驗結果以及Wilcoxon 符號秩檢驗表明多重局部擾動策略的有效性。在與其他算法對比中，所提算法優于IGA、DTSMA、CRO 和GA_JS這4 個算法，與GA_OP 和IDESAA 性能相近，略差于IGWO 和HSFLA，表明所提算法求解DFJSP 是有效的。

DFJSP 這類問題通常包含多個子問題，與合作型協同進化算法的分而治之思想相貼合，因此具有一定的研究潛力。未來可以使用不同的協同機制，或在求解子問題時使用不同的進化算法來設計合作型協同進化算法。也可以嘗試使用合作型協同進化算法求解多目標DFJSP 以及其他車間調度問題。