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

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

0 引言

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟2.2.1在調(diào)度時(shí)刻點(diǎn)，即機(jī)器的空閑時(shí)間，得到ArrivedUnits的值。具體方法如下：依次從ArrivedSublot遍歷到Tj，直到某一子批在調(diào)度時(shí)刻點(diǎn)還未達(dá)到階段i，利用這一子批更新ArrivedSublot。將在調(diào)度時(shí)刻點(diǎn)，已經(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)度時(shí)刻點(diǎn)開始進(jìn)行加工，開始時(shí)間即為調(diào)度時(shí)刻點(diǎn)，完工時(shí)間為開始時(shí)間與加工時(shí)間之和。利用完工時(shí)間更新機(jī)器的空閑時(shí)間，利用該子批所包含的加工單元數(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)前子批開始加工，開始時(shí)間為子批ArrivedSublot-1運(yùn)輸?shù)诫A段i的時(shí)間，完工時(shí)間為開始加時(shí)間與加工時(shí)間之和。利用完工時(shí)間更新機(jī)器的空閑時(shí)間，利用該子批所包含的加工單元數(shù)更新SchedulingUnits和ScheduledUnits。

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

綜上所述，針對問題的解碼過程，可得到4個(gè)可配置的解碼啟發(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è)計(jì)了初始解的生成方法。首先，介紹了分割矩陣Δn的生成方法，然后給出了批次序列π的生成方法。對于初始化Δn，設(shè)計(jì)了3種方法，即均勻初始化(Uniform Initialization，UI)、隨機(jī)初始化(Random Initialization，RI)和混合初始化(Mixed Initialization，MI)。具體流程描述如下：

(1)均勻初始化方法

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

步驟 1對于每個(gè)批次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]得到一個(gè)隨機(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打亂子批排序。通過上述步驟，每個(gè)子批規(guī)模已被確定。為保證隨機(jī)性，子批序列被隨機(jī)打亂。

一旦分割矩陣Δn生成，各批次中子批的加工時(shí)間就能夠確認(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àn)榕苛鞯膽?yīng)用，這些規(guī)則都不能直接用于MOHFSP_VS，具體操作見文獻(xiàn)[13]。

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

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

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

(24)

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

(25)

(26)

(27)

(28)

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

MDABC算法在雇傭蜂階段，采用了VND策略。因此，需要根據(jù)解的編碼來設(shè)計(jì)鄰域結(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ī)插入到一個(gè)隨機(jī)選擇的位置中。②交換操作：從批次序列向量πn中隨機(jī)選擇兩批次，然后交換它們的位置。③變化操作：從批次分割矩陣集合中隨機(jī)選取帶有至少兩個(gè)子批的批次ψj。針對ψj，在每一階段i，隨機(jī)選擇兩個(gè)子批，將一個(gè)子批的規(guī)?？s減一個(gè)基于分布U[0,5]得到的一整數(shù)，而相應(yīng)地，將另一子批的規(guī)模增加一個(gè)相同的整數(shù)。④組合結(jié)構(gòu)1：先執(zhí)行插入操作，再執(zhí)行變化操作。⑤組合結(jié)構(gòu)2：先執(zhí)行交換操作，再執(zhí)行變化操作。

在MDABC算法的第二階段，兩個(gè)解之間需要執(zhí)行協(xié)同操作。對于車間調(diào)度問題，交叉算子具有良好的性能，能夠在保證遺傳優(yōu)良信息的基礎(chǔ)上，同時(shí)又有一定的全局搜索性。對于組合優(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)確定一個(gè)批次在分割信息時(shí)，其在每一階段的批次分割，以一定的概率從兩個(gè)父解中的批次分割矩陣中選取(以下稱為選取概率)。從批次1到批次n，依次采取上述操作，確定完整的批次分割信息。

2.6 自動(dòng)算法配置問題

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

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

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

2.7 自動(dòng)算法設(shè)計(jì)方法

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

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

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

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

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

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

為了進(jìn)行全局的調(diào)優(yōu)以確定最佳算法配置，從400個(gè)中大規(guī)模算例中隨機(jī)選擇100個(gè)具有不同問題規(guī)模的算例作為I/F-Race的測試算例。這100個(gè)算例構(gòu)成了算法1中的測試集合I={I1,…,Ii,…IG}，它們的順序是隨機(jī)打亂的。本文將預(yù)算成本設(shè)置為實(shí)驗(yàn)的數(shù)量，一次實(shí)驗(yàn)是指利用一種算法配置求解一個(gè)測試算例?？傤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個(gè)迭代過程。隨著迭代數(shù)的增加，每代的預(yù)算成本逐漸增加。同時(shí)，迭代1用到了一個(gè)測試算例，迭代2、3、4、5分別用到了2、3、3、4個(gè)測試算例。這意味著在迭代初期，精英配置和劣質(zhì)配置比較容易識別，而在迭代后期，每個(gè)候選配置將需要更加細(xì)致地評估。這背后的原因是，在后續(xù)的迭代中生成的候選配置較為相似，因此需要更多的評估成本進(jìn)行識別。

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

表5 輸出的10個(gè)精英配置

3.3 算法測試階段

為了評估由AAD自動(dòng)構(gòu)建的MOEA的性能，將其與現(xiàn)有文獻(xiàn)中的4種MOEAs進(jìn)行比較，分別是MOCGWO[26]、MOEA/D[24]、PHMOEA/D[27]和NSGA-II[28]。選擇它們作為比較對象的原因如下：①M(fèi)OEA/D和NSGA-II是解決多目標(biāo)調(diào)度問題和其他各種多目標(biāo)優(yōu)化問題的著名算法框架；②MOCGWO和PHMOEA/D已被證明在解決多目標(biāo)HFSPs時(shí)性能是優(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ù)集上的對比分析

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

對比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的運(yùn)行時(shí)間內(nèi)都不能獲得最優(yōu)解。同時(shí)，MOEAs的運(yùn)行時(shí)間遠(yuǎn)小于CPLEX。通過這些觀察，可以得出結(jié)論，利用CPLEX求解混合整數(shù)規(guī)劃模型很難得到包含所有最優(yōu)Pareto解的Pareto解集。此外，CPLEX的運(yùn)行時(shí)間是難以接受的。綜上所述，對比于傳統(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)越性是可以得到驗(yàn)證的。

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

根據(jù)表8中展示的C-metric結(jié)果可以看出，對于所有的15個(gè)問題，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)計(jì)上明顯優(yōu)于其他4種算法。對于C-metric標(biāo)準(zhǔn)差，可以看出AAD算法得到的值總是大于其他算法得到的值。這是因?yàn)槠渌惴ǖ玫降腜areto解很難支配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解集更加逼近真實(shí)的Pareto前沿。從D-metric標(biāo)準(zhǔn)差值來看，AAD算法對于大多數(shù)問題是能夠得到最小值的，這可以說明AAD算法具有良好的魯棒性。為了更加直觀、清晰地展示它們的性能，圖9展示了所有算法針對4個(gè)不同問題規(guī)模測試算例得到的Pareto解集。圖9顯示AAD算法的確可以得到質(zhì)量更好且分布更加均勻的Pareto解，這與數(shù)值分析所得的結(jié)論是一致的。綜上所述，AAD算法在解決MOHFSP_VS時(shí)的性能是優(yōu)越且高效的。

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

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

4 結(jié)束語

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

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