含不相關(guān)機(jī)的多目標(biāo)混合流水車間調(diào)度

軒 華，關(guān)瀟風(fēng)，王薛苑

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

0 引 言

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

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

1 問(wèn)題與建模

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

問(wèn)題的其它假設(shè)如下：

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

(2)一臺(tái)機(jī)器一次至多加工一個(gè)工件，而一個(gè)工件一次至多在一臺(tái)機(jī)器加工；

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

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

參數(shù)定義如下：

N：總工件數(shù)；

M：總工序數(shù)；

ms：工序s可利用的機(jī)器數(shù)；

j：工件標(biāo)號(hào)，j=1，2，…，N；

s：工序標(biāo)號(hào)，s=1，2，…，M；

l：機(jī)器標(biāo)號(hào)，l=1，2，…，ms；

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

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

Pjsl：工件j在工序s的機(jī)器l的基本處理時(shí)間；

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

NUMsl：工序s的機(jī)器l上分配的工件總數(shù)，0≤NUMsl≤N；

k：某臺(tái)機(jī)器所進(jìn)行的加工任務(wù)的編號(hào)，0≤k≤NUMsl；

JOBslk：工序s的機(jī)器l上分配的第k個(gè)任務(wù)對(duì)應(yīng)的工件號(hào)；

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

IEsl：工序s的機(jī)器l處于空閑狀態(tài)時(shí)機(jī)器的單位時(shí)間能耗；

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

Xslki：二元變量，若工序s機(jī)器l以速度i來(lái)加工第k個(gè)任務(wù)，則Xslki=1，否則Xslki=0；

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

Zslk：二元變量，若工序s上機(jī)器l加工的相鄰兩個(gè)加工任務(wù)k和k+1之間有時(shí)間間隔，則Zslk=1，否則Zslk=0；

BTslk：工序s上機(jī)器l的任務(wù)k的開(kāi)始加工時(shí)間；

CTslk：工序s上機(jī)器l的任務(wù)k的完成加工時(shí)間；

DTjs：工件j在工序s的開(kāi)始時(shí)間；

FTjs：工件j在工序s的完成時(shí)間；

Cmax：最大完工時(shí)間；

SE：總能耗；

π：調(diào)度方案。

問(wèn)題目標(biāo)

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，F(xiàn)Tjs≥0，?j，s

(14)

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

2 多目標(biāo)離散灰狼算法

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

2.1 編碼和解碼

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

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

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

2.2 灰狼種群初始化

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

初始灰狼種群生成過(guò)程如下：

步驟1 隨機(jī)生成一個(gè)初始灰狼種群；

步驟2 按照反向?qū)W習(xí)策略，產(chǎn)生反向種群；

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

(1)計(jì)算每個(gè)個(gè)體π的被支配個(gè)數(shù)nπ和支配個(gè)體的集合Hπ；

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

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

步驟4 擁擠距離排序：

(1)取單個(gè)等級(jí)集合內(nèi)個(gè)體，將它們按照一個(gè)目標(biāo)的數(shù)值進(jìn)行非降序排列；

(2)針對(duì)該目標(biāo)，將該非支配集合內(nèi)個(gè)體的最大目標(biāo)值作為fmax，最小目標(biāo)值作為fmin。將這兩個(gè)極值點(diǎn)對(duì)應(yīng)個(gè)體的擁擠距離設(shè)置為一個(gè)無(wú)窮大的數(shù)；計(jì)算其余個(gè)體π最相鄰個(gè)體之間的距離，即個(gè)體π-1和π+1的目標(biāo)值的差，使用fmax和fmin進(jìn)行歸一化，得到

(15)

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

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

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

步驟5 按照F0，F(xiàn)1，…從排序后的擁擠距離序列中選擇前pop個(gè)灰狼個(gè)體作為最終初始灰狼種群。

2.3 領(lǐng)導(dǎo)層個(gè)體的選擇

2.4 捕食行為機(jī)制

若ω狼僅跟隨領(lǐng)導(dǎo)層狼進(jìn)行捕食，可能會(huì)降低算法的搜索能力，導(dǎo)致過(guò)早收斂。借鑒文獻(xiàn)[6]，設(shè)計(jì)了ω狼自走模式以提高算法搜索能力。

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

(16)

式中：acmax=1，acmin=0，G為當(dāng)前迭代次數(shù)，Gmax為最大迭代數(shù)。

2.4.1 跟隨模式

根據(jù)MHFSP-UM&TT的特點(diǎn)，提出了基于交叉的個(gè)體生成方式，即ω狼按照一定的概率與領(lǐng)導(dǎo)層 (α，β，δ) 中的一個(gè)個(gè)體進(jìn)行交叉操作，從而產(chǎn)生新個(gè)體new_π，即

(17)

式中：rand為在區(qū)間(0，1)內(nèi)產(chǎn)生的隨機(jī)數(shù)，CX為交叉操作。

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

圖2 交叉操作

Operator1：均勻兩點(diǎn)交叉

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

步驟2 從[1，2NM]隨機(jī)生成兩個(gè)點(diǎn)，分別將πω和πα分成3個(gè)區(qū)段；

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

Operator2：多點(diǎn)交叉

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

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

2.4.2 自走模式

在自走模式中，ω狼不跟隨領(lǐng)導(dǎo)層灰狼去捕食，而是自己去尋找食物，依靠變異操作來(lái)實(shí)現(xiàn)。若隨機(jī)數(shù)rand<0.5，對(duì)機(jī)器分配碼執(zhí)行多點(diǎn)變異(Operator3)，如圖3(a)所示，否則對(duì)速度選擇碼執(zhí)行Operator3，如圖3(b)所示。

圖3 多點(diǎn)變異操作

Operator3：多點(diǎn)變異

對(duì)于ω狼的每個(gè)元素，若隨機(jī)數(shù)rand<0.05，取同一工序的其余機(jī)器號(hào)或同一機(jī)器的其余加工速度替換原有機(jī)器號(hào)或原有機(jī)器加工速度。

2.5 精英保留

精英保留策略會(huì)記錄當(dāng)前種群中最好的個(gè)體，迭代過(guò)程中可能產(chǎn)生很多重復(fù)的父代，嚴(yán)重影響算法性能。由式(15)可知，如果擁擠距離為0，則至少存在3個(gè)相同個(gè)體，為增加種群多樣性，執(zhí)行如下過(guò)程：

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

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

步驟3 記錄剩余的個(gè)體數(shù)，如果它小于種群規(guī)模pop，則隨機(jī)生成個(gè)體補(bǔ)充到PPG+1中，否則選取前pop個(gè)個(gè)體進(jìn)入PPG+1中。

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

圖4 MODGWO算法流程

3 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

(18)

(19)

(20)

(21)

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

3.1 數(shù)據(jù)產(chǎn)生

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

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

3.2 結(jié)果分析

表1給出了這3種算法的測(cè)試結(jié)果，從該表可看出，由所提出算法MODGWO得到的IGDI小于NSGA-II和MOIHS，有13個(gè)算例的IGDI為0；MODGWO在20個(gè)算例中的ΩI超過(guò)其它兩種算法，有13個(gè)算例的參考集Q*的所有非支配解由MODGWO提供。針對(duì)所有算例，MODGWO的運(yùn)行時(shí)間比NSGA-II略長(zhǎng)，但均少于MOIHS。

表1 3種算法的測(cè)試結(jié)果

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

圖5 4個(gè)算例計(jì)算10次的非支配解分布

4 結(jié)束語(yǔ)

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