基于Co-CEM的柔性車間調(diào)度優(yōu)化算法

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

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

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

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

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

1 Co-CEM算法原理

1.1 個體編碼與解碼

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

1.2 種群初始化

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

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

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

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

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

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

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

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

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

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

1.3 概率模型及其更新

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

Q(i,j)=

(1)

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

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

om(i)=

(2)

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

sv=P(i,:)×om

(3)

sv=sv/sum(sv)

(4)

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

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

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

(5)

(6)

(7)

(8)

2 基于主動調(diào)度的遺傳解碼

2.1 調(diào)度類型

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

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

2.2 基于主動調(diào)度的遺傳解碼

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

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

(9)

(10)

(11)

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

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

為將優(yōu)化后的活動調(diào)度信息保留到后續(xù)計算,在工序重排時按照逆序數(shù)減小的趨勢進行調(diào)整[15]。

基于主動調(diào)度的遺傳解碼算法如下:

1) 輸入半活動調(diào)度OS,當前總工序數(shù)nt,設(shè)置延遲度η。

2) 遍歷當前工序數(shù)nt,執(zhí)行以下過程。

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

② 從emachine上找到最早開始時間小于等于mect的工序eeligible_tasks,以O(shè)S中的下標為優(yōu)先級找到最高優(yōu)先級的工序作為參考工序rtask。

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

3) 從eeligible_tasks中選取優(yōu)先級最高的工序進行主動調(diào)度,得到stask。

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

5) 輸出活動調(diào)度OS′。

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

3 面向FJSP的Co-CEM

3.1 協(xié)同進化策略

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

圖1 協(xié)同進化策略Fig.1 Coevolutionary strategy

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

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

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

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

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

相應(yīng)的機器搜索算子的詳細步驟如下:

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

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

3.2 基于關(guān)鍵工序的鄰域搜索

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

(12)

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

Lk={v

(13)

Rk={v

(14)

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

(15)

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

基于關(guān)鍵工序的鄰域搜索算法如下:

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

2) 種群在ns次數(shù)下,執(zhí)行以下過程:

① 將種群P按照適應(yīng)度進行排序,適應(yīng)度高的個體排在左側(cè),并對個體進行鄰域搜索,次數(shù)為ns;

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

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

④ 根據(jù)替換規(guī)則檢查是否替換,如果是則將p編碼為個體Pindex。

3) 輸出優(yōu)化后的種群P。

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

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

4.1 實驗?zāi)康呐c方案

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

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

4.2 實驗環(huán)境與數(shù)據(jù)集

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

4.3 實驗與結(jié)果分析

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

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

表1 算法參數(shù)Table 1 Algorithm parameter

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

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

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

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

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

表2 不同用例下CEM-I與CEM-G結(jié)果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所示,最優(yōu)結(jié)果被加粗,可以看出CEM-G與CEM-I的結(jié)果均優(yōu)于CEM。從最優(yōu)結(jié)果來看,CEM-G在11項用例中取得了最優(yōu)結(jié)果,CEM-I在10項用例中取得了最優(yōu)結(jié)果。從均值角度來看,CEM-G在大部分情況下可以得到優(yōu)于CEM-I的結(jié)果。從標準差角度來看,CEM-G在大部分用例中的標準差均小于CEM-I。綜上證明了遺傳解碼在CEM中大部分情況下優(yōu)于插入式解碼并且更加穩(wěn)定。

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

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

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

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

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

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

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

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

5 結(jié)論

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

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