合作型協(xié)同進(jìn)化遺傳算法求解分布式柔性作業(yè)車間調(diào)度問題＊

董博文 王有遠(yuǎn)

（①南昌航空大學(xué)飛行器工程學(xué)院，江西 南昌 330063；②南昌航空大學(xué)工業(yè)工程研究所，江西 南昌 330063；③南昌市航空復(fù)雜系統(tǒng)與智能科學(xué)重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063）

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

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

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

1 分布式柔性作業(yè)車間調(diào)度問題

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

2 合作型協(xié)同進(jìn)化遺傳算法求解DFJSP

2.1 編碼與解碼

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

圖1 DFJSP 實(shí)例的一個(gè)編碼方案

表1 DFJSP 實(shí)例

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

圖2 編碼方案對應(yīng)的調(diào)度甘特圖

2.2 協(xié)同機(jī)制

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

2.3 種群初始化與進(jìn)化算子

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

選擇算子用于模擬適者生存的原則，能夠幫助種群向最優(yōu)個(gè)體收斂，使用三元錦標(biāo)賽進(jìn)行選擇，以平衡隨機(jī)協(xié)同機(jī)制收斂速度慢的影響。

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

圖3 工序排序兩點(diǎn)順序交叉

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

2.4 多重局部擾動策略

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

鄰域1：將關(guān)鍵工廠中的一個(gè)工件分配到完工時(shí)間最小的工廠中。

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

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

鄰域4：隨機(jī)選擇一個(gè)關(guān)鍵工序，與關(guān)鍵工廠的其他工序交換。

鄰域5：隨機(jī)選擇一個(gè)關(guān)鍵工序，插入到關(guān)鍵工廠工序序列的某個(gè)位置。

鄰域6：對于關(guān)鍵工廠中關(guān)鍵路徑，采用移動一個(gè)工序的鄰域搜索方法。

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

多重局部擾動過程如下：

Step1：隨機(jī)選擇一個(gè)鄰域擾動算子。

Step2：根據(jù)鄰域結(jié)構(gòu)生成一個(gè)新解。

Step3：若新解優(yōu)于原解，以新解為中心返回Step1，否則返回Step2，直到鄰域結(jié)構(gòu)全部搜索完。

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

2.5 算法整體框架

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

圖4 CCGA 算法偽代碼

3 實(shí)驗(yàn)驗(yàn)證

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

3.1 多重局部擾動策略有效性驗(yàn)證

為驗(yàn)證多重局部擾動策略的有效性，使用2 工廠下的23 個(gè)基準(zhǔn)進(jìn)行對比實(shí)驗(yàn)，對比結(jié)果見表2。

表2 CCGA-non 與CCGA 對比實(shí)驗(yàn)

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

3.2 CCGA 算法有效性驗(yàn)證

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

表4 CCGA 和其他算法計(jì)算結(jié)果對比（3 工廠）

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

4 工廠情形時(shí)可用生產(chǎn)資源進(jìn)一步增加，CCGA和GA_JS、GA_OP、IDESAA、IGWO、HSFLA 均能找到23 個(gè)基準(zhǔn)的最優(yōu)解，在此不再列出實(shí)驗(yàn)結(jié)果。從以上結(jié)果分析可知，CCGA 在求解DFJSP 時(shí)是有效的。圖5 所示為2 工廠情形時(shí)基準(zhǔn)la08 的最優(yōu)調(diào)度甘特圖。

圖5 2 工廠情形la08 基準(zhǔn)調(diào)度甘特圖

4 結(jié)語

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

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