袁帥鵬，李鐵克，王柏琳

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

0 引言

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

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

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

1 問題描述及模型

1.1 問題描述

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

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

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

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

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

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

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

表1 符號(hào)變量含義

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

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

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

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

2.1 編碼解碼策略

2.1.1 編碼策略

2.1.2 解碼策略

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

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

σh=

(18)

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

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

(19)

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

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

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

(20)

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

2.2 鄰域解的生成

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

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

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

步驟1從子集X中隨機(jī)抽取一個(gè)工件組。

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

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

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

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

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

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

2.2.3 鄰域解的生成

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

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

2.3 重置機(jī)制

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

2.4 算法流程

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

每組實(shí)驗(yàn)隨機(jī)生成10組測(cè)試算例，采用相對(duì)偏差率(PRD)[14]來衡量算法性能，PRD計(jì)算公式為：

(21)

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

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

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

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

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

續(xù)表3

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

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

3.3 最優(yōu)性檢驗(yàn)

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

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

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

為進(jìn)一步測(cè)試EMBO的性能，本文選取了3種針對(duì)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)行對(duì)比，3種算法均采用原文推薦的參數(shù)設(shè)置。此外，由于本文問題與文獻(xiàn)中所研究問題存在一定的差別，實(shí)驗(yàn)過程中對(duì)3種算法的評(píng)價(jià)函數(shù)做了適應(yīng)性調(diào)整。

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

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

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

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

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

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

4 結(jié)束語

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

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