軒 華,關(guān)瀟風(fēng),王薛苑
(鄭州大學(xué) 管理工程學(xué)院,河南 鄭州 450001)
近年來(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)行求解。
在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,pjsli
問(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)定義了變量取值范圍。
灰狼優(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]。
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í)間。
采用反向?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è)體作為最終初始灰狼種群。
若ω狼僅跟隨領(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ī)器加工速度。
精英保留策略會(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算法流程
為驗(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種算法,將種群規(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)生一組算例。
表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次的非支配解分布
研究了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ì)更加高效的智能算法等等。