含不相關機的多目標混合流水車間調度

軒 華，關瀟風，王薛苑

(鄭州大學 管理工程學院，河南 鄭州 450001)

0 引 言

近年來，綠色制造受到了高度重視，178個國家和地區于2015年簽署了《巴黎協定》，中國也在“中國制造2025”中明確綠色制造是其重大戰略方向之一[1]。多階段混合流水車間(multi-stage hybrid flow shop，MHFS)調度問題廣泛存在于鋼鐵、化工、紡織、半導體等行業，因此探討MHFS的綠色制造問題具有實際意義。

在多目標優化的研究中，大都是假設機器加工速度固定不變，例如文獻[1]針對MHFS調度提出了改進NSGAII算法以同時最小化總能耗和最大完工時間；文獻[2]針對可重入MHFS調度，提出了多目標蟻獅優化算法以同時最小化最大完工時間和能耗成本。然而，在實際生產中，可通過調節機器自身的加工速度來更好地滿足生產需求。令機器具有不同加工速度，文獻[3]研究了含有限緩沖的流水線調度，為最小化總能耗和最大完工時間，提出了混合探路者算法；文獻[4]為解決置換流水車間調度的最大完工時間和總碳排放最小化問題，提出了改進的混合布谷鳥算法；文獻[5]針對作業車間調度問題提出了多目標離散灰狼算法以同時優化總能耗和最大完工時間；針對MHFS調度，文獻[6，7]分別提出了新型教學優化算法和新型蛙跳算法以最小化總能耗和總延遲，文獻[8]提出了一種基于分解的多目標離散人工蜂群算法以最小化最大完工時間和總能耗。就目前查閱的文獻而言，機器加工速度可變的MHFS調度的研究還較為欠缺；另外，大多數研究聚焦于生產時間表的確定，而較少考慮機器調度和運輸計劃間的協調，因此，針對不相關機和傳送的MHFS問題(multi-stage hybrid flow shop problem with unrelated machines and transportation time，MHFSP-UM&TT)，本文提出了多目標離散灰狼優化(multi-objective discrete grey wolf optimization algorithm，MODGWO)算法進行求解。

1 問題與建模

在MHFSP-UM&TT中，N個待加工工件需按相同的生產路徑依次經過M道工序進行處理，每道工序上有多臺機器(至少有一道工序上的機器多于一臺)，這些機器是不相關并行機，無機器資格約束，即工件在某道工序的加工可由該工序上的任一機器來完成。每臺機器具有mul種速度，速度集V={v1，v2，…，vmul}， 當工件在機器上正在加工時，該機器的加工速度不發生變化。工件在前臺機器完成加工后，到下道工序開始加工前，有一個已知的時間滯后，即傳送時間，其值由搬運工件的運輸機所決定。生產過程中，機器存在兩種不同狀態：加工狀態和空閑狀態。如果工件j在機器上以更高的速度加工，其處理時間雖然會較短但能耗會增加，即對于vi>vg，pjsliBEslg×pjslg。

問題的其它假設如下：

(1)一道工序的加工不允許中斷；

(2)一臺機器一次至多加工一個工件，而一個工件一次至多在一臺機器加工；

(3)工序間緩沖能力無限；

(4)機器在任意時刻可用，不考慮損壞和維修。

參數定義如下：

N：總工件數；

M：總工序數；

ms：工序s可利用的機器數；

j：工件標號，j=1，2，…，N；

s：工序標號，s=1，2，…，M；

l：機器標號，l=1，2，…，ms；

vi，vg：機器加工速度，i，g=1，2，…，mul；

TPs：工件在工序s完成加工后的傳送時間；

Pjsl：工件j在工序s的機器l的基本處理時間；

pjsli：工件j在工序s的機器l上以速度vi加工的處理時間，pjsli=Pjsl/vi；

NUMsl：工序s的機器l上分配的工件總數，0≤NUMsl≤N；

k：某臺機器所進行的加工任務的編號，0≤k≤NUMsl；

JOBslk：工序s的機器l上分配的第k個任務對應的工件號；

SBEsl：工序s的機器l基本單位加工能耗；

IEsl：工序s的機器l處于空閑狀態時機器的單位時間能耗；

BEsli：工序s的機器l以速度vi加工工件時機器的單位時間能耗，BEsli=SBEsl*vi2；

Xslki：二元變量，若工序s機器l以速度i來加工第k個任務，則Xslki=1，否則Xslki=0；

Yjsli：二元變量，若工件j在工序s的加工由機器l以速度i完成，則Yjsli=1，否則Yjsli=0；

Zslk：二元變量，若工序s上機器l加工的相鄰兩個加工任務k和k+1之間有時間間隔，則Zslk=1，否則Zslk=0；

BTslk：工序s上機器l的任務k的開始加工時間；

CTslk：工序s上機器l的任務k的完成加工時間；

DTjs：工件j在工序s的開始時間；

FTjs：工件j在工序s的完成時間；

Cmax：最大完工時間；

SE：總能耗；

π：調度方案。

問題目標

minCmax

(1)

minH

(2)

π滿足約束

(3)

(4)

(5)

(6)

(7)

Cmax=max{FTjM}，?j

(8)

(9)

Yjsli∈{0，1}，?j，s，l，i

(10)

Yjsli∈{0，1}，?j，s，l，i

(11)

Xslki∈{0，1}，?s，l，k，i

(12)

Zslk∈{0，1}，?s，l，k

(13)

DTjs，FTjs≥0，?j，s

(14)

上述式(1)、式(2)為目標，即同時追求最大完工時間和總能耗的最小化；約束(3)表示每個工件在任一工序只能由一臺機器以某一確定速度來加工；約束(4)表示針對機器上某一個加工任務k，機器只能用一個速度來加工。約束(5)定義了工件在各工序開始加工的時間；約束(6)定義了工件的在各工序結束加工的時間；約束(7)說明了每臺機器上每個任務的開工和完工時間之間的關系；約束(8)～約束(9)計算了最大完工時間和總能耗；約束(10)確保了所有工件由階段上所有機器來完成；約束(11)～約束(14)定義了變量取值范圍。

2 多目標離散灰狼算法

灰狼優化(grey wolf optimization，GWO)算法是一種模仿狼群捕獵行為的群體智能優化算法，它具有參數少及優化效果較好等優點，其主要過程包括生成一個初始灰狼種群，選出領導層的3頭狼(α，β，δ)，底層狼ω向領導層的狼移動、從而包圍和攻擊獵物，完成捕食，已經被應用于許多調度問題[9-14]。

2.1 編碼和解碼

MHFSP-UM&TT需解決工件加工順序、工件加工機器以及機器加工速度，根據問題特點，設計了基于機器分配碼和速度選擇碼的編碼方案來表述個體。采用整數編碼，每個個體長度為2NM，其中前NM個元素wjs表示機器號，滿足[1，ms]的離散均勻分布，后NM個元素ejs對應機器加工速度，滿足[v1，vmul]的離散均勻分布。pop個個體組成灰狼狼群，圖1顯示了N=M=2的一個灰狼種群。

圖1 MHFSP-UM&TT的灰狼種群表述

為解決工件調度，需確定分配到同一機器上的工件加工順序，因此提出了基于最短處理時間原則的解碼方案。對于每個個體，由其機器分配碼和速度選擇碼可知相應的機器及其加工速度，在第一道工序，將由同一臺機器加工的工件按照最短處理時間進行非降序排列，獲得各臺機器上工件加工順序，即加工任務序列，對于每臺機器，排在第一位置的工件開工時間為零，其它工件的開工時間則為其緊前工件的完工時間；在第2，…，M道工序，計算工件到達該工序的時間，取它和所分配機器的最早可利用時間的最大值作為工件在該機器的開工時間。

2.2 灰狼種群初始化

采用反向學習策略以及基于非支配等級和擁擠距離的方法生成初始灰狼種群。令A=(d1，d2，…，dD) 為D維空間中的一個點，其中dq∈[a，b]， 則反向點A′=(d′1，d′2，…，d′D)，d′q=a+b-dq。

初始灰狼種群生成過程如下：

步驟1 隨機生成一個初始灰狼種群；

步驟2 按照反向學習策略，產生反向種群；

步驟3 將隨機初始種群和反向種群合并，劃分非支配等級：

(1)計算每個個體π的被支配個數nπ和支配個體的集合Hπ；

(2)找出nπ=0的個體，將其放入等級為0的非支配集合F0中；

(3)被放入F0內的個體數量為μ0，對于F0內的每個個體θ(0r)，r=1，2，…，μ0， 找到其支配個體集合Hθ(0r)， 針對每個個體σ∈Hθ(0r)，nσ=nσ-1， 若nσ=0，將個體σ放入等級為1的非支配集合F1中，以此類推，直至所有個體都被分級。

步驟4 擁擠距離排序：

(1)取單個等級集合內個體，將它們按照一個目標的數值進行非降序排列；

(2)針對該目標，將該非支配集合內個體的最大目標值作為fmax，最小目標值作為fmin。將這兩個極值點對應個體的擁擠距離設置為一個無窮大的數；計算其余個體π最相鄰個體之間的距離，即個體π-1和π+1的目標值的差，使用fmax和fmin進行歸一化，得到

(15)

(3)遍歷目標，將個體π的每個目標歸一化后的f′π相加得到擁擠距離；

(4)進入下一等級非支配集合，返回步驟4的(1)，直至完成所有集合內個體擁擠距離的計算；

(5)對于每一非支配集合，基于擁擠距離進行非升序排列。

步驟5 按照F0，F1，…從排序后的擁擠距離序列中選擇前pop個灰狼個體作為最終初始灰狼種群。

2.3 領導層個體的選擇

2.4 捕食行為機制

若ω狼僅跟隨領導層狼進行捕食，可能會降低算法的搜索能力，導致過早收斂。借鑒文獻[6]，設計了ω狼自走模式以提高算法搜索能力。

令ω狼執行跟隨模式的概率為ac，執行自走模式的概率為(1-ac)，通過ac的動態變化以使算法在迭代前期著重于搜索能力，迭代后期著重于開發能力，其中ac滿足

(16)

式中：acmax=1，acmin=0，G為當前迭代次數，Gmax為最大迭代數。

2.4.1 跟隨模式

根據MHFSP-UM&TT的特點，提出了基于交叉的個體生成方式，即ω狼按照一定的概率與領導層 (α，β，δ) 中的一個個體進行交叉操作，從而產生新個體new_π，即

(17)

式中：rand為在區間(0，1)內產生的隨機數，CX為交叉操作。

采用均勻兩點交叉和多點交叉兩種方式，若隨機數rand<0.2，執行均勻兩點交叉(Operator1)，如圖2(a)所示，否則執行多點交叉(Operator2)，如圖2(b)所示。

圖2 交叉操作

Operator1：均勻兩點交叉

步驟1 隨機選擇 {α，β，δ} 中的一個，這里以圖2(a)為例；

步驟2 從[1，2NM]隨機生成兩個點，分別將πω和πα分成3個區段；

步驟3 隨機生成數ri(ri∈{1，2，3})。ri=1時，用πα第一區段替換πω第一區段；ri=2時，用πα第二區段替換πω第二區段；ri=3時，用πα第三區段替換πω第三區段。

Operator2：多點交叉

步驟1 生成一個由0和1組成的字符串SN={z1，z2，…，z2NM}， 其中1出現的概率為0.05。

步驟2 若zc=0 (c∈{1，2，…，2NM})， 則new_π第c個位置的元素繼承πω的機器號或機器加工速度，否則繼承πα的機器號或機器加工速度。

2.4.2 自走模式

在自走模式中，ω狼不跟隨領導層灰狼去捕食，而是自己去尋找食物，依靠變異操作來實現。若隨機數rand<0.5，對機器分配碼執行多點變異(Operator3)，如圖3(a)所示，否則對速度選擇碼執行Operator3，如圖3(b)所示。

圖3 多點變異操作

Operator3：多點變異

對于ω狼的每個元素，若隨機數rand<0.05，取同一工序的其余機器號或同一機器的其余加工速度替換原有機器號或原有機器加工速度。

2.5 精英保留

精英保留策略會記錄當前種群中最好的個體，迭代過程中可能產生很多重復的父代，嚴重影響算法性能。由式(15)可知，如果擁擠距離為0，則至少存在3個相同個體，為增加種群多樣性，執行如下過程：

步驟1 合并父代PPG={π}、 子代CPG={new_π}。

步驟2 對合并后的種群進行非支配排序劃分集合，計算每一集合內個體的擁擠距離，將擁擠距離為0的個體刪除，按擁擠距離非升序排列該等級內個體。

步驟3 記錄剩余的個體數，如果它小于種群規模pop，則隨機生成個體補充到PPG+1中，否則選取前pop個個體進入PPG+1中。

綜上，可繪制MODGWO算法流程，如圖4所示。

圖4 MODGWO算法流程

3 實驗設計與分析

為驗證MODGWO的有效性，將其與NSGA-II和多目標改進和聲搜索(記為MOIHS)算法對比以測試算法性能，其中，NSGA-II于2002年被提出并應用于多個領域[15]；改進和聲搜索算法已用于求解單目標問題[16]，引入非支配等級、擁擠距離排序和精英保留策略，使其可優化多目標問題，稱之為MOIHS。

所有算法均采用Matlab R2018a編程，在處理器為AMD Ryzen 7400H，CPU為2.9 Hz，內存為16 G的微機上運行。測試結果通過距離指標IGDI、比例指標ΩI和ζI以及運行時間CPU(單位秒)來衡量，其中IGDI定義為算法I所輸出的非支配解集QI內元素相對于參考集Q*的距離[5]，ΩI為Q*中由算法I提供的非支配解占Q*整體的比例[17]，ζI為算法I提供的非支配解的個數。IGDI和ΩI計算如下

(18)

(19)

(20)

(21)

其中，參考集Q*是將3種算法得出的非支配解合并后，通過非支配等級劃分獲取的非支配解集；E是優化目標的數量；由于最大完工時間和總能耗在數量級方面差異較大，故先對數據歸一化處理，即計算式(20)，再獲取IGDI。由式(18)可知IGDI與算法性能成反比。

3.1 數據產生

為公平比較上述3種算法，將種群規模pop均設為100，最大迭代次數Gmax設為400。令NSGA-II中交叉概率為0.9，變異概率為0.2；MOIHS中新和聲取自和聲庫概率為0.9，音調微調概率為0.05。

其它數據產生如下：基本處理時間Pjsl～U[4，10]； 工件傳送時間TPs～U[2，5]； 機器基本單位加工能耗SBEsl～U[2，4]； 單位時間空閑能耗IEsl=1；機器加工速度V={1.0，1.3，1.5，1.7，2.0}； 每道工序的不相關機數ms∈{2，3，4}。 工件數N∈{30，50，60，90，100，120，150}， 工序數M∈{2，4，6}， 據此產生21個問題組合，每種組合產生一組算例。

3.2 結果分析

表1給出了這3種算法的測試結果，從該表可看出，由所提出算法MODGWO得到的IGDI小于NSGA-II和MOIHS，有13個算例的IGDI為0；MODGWO在20個算例中的ΩI超過其它兩種算法，有13個算例的參考集Q*的所有非支配解由MODGWO提供。針對所有算例，MODGWO的運行時間比NSGA-II略長，但均少于MOIHS。

表1 3種算法的測試結果

圖5為3種算法求解30*6、50*6、90*4和50*4這4個算例分別運行10次得到的所有非支配解的分布圖，從該圖可知，由MODGWO算法產生的非支配解多數優于其它兩種算法，這也說明了MODGWO求解MHFSP-UM&TT的有效性。

圖5 4個算例計算10次的非支配解分布

4 結束語

研究了MHFSP-UM&TT，以最小化最大完工時間和總能耗為目標建立整數規劃模型，并利用多目標離散灰狼優化算法求解該問題。主要工作有：①采用反向學習策略縮短狼群到食物的距離，在捕食行為中引入了自走模式以提高算法的搜索能力，利用精英保留策略保存優良個體；②通過實驗驗證了MODGWO算法求解MHFSP-UM&TT的有效性和優越性。綠色調度廣泛存在于實際生產中，未來可深入研究此類問題，如考慮機器資格約束、模糊加工等特征，設計更加高效的智能算法等等。