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

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

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

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

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

1 Co-CEM算法原理

1.1 個(gè)體編碼與解碼

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

1.2 種群初始化

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

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

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

3)最小加工時(shí)間:工序分配給加工時(shí)間最短的機(jī)器;

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

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

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

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

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

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

1.3 概率模型及其更新

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

Q(i,j)=

(1)

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

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

om(i)=

(2)

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

sv=P(i,:)×om

(3)

sv=sv/sum(sv)

(4)

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

對(duì)于機(jī)器向量的生成步驟也采用類(lèi)似的方法處理。通過(guò)mm去除掉采樣過(guò)程中的無(wú)用解,保證了所生成的解是有效的。

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

(5)

(6)

(7)

(8)

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

2.1 調(diào)度類(lèi)型

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

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

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

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

在解碼分配下一道加工工序時(shí),設(shè)當(dāng)前剩余未加工工序?yàn)榧蠟镻,對(duì)任意一道工序O∈P,設(shè)其前置工序?yàn)閜j,分配的機(jī)器為M(O)。此外,定義Et(·)表示任意一道機(jī)器的最早可用時(shí)間,則有:

(9)

(10)

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 面向FJSP的Co-CEM

3.1 協(xié)同進(jìn)化策略

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

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

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

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

2)設(shè)當(dāng)前任務(wù)數(shù)為N,對(duì)N個(gè)任務(wù)進(jìn)行編號(hào),從其中隨機(jī)選擇若干個(gè)任務(wù)得到集合u,定義v為集合u的補(bǔ)集,如果選擇的任務(wù)數(shù)為0或者等于N,則重新進(jìn)行選擇;

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

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

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

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

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

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

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

(12)

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

Lk={v

(13)

Rk={v

(14)

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

(15)

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

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

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

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

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

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

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

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

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

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

4 單目標(biāo)FJSP下Co-CEM實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)?zāi)康呐c方案

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

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

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

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

4.3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

1)實(shí)驗(yàn)1 插入式解碼與遺傳解碼之間的性能對(duì)比。

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

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

圖2 不同用例下不同解碼算法之間的對(duì)比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ù)的增加,最晚完工時(shí)間的變化趨勢(shì),即收斂趨勢(shì)圖,結(jié)果如圖3所示,可以看出CEM-G的收斂速度明顯優(yōu)于CEM-I。最后分別使用Kacem的5個(gè)用例與BRdata的10個(gè)測(cè)試用例,對(duì)不同解碼算法的優(yōu)化性能進(jìn)行差異化分析:分別使用CEM、CEM-I及CEM-G各自運(yùn)行30次,并分別列出15個(gè)用例下的最優(yōu)結(jié)果、平均值與標(biāo)準(zhǔn)差,結(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é)果來(lái)看,CEM-G在11項(xiàng)用例中取得了最優(yōu)結(jié)果,CEM-I在10項(xiàng)用例中取得了最優(yōu)結(jié)果。從均值角度來(lái)看,CEM-G在大部分情況下可以得到優(yōu)于CEM-I的結(jié)果。從標(biāo)準(zhǔn)差角度來(lái)看,CEM-G在大部分用例中的標(biāo)準(zhǔn)差均小于CEM-I。綜上證明了遺傳解碼在CEM中大部分情況下優(yōu)于插入式解碼并且更加穩(wěn)定。

2)實(shí)驗(yàn)2 協(xié)同進(jìn)化策略對(duì)CEM性能的影響。

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

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

3)實(shí)驗(yàn)3 Co-CEM與其他算法的對(duì)比。

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

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

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

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

5 結(jié)論

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

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