基于Co-CEM的柔性車間調度優化算法

張政, 徐鵬, 孟宇龍, 盧中玉, 鄒家睿

(1.哈爾濱工程大學,計算機科學與技術學院, 黑龍江 哈爾濱 150001; 2.中國船舶重工集團有限公司, 江蘇 連云港 222006)

柔性車間調度問題是船舶制造過程的一種抽象描述,本文旨在提出一種有效的智能優化算法,對傳統的排產問題進行求解,從而保證國內船舶制造企業生產計劃的穩定性和有效性,減少計劃的盲目性。除船舶制造業外,其他領域如電力系統、醫療資源分配系統等均存在以上需求,因此基于柔性車間調度模型對傳統調度問題進行求解,對實際的生產制造如中國制造2025等規劃均具有重要的現實意義。

近年來,國內外研究人員主要解決如何減少柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)的最晚完工時間。Zhang等[1]使用一種基于圖神經網絡的深度強化學習方法來產生工序的優先級分配規則。Park等[2]同樣使用圖神經網絡,將車間調度問題看作一些隨著時間變化的決策問題,使用圖表示當前的狀態,并且驗證了算法在未見過的實例上也有很好的表現。一些群體智能算法也可以用在FJSP的求解上。Brandimarte[3]使用啟發式規則確定每道工序所分配的機器,因而可以將FJSP轉化為車間調度問題(job shop scheduling problem,JSP),然后使用禁忌搜索來求解JSP。Pezzella等[4]針對種群的初始化問題設計了一系列種群初始化規則來生成高質量初始種群。Yuan等[5]將差分進化算法(differential evolution,DE)應用在FJSP相關的求解上,使用了一種新穎的轉化方法,同時使用了一種局部搜索機制加強算法的搜索性能,并定義了2種領域結構。劉晶晶等[6]設計了一種混合果蠅遺傳優化算法對FJSP進行求解,其中使用了兩階段組合進行優化,實驗證明了算法可行性。石小秋等[7]建立了FJSP相應的數學模型,其中提出了一種基于總個體數的評價指標,用以分析算法參數對性能的影響,并提出了一種并提出了一種自適應變級遺傳雜草算法。Zhu等[8]針對加工時間的不確定性提出了區間灰色數字的方法來解決,并且針對工序間的物料清單(bill of materials,BOM)結構定義了相關樹形模型,最后提出了基于層級領導優化器的多微粒子群算法。Gu[9]針對考慮低碳的FJSP,提出了混合人工蜂群算法。Chen等[10]在考慮工序間傳送時間的約束條件下,提出了一種混合離散粒子群算法來求解。同時,Wang等[11]針對工序啟動時間和滯后時間的約束條件,提出了基于遺傳算法和禁忌搜索的混合優化算法。Ding等[12]提出了一種鏈式編碼規則和相應的反向解碼來迅速定位關鍵工序,并且提出了一種策略協作的自適應算法。

本文針對FJSP,提出使用交叉熵算法(cross-entropy method,CEM)進行求解。首先通過分析不同調度之間的關系,提出基于主動調度的遺傳解碼算法,然后為解決CEM局部搜索能力不足的問題,對其進行改進提出基于協同進化策略的交叉熵算法(cooperative coevolution-based CEM,Co-CEM),實驗證明協同進化策略,有效彌補CEM局部搜索能力較弱的問題。

1 Co-CEM算法原理

1.1 個體編碼與解碼

柔性作業車間調度可以分解為機器分配問題(routing problem)與工序排序問題(sequencing problem)2個子問題,因此,合適的解結構應該表示工序間的加工順序與每道工序所分配的機器。常用的編碼方式包括三元組模式[4]和雙向量模式[5]。考慮本文提出的算法需要分別處理2種問題,所以采用雙向量模式編碼個體:即工序向量與機器向量。

1.2 種群初始化

本文所提算法針對FJSP的每一個解分別使用機器分配規則與工序順序規則來初始化,共使用4種機器分配規則來初始化解向量的機器分配部分,包括2種全局初始化規則、1種局部分配規則與1種隨機分配規則。步驟如下:

1)全局最小負載[4]:每次從所有的機器中選擇負載最小的機器進行分配;

2)隨機排列[4]:首先對工序向量進行隨機排序,接著從左往右依次遍歷工序向量,對每道工序選擇負載最小的機器;

3)最小加工時間:工序分配給加工時間最短的機器;

4)隨機分配:每臺設備能夠完成所有工序的情況下,對每一道工序,隨機分配對應的加工機器。

針對解向量的工序部分的初始化,本文使用了3種排序規則,步驟如下:

1)最多剩余工時:根據每個任務剩余的工時進行工序分配。從所有任務中選擇一個具有最小剩余工時的任務分配其工序;

2)最多剩余工序:根據每個任務剩余的工序數進行工序分配。從所有任務中選擇一個具有最少工序數的任務分配其工序;

3)隨機排序:隨機分配所有工序的加工順序。

如上所述,共有4種機器分配規則和3種工序排序規則。為減少算法的超參數,本文使用一種基于啟發式規則的自適應種群初始化方法[13]生成初始解集,可以在一定程度上保證算法的健壯性。

1.3 概率模型及其更新

定義P∈RN×N是用于生成工序向量的工序概率分布矩陣,Q∈RN×M為用于生成機器向量的機器概率分布矩陣,其中N為總工序數,M為總機器數,則P(i,j)表示工序向量的第i個位置分配工序j的概率,為保證整個解空間可以被均勻采樣,在初始狀態下令P(i,j)=1/N。Q(i,j)表示機器向量的第i個位置分配機器j的概率,初始值為:

Q(i,j)=

(1)

式中mi表示可以加工工序i的機器數。

由于同一任務的工序之間存在先后關系約束,工序向量的第i個位置可選擇的工序不能任意取自1,2,…,N,而與工序向量下標0～(i-1)所選擇的工序有關。同樣,由于機器選取與工序選取的內在關系,機器向量受到相同約束制約,即第i個位置可選擇機器不能任意取自所有機器,而是與該位置對應工序可選擇的機器集有關。針對該約束條件,分別引入工序向量om與機器向量mm。以om向量為例,定義om∈RN,表示當前位置可選擇的所有工序,取值為:

om(i)=

(2)

當對工序向量的位置i選擇工序時,使用om進行篩選,得到概率分布向量sv然后對其處理保證概率和為1,使得生成的工序是可行解,計算步驟為:

sv=P(i,:)×om

(3)

sv=sv/sum(sv)

(4)

一旦工序向量第i個位置的工序確定,則更新om,保證后續生成的工序有效。

對于機器向量的生成步驟也采用類似的方法處理。通過mm去除掉采樣過程中的無用解,保證了所生成的解是有效的。

在采樣得到新種群后,交叉熵算法會根據適應度選擇ne個精英個體用來更新工序概率分布矩陣P和機器概率分布矩陣Q,更新公式為:

(5)

(6)

(7)

(8)

2 基于主動調度的遺傳解碼

2.1 調度類型

對于一個可行解,其機器向量部分是固定的,確定了每道工序分配的機器。同時,主要的調度類型可以分為活動調度、半活動調度和非延遲調度3類[14]。如果以最晚完工時間作為評價指標,則相關最優解只存在于活動調度中[13],同時1.1節中介紹的樸素解碼算法只能得到半活動調度。

該問題可以使用一種插入式解碼算法[15]解決,但是由于工序向量中工序位置不能反映實際加工優先級,由式(5)可知,存在誤導概率分布矩陣更新從而影響收斂速度的問題。

2.2 基于主動調度的遺傳解碼

針對2.1節描述的當前解碼存在的問題,本文提出了基于主動調度的遺傳解碼。樸素的解碼算法會得到半活動調度的根本原因在于嚴格按照工序向量的工序順序安排加工。因此,本文提出基于主動調度的解碼算法。

在解碼分配下一道加工工序時,設當前剩余未加工工序為集合為P,對任意一道工序O∈P,設其前置工序為pj,分配的機器為M(O)。此外,定義Et(·)表示任意一道機器的最早可用時間,則有:

(9)

(10)

(11)

式中:η∈(0,1)為延遲度,表示為了讓更多工序滿足提前主動調度的條件,可以適當延遲后續工序的最早開始時間。

在得到當前分配的所有可主動調度工序后,對其按照加工時長進行排序,選擇具有最長加工時長的工序進行實際的主動調度,保證參考工序前的空閑時間段盡可能的小。如果當前符合以下條件之一:1)多道工序滿足實際的主動調度條件;2)不存在可主動調度工序;3)參考工序前不存在空閑時間段;則調度優先級最高的工序。每道工序的優先級為其在工序向量中的實際下標,下標越小即越靠近工序向量左側的工序優先級越高。這種解碼方式可以使算法在更小的空間內搜索增大找到最優解的概率。

為將優化后的活動調度信息保留到后續計算,在工序重排時按照逆序數減小的趨勢進行調整[15]。

基于主動調度的遺傳解碼算法如下:

1) 輸入半活動調度OS,當前總工序數nt,設置延遲度η。

2) 遍歷當前工序數nt,執行以下過程。

① 每次分配一道工序i,計算當前所有未分配工序的最早結束時間tfinish,令mect=min(tfinish)并計算從當前未分配的工序中找到最早結束時間為mect的工序etask,從機器向量中獲取etask分配的加工機器emachine。

② 從emachine上找到最早開始時間小于等于mect的工序eeligible_tasks,以OS中的下標為優先級找到最高優先級的工序作為參考工序rtask。

③ 獲取emachine的最早可用時間gstart,并從eeligible_tasks中選取可主動調度工序gend。令itask=eeligible_tasks[tfinish[eeligible_tasks]≤gend],如果itask的長度不為零,就從itask中選取加工時長最長的工序eeligible_tasks。

3) 從eeligible_tasks中選取優先級最高的工序進行主動調度,得到stask。

4) 在不影響最終結果的條件下將stask按照逆序數減少的趨勢插入適當位置,將stask從未分配工序集合中刪除,并更新受影響工序的最早開始時間和受影響機器的最早可用時間。

5) 輸出活動調度OS′。

基于主動調度的遺傳解碼算法引入了超參數——延遲度,所以該值的選取會對解碼結果有較大的影響。為避免延遲度較大而導致整體完工時間的推遲,延遲度應該取[0.1,0.2)。

3 面向FJSP的Co-CEM

3.1 協同進化策略

本節提出使用協同進化策略加強交叉熵算法的局部搜索能力,在全局搜索持續ns代陷入“停滯”時,使用協同進化策略,分別使用工序搜索算子與機器搜索算子進行迭代,最后在滿足一定條件后,重新再使用概率矩陣進行全局搜索。算法整體流程如圖1所示。

圖1 協同進化策略Fig.1 Coevolutionary strategy

對于工序搜索算子,設存在父代個體m、n,則步驟如下:

1)判斷m與n是否相同,如果相同則隨機交換兩道不屬于同一任務的工序得到新個體并直接返回;否則執行步驟2);

2)設當前任務數為N,對N個任務進行編號,從其中隨機選擇若干個任務得到集合u,定義v為集合u的補集,如果選擇的任務數為0或者等于N,則重新進行選擇;

3)子代p個體中屬于集合u中的工序從父代個體m中依次拷貝到對應位置,剩余屬于集合v中的工序則依次從父代個體n中依次拷貝到對應位置;

4)相反的,子代q個體中屬于集合u中的工序從父代個體n中依次拷貝到對應位置,剩余屬于集合v中的工序則依次從父代個體m中依次拷貝到對應位置。

相應的機器搜索算子的詳細步驟如下:

1)設當前工序數為N,從N道工序中,隨機選擇k道組成集合u,如果集合u中元素的個數為0或者等于N,則重新進行選擇。

2)將父代個體m和n中屬于集合u中的工序,對其分配的機器進行交換得到后代個體p、q。

3.2 基于關鍵工序的鄰域搜索

本文使用了一種基于關鍵工序的鄰域搜索算法,用來優化協同進化策略中的部分精英個體。首先基于析取圖模型[14],定義包含n個關鍵工序的集合c(G)={c1,c2,…,cn},同時令Cmax(G)表示析取圖G對應的最晚完工時間。因為圖G的最晚完工時間不小于任意的關鍵路徑,所以只有移動關鍵工序Oi,jc(G)才能減小最晚完工時間。設通過移除圖G中的一道關鍵工序ci得到圖G-。則移動關鍵工序ci到工序v前無環的條件[16]為當且僅當滿足:

(12)

令ωk為圖G-中機器k上根據開始加工時間非降序排序得到的集合,且ci?ωk,定義ωk中的2個工序子集Lk和Rk為:

Lk={v

(13)

Rk={v

(14)

對?v∈Γk,其中Γk為處于Lk-Rk與Rk-Lk間的工序集合,將ci插入得到一個調度解G′[17],且Γk中存在最優插入位置當且僅當滿足:

(15)

設Ol(l=1,2,…,Nc)為要移動的關鍵工序,Nc為當前調度的關鍵工序的個數。將關鍵工序從原來的關鍵路徑刪除并插入新的位置,且插入位置滿足式(15),則新解的最晚完工時間不會大于舊的最晚完工時間。

基于關鍵工序的鄰域搜索算法如下:

1) 輸入算法參數,包括種群P,種群搜索率θ,最大鄰域搜索次數nl,設置搜索次數ns為max(len(p))×θ),1)。

2) 種群在ns次數下,執行以下過程:

① 將種群P按照適應度進行排序,適應度高的個體排在左側,并對個體進行鄰域搜索,次數為ns;

② 從P中根據輪盤賭算法選擇一個個體Pindex,并解碼其為析取圖;

③ 只要G*不為空且未達到最大鄰域搜索次數nl,持續移動G的關鍵工序得到鄰域解G*,并根據替換規則比較G與G*;

④ 根據替換規則檢查是否替換,如果是則將p編碼為個體Pindex。

3) 輸出優化后的種群P。

其中一個新的調度解替換舊的調度解當且僅當滿足其一:1)新解有更小的最晚完工時間;2)新解有相同的最晚完工時間但是有更少的關鍵路徑。

4 單目標FJSP下Co-CEM實驗與分析

4.1 實驗目的與方案

本節實驗主要分為3個部分:1)為了分析基于主動調度的遺傳解碼與插入式解碼之間的性能差異,首先在隨機初始化條件下對二者解碼得到的結果進行對比,其次分別將二者加入CEM進行對比;2)為了驗證協同進化策略對CEM性能的影響,分別在有、無該策略的條件進行對比;3)將Co-CEM與現在具有較強競爭力的算法進行對比,證明算法的可靠性。

上述實驗主要對比指標為算法得到調度解的最晚完工時間,越小的最晚完工時間表示工序之間空閑時間段越少,表明算法的優化性能越強。其中最晚完工時間使用秒作為單位。

4.2 實驗環境與數據集

本文算法都使用Python編程實現,計算機處理器 CPU主頻為四核3 GHz,內存16 GB。數據集包括Kacem[18-19]與BRdata[3],其中Kacem數據集包括5項用例,BRdata包含10項用例,BRdata中的用例的工序數包括從最少的55道至最多的240道。

4.3 實驗與結果分析

當使用進化算法求解FJSP時,由于問題規模不同,求解難度也不盡相同,因此應當對不同的用例,設置相應的算法參數。

算法的超參數包括:迭代次數、策略切換閾值、種群大小和精英解個數等,此外還有2個概率模型各自的更新率α和β。設輸入數據的任務數為n,機器數為m,算法參數設置如表1所示。

表1 算法參數Table 1 Algorithm parameter

1)實驗1 插入式解碼與遺傳解碼之間的性能對比。

首先使用基于啟發式規則的初始化方法得到大小為n的初始種群,然后分別使用樸素解碼、插入式解碼與基于主動調度的遺傳解碼計算原始種群的最晚完工時間,最后對不同條件下得到的結果進行對比。

采用BRdata數據集中數據規模各不相同的Mk01、Mk02、Mk04和Mk07用例作為測試數據,種群規模為50。實驗結果如圖2所示,可以看出,由于樸素解碼得到的結果為半活動調度解,以至于最晚完工時間不是最優的。接下來對比插入式解碼與遺傳解碼,從Mk01、Mk02與Mk07 3個用例可以看出二者的結果相差無幾,然而在Mk04用例中,大部分情況下遺傳解碼要明顯優于插入式解碼。接下來分析2種不同解碼方式對算法的性能的影響。

圖2 不同用例下不同解碼算法之間的對比Fig.2 Comparison between different decoding algorithms for different use cases

令CEM-I表示應用插入式解碼的算法,CEM-G表示使用遺傳解碼的算法,同樣使用Mk01、Mk02、Mk04和Mk07用例,比較CEM-I與CEM-G隨著迭代次數的增加,最晚完工時間的變化趨勢,即收斂趨勢圖,結果如圖3所示,可以看出CEM-G的收斂速度明顯優于CEM-I。最后分別使用Kacem的5個用例與BRdata的10個測試用例,對不同解碼算法的優化性能進行差異化分析:分別使用CEM、CEM-I及CEM-G各自運行30次,并分別列出15個用例下的最優結果、平均值與標準差,結果如表2所示。

表2 不同用例下CEM-I與CEM-G結果Table 2 CEM-I vs. CEM-G results for different use cases

圖3 不同用例下CEM-G與CEM-I的收斂圖Fig.3 Convergence plot of CEM-G vs. CEM-I for different use cases

如表2所示,最優結果被加粗,可以看出CEM-G與CEM-I的結果均優于CEM。從最優結果來看,CEM-G在11項用例中取得了最優結果,CEM-I在10項用例中取得了最優結果。從均值角度來看,CEM-G在大部分情況下可以得到優于CEM-I的結果。從標準差角度來看,CEM-G在大部分用例中的標準差均小于CEM-I。綜上證明了遺傳解碼在CEM中大部分情況下優于插入式解碼并且更加穩定。

2)實驗2 協同進化策略對CEM性能的影響。

為驗證協同進化策略對算法性能的影響,本次實驗使用了5項Kacem用例與10項BRdata用例,對CEM與Co-CEM的性能進行對比,并且均使用相同超參數與概率模型更新機制,此外由于協同進化策略使用到了鄰域搜索算法,為了公平起見,將該鄰域搜索算法也加入到CEM中,并且二者的解碼算法均使用基于主動調度的遺傳解碼。各自運行30次結果如表3所示,其中最優結果被加粗。

從表3可以看出,Co-CEM的結果均優于CEM,其中Kacem用例中二者獲得的最優結果相同,但是CEM的標準差指標不為0,表示健壯性不如Co-CEM。綜上,協同進化策略可以較好地完善交叉熵算法的局部搜索能力,增大算法得到優質解的概率。

3)實驗3 Co-CEM與其他算法的對比。

為了驗證Co-CEM的有效性,使用Kacem用例與BRdata用例,分別與并行變鄰域搜索算法[20](parallel variable neighborhood search,PVNS)、教與學優化算法[21](teaching-learning-based optimization,TLBO)、自適應變鄰域搜索遺傳算法[22](improved genetic algorithm with adaptive variable neighborhood search,IGA-AVNS)進行對比,結果如表4所示,其中最優結果被加粗。

表4 Co-CEM與若干FJSP優化算法之間的對比Table 4 Comparison between Co-CEM and several FJSP optimization algorithms

首先分析5項Kacem用例,可以看出Co-CEM均得到了最優解。此外在BRdata用例中,Co-CEM明顯優于所對比算法:Co-CEM在2項用例中超過了PVNS、在7項用例中超過了TLBO與MAPSO、在2項用例中超過了IGA-AVNS,并且在Mk01、Mk5等用例中平均值要優于后者。Co-CEM在所有15項用例中,除了Mk5沒有得到最優解,其余用例均取得了最優解。值得注意的是,Co-CEM在Mk07與Mk10用例上取得了其他算法沒有搜索到的最優解。綜上所述,實驗證明了Co-CEM相對于其他算法具有一定的優越性與健壯性,并且可以有效求得相應問題的優質解。Mk07跟Mk10獲得的優質解的甘特圖如圖4和圖5所示。

圖4 Mk07用例最晚完工時間為139的甘特圖Fig.4 Makespan of 139 in the Mk07 instance

5 結論

1)研究了不同調度類型之間的關系,然后提出了基于主動調度的遺傳解碼算法,并通過實驗對比了常用的插入式解碼算法,驗證了所提解碼算法的有效性。最后,驗證了遺傳解碼對交叉熵算法的性能提升。

2)提出了一種基于協同進化策略的交叉熵算法求解柔性作業車間調度問題的方法,其中結合了鄰域搜索結構,彌補了交叉熵算法局部搜索能力較弱的問題。最后實驗對比驗證了協同進化策略對算法性能的提升,并且與現有具有競爭力的算法進行了對比,證明了所提算法的高效性與優越性。