袁帥鵬，李鐵克，王柏琳

(1.北京科技大學(xué) 經(jīng)濟管理學(xué)院，北京 100083；2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心，北京 100083)

0 引言

成組調(diào)度(Group Scheduling, GS)源于單元制造系統(tǒng)，是一種利用工件在設(shè)計和加工上的相似性，將工件進(jìn)行分組加工，以提高生產(chǎn)效率的生產(chǎn)組織方法。由于其結(jié)構(gòu)化、高效率和低成本的生產(chǎn)優(yōu)勢，GS已廣泛應(yīng)用于汽車裝配[1]、電路板印刷[2]、鋼鐵制造[3]等領(lǐng)域。迄今，已有關(guān)于GS問題的研究成果主要聚焦于經(jīng)典的流水車間環(huán)境，問題假定同一階段有且僅有一臺機器[4]，而實際的工業(yè)環(huán)境多以混合流水車間為主，即通常會在瓶頸工序設(shè)置多臺并行機以平衡各階段的生產(chǎn)節(jié)奏、降低瓶頸工序?qū)ο到y(tǒng)產(chǎn)出的影響。相比前者，混合流水車間具有更好的靈活性和穩(wěn)定性，但同時也增加了調(diào)度問題求解的難度。因此，對混合流水車間環(huán)境下的GS問題展開研究具有重要的理論意義和實用價值。

與經(jīng)典調(diào)度問題不同，GS需要同時考慮工件組間調(diào)度和各工件組內(nèi)工件間調(diào)度兩個相關(guān)子問題，對于混合流水車間成組調(diào)度(Hybrid Flowshop Group Scheduling, HFSGS)問題，還需要進(jìn)一步考慮各工件組在各階段并行機上的指派過程，是一類復(fù)雜的聯(lián)合決策優(yōu)化問題。此外，在HFSGS問題中，由于同組內(nèi)工件間的相似性，組內(nèi)工件間切換的準(zhǔn)備時間通常可以忽略(或視為加工時間的一部分)，但需考慮工件組間切換的準(zhǔn)備時間。LOGENDRAN等[5]首次對具有序列不相關(guān)準(zhǔn)備時間和一致并行機類型的HFSGS問題進(jìn)行了研究，分析了存在單準(zhǔn)備時間和多準(zhǔn)備時間兩種情況下問題的性質(zhì)特征，并提出一種三階段啟發(fā)式算法(LN-PT-M)；SHAHVARI等[6]指出序列相關(guān)準(zhǔn)備時間具有更為重要的實際意義，進(jìn)而對帶有序列相關(guān)準(zhǔn)備時間的HFSGS問題展開研究，以最小化Makespan為目標(biāo)建立了混合整數(shù)線性規(guī)劃模型，并提出6種改進(jìn)的禁忌搜索算法；針對同樣的問題，KESHAVARZ等[7]開發(fā)了一種文化基因算法，并基于所設(shè)計算法給出了問題最優(yōu)解的下界；KARIMI等[8]同時考慮了最小化Makespan和加權(quán)拖期兩個優(yōu)化目標(biāo)，構(gòu)建了問題的數(shù)學(xué)模型，并提出一種改進(jìn)的多階段非支配排序遺傳算法；FENG等[9]進(jìn)一步研究了一類具有預(yù)防性維護的HFSGS問題，從設(shè)備和系統(tǒng)兩個層面分別構(gòu)建了問題的數(shù)學(xué)模型，并提出一種嵌套遺傳進(jìn)化的模擬退化算法；SHAHVARI[10]研究了一類混合流水車間批處理調(diào)度問題，與本文問題不同，該問題未考慮成組技術(shù)假設(shè)，假定同組內(nèi)的工件可拆分為更小的批次且可以被分配到不同的設(shè)備上加工，以最小化總加權(quán)完工時間和總加權(quán)拖期為目標(biāo)構(gòu)建了問題的混合整數(shù)線性規(guī)劃模型，并提出一種改進(jìn)的禁忌搜索算法。

上述文獻(xiàn)為HFSGS問題的研究提供了良好的理論基礎(chǔ)，但已有成果均基于一致并行機環(huán)境，即假定工件在同一階段上的加工時間為定值。而在部分工業(yè)環(huán)境中，由于新老設(shè)備的交替使用，無關(guān)并行機(工件在同一階段上的加工時間與選取的并行機有關(guān))的應(yīng)用場景屢見不鮮，此種情況下工件在各階段上的指派過程會更加復(fù)雜，這對問題性質(zhì)分析和模型構(gòu)建都提出了新的挑戰(zhàn)。此外，由于HFSGS屬于一類多維度、聯(lián)合決策優(yōu)化問題，而已有研究多采用分階段的方式對多個子問題進(jìn)行單獨求解，缺乏對問題特征知識的挖掘以及子問題間關(guān)聯(lián)特征的分析，導(dǎo)致算法的穩(wěn)健性較差。鑒于以上兩點，本文在考慮序列相關(guān)準(zhǔn)備時間約束的情況下，對無關(guān)并行機類型的HFSGS問題展開研究，首先以最小化Makespan為目標(biāo)建立了問題的數(shù)學(xué)模型，然后結(jié)合問題的聯(lián)合決策特征提出一種改進(jìn)的候鳥優(yōu)化算法，算法基于負(fù)載均衡思想和改進(jìn)先到先得策略對染色體進(jìn)行解碼，進(jìn)化過程中開發(fā)了不同的鄰域搜索機制來構(gòu)造鄰域結(jié)構(gòu)，并提出一種協(xié)同優(yōu)化的鄰域解生成策略。最后，基于不同問題規(guī)模的數(shù)據(jù)實驗對模型和算法的有效性進(jìn)行驗證。

1 問題描述及模型

1.1 問題描述

考慮序列相關(guān)準(zhǔn)備時間和無關(guān)并行機類型的HFSGS問題可描述如下：①工件被劃分為若干工件組并在多階段流水車間環(huán)境下加工，至少有一個階段存在多于1臺的并行機；②并行機類型為無關(guān)并行機，即同一階段上的并行機具有不同處理速度，工件在某一階段的加工時間與選取的并行機有關(guān)；③對于同工件組內(nèi)的工件，在每一階段上能且僅能選取一臺并行機進(jìn)行加工，且加工過程必須連續(xù)，不能被其他工件組內(nèi)的工件打斷；③各階段上的并行機在切換不同工件組時存在一定的準(zhǔn)備時間，該準(zhǔn)備時間序列相關(guān)，即準(zhǔn)備時間不僅與將要加工的工件組有關(guān)，還與緊前加工的工件組有關(guān)；⑤目標(biāo)為最小化最大完工時間，即Makespan。

該問題需要確定工件組間的加工順序、各工件組內(nèi)工件間的加工順序以及各工件組在各階段上并行機的指派3個子問題，使得所有工件的最大完工時間盡可能小。若使用FFm表示無關(guān)并行機類型的混合流水車間環(huán)境，fmls表示成組調(diào)度，sijk表示序列相關(guān)準(zhǔn)備時間，Cmax表示最大完工時間，根據(jù)三元組表示法，本文問題可描述為FFm|fmls,sijk|Cmax。為使問題更加明確，本文基于以下假設(shè)：

(1)階段間緩沖區(qū)的容量無限；

(2)所有工件、并行機在調(diào)度零時刻均為可用狀態(tài)，不考慮工件在階段間的運輸時間；

(3)生產(chǎn)環(huán)境具有穩(wěn)定性，不考慮設(shè)備故障、工件的惡化和學(xué)習(xí)效應(yīng)。

1.2 數(shù)學(xué)模型

為對問題FFm|fmls,sijk|Cmax進(jìn)行準(zhǔn)確描述，本節(jié)采用0-1整型決策變量的方式建立了其混合整數(shù)線性規(guī)劃模型，其中涉及的符號及含義如表1所示。

表1 符號變量含義

其混合整數(shù)線性規(guī)劃模型描述如下：

minCmax。

(1)

(2)

(3)

xi′ik+xii′k≤1,i=1,…,g,i′=1,…,g,

k=1,…,K;

(4)

(5)

(6)

i′=1,…,g,i=1,…,g，k=1,…,K；

(7)

Sik+M(2-xi′ik-zikh)≥Ci′k+si′ikh，

i=1,…,g，i′=0,…,g，k=1,…,K，

h=1,…,Mk；

(8)

cilk-pilkh+M(1-zikh)≥Sik,i=1,…,g，

l=1,…,ni，k=1,…,K，h=1,…,Mk；

(9)

cilk-pilkh+M(2-zikh-yil′l)≥cil′k,

i=1,…,g,1≤l′

k=1,…,K,h=1,…,Mk;

(10)

cil′k-pil′kh+M(1-zikh+yil′l)≥cilk,

i=1,…,g,1≤l′

k=1,…,K,h=1,…,Mk;

(11)

cilk-pilkh+M(1-zikh)≥0,i=1,2,…,g,

l=1,…,ni,k=1,h=1,…,Mk;

(12)

cilk-pilkh+M(1-zikh)≥cil(k-1),i=1,2,…,g,

l=1,…,ni,k=2,…,K,h=1,…,Mk;

(13)

Cik≥cilk,i=1,…,g,l=1,…,ni,k=1,…,K;

(14)

Cmax≥Cik,i=1,…,g,k=1,…,K;

(15)

Sik,Cik,cilk≥0,i=1,…,g,

l=1,…,ni,k=1,…,K;

(16)

xi′ik,yil′l,zikh∈{0,1},i,i′=1,…,g,

1≤l′

(17)

目標(biāo)函數(shù)(1)表示最小化最大完工時間，即Makespan；約束(2)～約束(4)表示在任一階段上，各工件組均有且僅有一個緊前工件組(包含虛擬工件組G0)、至多一個緊后工件組，且兩者不能為同一個；約束(5)表示在任一階段的任一并行機上，有且僅有一個虛擬工件組G0，且G0必須安排在首個位置進(jìn)行加工；約束(6)表示對于任一工件組，在每一階段僅能選取一臺并行機進(jìn)行加工；約束(7)表示決策變量xi′ik和zikh之間的限制關(guān)系：在任一階段，只有兩個工件組在同一臺并行機加工時，才有可能存在緊鄰關(guān)系；約束(8)表示如果兩個工件組在某階段上存在緊鄰關(guān)系，則后續(xù)工件組內(nèi)任一工件的開工時間不小于緊前工件組的完工時間；約束(9)表示各工件在各階段上的開工時間要至少大于所在工件組在該階段上的開工時間；約束(10)和約束(11)為同工件組內(nèi)工件間的序列約束，即對于具有先后順序(不一定緊鄰)的兩個工件，后續(xù)工件的開工時間至少大于先前工件的完工時間；約束(12)表示任一工件在第一階段上的完工時間要大于其加工時間；約束(13)表示對于任一工件，只有在當(dāng)前工序完工后才可開始下一道工序的加工；約束(14)表示各工件組在各階段上的完工時間；約束(15)定義了所有工件組的最大完工時間；約束(16)～約束(17)為決策變量的取值范圍。該模型已通過CPLEX數(shù)學(xué)規(guī)劃軟件驗證了其正確性(詳見3.3節(jié)最優(yōu)性檢驗)。

2 改進(jìn)的候鳥優(yōu)化算法

由于問題FFm|fmls,sijk|Cmax的強NP難特性[5]，精確算法雖在理論上可以得到最優(yōu)解，但求解時間會隨著問題規(guī)模的增加呈指數(shù)倍增長，無法滿足實際應(yīng)用的需要，而基于智能優(yōu)化的元啟發(fā)式算法為快速求解該類問題提供了一種有效途徑。

候鳥優(yōu)化(Migrating Birds Optimization, MBO)算法是一種新興的、基于種群進(jìn)化和鄰域搜索的元啟發(fā)式算法，它通過模擬候鳥遷徙過程中V形隊列能夠提高鳥群飛行速度這一生物現(xiàn)象對問題進(jìn)行優(yōu)化[11]。MBO將每一個解視為鳥群中的一只鳥，優(yōu)化過程包括鳥群初始化、領(lǐng)飛鳥進(jìn)化、跟飛鳥進(jìn)化和領(lǐng)飛鳥替換4個階段，其中跟飛鳥被分為左種群子集和右種群子集兩部分。在整個進(jìn)化過程中，MBO采用左右群體集的并行搜索機制來指導(dǎo)種群進(jìn)化，使得算法具有較強全局搜索能力。同時，MBO通過鄰域共享機制來模擬個體間交互的過程，對于每一個體，會將自身較好的鄰域解共享至下一個個體，這種獨特的個體進(jìn)化機制能夠快速鎖定種群中的優(yōu)勢鄰域結(jié)構(gòu)，促使算法以較快的速度向優(yōu)勢解的方向進(jìn)化。當(dāng)前，MBO算法在求解調(diào)度類組合優(yōu)化問題方面已取得較好的效果[12-13]。據(jù)此，本文結(jié)合MBO的優(yōu)化機制和FFm|fmls,sijk|Cmax問題的特征，提出一種改進(jìn)的候鳥優(yōu)化(Enhanced MBO, EMBO)算法。EMBO采用置換序列的方式對染色體進(jìn)行編碼，基于負(fù)載均衡思想和改進(jìn)的先到先得策略將染色體解碼為問題的可行解；提出了一種基于準(zhǔn)備時間的最優(yōu)插入策略來構(gòu)造可行解的鄰域結(jié)構(gòu)，并提出一種協(xié)同優(yōu)化的鄰域解生成策略；為避免算法陷入局部最優(yōu)，設(shè)計了一種基于年齡閾值的重置機制。算法實施過程如下。

2.1 編碼解碼策略

2.1.1 編碼策略

2.1.2 解碼策略

考慮到各并行機具有不同的加工能力，解碼時首先基于負(fù)載均衡思想確定第一階段各并行機加工工件組的數(shù)量(記為σh)，然后結(jié)合子集X確定各工件組在第一階段上并行機的選擇及同一并行機上工件組間的加工順序，再由子集Yi確定各工件組內(nèi)工件間的加工順序；對于后續(xù)階段，根據(jù)上一階段的完工順序，采用改進(jìn)的先到先得策略確定各工件組在各階段上的并行機的選擇。具體實施步驟如下：

步驟1使用式(18)計算σh的值：

σh=

(18)

步驟3由式(19)確定各工件組在第一階段所選取并行機的編號，記為I1(i)：

I1(i)=GV(X(i)),i=1,2,…,g。

(19)

步驟4對于在同一并行機上加工的工件組集，按照子集X中出現(xiàn)的順序依次加工。

步驟5對于后續(xù)階段k(k=2,…,K)，使用式(20)確定工件組Gi(假定緊前工件組為Gi′)所選取的并行機編號Ik(i)，并按照上一階段完工的順序依次加工：

i=1,…,g，k=2,…,K。

(20)

由上述實施步驟可以看出，解碼過程充分考慮了并行機的負(fù)載均衡，并在先到先得策略基礎(chǔ)之上進(jìn)一步考慮了工件組在各并行機上準(zhǔn)備時間的差異性，使得算法具有較大的概率得到更好解。

2.2 鄰域解的生成

MBO是一種基于鄰域搜索的元啟發(fā)算法，鄰域結(jié)構(gòu)的設(shè)計對算法性能至關(guān)重要。由2.1節(jié)的編碼策略可以看出，子集X和Yi分別表示不同的子問題，為提高算法搜索效率，本節(jié)針對子集X和Yi設(shè)計了不同的鄰域構(gòu)造方案，并提出一種協(xié)同優(yōu)化策略將兩個子集整合為完成的鄰域解，具體如下。

2.2.1 子集X鄰域結(jié)構(gòu)設(shè)計

子集X主要用來確定各工件組在第一階段上并行機的選擇以及同一并行機上工件組間的加工順序，為搜索優(yōu)質(zhì)解，在構(gòu)造鄰域時要充分考慮各工件組在各階段并行機上加工時間和準(zhǔn)備時間的大小及差異性。本文以常用于組合優(yōu)化問題的插入算子為基礎(chǔ)，提出一種基于準(zhǔn)備時間的最優(yōu)插入操作來構(gòu)造子集X的鄰域結(jié)構(gòu)，實施步驟如下：

步驟1從子集X中隨機抽取一個工件組。

步驟2結(jié)合2.1節(jié)解碼策略中構(gòu)造的輔助向量GV，按照最小準(zhǔn)備時間原則在每個并行機基因區(qū)域內(nèi)選取1個插入點，進(jìn)而得到m1個插入位置。

步驟3根據(jù)插入位置得到m1個新工件組序列。

步驟4計算所得到新工件組序列的目標(biāo)值，選取最優(yōu)者作為子集X的鄰域結(jié)構(gòu)。

傳統(tǒng)的插入操作通常會隨機選取若干插入點，或插入所有可能的位置，這兩種方案均有一定的局限性。在所設(shè)計的算子中，被選取的工件組會按照最小準(zhǔn)備時間原則選取各并行機區(qū)域內(nèi)的最優(yōu)插入位置，具有較強的針對性。以圖1中的染色體為例，假定第一階段并行機的數(shù)量M1=2，通過解碼策略得到的輔助向量GV=[1,1,1,2,2]，圖2給出了子集X鄰域結(jié)構(gòu)設(shè)計的詳細(xì)過程。

2.2.2 子集Yi鄰域結(jié)構(gòu)設(shè)計

對于子集Yi，由于同工件組內(nèi)的工件在任一階段上均只能選取一臺并行機進(jìn)行加工，且無需考慮工件間切換的準(zhǔn)備時間，因此不同工件序列對目標(biāo)值的影響僅取決于工件的加工時間。鑒于此，算法采用常用于求解調(diào)度問題的前插、后插、隨機交換和區(qū)塊反轉(zhuǎn)4種操作來構(gòu)造其鄰域結(jié)構(gòu)，4種鄰域操作的執(zhí)行過程如圖3所示。

2.2.3 鄰域解的生成

雖然子集X和Yi的鄰域結(jié)構(gòu)被獨立設(shè)計，但兩者具有很強的關(guān)聯(lián)性，如何將它們有效組合進(jìn)而產(chǎn)生完整的鄰域解對算法性能至關(guān)重要?？紤]到問題FFm|fmls,sijk|Cmax的聯(lián)合決策特征，本文設(shè)計了協(xié)同優(yōu)化的鄰域解生成策略，具體思路如下：首先從當(dāng)前解的子集X中隨機選取一個工件組(記為Gi)，然后以Gi為基準(zhǔn)，對當(dāng)前解中Gi對應(yīng)的工件序列Yi執(zhí)行鄰域構(gòu)造操作，并從中選取最優(yōu)者插入Yi對應(yīng)的位置；隨后，以更新后的工件序列為基準(zhǔn)，將Gi按照最小準(zhǔn)備時間插入策略選取最優(yōu)插入位置，得到一個鄰域解；重復(fù)上述過程直至得到給定數(shù)量的鄰域解。在構(gòu)造鄰域解的過程中，為避免對同一工件組及其內(nèi)的工件序列執(zhí)行重復(fù)操作，我們引入禁忌搜索的思想，即對于任一個體，把每次隨機選取的工件組放入禁忌表中，在構(gòu)造下一個鄰域解時，檢測所選取的工件組是否已被存入禁忌表，如果存在則重新選取。

仍以圖1中的染色體為例，鄰域解的生成過程可用圖4表示。根據(jù)其執(zhí)行過程可以看出，在每次迭代過程中，該策略能夠針對特定的工件組及其工件序列進(jìn)行協(xié)同優(yōu)化。

2.3 重置機制

為有效平衡算法的全局搜索和局部搜索能力，本文提出一種基于年齡閾值的重置機制：首先為所有個體賦予初始值為1的年齡參數(shù)，在每一次迭代過程中，若當(dāng)前解不能由其最好的鄰域解替換，則將其年齡值增加1；否則，將當(dāng)前解的年齡值初始化為1。顯然，年齡越小表示后續(xù)迭代中找到更優(yōu)解的可能性越高，而年齡越大表示找到更好解的可能性較低，并且可能會陷入局部最優(yōu)狀態(tài)。因此，若個體的年齡值超過預(yù)先設(shè)定的閾值(記為limits)，則采用隨機生成的方式重置當(dāng)前個體。

2.4 算法流程

基于以上算法設(shè)計，EMBO算法求解問題FFm|fmls,sijk|Cmax的具體步驟如下：

步驟1初始化算法參數(shù)，包括種群規(guī)模p_size，每個個體產(chǎn)生自身鄰域解的數(shù)量α，傳遞給下一個個體鄰域解的數(shù)量β，巡回次數(shù)T，年齡閾值limits。

步驟2結(jié)合2.1節(jié)的編碼策略隨機生成初始種群，并將初始種群劃分為領(lǐng)飛鳥、左種群子集和右種群子集3部分。

步驟3領(lǐng)飛鳥進(jìn)化。采用2.2節(jié)的鄰域解生成策略構(gòu)造當(dāng)前領(lǐng)飛鳥的α個鄰域解，若鄰域解集中的最優(yōu)者優(yōu)于當(dāng)前領(lǐng)飛鳥，則使其替換之；然后從未使用的鄰域解中選取較優(yōu)的β個鄰域解加入左、右共享鄰域集(分別記為PNL和PNR)。

步驟4左種群子集進(jìn)化。對于左種群子集中的每一個解(跟飛鳥)，同樣采用2.2節(jié)的鄰域解生成策略構(gòu)造α-β個鄰域解，然后將α-β個鄰域解和共享鄰域集中的β個鄰域解合并形成鄰域解集，若鄰域解集中的最優(yōu)者優(yōu)于當(dāng)前跟飛鳥，則替換之；隨后從未使用的鄰域解中選取較優(yōu)的β個鄰域解更新PNL。

步驟5執(zhí)行與步驟4相似的操作更新右種群子集中的每一個解。

步驟6啟用2.3節(jié)的重置機制對當(dāng)前種群進(jìn)行更新。

步驟7檢查是否達(dá)到巡回次數(shù)T，若未達(dá)到，轉(zhuǎn)步驟2；否則，將領(lǐng)飛鳥隨機移動到左(或右)隊列的尾部，左(或右)隊列中的第一只飛鳥成為新的領(lǐng)飛鳥。

步驟8判斷終止條件，若不滿足，轉(zhuǎn)步驟2；否則，輸出最優(yōu)解及目標(biāo)值。

3 仿真實驗

3.1 實驗設(shè)計

實驗首先基于小問題規(guī)模測試算例將EMBO的運行結(jié)果與混合整數(shù)線性規(guī)劃模型取得的最優(yōu)解進(jìn)行對比，以檢驗EMBO的最優(yōu)性；然后從文獻(xiàn)中選取了3種求解HFSGS問題的元啟發(fā)式算法，并基于大問題規(guī)模的測試算例將EMBO的運行結(jié)果與3種算法進(jìn)行對比，以檢驗EMBO的有效性。實驗中所有算法均使用MATLAB R2015a編程實現(xiàn)，模型采用ILOG CPLEX 12.7.0數(shù)學(xué)規(guī)劃軟件進(jìn)行求解，算法測試環(huán)境為Intel i5-6200U/CPU 2.40 GHz/8.0 GB。

由于未發(fā)現(xiàn)可直接應(yīng)用于本文問題的基準(zhǔn)數(shù)據(jù)，本文選取文獻(xiàn)[7](研究一致并行機環(huán)境下具有序列相關(guān)準(zhǔn)備時間HFSGS問題)中的實驗數(shù)據(jù)作為參考，并對其進(jìn)行修正和擴充，得到以下實驗數(shù)據(jù)：階段數(shù)量K∈{2,3,5,7}，工件組數(shù)量g∈{3,4,5,10,15,30}，各工件組內(nèi)工件的數(shù)量ni∈{3,4,5,10}。根據(jù)階段數(shù)量、工件組和各工件組內(nèi)工件數(shù)量將以上數(shù)據(jù)分為6組小問題規(guī)模的實驗(K=2、g∈{3,4,5}和ni∈{3,4}的正交組合)和18組大問題規(guī)模的實驗(K∈{3,5,7}、g∈{10,15,30}和ni∈{5,10})。實驗中其他問題參數(shù)設(shè)置如下：每一階段并行機的數(shù)量為Mk∈DU[1,3]，工件加工時間pilkh∈DU[5,75]，序列相關(guān)準(zhǔn)備時間si′ikh∈DU[5,50]，數(shù)據(jù)格式DU[a,b]表示介于a和b之間的離散均勻分布。

每組實驗隨機生成10組測試算例，采用相對偏差率(PRD)[14]來衡量算法性能，PRD計算公式為：

(21)

式中：Cmax(A)表示當(dāng)前測試算例算法A得到的Cmax值，ref為當(dāng)前測試算例的參考值：對于小問題規(guī)模的算例，選取混合整數(shù)線性規(guī)劃模型取得的最優(yōu)值作為參考；對于大問題規(guī)模的測試算例，選取所有算法得到的最好解作為參考。

3.2 算法參數(shù)設(shè)置

算法參數(shù)設(shè)置對算法性能起著重要的作用。EMBO中的算法參數(shù)包括：種群規(guī)模p_size，鄰域解的生成數(shù)量α，鄰域解的傳遞數(shù)量β，巡回次數(shù)T，年齡閾值limits。其中，α要至少大于β+1，以確保當(dāng)前解的鄰域集中有足夠的鄰域解共享至后者。已有文獻(xiàn)均將α設(shè)置為3，將β設(shè)置為1，通過預(yù)備實驗發(fā)現(xiàn)這種參數(shù)設(shè)置同樣適用于本文問題且具有較好的效果，因此EMBO采用同樣的參數(shù)設(shè)置。對于其他3個參數(shù)，使用田口實驗設(shè)計方法[15]探討參數(shù)對算法性能的影響，針對每個參數(shù)設(shè)置4個水平值，具體如表2所示。并選用中等問題規(guī)模的樣本數(shù)據(jù)(K=5,n=15,ni=10)為例，使用EMBO對每組參數(shù)組合方案獨立運行10次，將10次求得Cmax的均值作為評價指標(biāo)(ARV)，結(jié)果如表3所示。

表2 參數(shù)組合方案

表3 參數(shù)組合正交表及其評價指標(biāo)值

續(xù)表3

根據(jù)表3進(jìn)一步統(tǒng)計了各個參數(shù)的響應(yīng)值和對算法性能的影響趨勢圖，結(jié)果分別如表4和圖5所示。由表4的統(tǒng)計結(jié)果可知，種群規(guī)模p_size對算法性能的影響最大，其次是巡回次數(shù)T，最大維持代數(shù)limit對算法性能的影響程度最小。結(jié)合圖5可以看出，當(dāng)p_size=11，T=20，limits=10時算法具有最好的性能，因此以下實驗均采用此參數(shù)設(shè)置。

表4 不同參數(shù)的響應(yīng)值

3.3 最優(yōu)性檢驗

由表5可以看出，第一組實驗10組測試算例EMBO均得到了與CPLEX一樣的目標(biāo)值，這證實了本文所設(shè)計模型的正確性，同時也說明EMBO針對小問題規(guī)模搜索最優(yōu)解的有效性。隨著問題規(guī)模的增加，EMBO取得的PRD均值呈現(xiàn)增加趨勢，但6組實驗EMBO的總體PRD均值僅為0.94%，這表明對于小問題規(guī)模的測試算例EMBO得到的Cmax值與最優(yōu)解的間隙非常的小。由SR值可以看出，56組測試算例(忽略4組CPLEX未得到最優(yōu)解的算例)中共35組得到了最優(yōu)解，這表明對于多半測試算例(約62.5%)EMBO均能在有限的時間內(nèi)得到最優(yōu)解。以上結(jié)果說明，對于小問題規(guī)模的測試算例，本文提出的EMBO具有很好的優(yōu)化性能。

表5 最優(yōu)性測試結(jié)果

3.4 與元啟發(fā)式算法對比

為進(jìn)一步測試EMBO的性能，本文選取了3種針對HFSGS問題提出的元啟發(fā)式算法，分別為文獻(xiàn)[6]的禁忌搜索算法(Tabu Search, TS)、文獻(xiàn)[7]的文化基因算法(Memetic Algorithm, MA)和文獻(xiàn)[8]的遺傳算法(Genetic Algorithm, GA)。將這3種算法應(yīng)用至本文問題，并將其求解性能與所提出的EMBO算法和CPLEX求得的可行解(非最優(yōu)解)進(jìn)行對比，3種算法均采用原文推薦的參數(shù)設(shè)置。此外，由于本文問題與文獻(xiàn)中所研究問題存在一定的差別，實驗過程中對3種算法的評價函數(shù)做了適應(yīng)性調(diào)整。

表6 四種算法和CPLEX的PRD均值(Mean)、標(biāo)準(zhǔn)差(Std.)統(tǒng)計結(jié)果

表7 不同階段和工件規(guī)模下四種算法及 CPLEX總體PRD均值對比

由表6的統(tǒng)計結(jié)果可以看出，18組測試實驗中EMBO的PRD均值全部低于其他3種算法和CPLEX，且所有測試實驗EMBO的總體PRD均值僅為1.32%，明顯低于GA(4.17%)、TS(3.30%)、MA(5.41%)和CPLEX(3.84%)，這表明EMBO的求解質(zhì)量優(yōu)于其他3種算法和CPLEX。對于PRD值的標(biāo)準(zhǔn)差，僅有1組實驗(K=7,g×ni=20×10)EMBO略高于TS，其他實驗EMBO均為4種算法中的最低者，且其總體PRD值的標(biāo)準(zhǔn)差為0.55%，同樣低于GA(1.43%)、TS(0.76%)和MA(0.75%)和CPLEX(0.91%)，說明EMBO在獲取較優(yōu)解的同時，求解性能也相對穩(wěn)定。

由表7可知，當(dāng)階段數(shù)量相同時，隨著問題規(guī)模的增加，4種算法的總體PRD均值都在逐漸降低(如：當(dāng)K=2時，EMBO在3種問題規(guī)模下所有測試算例的總體PRD均值分別為2.25%，1.87%，1.45%)，說明針對本文問題，4種算法的求解質(zhì)量均具有較好的穩(wěn)健性，其中EMBO始終低于其他3種算法，這表明EMBO在不同工件規(guī)模下均能得到相對較好的解；當(dāng)問題規(guī)模相同時，隨著階段數(shù)量的增加，所有測試算例EMBO、TS、MA三種算法求得的總體PRD均值同樣逐漸減小，且EMBO始終處于較低的水平，而GA出現(xiàn)震蕩的情況，這進(jìn)一步說明了EMBO在求解質(zhì)量和穩(wěn)定性方面的優(yōu)越性，同時說明EMBO、TS、MA三種算法優(yōu)于GA。整體上，不同問題規(guī)模和階段數(shù)量下CPLEX求得的總體PRD均值不存在嚴(yán)格的變化規(guī)律，但始終高于EMBO算法，這說明即使給予較長的求解時間，CPLEX的求解性能也弱于EMBO算法。另外，根據(jù)表8的檢驗結(jié)果可知，18組測試實驗EMBO與其他3種算法以及CPLEX通過配對t檢驗得到的p值均小于0.05，這進(jìn)一步說明與其他3種算法和CPLEX取得的可行解相比，EMBO的求解質(zhì)量存在顯著的優(yōu)越性。

表8 四種算法和CPLEX的PRD均值配對t檢驗結(jié)果

基于以上分析，可得出結(jié)論：針對問題FFm|fmls,sijk|Cmax，本文提出的EMBO算法在求解質(zhì)量和穩(wěn)定性方面優(yōu)于TS、MA、GA和CPLEX。

4 結(jié)束語

本文研究了一類帶有序列相關(guān)準(zhǔn)備時間和無關(guān)并行機類型的混合流水車間成組調(diào)度問題，該問題具有較為廣泛的工業(yè)應(yīng)用背景，但相關(guān)研究成果很少。為高效求解此調(diào)度問題，首先以最小化最大完工時間為目標(biāo)構(gòu)建了混合整數(shù)線性規(guī)劃模型，然后結(jié)合問題特征提出一種改進(jìn)的候鳥優(yōu)化算法。在該算法中，通過一種新的編碼和解碼策略來表征問題的解，設(shè)計了不同的鄰域搜索機制來構(gòu)造鄰域結(jié)構(gòu)，并提出一種協(xié)同優(yōu)化的鄰域解生成策略，為避免算法陷入局部最優(yōu)，開發(fā)了一種基于年齡閾值的重置機制。實驗階段，首先采用田口實驗方法確定了算法的最佳參數(shù)組合，然后基于小問題規(guī)模的測試算例驗證了模型的正確性和所提算法的最優(yōu)性能，最后基于大問題規(guī)模的測試算例將所提算法與其他主流元啟發(fā)式算法進(jìn)行了對比，證實了所提算法的高效性和穩(wěn)健性。本文創(chuàng)新點如下：①研究了無關(guān)并行機類型的混合流水車間成組調(diào)度問題，給出了問題的混合整數(shù)線性規(guī)劃模型；②設(shè)計了一種改進(jìn)的候鳥優(yōu)化算法，算法提出了基于負(fù)載均衡和改進(jìn)先到先得的解碼策略、基于準(zhǔn)備時間的最優(yōu)插入策略和協(xié)同優(yōu)化的鄰域解生成策略，顯著提升了算法的求解性能；③所設(shè)計的協(xié)同優(yōu)化策略也可以為其他具有聯(lián)合決策特征調(diào)度問題的求解提供有效途徑。

本文的優(yōu)化目標(biāo)為最小化最大完工時間，但實際工業(yè)應(yīng)用中往往需要考慮多個優(yōu)化目標(biāo)，因此基于多目標(biāo)優(yōu)化的混合流水車間成組調(diào)度問題是未來進(jìn)一步研究的方向。