軒 華， 李海云， 李 冰

(鄭州大學(xué) 管理學(xué)院， 河南 鄭州 450001)

0 引言

流水車間調(diào)度是制造業(yè)較為關(guān)注的一類研究問題，在工業(yè)和許多其他實(shí)踐中有著廣泛的應(yīng)用[1]。作為其中一類典型問題，置換流水車間調(diào)度問題(permutation flow shop scheduling problem，PFSSP)首次由Johnson[2]提出,并已被證明是一類典型的NP-hard組合優(yōu)化問題[3]。在現(xiàn)實(shí)生產(chǎn)中，由于機(jī)器故障或檢修等原因?qū)е聶C(jī)器在一定的時(shí)間段內(nèi)是不可用的，這就產(chǎn)生了本文所研究的具有機(jī)器可利用性的PFSSP。

在單目標(biāo)流水車間調(diào)度問題(flow shop scheduling problem，F(xiàn)SSP)的研究中，為最小化最大完工時(shí)間(makespan)，Mosheiov等[4]研究了帶單一維修時(shí)間窗的2臺(tái)機(jī)器流水車間和開放車間調(diào)度，對于流水車間，維修發(fā)生在第2臺(tái)機(jī)器，對于這2類問題提出了3/2近似算法；為求解m(m>2)個(gè)機(jī)器的FSSP，Miyata等[5]提出了構(gòu)造啟發(fā)式算法求解帶預(yù)防性維修和順序相關(guān)設(shè)置時(shí)間的無等待FSSP；Aggoune等[6]針對帶有限機(jī)器可利用性的FSSP，結(jié)合兩工件的臨時(shí)幾何方法和禁忌搜索算法提出了啟發(fā)式算法。

在多目標(biāo)FSSP的研究中，周炳海等[7]考慮了機(jī)器的衰退，提出了改進(jìn)雙目標(biāo)人工蜂群算法用于同時(shí)最小化makespan和維護(hù)成本；Zhang等[8]針對帶預(yù)防性和正確性維修的裝配式PFSSP，提出了新的迭代Pareto貪婪算法，用于同時(shí)最小化makespan和維護(hù)成本；Boufellouh等[9]針對帶預(yù)防性維修和全局資源約束的PFSSP，提出了非支配排序遺傳算法和粒子群優(yōu)化，用于同時(shí)最小化makespan和總生產(chǎn)成本。

求解PFSSP的優(yōu)化算法多以啟發(fā)式算法或元啟發(fā)式算法為主獲取問題近優(yōu)解。為最小化makespan，Abdel-Basset等[10]結(jié)合局域搜索策略和鯨魚優(yōu)化算法提出了混合鯨魚優(yōu)化算法；Zhao等[3]提出了一種混合高效作業(yè)序列映射方案和變鄰域搜索的和聲搜索算法；Liu等[11]結(jié)合NEH啟發(fā)式算法和局域搜索提出了一種混合差分進(jìn)化算法；Xie等[12]提出了一種基于教學(xué)-學(xué)習(xí)的混合優(yōu)化算法用來分別最小化makespan和最大延遲。作為一種智能優(yōu)化算法，遺傳算法已廣泛應(yīng)用于求解車間調(diào)度[8]等領(lǐng)域，而遺傳算法與其他算法的結(jié)合通常會(huì)提高求解性能，因此，在解決雙目標(biāo)PFSSP時(shí)如何設(shè)計(jì)有效的遺傳算法還要進(jìn)一步探討。

就目前查閱的文獻(xiàn)而言，關(guān)于帶機(jī)器可利用性的雙目標(biāo)PFSSP的研究較為有限，因此，為解決此類PFSSP，本文引入CDS啟發(fā)式算法、局域搜索、遺傳參數(shù)隨迭代數(shù)而變化的自適應(yīng)調(diào)整機(jī)制提出了一種改進(jìn)遺傳算法(improved genetic algorithm, IGA)，用于解決問題同時(shí)最小化總加權(quán)完成時(shí)間和總加權(quán)拖期。

1 問題描述及建模

1.1 問題描述

所研究的PFSSP可描述如下：n個(gè)待加工工件須經(jīng)m臺(tái)不同的機(jī)器進(jìn)行加工，即每個(gè)工件i有m道工序，以相同的加工順序依次在機(jī)器M1，機(jī)器M2，…，機(jī)器Mj，…，機(jī)器Mm上加工eij個(gè)時(shí)間段。每臺(tái)機(jī)器j有T個(gè)不可用時(shí)間窗，且不可用時(shí)間窗(Gjo,Hjo)事先已知且固定，工件在各機(jī)器的加工須在該機(jī)器的可利用時(shí)間段內(nèi)進(jìn)行。每臺(tái)機(jī)器一次至多處理一個(gè)工件，而每個(gè)工件一次只能在一臺(tái)機(jī)器上加工,工件一旦開始在一臺(tái)機(jī)器上加工，則該工序不允許中斷。

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

minF=μF1+λF2;

(1)

(2)

(3)

Cπ1j=aπ1+eπ1j,j=1;

(4)

Cπ1j≥Cπ1j-1+eπ1j,j∈(2,3,…,m);

(5)

Cπi1≥Cπi-11+eπi1,i∈(2,3,…,n);

(6)

Cπij≥max(Cπij-1,Cπi-1j)+eπij,i∈(2,

3,…,n),j∈(2,3,…,m);

(7)

Si1≥ai,i∈(1,2,…,n);

(8)

Cij≥Sij+eij,i∈(1,2,…,n),j∈(1,2,…,m);

(9)

Cij≤Gjo+M(1-Xijo),i∈(1,2,…,n),

j∈(1,2,…,m),o∈(1,2,…,T);

(10)

Cij≥eij+Hjo(1-Xijo)，i∈(1,2,…,n),

j∈(1,2,…,m),o∈(1,2,…,T);

(11)

(12)

(13)

Cij,Sij≥0,i∈(1,2,…,n),j∈(1,2,…,m);

(14)

Xijo,Yik∈(0,1),i,k∈(1,2,…,n),
j∈(1,2,…,m),o∈(1,2,…,T)。

(15)

其中，式(1)為所研究問題的目標(biāo)，即最小化總加權(quán)完成時(shí)間和總加權(quán)拖期的線性組合，兩部分分別由式(2)和式(3)計(jì)算得到，其中μ、λ分別為與完成時(shí)間和拖期相關(guān)的系數(shù)，且μ+λ=1；δi為工件i的目標(biāo)權(quán)重；Sim、Cim、eim分別為工件i在機(jī)器m上的開始時(shí)間、完工時(shí)間和加工時(shí)間;di為工件i的交貨期。對于序列π中的第一個(gè)工件π1,約束(4)定義了在第一臺(tái)機(jī)器上的完成時(shí)間，其中aπ1為工件π1的釋放時(shí)間。約束(5)表示在相鄰工序間的加工優(yōu)先級關(guān)系。對于工件加工序列的其他工件πi(i=2,3,…,n),約束(6)表示在第一臺(tái)機(jī)器的加工緊隨工件πi-1之后進(jìn)行。約束(7)描述了在后續(xù)機(jī)器上工件πi的完成時(shí)間由它在前道工序的完成時(shí)間以及其緊前工件πi-1在該機(jī)器的完成時(shí)間來決定。約束(8)確保了工件在第一臺(tái)機(jī)器的開始時(shí)間須在其釋放時(shí)間之后。約束(9)說明了同一個(gè)工件的開始和完成時(shí)間的關(guān)系。約束(10)和(11)確保了從工件開始加工到結(jié)束加工的整個(gè)時(shí)間段在機(jī)器的可用時(shí)間段內(nèi)，其中M為一個(gè)無窮大的數(shù)，Xijo為二元變量，當(dāng)工件i在機(jī)器j的第o個(gè)不可用時(shí)間窗之前加工時(shí)，Xijo=1，否則，Xijo=0。約束(12)表示序列的任一位置只能安排一個(gè)工件，其中Yik為二元變量，當(dāng)工件i分配到加工序列的位置k時(shí)，Yik=1，否則，Yik=0。約束(13)表示每個(gè)工件只能分派到序列內(nèi)的一個(gè)位置。約束(14)和(15)定義了變量取值范圍。

上述模型雖與文獻(xiàn)[13]類似，但也有不同：文獻(xiàn)[13]針對的是兩機(jī)FSSP，機(jī)器不可用時(shí)間段僅發(fā)生在第一臺(tái)機(jī)器，目標(biāo)是最小化最大完工時(shí)間，而本文研究的是多機(jī)問題，每臺(tái)機(jī)器均須考慮機(jī)器可利用性約束，目標(biāo)的最小化總加權(quán)完成時(shí)間和總加權(quán)拖期。

2 改進(jìn)遺傳算法

2.1 PFSSP的編碼及解碼

采用工件編號的整數(shù)編碼對工件加工序列進(jìn)行編碼?；谠摷庸ば蛄姓{(diào)度工件用來解碼，從機(jī)器M1至機(jī)器Mm，安排各機(jī)器上的工件加工時(shí)，檢查每個(gè)工件從Sij開始的eij個(gè)時(shí)間段是否出現(xiàn)在(Gjo,Hjo)內(nèi)，如沒有，則確定該Sij值;否則，需將Sij延后，直至(Sij,Sij+eij)在機(jī)器可利用時(shí)間段內(nèi)。

P個(gè)工件加工序列即構(gòu)成初始工件加工序列群。利用CDS啟發(fā)式算法產(chǎn)生40%的初始工件加工序列群，其余的則通過隨機(jī)程序產(chǎn)生。CDS啟發(fā)式算法實(shí)現(xiàn)過程如下。

Step1將m臺(tái)機(jī)器進(jìn)行臨近兩兩分組，構(gòu)成m-1個(gè)的虛擬兩機(jī)組合：[1,m]、[(1,2),(m-1,m)]、[(1,2,3),(m-2,m-1,m)],…,[(1,2,…,l),(m+1-l,…,m)]。

Step2對每一個(gè)虛擬兩機(jī)組合，分別計(jì)算工件i在虛擬兩機(jī)的總加工時(shí)間作為其在相應(yīng)虛擬機(jī)器的模擬加工時(shí)間，再利用文獻(xiàn)[2]算法獲得最優(yōu)加工序列，從而得到m-1個(gè)最優(yōu)加工序列。

Step3若(m-1)<40%P,則將上述過程產(chǎn)生的加工序列重復(fù)，以填補(bǔ)40%P-(m-1)個(gè)加工序列。

2.2 適應(yīng)度計(jì)算

由于本文優(yōu)化的目標(biāo)是最小化總加權(quán)完成時(shí)間和總加權(quán)拖期的加權(quán)和，故第π個(gè)工件加工序列的適應(yīng)度函數(shù)表示為

(16)

采用輪盤賭規(guī)則選擇適應(yīng)度值較高的工件加工序列執(zhí)行后續(xù)的交叉變異算子。

2.3 交叉和變異

設(shè)計(jì)自適應(yīng)交叉概率Pc和自適應(yīng)變異概率Pm以改善算法的搜索能力和收斂效果。定義當(dāng)前工件加工序列群的平均適應(yīng)度值fv：

(17)

令MG為最大迭代次數(shù)，g為當(dāng)前迭代次數(shù)，fx為最大適應(yīng)度值，Pcmax和Pcmin為交叉概率的最大值和最小值，Pmmax和Pmmin為變異概率的最大值和最小值。

(1)當(dāng)fπ≥fv時(shí)，即當(dāng)前加工序列的適應(yīng)度值較大時(shí)，Pc和Pm的取值隨當(dāng)前迭代次數(shù)的變化而變化。

(18)

(19)

(2)當(dāng)fπ

對輪盤賭規(guī)則選擇操作之后產(chǎn)生的序列群選擇連續(xù)的兩個(gè)父代工件加工序列A和B，從(0, 1)隨機(jī)產(chǎn)生一個(gè)數(shù)γ，當(dāng)γ

圖1 單點(diǎn)交叉Figure 1 Single-point crossover

對交叉操作后得到的新序列群內(nèi)的每個(gè)工件加工序列，從(0,1)隨機(jī)生成一個(gè)數(shù)u，若u

圖2 翻轉(zhuǎn)逆序變異Figure 2 Reverse order mutation

2.4 局域搜索

對執(zhí)行上述操作后目標(biāo)值仍未改進(jìn)的工件加工序列Z依次執(zhí)行基于如下鄰域搜索機(jī)制的局域搜索，當(dāng)變換之后的鄰域解優(yōu)于當(dāng)前解時(shí)，記錄最佳解，搜索結(jié)束，否則保留當(dāng)前解。

(1)兩兩交換。隨機(jī)選擇工件加工序列的2個(gè)工件編號，將其進(jìn)行交換，如圖3所示。

圖3 兩兩交換Figure 3 Pair-wise exchange

(2)單工件插入。隨機(jī)產(chǎn)生工件加工序列的2個(gè)工件位，將工件位靠前的工件編號插入到工件位靠后的工件編號的前面，如圖4所示。

圖4 單工件插入Figure 4 Single-job insertion

(3)多工件插入。隨機(jī)選擇工件加工序列的1個(gè)工件片段，從除去該工件片段外的部分工件加工序列里隨機(jī)選擇1個(gè)工件位，將所除去的工件片段插入至該位置，如圖5所示。

圖5 多工件插入Figure 5 Multiple-job insertion

2.5 改進(jìn)遺傳算法的計(jì)算流程

改進(jìn)遺傳算法具體描述如下。

Step1算法參數(shù)初始化。工件加工序列群規(guī)模P，最大迭代次數(shù)MG，交叉概率Pc，變異概率Pm。

Step2工件加工序列群初始化。由CDS啟發(fā)式算法和隨機(jī)程序的兩階段過程構(gòu)造初始加工序列群。

Step3計(jì)算每個(gè)工件加工序列的適應(yīng)度值，應(yīng)用輪盤賭規(guī)則選擇出優(yōu)秀的工件加工序列。

Step4基于自適應(yīng)交叉概率Pc進(jìn)行單點(diǎn)交叉。

Step5基于自適應(yīng)變異概率Pm進(jìn)行翻轉(zhuǎn)逆序變異。

Step6判斷經(jīng)交叉和變異后的工件加工序列的適應(yīng)度值較原工件加工序列是否有所改善，對未改善的工件加工序列依次基于兩兩交換、單工件插入和多工件插入產(chǎn)生鄰域解，若發(fā)現(xiàn)鄰域解優(yōu)于當(dāng)前解或3種鄰域搜索機(jī)制執(zhí)行完畢，結(jié)束局域搜索。

Step7判斷當(dāng)前迭代數(shù)是否超過MG，如超過，輸出最佳目標(biāo)值；反之，更新當(dāng)前迭代數(shù)，轉(zhuǎn)至Step 3。

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

為了公平起見，將所提出的結(jié)合CDS啟發(fā)式算法和局域搜索的改進(jìn)遺傳算法(IGA)與求解PFSSP的混合遺傳算法(HGA)[14]、不考慮自適應(yīng)遺傳參數(shù)設(shè)置的改進(jìn)遺傳算法(N-IGA)、結(jié)合NEH啟發(fā)式算法的自適應(yīng)遺傳算法(AGA&NEH)[15]進(jìn)行比較。所有實(shí)驗(yàn)均利用MATLAB 2020a編譯，在內(nèi)存為4.00 GB，處理器為AMD A10-9600P，主頻為2.4 GHz的計(jì)算機(jī)上運(yùn)行。經(jīng)實(shí)驗(yàn)測試，將N-IGA的交叉概率Pc和變異概率Pm分別設(shè)為0.65和0.02，所有算法的工件加工序列群規(guī)模均為100，以HGA運(yùn)行1 500代且最大運(yùn)行時(shí)間不超過120 s作為其他3種算法的停止條件。

用仿真實(shí)驗(yàn)對隨機(jī)數(shù)據(jù)測試不同Pc和Pm取值，將得到的最佳解所對應(yīng)的Pc和Pm值作為其最終取值：(Pcmin,Pcmax)=(0.4,0.8)，(Pmmin,Pmmax)=(0.05,0.1)。

3.1 參數(shù)設(shè)置

借鑒文獻(xiàn)[16]，μ取2個(gè)不同值，分別為μ=0.3，μ=0.7。令R表示交貨期的松弛度，取3個(gè)不同值，分別為R=0.5，R=1.0，R=1.5[17]。n=(50,100,150)，m=(5,10)，ai、δi和eij分別在(1,5)、(1,4)、(1,20)隨機(jī)產(chǎn)生。簡單起見，假定每臺(tái)機(jī)器有一個(gè)不可用時(shí)間段，即o=1，但所提出的算法也可以求解機(jī)器有多個(gè)不可用時(shí)間段的情況。

3.2 IGA的效果分析

為說明CDS啟發(fā)式算法和基于3種鄰域搜索機(jī)制的局域搜索對IGA的影響，取n=(50,100,150)，m=10，μ=0.3，R=(0.5,1.0,1.5)，將IGA、不采用局域搜索的結(jié)合CDS啟發(fā)式和自適應(yīng)遺傳參數(shù)的遺傳算法(CDS-AGA)和利用隨機(jī)程序產(chǎn)生初始加工序列群的結(jié)合局域搜索和自適應(yīng)遺傳參數(shù)的遺傳算法(LS-AGA)進(jìn)行對比。上述參數(shù)共產(chǎn)生了9個(gè)問題組合，取每個(gè)組合10次運(yùn)行結(jié)果的平均值作為該組合的測試結(jié)果，因此，本實(shí)驗(yàn)共測試了90組實(shí)驗(yàn)數(shù)據(jù)。以CDS-AGA算法運(yùn)行1 500代且最大運(yùn)行時(shí)間不超過120 s作為其他2種算法的停止條件。測試結(jié)果如表1所示，其中加粗顯示的為最佳目標(biāo)值。

表1 IGA、LS-AGA、CDS-AGA算法的測試結(jié)果Table 1 Test results of IGA,LS-AGA,CDS-AGA

由表1可看出，IGA的目標(biāo)值均優(yōu)于CDS-AGA和LS-AGA，說明在相同運(yùn)行時(shí)間下，嵌入的3種鄰域搜索機(jī)制可產(chǎn)生更佳鄰域解，應(yīng)用CDS啟發(fā)式算法能夠獲得更好的初始加工序列群。

3.3 測試結(jié)果與分析

(n,m,μ,R)的不同取值共產(chǎn)生了36個(gè)問題組合，每個(gè)組合隨機(jī)運(yùn)行10次，取其平均值作為該問題組合的測試結(jié)果，因此，本實(shí)驗(yàn)共測試了360個(gè)實(shí)例。定義γ1、γ2、γ3為目標(biāo)改進(jìn)率分別為

γ1=(FHGA-FIGA)/FIGA×100%;

γ2=(FN-IGA-FIGA)/FIGA×100%;

γ3=(FAGA&NEH-FIGA)/FIGA×100%。

式中：F表示目標(biāo)值。

(1)對不同規(guī)模問題的測試結(jié)果見表2。由表2可知，在平均計(jì)算時(shí)間77.65 s內(nèi)，HGA、N-IGA、AGA&NEH、IGA的目標(biāo)值分別為148 349.00、145 529.86、151 117.96、140 666.61，IGA相較于HGA改進(jìn)了5.05%，較N-IGA改進(jìn)了3.09%，較AGA&NEH改進(jìn)了7.33%。

表2 不同規(guī)模問題的測試結(jié)果Table 2 Test results of different scale problems

(2)為了對實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)意義下的分析和比較，取n=(50,100,150)且m=(5,10)的不同規(guī)模問題，對IGA相較于其他3種算法的目標(biāo)改進(jìn)率進(jìn)行統(tǒng)計(jì)學(xué)檢驗(yàn)，如圖6和圖7所示，IGA相較于其他3種算法均有明顯改進(jìn)。

圖6 不同μ取值下的目標(biāo)改進(jìn)率區(qū)間圖(95%的置信區(qū)間)Figure 6 Interval diagram of target improvement rate for different μ value (95% confidence interval)

圖7 不同R取值下的目標(biāo)改進(jìn)率區(qū)間圖(95%的置信區(qū)間)Figure 7 Interval diagram of target improvement rate for different R value (95% confidence interval)

取n=(50, 100, 150)，m=10，μ=0.3，R=0.5的4個(gè)算例在最大迭代次數(shù)1 500的限制條件下運(yùn)行上述4種算法，得到如圖8的趨勢圖，說明在相同迭代數(shù)內(nèi)，IGA得到的目標(biāo)值更優(yōu)。

圖8 隨迭代次數(shù)變化的目標(biāo)值變化趨勢Figure 8 Trend of the target value changing with the number of iterations

4 結(jié)束語

本文研究了具有機(jī)器可利用性和工件釋放時(shí)間的PFSSP。為盡可能最小化總加權(quán)完成時(shí)間和總加權(quán)拖期的加權(quán)和，提出了IGA進(jìn)行求解不同規(guī)模的PFSSP，通過仿真實(shí)驗(yàn)說明了IGA能夠在可接受的計(jì)算時(shí)間內(nèi)得到較好的近優(yōu)解。未來研究可將所提算法推廣以求解FSSP或研究其他啟發(fā)式算法(人工蜂群算法等)求解具有機(jī)器可利用性的PFSSP。