多目標(biāo)變分批混合流水車間調(diào)度算法自動設(shè)計

張 彪，孟磊磊，桑紅燕，盧 超

(1.聊城大學(xué) 計算機(jī)學(xué)院，山東 聊城 252000；2.中國地質(zhì)大學(xué)(武漢)計算機(jī)學(xué)院，湖北 武漢 430074)

0 引言

混合流水車間調(diào)度問題(Hybrid Flowshop Scheduling Problem, HFSP)作為流水車間調(diào)度問題的一個分支，因其重要的理論價值和實用價值引起了研究人員的廣泛關(guān)注[1-5]。HFSP常見于電子、家具、紡織、石化、制藥等各種柔性制造車間中[6-7]。HFSP要根據(jù)生產(chǎn)約束確定各階段的作業(yè)順序和機(jī)器分配，即使是在非常小規(guī)模的問題實例上，也被證明是NP困難的[1]。在目前大多數(shù)關(guān)于HFSP的研究中，作業(yè)是不能被分割的，即每個作業(yè)在某一特定階段完成之前不能轉(zhuǎn)移到下游階段。然而，在許多現(xiàn)實場景中，這將對生產(chǎn)效率產(chǎn)生負(fù)面影響，在這些場景中，一個作業(yè)是由一系列相同的加工單元組成的。

REITER[8]首先在作業(yè)車間調(diào)度問題中引入了批量流技術(shù)，高效地完成了基于生產(chǎn)效率的調(diào)度目標(biāo)。如今，批量流技術(shù)被制造企業(yè)廣泛使用，以提升它們的客戶服務(wù)[9]。批量流技術(shù)將一個給定的批次分割成若干較小的子批，以實現(xiàn)在一個多階段制造車間中同一批次在不同階段中的并行加工。也就是說，批次的一個子批一旦在某一階段完成加工，就可以立即運輸?shù)较掠坞A段。因此，它的好處是減少生產(chǎn)周期，從而更快地生產(chǎn)和交付產(chǎn)品。此外，它還具有減少在制品庫存、線邊倉和空間需求的優(yōu)點。批量流的劃分方法可分為等量分批、一致分批和可變分批[9-10]。在等量分批下，同一批次的不同子批規(guī)模是相同的，并且在不同階段保持一致；在一致分批下，批次的不同子批規(guī)模可能不同，但在不同階段保持一致；而在可變分批下，批次的不同子批規(guī)模可能不同，并且在不同階段也保持變化。顯然，可變分批是最復(fù)雜的情形，等量分批和一致分批則可作為可變分批的特例。

因此，本文將可變分批引入HFSP中，除了考慮批次順序和機(jī)器分配之外，每個批次的批次分割(即子批數(shù)量和子批規(guī)模)都應(yīng)被考慮。本文研究的問題比經(jīng)典HFSP要困難得多，顯然也是NP困難的。批量流技術(shù)能夠縮短生產(chǎn)周期，但它也有實現(xiàn)成本，如子批的運輸和管理。也就是說，子批的數(shù)量越大，最大完工時間就可能越小，但相應(yīng)的運輸成本會增加。因此，考慮到實際中子批的運輸成本，子批的總量會受到限制。總而言之，最大完工時間與子批總量之間通常存在著一種權(quán)衡關(guān)系。因此，本文將致力于解決多目標(biāo)變分批混合流水車間調(diào)度問題(Multi-objective Hybrid Flowshop Scheduling Problem with Variable Sublot, MOHFSP_VS)，同時優(yōu)化最大完工時間和子批總量。

在現(xiàn)有批量流HFSP文獻(xiàn)中，涉及到多目標(biāo)優(yōu)化，只查到兩篇論文。CHEN等[11]研究了一種具有一致分批的HFSP，同時考慮機(jī)器具有不同的加工速度，以最小化最大完工時間和能耗為目標(biāo)，其提出一種多目標(biāo)遺傳算法，在其研究中，每個批次的子批數(shù)量是預(yù)先確定的。LI等[12]研究了一種可變子批的多目標(biāo)HFSP，最小化4個目標(biāo)，即逗留時間懲罰、能量消耗、提前和延遲值。需要注意的是，在該研究中，可變子批只是指每個批次在不同階段的子批數(shù)量可能不同，但同一批次不同子批的規(guī)模是相同的，即每個子批的加工時間是預(yù)先確定的。為求解上述問題，LI等[12]提出了基于分解的多目標(biāo)進(jìn)化算法。在上述研究中，來自不同批次的子批可以混合。但當(dāng)不同批次間具有啟動作業(yè)時，這種設(shè)置是不現(xiàn)實的，因為要頻繁地進(jìn)行切換，嚴(yán)重影響加工效率。因此，本文設(shè)定來自不同批次的子批不可以混合。此外，上述研究均將批量流作為問題約束，沒有研究生產(chǎn)效率與批量分割之間的權(quán)衡關(guān)系，而本文將重點研究這一問題。ZHANG等[13]研究了基于一致分批的HFSP，同時考慮了啟動和運輸操作，并利用AAD算法取得了滿意的效果。本文將在此基礎(chǔ)上，研究基于可變分批的HFSP，利用自動算法設(shè)計(Automated Algorithm Design,AAD)方法自動構(gòu)建MOEA。

因為問題的NP難特性，為解決MOHFSP_VS，本文采用多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm, MOEA)進(jìn)行求解。眾所周知，MOEA的性能在很大程度上依賴于算法參數(shù)值(包括數(shù)值參數(shù)和類別參數(shù))的設(shè)置[14-15]。事實上，這些參數(shù)的設(shè)置取決于所解決的問題。然而，傳統(tǒng)的設(shè)置過程可能會受到以往經(jīng)驗的影響。為了消除這些限制，本文引入一種自動算法設(shè)計(AAD)方法[16-19]基于算法框架來自動構(gòu)建MOEA。本文采用的AAD方法稱為I/F-Race(iterated F-race)[16]，它通過測試一組測試算例，自動尋找并組合最佳參數(shù)取值，從而構(gòu)建一個針對給定問題表現(xiàn)優(yōu)異的自動算法，避免了過多的人為干預(yù)。關(guān)于所選擇的算法框架，本文采用多目標(biāo)離散人工蜂群算法(Multi-objective Discrete Artificial Bee Colony algorithm, MDABC)[20]。MDABC利用分解策略，通過使用聚合函數(shù)將多目標(biāo)問題分解為若干標(biāo)量子問題，并通過協(xié)作的方法同時優(yōu)化這些子問題。選擇該算法框架的原因如下：一方面，MDABC在HFSP上表現(xiàn)出了優(yōu)異的性能；另一方面，求解MOHFSP_VS，需要同時解決一些耦合的問題，如批次排序、機(jī)器分配和批量分割，因此，在解的編碼中需要包含不同的部分來呈現(xiàn)不同的解空間信息，每個部分都有其特定的鄰域結(jié)構(gòu)。此外，由于問題間是高度耦合的，使用基于鄰域結(jié)構(gòu)的元啟發(fā)式算法可以實現(xiàn)不同鄰域結(jié)構(gòu)之間的交互。而MDABC正是基于變鄰域下降策略(Variable Neighborhood Descent, VND)開發(fā)的一種基于協(xié)作的MOEA。

本文的主要貢獻(xiàn)總結(jié)如下：①在可變分批策略下，研究了考慮啟動和運輸操作的多目標(biāo)HFSP；②建立了多目標(biāo)混合整數(shù)規(guī)劃模型，同時優(yōu)化最大完工時間和子批總數(shù)；③引入了一種自動算法設(shè)計方法，構(gòu)建高性能的MOEA。

1 問題描述

在MOHFSP_VS中，一系列批次要經(jīng)過連續(xù)的階段進(jìn)行加工，每個階段包含若干相同的機(jī)器，并且每個批次包含若干加工單元，加工單元的數(shù)量稱為批次規(guī)模。在變分批策略下，每個批次被分割成若干子批，受運輸管理的限制，子批的數(shù)量有一個最大限定值。每個子批包含不同數(shù)量的加工單元，加工單元的數(shù)量稱為子批規(guī)模。批次的子批數(shù)量和子批規(guī)模在不同階段是發(fā)生變化的。來自同一批次的不同子批需要在每個階段的同一臺機(jī)器上連續(xù)加工，子批內(nèi)的加工單元也是連續(xù)性地加工。也就是說，一個子批的加工時間是子批規(guī)模和單位加工時間(一個加工單元的加工時間)的乘積。不同的批次之間機(jī)器需要執(zhí)行啟動操作，而同一批次的任意兩個連續(xù)子批間則不需要啟動操作。此外，不同批次在不同階段需要的啟動時間也不同的。當(dāng)一個子批在某一階段完成加工后，立即被運輸?shù)较乱浑A段，兩個不同連續(xù)階段之間的運輸時間是不同。MOHFSP_VS的特征如下:

(1)所有批次中的加工單元在0時刻均是可用的，不考慮優(yōu)先權(quán)和中斷。

(2)機(jī)器可以有空閑時間，各階段之間的緩沖區(qū)容量是無限的。

(3)每個批次都要經(jīng)過所有階段，在一個階段上，每個批次只能分配到一臺機(jī)器。

(4)每個批次被分割成若干子批，但子批數(shù)有一個限定的最大值。每個子批規(guī)?？赡懿煌?，相同子批在不同階段上的規(guī)模也可能不同。

(5)每個子批在某一階段完成加工后，將立即傳輸?shù)较掠坞A段。

(6)同一批次的各個子批在一臺機(jī)器上連續(xù)地進(jìn)行加工。在運輸?shù)教囟A段后，第一個子批可在啟動操作之后開始加工，其余的子批在運輸?shù)竭@個階段后，在前一個子批完成加工后開始加工。

(7)在任意時刻，一臺機(jī)器至多只能加工一個加工單元，一個子批中的加工單元連續(xù)地進(jìn)行加工。

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

MOHFSP_VS需要確定不同階段的批次分割、批次順序和機(jī)器分配。為了建立多目標(biāo)混合整數(shù)規(guī)劃模型，表1和表2所示為問題參數(shù)和決策變量的符號與定義。對于可變分批，與等量和一致分批相比，存在一個重要的約束條件，即對于一個給定的批次，它的任一子批都不能包含屬于那些在先前階段未完成并轉(zhuǎn)移到該階段的子批中的加工單元。因此，該模型的主要貢獻(xiàn)在于引入了一個決策變量Xi,j,e,e′，用來描述批次的子批規(guī)模間關(guān)系。

表1 模型問題參數(shù)符號與定義

表2 模型決策變量符號與定義

基于表1和表2中的符號表示，本文建立的多目標(biāo)混合整數(shù)規(guī)劃模型如下：

目標(biāo)函數(shù)：

minMS;

(1)

(2)

s.t.

MS≥Em,j,L,?j∈J;

(3)

Si,j,e≥0,?i∈I,j∈J,e∈[1,L];

(4)

(5)

(6)

B1,j,1≥t1,j,?j∈J；

(7)

Ei,j,e-Bi,j,e=pk,j×Si,j,e，

?i∈I,j∈J,e∈[1,…,L]；

(8)

Bi,j,e+1-Ei,j,e≥0，?i∈I,

j∈J,e∈[1,…,L-1]；

(9)

Yi,j,j′,k+Yi,j′,j,k≤1，?j,j′∈J,k∈Mi；

(10)

Yi,j,j′,k+Yi,j′,j,k≤Di,j,k+Di,j′,k，

?i∈I,j,j′∈J,k∈Mi；

(11)

Di,j,k+Di,j′,k-1≤Yi,j,j′,k+Yi,j′,j,k,

?i∈I,j,j′∈J,k∈Mi；

(12)

Bi,j,1-Ei,j′,L-ti,j+Q×(3-Yi,j′,j,k-Di,j,k-

Di,j′,k)≥0，?i∈I,j,j′∈J,k∈Mi；

(13)

?i∈I,j∈J,e∈[1,…,l]；

(14)

Bi+1,j,1≥Ei,j,1+fi,j×Wi,j,1+si+1,j,

?i∈{1,2,…m-1},j∈J;

(15)

Bi+1,j,1+Q×(1-Xi+1.j,1,e′)≥fi,j×Wi,j,e′+ti+1,j+

Ei,j,e′,?i∈I,j∈J,e′∈[1,…,L];

(16)

Bi+1,j,e+Q×(1-Xi+1,j,e,e′)≥Ei.j,e′+fi,j×Wi,j,e,

?i∈I,j∈J,e,e′∈[2,…,L];

(17)

i∈[1,…,m-1],j∈J,

u∈[1,…,L],u′∈[2,…,L];

(18)

Wi,j,e≥Wi,j,e+1,?i∈I,j∈J,e∈[1,…,L-1];

(19)

Di,j,k∈{0,1},

?i∈I,j∈J,k∈M,k∈{1,2,…,σi};

(20)

Yi,j,j′,k∈{0,1},?i∈I,j,j′∈J,k∈M;

(21)

Wi,j,e∈{0,1},?i∈I,j∈J,e∈[1,…,L];

(22)

Xi,j,e,e′∈{0,1},?i∈I,j∈J,e,e′∈[1,…,n]。

(23)

其中：式(1)定義了模型的目標(biāo)之一：最大完工時間(MS)。式(2)定義了模型的目標(biāo)之二：批次在所有階段的子批總數(shù)(NOS)。式(3)保證MS要大于每個批次的最后一個子批在最后一階段上的完工時間。式(4)要求在每個階段每個子批的規(guī)模要大于等于0。式(5)要求在每一階段對于給定的批次，子批規(guī)模之和等于批次的總規(guī)模。式(6)保證了每個批次都要經(jīng)過所有階段的加工，并且在每個階段只能分配到一臺機(jī)器上。因為在問題中考慮了啟動操作，式(7)要求在第一個階段，每個批次的第一個子批的開始加工時間要大于它的啟動時間。式(8)保證了每個子批的加工不能被打斷。式(9)保證在每個階段，來自給定批次的子批只有在它相鄰的前一個子批完成加工之后才能開始加工。式(10)～式(12)共同定義了變量Di,j,k和Yi,j,j′,k的關(guān)系，兩個變量的取值決定了批次的機(jī)器分配和調(diào)度次序。式(13)表達(dá)了如果有任意的批次在其之前加工，每個批次的第一個子批只有在啟動操作完成之后才能開始加工。式(14)定義了決策變量Si,j,e和Wi,j,e的關(guān)系，當(dāng)Si,j,e>0時，Wi,j,e=1，而當(dāng)Si,j,e=0時，Wi,j,e=0。式(15)表達(dá)了在非第一階段的各個階段，每個批次的第一個子批只有在先前階段完成加工并到達(dá)后才能開始加工。式(16)定義了在非第一階段的各個階段，每個批次的第一個子批只有在相關(guān)的另一子批在前一階段完成加工并到達(dá)以及完成啟動操作后才能開始加工。式(17)表述了每個批次的子批(第一子批除外)是否能夠在相關(guān)子批的前一階段完成加工并到達(dá)后開始加工。式(18)表明對于給定的批次，對于其內(nèi)的子批，不能包含屬于在前一階段還沒有完成加工的子批內(nèi)的加工單元。式(16)～式(18)共同定義了應(yīng)用變分批之后的重要約束：對于一個給定的批次，其任一子批都不能包含在先前階段未完成或者沒有轉(zhuǎn)移到該階段子批中的加工單元。式(19)保證了優(yōu)先給予位列前面的子批去容納加工單元。式(20)～式(23)定義了4個決策變量的取值范圍。

1.2 兩目標(biāo)的權(quán)衡關(guān)系

變分批技術(shù)能夠有效降低最大完工時間，但其自身也有實現(xiàn)成本：分批之后，子批總數(shù)增加，需要管理更多的運輸作業(yè)，從而加大了運輸成本。同時，不充分的分批會限制提升生產(chǎn)效率的效果，從而導(dǎo)致較大的最大完工時間。也就是說，最大完工時間和子批總數(shù)存在著權(quán)衡關(guān)系。為了進(jìn)一步解釋和評估它們之間的關(guān)系，這里考慮一個具有4個批次和2個階段(第一階段擁有3臺機(jī)器，第二階段擁有2臺機(jī)器)的測試實例。每個批次的最大子批數(shù)量設(shè)為5，其他相關(guān)的加工數(shù)據(jù)如下：

fi,j=[12,10,10,11]，Tj=[66,57,79,85]。

事實上，一個多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem, MOP)的Pareto最優(yōu)解能夠成為MOP標(biāo)量子問題的最優(yōu)解[13]。因此，為了得到MOHFSP_VS的Pareto最優(yōu)解，利用50個均勻分布的權(quán)重向量對兩個目標(biāo)進(jìn)行線性加權(quán)，生成50個不同的標(biāo)量子問題。采用IBM ILOG CPLEX12.7.1(著名的商用數(shù)學(xué)規(guī)劃模型求解器)求解50個標(biāo)量子問題的最優(yōu)解，并將收集到的非支配解標(biāo)注到圖1中。從圖1中可以看出，MS和NOS兩個目標(biāo)不能同時被優(yōu)化，即隨著子批總數(shù)的增加，最大完工時間在逐漸減少。此外，圖1中最優(yōu)MS和最優(yōu)NOS兩個解所對應(yīng)的調(diào)度方案如圖2和圖3所示。圖2為最優(yōu)NOS對應(yīng)的調(diào)度甘特圖，從圖中可以看出每個批次均只含有一個子批，NOS也就最小，MS相應(yīng)地也就最大，此調(diào)度方案相當(dāng)于不采用分批的HFSP調(diào)度。圖3為最優(yōu)MS對應(yīng)的調(diào)度甘特圖，從圖中可以看出每個批次均分割為若干子批，NOS最大，MS相應(yīng)地也就最小。綜上所述，變分批技術(shù)能夠有效地降低MS，同時，MS和NOS兩目標(biāo)間存在著權(quán)衡關(guān)系。

2 針對問題特性的算法配置及自動算法設(shè)計

MDABC主要包含種群初始化階段、基于VND的雇傭蜂階段、基于協(xié)作的旁觀者蜂階段以及基于解交換的偵查蜂階段4個階段[19]。在種群初始化階段，由于采用了分解策略，需要在解空間中隨機(jī)生成N個解(Xi,i=1,…,N)，每個解都要分配一個特定的權(quán)重(Wi,i=1,…,N)；在基于VND的雇傭蜂階段，每個解通過VND策略搜索鄰域結(jié)構(gòu)來改進(jìn)自己；在基于協(xié)作的旁觀者峰階段，它的核心思想在于利用優(yōu)良解探索更多的協(xié)作信息；在基于解交換的偵查蜂階段，會判定每個子問題的解是否在過去的L次連續(xù)迭代中得到了改進(jìn)。如果沒有，則尋找它所支配的鄰近子問題中的一個解，然后，兩個鄰近子問題交換它們的解。

在MDABC中，存在3個需要配置的數(shù)值參數(shù)，包括子問題的數(shù)量(N)、每個子問題鄰近子問題的數(shù)量(T)、交換解前連續(xù)不成功的代數(shù)(L)。對于可配置的類別參數(shù)，它們與MOHFSP_VS的問題特征緊密相關(guān)。接下來，考慮到問題特性，本文先設(shè)計了問題的編碼方案和權(quán)重的產(chǎn)生方法，然后詳細(xì)介紹了4個可配置的類別參數(shù)和1個相關(guān)的數(shù)值參數(shù)。

2.1 問題編碼與權(quán)重產(chǎn)生

根據(jù)問題描述，求解MOHFSP_VS需要同時解決3個相互耦合的問題，即批次排序、機(jī)器分配以及批次分割。利用元啟發(fā)式算法求解優(yōu)化問題時，解的編碼需要承載必要的信息，能夠利用解碼規(guī)則翻譯成詳細(xì)的調(diào)度方案。在有限的計算成本限制下，批次序列編碼[21-23]在研究中得到了廣泛應(yīng)用且表現(xiàn)優(yōu)異。批次序列表示在第一階段的批次調(diào)度順序，而在后續(xù)階段中，批次的調(diào)度順序由相應(yīng)的啟發(fā)式規(guī)則得到，機(jī)器分配同樣如此。由于不允許來自不同批次的子批混合在一起，批次分割需要單獨處理。綜上所述，在本文中，解的編碼分為兩部分：①一個n維的向量π={π1,…,πj,…,πn}，其中πj表示批次索引，n表示批次的數(shù)量；②批次分割矩陣的集合，即Δn={ψ1,…,ψj,…,ψn}，其中ψj為具有m行L列的批次分割矩陣,

2.2 動態(tài)解碼和可配置的解碼啟發(fā)式規(guī)則

解碼過程是將解的編碼翻譯成可行調(diào)度方案的過程。為了求解MOHFSP_VS，需要同時考慮3個問題：批次序列，機(jī)器分配，以及批次分割。鑒于變分批技術(shù)的引入，為防止不可行解的產(chǎn)生，本文提出一種動態(tài)的解碼過程，如下所示：

步驟1在第一個階段，即i=1,依次從序列π={π1,…,πj,…,πn}中取出πj。執(zhí)行以下流程：

步驟 1.1根據(jù)可配置的啟發(fā)式規(guī)則，確定πj的分配機(jī)器和機(jī)器空閑時間。

步驟 1.2計算批次πj的各子批在第一階段的加工時間。根據(jù)加工約束，依次調(diào)度各子批。有如下兩種情形：

(1)若為第一子批，則子批的開始加工時間為機(jī)器的空閑時間和啟動時間之和。完工時間為開始加工時間和子批的加工時間之和。利用完工時間更新機(jī)器的空閑時間。

(2)若不是第一子批，則子批的開始加工時間為機(jī)器的空閑時間。完工時間為開始加工時間和子批的加工時間之和。

步驟 2.1根據(jù)可配置的啟發(fā)式規(guī)則，確定πj′的分配機(jī)器和機(jī)器空閑時間。

步驟 2.2計算πj′的各子批在階段i的加工時間。定義4個臨時變量：變量ScheduledUnits記錄已調(diào)度過的加工單元數(shù)量、SchedulingUnits記錄可以調(diào)度的加工單元數(shù)量、ArrivedUnits記錄已到達(dá)的加工單元總數(shù)、ArrivedSublot記錄還沒到的最鄰近子批。根據(jù)加工約束，依次調(diào)度各子批。有如下兩種情形:

(1)若為第一子批，執(zhí)行如下流程：

步驟 2.2.1在調(diào)度時刻點，即機(jī)器的空閑時間和啟動時間之和，得到ArrivedUnits的值。具體方法如下：依次從ArrivedSublot遍歷到Tj，直到某一子批在調(diào)度時刻點還未達(dá)到階段i，利用這一子批更新ArrivedSublot。將在調(diào)度時刻點已經(jīng)達(dá)到階段i的子批所包含的加工單元數(shù)記錄到ArrivedUnits中。

步驟 2.2.2得到SchedulingUnits的值，具體方法為SchedulingUnits=ArrivedUnits-ScheduledUnits。開始調(diào)度第1子批，有如下兩種情形:

1)若第一子批在階段i所包含的加工單元數(shù)小于或等于SchedulingUnits，則在調(diào)度時刻點開始進(jìn)行加工，開始加工時間即為調(diào)度時刻點，完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間，利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

2)若第一子批在階段i所包含的加工單元數(shù)大于SchedulingUnits，則需要等待足夠的加工單元數(shù)到來之后才能開始進(jìn)行加工。具體方法如下：依次從ArrivedSublot遍歷到Tj，將子批的加工單元數(shù)加到ArrivedUnits，得到SchedulingUnits，該遍歷到SchedulingUnits大于等于第一子批在階段i所包含的加工單元數(shù)停止，并更新ArrivedSublot。第一子批開始加工，開始時間為子批ArrivedSublot-1運輸?shù)诫A段i的時間，完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間，利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

(2)若不是第一子批，執(zhí)行如下流程：

步驟2.2.1在調(diào)度時刻點，即機(jī)器的空閑時間，得到ArrivedUnits的值。具體方法如下：依次從ArrivedSublot遍歷到Tj，直到某一子批在調(diào)度時刻點還未達(dá)到階段i，利用這一子批更新ArrivedSublot。將在調(diào)度時刻點，已經(jīng)達(dá)到階段i的子批所包含的加工單元數(shù)記錄到ArrivedUnits中。

步驟 2.2.2得到SchedulingUnits的值，具體方法為SchedulingUnits=ArrivedUnits-ScheduledUnits。開始調(diào)度當(dāng)前子批，有如下兩種情形:

1)如果當(dāng)前子批在階段i所包含的加工單元數(shù)小于或等于SchedulingUnits，則在調(diào)度時刻點開始進(jìn)行加工，開始時間即為調(diào)度時刻點，完工時間為開始時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間，利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

2)如果當(dāng)前子批在階段i所包含的加工單元數(shù)大于SchedulingUnits，則需要等待足夠的加工單元數(shù)到來之后才能開始進(jìn)行加工。具體方法如下：依次從ArrivedSublot遍歷到Tj，將子批的加工單元數(shù)加到ArrivedUnits，得到SchedulingUnits，該遍歷到SchedulingUnits大于等于當(dāng)前子批在階段i所包含的加工單元數(shù)停止，并更新ArrivedSublot。當(dāng)前子批開始加工，開始時間為子批ArrivedSublot-1運輸?shù)诫A段i的時間，完工時間為開始加時間與加工時間之和。利用完工時間更新機(jī)器的空閑時間，利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

可配置的啟發(fā)式規(guī)則描述如下?？紤]批次序列，本文引入了“先到先得”規(guī)則，因為其在求解以時間為目標(biāo)的調(diào)度問題[1]時表現(xiàn)出了良好的性能。具體來說，在第一階段，編碼中的批次序列可以直接反映批次的調(diào)度順序。而在后續(xù)階段的批次調(diào)度順序均按“先到先得”規(guī)則而定，即在上一階段較早完成的批次，可優(yōu)先在下一階段進(jìn)行加工?？紤]到批次分割的特點，本文提出兩種方法來實現(xiàn)“先到先得”規(guī)則：①“子批優(yōu)先”(Sublot Preemption, SP)，即在前一階段較早完成的子批所屬的批次具有優(yōu)先加工權(quán);②“批次優(yōu)先”(Lot Preemption, LP)，即在前一階段較早完成的最后一個子批所屬的批次具有優(yōu)先加工權(quán)?？紤]機(jī)器分配，本文采用“優(yōu)先可用”(First Available, FA)和“優(yōu)先完成”(First Completion, FC)兩種規(guī)則?！皟?yōu)先可用”表示具有較早可用時間的機(jī)器擁有優(yōu)先分配權(quán)；“優(yōu)先完成”表示較早能夠加工完批次的機(jī)器擁有優(yōu)先分配權(quán)。

綜上所述，針對問題的解碼過程，可得到4個可配置的解碼啟發(fā)式規(guī)則組合，即“批次優(yōu)先”和“優(yōu)先可用”的組合(LP_FA)、“批次優(yōu)先”和“優(yōu)先完成”的組合(LP_FC)、“子批優(yōu)先”和“優(yōu)先可用”的組合(SP_FA)以及“子批優(yōu)先”和“優(yōu)先完成”的組合(SP_FC)。

2.3 可配置的初始解生成方法

好的初始解生成方法有利于提高元啟發(fā)式算法搜索效率。本節(jié)基于問題編碼，設(shè)計了初始解的生成方法。首先，介紹了分割矩陣Δn的生成方法，然后給出了批次序列π的生成方法。對于初始化Δn，設(shè)計了3種方法，即均勻初始化(Uniform Initialization，UI)、隨機(jī)初始化(Random Initialization，RI)和混合初始化(Mixed Initialization，MI)。具體流程描述如下：

(1)均勻初始化方法

(2)隨機(jī)初始化方法

步驟 1對于每個批次j(j=1,…,n)來說，首先將剩余規(guī)模rj的值設(shè)為Tj。對于批次j來說，在階段i(i=1,…,m)上，依次從子批e=1到子批e=L，確定它們的子批規(guī)模。

步驟 2若e∈[1,L-1]，批次j的子批e在階段i上的子批規(guī)模Si,j,e在區(qū)間[0,rj]內(nèi)隨機(jī)產(chǎn)生。

步驟 3若e=L，批次j的子批e在階段i上的子批規(guī)模Si,j,e設(shè)置為rj。

(3)混合初始化方法

步驟 1以一種均勻的方式分割批次j(j=1,…,n)。

步驟 2.1在區(qū)間[0,Si,j,e]得到一個隨機(jī)整數(shù)Random，然后以50%的概率執(zhí)行Si,j,e=Si,j,e+Random或者Si,j,e=Si,j,e-Random。

步驟 2.2對于子批L+1-e，則以50%的概率執(zhí)行Si,j,L+1-e=Si,j,L+1-e-Random或者Si,j,L+1-e=Si,j,L+1-e+Random。

步驟 2.3打亂子批排序。通過上述步驟，每個子批規(guī)模已被確定。為保證隨機(jī)性，子批序列被隨機(jī)打亂。

一旦分割矩陣Δn生成，各批次中子批的加工時間就能夠確認(rèn)，因此根據(jù)一些啟發(fā)式規(guī)則，批次序列πn的初始化也能夠完成。本文引入了文獻(xiàn)中用于初始化批次排列的6種啟發(fā)式規(guī)則，它們均在求解HFSP中表現(xiàn)出了較好的性能，分別為SPT(shortest processing time)，VSPT(variant of SPT)，NEH(Nawaz, Enscore, and Ham)，GRASP(greedy randomized adaptive search procedure)，GRASP_NEH，以及RI(random initialization)。除了RI之外，因為批量流的應(yīng)用，這些規(guī)則都不能直接用于MOHFSP_VS，具體操作見文獻(xiàn)[13]。

綜上所述，本文采用了3種批次分割矩陣初始化方法和6種批次序列初始化方法。將它們結(jié)合起來，總共可以得到18種方法來進(jìn)行解的初始化。

2.4 可配置的分解策略和目標(biāo)歸一化

基于分解策略求解組合優(yōu)化問題，有兩種通用的策略去聚集多個目標(biāo)：加權(quán)和方法(Weighted Sum)和切比雪夫方法(Tchebycheff)[24]。本文將這兩種分解方法設(shè)置為可配置的。此外，在先期實驗中，已知兩個目標(biāo)有不同的量綱。若不采取措施將導(dǎo)致算法偏向于量綱大的目標(biāo)進(jìn)行搜索。為解決這一問題，本文采用簡單的Max-Min方法對兩個目標(biāo)進(jìn)行歸一化，如式(24)所示。歸一化方法的使用和不使用在本文中被認(rèn)為是可配置的。

(24)

根據(jù)上述定義，兩目標(biāo)的上下界可以經(jīng)過下列公式得出：

(25)

(26)

(27)

(28)

2.5 鄰域結(jié)構(gòu)設(shè)計及可配置的協(xié)同操作

MDABC算法在雇傭蜂階段，采用了VND策略。因此，需要根據(jù)解的編碼來設(shè)計鄰域結(jié)構(gòu)。對于批次序列向量π={π1,…,πj,…,πn}，本文采用兩種應(yīng)用廣泛的鄰域結(jié)構(gòu)，即插入和交換策略。對于批次分割矩陣集合Δn={ψ1,…,ψj,…,ψn}，本文提出一種批次分割矩陣ψj的變化操作。在此基礎(chǔ)上，提出兩種組合結(jié)構(gòu)，分別組合插入操作和變化操作，以及交換操作和變化操作。5種鄰域結(jié)構(gòu)具體如圖4所示：①插入操作：從批次序列向量πn中隨機(jī)選擇一批次，然后將它隨機(jī)插入到一個隨機(jī)選擇的位置中。②交換操作：從批次序列向量πn中隨機(jī)選擇兩批次，然后交換它們的位置。③變化操作：從批次分割矩陣集合中隨機(jī)選取帶有至少兩個子批的批次ψj。針對ψj，在每一階段i，隨機(jī)選擇兩個子批，將一個子批的規(guī)?？s減一個基于分布U[0,5]得到的一整數(shù)，而相應(yīng)地，將另一子批的規(guī)模增加一個相同的整數(shù)。④組合結(jié)構(gòu)1：先執(zhí)行插入操作，再執(zhí)行變化操作。⑤組合結(jié)構(gòu)2：先執(zhí)行交換操作，再執(zhí)行變化操作。

在MDABC算法的第二階段，兩個解之間需要執(zhí)行協(xié)同操作。對于車間調(diào)度問題，交叉算子具有良好的性能，能夠在保證遺傳優(yōu)良信息的基礎(chǔ)上，同時又有一定的全局搜索性。對于組合優(yōu)化問題，應(yīng)用廣泛的交叉算子有部分映射交叉(Partial Mapped Crossover，PMX)、順序交叉(Order Crossover，OX)、基于位置交叉(Position-based Crossover，PBX)、基于順序交叉(Order-Based Crossover，OBX)、循環(huán)交叉(Cycle Crossover，CX)和子環(huán)交換交叉(Subtour Exchange Crossover，SEX)。針對解編碼中的批次序列向量，圖5展示了上述交叉算子的示意圖。而對于批次分割矩陣，由于受固定批量大小的約束，上述交叉算子可能會產(chǎn)生不可行解。因此，為了能夠?qū)崿F(xiàn)信息共享，促進(jìn)它們之間的協(xié)作，本文引入了矩陣選取操作[13]，如圖6所示。具體來說，當(dāng)確定一個批次在分割信息時，其在每一階段的批次分割，以一定的概率從兩個父解中的批次分割矩陣中選取(以下稱為選取概率)。從批次1到批次n，依次采取上述操作，確定完整的批次分割信息。

2.6 自動算法配置問題

本節(jié)給出自動算法配置問題，其形式化定義由BIRATTARI[16]給出。在配置問題中，存在4個可配置的數(shù)值參數(shù)和4個可配置的類別參數(shù)。數(shù)值參數(shù)包括交換解前連續(xù)不成功的代數(shù)、每個子問題鄰近子問題的數(shù)量、子問題的數(shù)量，以及選取概率。分類參數(shù)包括初始化方法、解碼策略、聚集方法，以及批次序列的交互方法。表3列出了可配置參數(shù)及其分布。

表3 可配置參數(shù)及其分布

由表3可知，在構(gòu)建自動MOEA的過程中，有8個可配置的參數(shù)，標(biāo)記為Xd，d=1,…,8。這些參數(shù)取值范圍不同，其取值需要從相應(yīng)的參數(shù)取值空間中采樣。假設(shè)θ={x1,…,xd,…,xNparam}定義了一種算法配置，其中xd表示參數(shù)Xd的取值，同時假設(shè)Θ為所有的算法配置集合。當(dāng)考慮使用I/F-Race來構(gòu)建自動算法時，需要測試一組測試算例。設(shè)置c(θ)表示算法配置θ在測試算例集上的預(yù)期代價值。I/F-Race旨在找到具有最小代價值c(θ*)的最優(yōu)算法配置θ*。

2.7 自動算法設(shè)計方法

I/F-Race作為一種機(jī)器學(xué)習(xí)方法，首次被應(yīng)用于處理模型選擇問題[15]，該方法包含多個F-Race流程。I/F-Race從一組有限的候選算法配置開始，在一組測試算例上進(jìn)行測試。一個F-Race流程包含幾個迭代步驟。在每個步驟中，候選配置將在單個測試算例上進(jìn)行評估。在每個步驟之后，將那些在數(shù)理統(tǒng)計上比至少一個算法配置表現(xiàn)差的候選配置拋棄掉，剩下的算法配置將繼續(xù)進(jìn)行評估。為求解MOHFSP_VS，本文采用文獻(xiàn)[13]所設(shè)計的F-Race的流程。算法1給出了I/F-Race算法流程，其中Race()表示F-Race流程。I/F-Race主要包括3個步驟：①根據(jù)給定的分布抽樣新配置；②從新抽樣的配置中選擇最佳配置；③更新抽樣分布使抽樣偏向于最佳配置。具體流程見文獻(xiàn)[16]。

算法1I/F-Race流程。

輸入:I={I1,…,Ii,…IG}

參數(shù)空間:X={X1,…,X9}

總預(yù)算成本:B

1：Θk～SampleUniform(X)

2：Θelite:=Race(Θ1,B1)

3：j:=j+1

4：WhileBused≤Bdo

5: Θnew～Sample(X,Θelite)

6: Θj=Θnew∪Θelite

7: Θelite:=Race(Θj,Bj)

8:j:=j+1

9: EndWhile

輸出:Θelite

3 實驗設(shè)計

本章通過與其他4種高性能的MOEAs以及CPLEX進(jìn)行比較，驗證自動算法的有效性。對于MOEAs來說，在可接受的時間內(nèi)獲得滿意解具有重要的實際意義，因此本文以運行時間作為算法終止準(zhǔn)則，運行時間設(shè)置為n×m×tms，其中n為批次的數(shù)量，m為階段數(shù)，t為一固定值。這種終止準(zhǔn)則能夠為規(guī)模大的測試算例提供更多的計算時間。本文中，t設(shè)置為200，在這種時間限制下，本文所比較的算法在大多數(shù)情況下都能夠收斂。所有比較的MOEAs均采用C++語言編寫，仿真實驗運行在3.60 GHZ Intel Core i7處理器上。

3.1 測試數(shù)據(jù)和性能指標(biāo)

本文收集了15個小規(guī)模算例和400個中大規(guī)模算例，每個測試算例用批次數(shù)量、階段數(shù)和機(jī)器布局來標(biāo)識。小規(guī)模算例中，批次數(shù)量n來自集合{3,5,8,10,12}，階段數(shù)m來自集合{2,3,4}。這樣，通過組合n和m，可得到15種不同的n×m。中大規(guī)模算例中，批次數(shù)量n來自集合{20,40,60,80,100}，階段數(shù)m來自集合{3,5,8,10}。通過組合n和m，將得到20種不同的n×m。關(guān)于機(jī)器布局，本文采用了4種不同的類型，如下所示：

(1)第一階段具有一臺機(jī)器，其他階段具有3臺機(jī)器。

(2)第二階段具有一臺機(jī)器，其他階段具有3臺機(jī)器。

(3)第二階段具有兩臺機(jī)器，其他階段具有3臺機(jī)器。

(4)所有階段具有3臺機(jī)器。

在中大規(guī)模算例中，通過組合4種不同機(jī)器布局的類型，會產(chǎn)生80種組合。對于每個組合，本文將隨機(jī)生成5個測試算例，總共可以獲得400個測試算例。在小規(guī)模算例中，為了直觀地反映CPLEX和MOEAs的性能隨問題規(guī)模增加而發(fā)生的變化，只組合類型(4)，對于每種組合，隨機(jī)產(chǎn)生一個測試算例，總共得到15個測試算例。關(guān)于生產(chǎn)數(shù)據(jù)的生成，給出如下合理范圍：每個批次的加工單元數(shù)量取自均勻分布U[50,100]，加工單元的加工時間取自均勻分布U[1,10],啟動時間和運輸時間分別由均勻分布U[50, 100]和U[10, 20]得出。另外，最大子批數(shù)量設(shè)置為30。

本文選擇C-metric和D-metric兩個性能指標(biāo)[13]來評價MOEAs的性能。為了消除目標(biāo)值不同量綱的影響，在度量中采用歸一化處理。

3.2 算法調(diào)優(yōu)階段

為了進(jìn)行全局的調(diào)優(yōu)以確定最佳算法配置，從400個中大規(guī)模算例中隨機(jī)選擇100個具有不同問題規(guī)模的算例作為I/F-Race的測試算例。這100個算例構(gòu)成了算法1中的測試集合I={I1,…,Ii,…IG}，它們的順序是隨機(jī)打亂的。本文將預(yù)算成本設(shè)置為實驗的數(shù)量，一次實驗是指利用一種算法配置求解一個測試算例?？傤A(yù)算成本B設(shè)為2000，每次F-Race流程中候選配置的最小保留數(shù)目設(shè)為10。表4給出了I/F-Race算法執(zhí)行優(yōu)化的過程數(shù)據(jù)。

表4 I/F-Race中產(chǎn)生的過程數(shù)據(jù)

從表4可以看出，共存在5個迭代過程。隨著迭代數(shù)的增加，每代的預(yù)算成本逐漸增加。同時，迭代1用到了一個測試算例，迭代2、3、4、5分別用到了2、3、3、4個測試算例。這意味著在迭代初期，精英配置和劣質(zhì)配置比較容易識別，而在迭代后期，每個候選配置將需要更加細(xì)致地評估。這背后的原因是，在后續(xù)的迭代中生成的候選配置較為相似，因此需要更多的評估成本進(jìn)行識別。

在測試了13個實例后，I/F-Race輸出了10個精英配置，如表5所示。從表5可以看出，每個配置都不同于其他配置。這意味著高性能算法可以通過配置不同的參數(shù)值組合來構(gòu)造。對于數(shù)值參數(shù)X1，10個精英配置的取值均大于1，這也證明了MDABC算法中重啟策略的有效性。對于數(shù)值參數(shù)X4，可以看出，在10個精英配置中，有9個配置取值大于0.5，這說明在執(zhí)行交互操作的時候，選擇優(yōu)良解中的信息更有利于尋優(yōu)。對于類別參數(shù)X5，可以看出，所有配置都選擇了RI來初始化批次分割矩陣，這證明RI表現(xiàn)明顯優(yōu)于其他兩種方法。在初始化批次排列時，9個精英配置選擇了RI來進(jìn)行初始化，只有一種配置選擇了VSPT，從而說明了RI方法的有效性。對于類別參數(shù)X6，所有精英配置均使用FA策略來選擇機(jī)器，這說明FA比FC更適合解決本文問題。所有配置使用SP策略來執(zhí)行批次排序，這是因為SP比LP更好地利用了批量流的特性。對于類別參數(shù)X7，所有算法配置均采用了加權(quán)和方法，同時均使用了目標(biāo)歸一化。這證明了加權(quán)和方法以及目標(biāo)歸一化為更加適合MOHFSP_VS的適應(yīng)度值評估方法。對于類別參數(shù)X8，10種精英配置中，出現(xiàn)了5個配置選擇了PBX，3個配置選擇了OBX，而TPX和CX各被1個配置選中。在接下來的算法測試階段，將使用最優(yōu)的算法配置來構(gòu)造自動算法求解MOHFSP_VS，即X1=21，X2=10，X3=245，X4=0.7，X5=RI_RI，X6=FA_SP，X7=WS_USE，X8=PBX。

表5 輸出的10個精英配置

3.3 算法測試階段

為了評估由AAD自動構(gòu)建的MOEA的性能，將其與現(xiàn)有文獻(xiàn)中的4種MOEAs進(jìn)行比較，分別是MOCGWO[26]、MOEA/D[24]、PHMOEA/D[27]和NSGA-II[28]。選擇它們作為比較對象的原因如下：①MOEA/D和NSGA-II是解決多目標(biāo)調(diào)度問題和其他各種多目標(biāo)優(yōu)化問題的著名算法框架；②MOCGWO和PHMOEA/D已被證明在解決多目標(biāo)HFSPs時性能是優(yōu)異的，另外它們采用的解編碼都是兩層的，適合MOHFSP_VS的求解。本文也對比較算法中的參數(shù)進(jìn)行了適當(dāng)?shù)脑O(shè)置。對于PHMOEA/D中的數(shù)值參數(shù)，本文采用文獻(xiàn)中所建議的田口法[25]進(jìn)行設(shè)置。對于MOCGWO、MOEA/D和NSGA-II中的數(shù)值參數(shù)，在對應(yīng)的文獻(xiàn)中沒有找到具體的配置方法。因此，首先確定其數(shù)值參數(shù)的合理取值范圍，然后通過田口法進(jìn)行配置。對于比較算法中的類別參數(shù)，為了進(jìn)行公平的比較，所有比較算法都采用了本文所提出的編碼方案。在此基礎(chǔ)上，對于其他的類別參數(shù)，即初始化方法、解碼策略、聚集函數(shù)方法、目標(biāo)歸一化以及交叉算子，則根據(jù)表5輸出的最佳配置中出現(xiàn)的大多數(shù)進(jìn)行設(shè)置。

3.3.1 MOEAs算法與CPLEX在小規(guī)模數(shù)據(jù)集上的對比分析

對于每個算例，分配20個均勻分布的權(quán)重，CPLEX通過對兩個目標(biāo)線性加權(quán)的方式獨立運行20次，每次運行的時間限制設(shè)置為3 600 s。通過收集20次運行的解，得到一組非支配解。對于MOEAs，針對每個測試算例，獨立運行5次，每次運行時間設(shè)置為n×m×200 ms。表6和表7分別展示了基于C-metric和D-metric指標(biāo)的平均值(AVG)和標(biāo)準(zhǔn)差(SD)。此外，表7中還展示了MOEAs和CPLEX求解每個算例的運行時間。

對比AAD算法和CPLEX，基于C-metric指標(biāo)，從表6可以看出，CPLEX在問題3×2和3×3上取得了較大的C-metric均值，但隨著問題規(guī)模的增加，AAD算法在其他所有問題上均取得了更大的C-metric均值。對比于CPLEX的0.056，AAD算法取得了明顯大的總體平均值0.430。基于D-metric指標(biāo)，從表7中可以看出，AAD算法在問題3×3上取得了更小的D-metric均值，這說明AAD算法在3×3問題上得到的Pareto解在解集上分布更加均勻。除了問題3×2，AAD算法在其他問題上均取得了更小的D-metric均值，并取得了更小的總體平均值0.107。此外，從表7中可以看出，隨著批次和階段數(shù)量的增加，由于問題的NP難特性，從問題5×2開始，所有權(quán)重下，CPLEX在3 600 s的運行時間內(nèi)都不能獲得最優(yōu)解。同時，MOEAs的運行時間遠(yuǎn)小于CPLEX。通過這些觀察，可以得出結(jié)論，利用CPLEX求解混合整數(shù)規(guī)劃模型很難得到包含所有最優(yōu)Pareto解的Pareto解集。此外，CPLEX的運行時間是難以接受的。綜上所述，對比于傳統(tǒng)的數(shù)學(xué)規(guī)劃求解方法，MOEAs的優(yōu)越性是可以得到體現(xiàn)的。與其他MOEAs相比，基于C-metric，AAD算法在所有問題上均可以取得較大的均值。在所有問題上，根據(jù)C-metric結(jié)果，MOEA/D、PHMOEA/D和NSGA-II這3種算法所獲得的Pareto解全部可以被AAD算法得到的Pareto解所支配?；贒-metric的均值，AAD算法同樣在所有問題上表現(xiàn)最好。由此說明，AAD算法在小規(guī)模測試算例上取得的Pareto解集具有良好的收斂性和高效性。通過與CPLEX和其他MOEAs的對比，在小規(guī)模數(shù)據(jù)集上，AAD算法的高效性和優(yōu)越性是可以得到驗證的。

表6 小規(guī)模數(shù)據(jù)集上C-metric AVG(SD)值對比

表7 小規(guī)模數(shù)據(jù)集上D-metric AVG(SD)值對比

3.3.2 MOEAs算法在中大規(guī)模數(shù)據(jù)集上的對比分析

對于中大規(guī)模數(shù)據(jù)集上的每個測試算例，分別計算得到C-metric和D-metric的平均值和標(biāo)準(zhǔn)差。然后在相同的問題規(guī)模下，再次進(jìn)行平均，結(jié)果統(tǒng)計在表8和表9中。此外，為了驗證C-metric和D-metric結(jié)果的統(tǒng)計有效性，采用單因素方差分析(ANOVA)對平均值進(jìn)行分析。圖7和圖8分別顯示了在95%置信水平上C-metric和D-metric結(jié)果的Tukey HSD區(qū)間圖。在區(qū)間圖中，若兩種算法之間沒有重疊，則它們之間存在統(tǒng)計意義上的顯著差異。

根據(jù)表8中展示的C-metric結(jié)果可以看出，對于所有的15個問題，AAD相對于其他任何算法得到的C-metric均值都是最大的，并且所獲得的總體平均值遠(yuǎn)遠(yuǎn)大于其他算法。該結(jié)果意味著，AAD算法獲得的Pareto解中有很少一部分會被其他算法的Pareto解所支配，而其他算法獲得的Pareto解中大部分會被AAD算法所獲得的Pareto解所支配。由此證明AAD算法的收斂性在所有MOEAs中是最好的。從圖7中可以看出，基于C-metric均值數(shù)據(jù)，AAD算法在數(shù)理統(tǒng)計上明顯優(yōu)于其他4種算法。對于C-metric標(biāo)準(zhǔn)差，可以看出AAD算法得到的值總是大于其他算法得到的值。這是因為其他算法得到的Pareto解很難支配AAD所取得的Pareto解。因此，其他算法得到的C-metric標(biāo)準(zhǔn)差值總是比AAD算法小?；贒-metric比較，從表9中可以看出，AAD的總體平均值(0.093)遠(yuǎn)小于MOCGWO(0.317)、MOEA/D(0.648)、PHMOEA/D(0.842)和NSGA-II(0.282)。由圖8可以看到，根據(jù)顯著性分析結(jié)果，AAD再次明顯優(yōu)于其他4種算法。由此證明AAD取得的Pareto解集不但具有最好的收斂性，而且解集的分布性也是最好的，所得的Pareto解集更加逼近真實的Pareto前沿。從D-metric標(biāo)準(zhǔn)差值來看，AAD算法對于大多數(shù)問題是能夠得到最小值的，這可以說明AAD算法具有良好的魯棒性。為了更加直觀、清晰地展示它們的性能，圖9展示了所有算法針對4個不同問題規(guī)模測試算例得到的Pareto解集。圖9顯示AAD算法的確可以得到質(zhì)量更好且分布更加均勻的Pareto解，這與數(shù)值分析所得的結(jié)論是一致的。綜上所述，AAD算法在解決MOHFSP_VS時的性能是優(yōu)越且高效的。

表8 中大規(guī)模數(shù)據(jù)集上C-metric AVG(SD)值對比

表9 中大規(guī)模數(shù)據(jù)集上D-metric AVG(SD)值對比

4 結(jié)束語

考慮變分批技術(shù)，本文研究了以最小化最大完工時間和子批總數(shù)為目標(biāo)的MOHFSP_VS，并考慮了啟動和運輸操作。建立了一個多目標(biāo)混合整數(shù)規(guī)劃模型，并通過求解CPLEX模型來評估兩個目標(biāo)間的權(quán)衡關(guān)系。為了求解該一問題，本文在MDABC算法框架的基礎(chǔ)上，引入了AAD方法來自動構(gòu)造高性能的MOEA。針對問題特性，提出了動態(tài)解碼策略；針對具體問題特征和算法框架，對于可配置類別和數(shù)值參數(shù)，給出了合理的取值區(qū)間；對于AAD方法，采用了I/F-Race方法；最后，通過實驗證明，自動生成的MOEA表現(xiàn)是非常突出的。

對于MOHFSP_VS，未來的研究包括：①設(shè)計更高效的編碼和解碼策略；②基于問題特性開發(fā)啟發(fā)式規(guī)則進(jìn)一步改進(jìn)結(jié)果；③評估一些其他目標(biāo)(例如總流經(jīng)時間，總提前和延遲時間，和機(jī)器利用率等)；④考慮車間動態(tài)事件的影響，研究動態(tài)和重調(diào)度策略。對于AAD方法，筆者將嘗試將算法框架視為一個可配置參數(shù)，則具體參數(shù)將隸屬于算法框架，重新定義算法配置問題和I/F-Race流程。