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

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

0 引言

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

(5)每個子批在某一階段完成加工后，將立即傳輸到下游階段。

(6)同一批次的各個子批在一臺機器上連續(xù)地進行加工。在運輸到特定階段后，第一個子批可在啟動操作之后開始加工，其余的子批在運輸到這個階段后，在前一個子批完成加工后開始加工。

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

1.1 數學模型

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

表1 模型問題參數符號與定義

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

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

目標函數：

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

1.2 兩目標的權衡關系

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

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

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

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

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

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

2.1 問題編碼與權重產生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)均勻初始化方法

(2)隨機初始化方法

步驟 1對于每個批次j(j=1,…,n)來說，首先將剩余規(guī)模rj的值設為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]內隨機產生。

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

(3)混合初始化方法

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

步驟 2.1在區(qū)間[0,Si,j,e]得到一個隨機整數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ī)模已被確定。為保證隨機性，子批序列被隨機打亂。

一旦分割矩陣Δn生成，各批次中子批的加工時間就能夠確認，因此根據一些啟發(fā)式規(guī)則，批次序列πn的初始化也能夠完成。本文引入了文獻中用于初始化批次排列的6種啟發(fā)式規(guī)則，它們均在求解HFSP中表現出了較好的性能，分別為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之外，因為批量流的應用，這些規(guī)則都不能直接用于MOHFSP_VS，具體操作見文獻[13]。

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

2.4 可配置的分解策略和目標歸一化

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

(24)

根據上述定義，兩目標的上下界可以經過下列公式得出：

(25)

(26)

(27)

(28)

2.5 鄰域結構設計及可配置的協(xié)同操作

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

在MDABC算法的第二階段，兩個解之間需要執(zhí)行協(xié)同操作。對于車間調度問題，交叉算子具有良好的性能，能夠在保證遺傳優(yōu)良信息的基礎上，同時又有一定的全局搜索性。對于組合優(yōu)化問題，應用廣泛的交叉算子有部分映射交叉(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展示了上述交叉算子的示意圖。而對于批次分割矩陣，由于受固定批量大小的約束，上述交叉算子可能會產生不可行解。因此，為了能夠實現信息共享，促進它們之間的協(xié)作，本文引入了矩陣選取操作[13]，如圖6所示。具體來說，當確定一個批次在分割信息時，其在每一階段的批次分割，以一定的概率從兩個父解中的批次分割矩陣中選取(以下稱為選取概率)。從批次1到批次n，依次采取上述操作，確定完整的批次分割信息。

2.6 自動算法配置問題

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

表3 可配置參數及其分布

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

2.7 自動算法設計方法

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

算法1I/F-Race流程。

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

參數空間:X={X1,…,X9}

總預算成本: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 實驗設計

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

3.1 測試數據和性能指標

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

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

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

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

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

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

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

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

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

表4 I/F-Race中產生的過程數據

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

在測試了13個實例后，I/F-Race輸出了10個精英配置，如表5所示。從表5可以看出，每個配置都不同于其他配置。這意味著高性能算法可以通過配置不同的參數值組合來構造。對于數值參數X1，10個精英配置的取值均大于1，這也證明了MDABC算法中重啟策略的有效性。對于數值參數X4，可以看出，在10個精英配置中，有9個配置取值大于0.5，這說明在執(zhí)行交互操作的時候，選擇優(yōu)良解中的信息更有利于尋優(yōu)。對于類別參數X5，可以看出，所有配置都選擇了RI來初始化批次分割矩陣，這證明RI表現明顯優(yōu)于其他兩種方法。在初始化批次排列時，9個精英配置選擇了RI來進行初始化，只有一種配置選擇了VSPT，從而說明了RI方法的有效性。對于類別參數X6，所有精英配置均使用FA策略來選擇機器，這說明FA比FC更適合解決本文問題。所有配置使用SP策略來執(zhí)行批次排序，這是因為SP比LP更好地利用了批量流的特性。對于類別參數X7，所有算法配置均采用了加權和方法，同時均使用了目標歸一化。這證明了加權和方法以及目標歸一化為更加適合MOHFSP_VS的適應度值評估方法。對于類別參數X8，10種精英配置中，出現了5個配置選擇了PBX，3個配置選擇了OBX，而TPX和CX各被1個配置選中。在接下來的算法測試階段，將使用最優(yō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自動構建的MOEA的性能，將其與現有文獻中的4種MOEAs進行比較，分別是MOCGWO[26]、MOEA/D[24]、PHMOEA/D[27]和NSGA-II[28]。選擇它們作為比較對象的原因如下：①MOEA/D和NSGA-II是解決多目標調度問題和其他各種多目標優(yōu)化問題的著名算法框架；②MOCGWO和PHMOEA/D已被證明在解決多目標HFSPs時性能是優(yōu)異的，另外它們采用的解編碼都是兩層的，適合MOHFSP_VS的求解。本文也對比較算法中的參數進行了適當的設置。對于PHMOEA/D中的數值參數，本文采用文獻中所建議的田口法[25]進行設置。對于MOCGWO、MOEA/D和NSGA-II中的數值參數，在對應的文獻中沒有找到具體的配置方法。因此，首先確定其數值參數的合理取值范圍，然后通過田口法進行配置。對于比較算法中的類別參數，為了進行公平的比較，所有比較算法都采用了本文所提出的編碼方案。在此基礎上，對于其他的類別參數，即初始化方法、解碼策略、聚集函數方法、目標歸一化以及交叉算子，則根據表5輸出的最佳配置中出現的大多數進行設置。

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

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

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

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

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

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

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

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

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

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

4 結束語

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

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