胡 蓉,伍 星,毛劍琳,錢 斌

(1.昆明理工大學(xué)信息工程與自動化學(xué)院,云南昆明 650500;2.云南機(jī)電職業(yè)技術(shù)學(xué)院,云南昆明 650000;3.昆明理工大學(xué)機(jī)電工程學(xué)院,云南昆明 650500)

1 引言

綠色制造作為同時(shí)考慮環(huán)境和能耗的生產(chǎn)模式,是工業(yè)生產(chǎn)實(shí)現(xiàn)高質(zhì)量、可持續(xù)發(fā)展的重要環(huán)節(jié).近年,中國碳達(dá)峰、碳中和“雙碳”目標(biāo)的提出和推行,對我國能源及制造業(yè)在節(jié)能減排方面提出了更高要求.企業(yè)要在競爭激烈的市場中勝出,生產(chǎn)成本的有效控制是關(guān)鍵.如何對生產(chǎn)過程進(jìn)行優(yōu)化調(diào)度實(shí)現(xiàn)降本增效,已成為企業(yè)的生命線.此外,公司之間生產(chǎn)合作和企業(yè)兼并現(xiàn)象日益普遍,分布式制造已經(jīng)成為一種重要生產(chǎn)模式[1].在上述背景下,有必要深入開展綠色分布式生產(chǎn)調(diào)度方面的研究.

作業(yè)車間調(diào)度問題(job shop scheduling problem,JSSP)是工業(yè)生產(chǎn)中一類非常重要的問題.經(jīng)典JSSP的研究通常局限于工件在各機(jī)器或設(shè)備上只加工1次.然而,在鋼鐵生產(chǎn)、半導(dǎo)體制造等戰(zhàn)略性行業(yè)中,部分關(guān)鍵工件需在同一機(jī)器上處理多次(如鋼卷退火和晶圓加工)[2].這表明研究綠色分布式可重入作業(yè)車間調(diào)度問題(green distributed reentrant JSSP,GDRJSSP)的建模與求解,具有重要現(xiàn)實(shí)意義.在計(jì)算復(fù)雜性上,JSSP歸約于GDRJSSP,而JSSP屬于典型NP難問題,故GDRJSSP也為NP難問題.因此,研究該問題也具有顯著理論價(jià)值.

綠色生產(chǎn)調(diào)度的已有研究主要聚焦于單工廠或車間調(diào)度問題,包括綠色單機(jī)調(diào)度問題[1]、綠色并行機(jī)調(diào)度問題[3]、綠色流水車間調(diào)度問題[4]、綠色混合流水車間調(diào)度問題[5]、綠色作業(yè)車間調(diào)度問題[6]和綠色柔性作業(yè)車間調(diào)度問題[7].在分布式工廠方面,已有研究還較為有限,主要為綠色分布式流水車間調(diào)度問題[8]、綠色分布式裝配流水車間調(diào)度問題[9]、綠色分布式作業(yè)車間調(diào)度問題[10].對于GDRJSSP,尚無研究報(bào)道,故亟需對其開展研究.

生產(chǎn)調(diào)度問題多為NP難問題,具有非凸幾何結(jié)構(gòu),其主要求解算法包括運(yùn)籌學(xué)算法和智能優(yōu)化算法.運(yùn)籌學(xué)算法(如分枝定界、列生成、分枝定價(jià))追求獲取問題最優(yōu)解.然而,對于非凸優(yōu)化問題,至今還沒有多項(xiàng)式時(shí)間可獲取最優(yōu)解的通用算法.這使得運(yùn)籌學(xué)算法需遍歷或部分遍歷問題解空間,從而無法在較短時(shí)間內(nèi)得到較大規(guī)模問題的滿意解.智能優(yōu)化算法追求盡快獲取問題優(yōu)質(zhì)解,其特點(diǎn)在于可通過對解空間較少區(qū)域的搜索來實(shí)現(xiàn)對目標(biāo)值較廣且較優(yōu)區(qū)域的搜索[11].這使其能在較短時(shí)間內(nèi)獲取問題的優(yōu)質(zhì)解,從而成為目前求解各類復(fù)雜調(diào)度問題(包括文獻(xiàn)[1,3-10]的問題)的主要算法.

差分進(jìn)化(differential evolution,DE)算法將群體中個(gè)體間差異和競爭產(chǎn)生的群體智能用于優(yōu)化搜索方向,具有較強(qiáng)的全局搜索能力和內(nèi)在的并行搜索特性,被成功用于有效求解各種復(fù)雜優(yōu)化問題[12].DE的研究受到眾多學(xué)者的關(guān)注,已成功應(yīng)用于求解交通運(yùn)輸、電力系統(tǒng)、化工制藥等領(lǐng)域中的優(yōu)化問題求解.在生產(chǎn)調(diào)度問題求解方面,現(xiàn)有的有效DE均采用混合算法框架,即利用DE對問題解空間執(zhí)行全局搜索,同時(shí)根據(jù)問題特點(diǎn)加入合適的局部搜索,從而形成某種混合DE.譬如,Wang等[13]提出一種離散DE求解阻塞流水車間調(diào)度問題,其優(yōu)化目標(biāo)為最大完工時(shí)間最小.Wu等[14]針對分布式裝配柔性作業(yè)車間調(diào)度問題,設(shè)計(jì)結(jié)合模擬退火的混合DE進(jìn)行求解,以實(shí)現(xiàn)提前/延遲和總成本同時(shí)最小.對于GDRJSSP,目前沒有基于DE的求解算法研究,故本文設(shè)計(jì)混合DE進(jìn)行求解.

綜上,本文提出一種融入概率學(xué)習(xí)的混合DE(hybrid DE incorporated with probabilistic learning,HDEPL),用于求解優(yōu)化目標(biāo)為同時(shí)最小化總完工時(shí)間和總能耗的GDRJSSP.首先,分析問題特點(diǎn),設(shè)計(jì)編碼規(guī)則來確定搜索空間,并設(shè)計(jì)活動化解碼規(guī)則來提升解的質(zhì)量.其次,采用DE執(zhí)行全局搜索,同時(shí)加入基于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的多維概率模型合理學(xué)習(xí)和積累優(yōu)質(zhì)解(即當(dāng)前種群中的較優(yōu)解)的模式信息,提升算法驅(qū)動全局搜索較快探測或感知到解空間中優(yōu)質(zhì)解區(qū)域的能力.下一步,分析問題解的結(jié)構(gòu)特征,設(shè)計(jì)基于關(guān)鍵路徑的4種鄰域結(jié)構(gòu)來對當(dāng)前非劣解集中各非劣解執(zhí)行較深入的局部搜索,進(jìn)而利用基于非關(guān)鍵路徑的節(jié)能策略嘗試降低各非劣解對應(yīng)的總能耗.最后,將算法應(yīng)用于各種規(guī)模的測試問題進(jìn)行對比分析,驗(yàn)證了HDE-PL能夠有效求解GDRJSSP.

2 問題描述

2.1 GDRJSSP描述

GDRJSSP可描述為:考慮n個(gè)工件J={J1,···,Jn},分別分配到F個(gè)工廠上加工,每個(gè)工廠均有m臺加工機(jī)器M={M1,···,Mm},每臺機(jī)器存在s種可調(diào)節(jié)的速度檔位且對應(yīng)加工速度表示為V={v1,···,vs}.按工藝要求每個(gè)工件需要重復(fù)加工L次,即工件Ji的第j道工序用Oi,j來表示,工件Ji完成加工工序{Oi,1,···,Oi,m×L}的數(shù)量是m×L,相應(yīng)的基本加工時(shí)間為pi,j.由于機(jī)器的加工速度可調(diào)整,當(dāng)機(jī)器以速度vz加工工序Oi,j時(shí),實(shí)際加工時(shí)間為pi,j,z=pi,j/vz.設(shè)工序Oi,j的開工時(shí)間為Si,j,完工時(shí)間為Ci,j,工廠k的完工時(shí)間為Ck,工廠k中機(jī)器Mj的開工時(shí)間為Sj,k.當(dāng)機(jī)器Mj以速度vz加工時(shí),單位時(shí)間能耗為EPj,z.當(dāng)機(jī)器Mj上未加工工件時(shí),則該機(jī)器處于待機(jī)狀態(tài),其單位時(shí)間能耗為EIj.令π={π1,···,πn×m×L}為整體的工序序列,為工廠f中的工序序列,nf為分配到工廠f中的工件數(shù),其中

同時(shí),生產(chǎn)環(huán)境設(shè)定為:在零時(shí)刻即可加工,即工件到達(dá)時(shí)間設(shè)置為零;機(jī)器間緩沖區(qū)大小不受限制;機(jī)器可采用數(shù)個(gè)檔位分別進(jìn)行勻速加工,每臺機(jī)器只能完成一道工序的加工;每道工序需在前一道工序加工結(jié)束后才可加工;不能打斷工序在機(jī)器上的加工.優(yōu)化或調(diào)度目標(biāo)是確定工件在工廠上的分配情況、各機(jī)器上工件工序在加工順序以及機(jī)器速度設(shè)置,使得生產(chǎn)效率指標(biāo)Cmax和總能耗指標(biāo)(total energy consumption,TEC)達(dá)到最優(yōu).基于以上描述,建立如下數(shù)學(xué)模型:

其中: 式(1)為優(yōu)化目標(biāo),即要求最大完工時(shí)間和總能耗同時(shí)最小;式(2)保證每個(gè)工件都能唯一分配到一個(gè)工廠中;式(3)-(4)保證同一工件的所有操作都必須分配到同一工廠中且工件的操作滿足工藝約束;每臺機(jī)器的首個(gè)加工工件由式(5)確定;工件在機(jī)器上加工順序的唯一性由式(6)保證;式(7)-(8)限定任意時(shí)刻一個(gè)工件最多只能在一臺機(jī)器上處理;式(9)限定一臺機(jī)器最多只能同時(shí)處理一個(gè)工件,其中Q為極大的正數(shù);式(10)確定每臺機(jī)器的開始加工時(shí)間;式(11)確定每個(gè)工廠的完工時(shí)間;式(12)-(13)確定最大完工時(shí)間Cmax;式(14)限定任意時(shí)刻一個(gè)操作僅能在同一速度下進(jìn)行處理;式(15)計(jì)算加工狀態(tài);式(16)計(jì)算待機(jī)狀態(tài)的總能耗,其中ψj為機(jī)器Mj的能耗系數(shù);式(17)計(jì)算加工過程中的總能量消耗.此外,設(shè)置二進(jìn)制決策變量xr,i,j,k,yi,t,j和hi,j,z.若工件j為工廠k中機(jī)器Mj上加工工件r的后繼工件,置xr,i,j,k=1,否則xr,i,j,k=0;若工件i在機(jī)器Mt上完工后繼續(xù)在機(jī)器Mj上加工,置yi,t,j=1,否則yi,t,j=0;若工件i的第j個(gè)操作Oi,j以速度vz處理,置hi,j,z=1,否則hi,j,z=0.

2.2 Pareto最優(yōu)

GDRJSSP需同時(shí)考慮最小化生產(chǎn)效率指標(biāo)及能耗指標(biāo),屬于多目標(biāo)優(yōu)化問題.該類問題需通過支配關(guān)系來確定最優(yōu)解集.關(guān)于多目標(biāo)優(yōu)化中的支配、非劣解、非劣解集、Pareto最優(yōu)解集等概念,可參見文獻(xiàn)[15].在求解NP難的多目標(biāo)優(yōu)化問題(如GDRJSSP)時(shí),智能優(yōu)化算法追求在較短時(shí)間內(nèi)獲取盡量逼近Pareto最優(yōu)解集的優(yōu)質(zhì)非劣解集.

3 融入概率學(xué)習(xí)的混合DE算法(HDE-PL)

GDRJSSP需將工件分配給不同的工廠并確定各工廠內(nèi)的工件加工順序,同時(shí)還要確定各工廠內(nèi)機(jī)器的加工速度.因此,采用三元組(π,A,V)來表示HDE-PL的個(gè)體(即問題的可行解),其中π為工序序列,A為工廠分配向量,V為加工速度矩陣.

智能優(yōu)化算法均是采用相應(yīng)機(jī)制不斷生成新個(gè)體或新解來實(shí)現(xiàn)搜索的.在HDE-PL的全局搜索部分,采用DE進(jìn)化機(jī)制改變當(dāng)前個(gè)體中的π來生成新個(gè)體,并利用概率學(xué)習(xí)模型采樣機(jī)制生成與當(dāng)前個(gè)體中的π和A均不同的新個(gè)體,同時(shí)用較優(yōu)新個(gè)體替換舊個(gè)體并更新非劣解集,從而逐步引導(dǎo)搜索前往問題解空間中存在優(yōu)質(zhì)解的區(qū)域.在HDE-PL的局部搜索部分,先采用多鄰域變換機(jī)制嘗試改進(jìn)當(dāng)前非劣解集中每個(gè)解(對應(yīng)存在優(yōu)質(zhì)解的區(qū)域)中的π,再利用調(diào)速節(jié)能機(jī)制嘗試改進(jìn)這些解中的V,從而生成更優(yōu)的新個(gè)體.HDE-PL正是通過上述機(jī)制不斷合理變換π,A和V的取值,從而實(shí)現(xiàn)對GDRJSSP解空間的搜索.

3.1 編碼

工序序列π的編碼方式為基于工件的工序編碼,即π={π1,···,πn×m×L}(實(shí)例見表1最后1行).

表1 調(diào)度解的表達(dá)Table 1 Illustration of scheduling solution

在采用DE生成新個(gè)體時(shí),當(dāng)前個(gè)體中的A和V保持不變,只對π進(jìn)行改變.然而,標(biāo)準(zhǔn)DE的個(gè)體為實(shí)數(shù)向量,只能在連續(xù)域空間內(nèi)進(jìn)行搜索.為使DE 可求解GDRJSSP,利用可重入最小值排序(reentrant smallest order value,RSOV)規(guī)則[16],將DE 中的第i個(gè)實(shí)數(shù)向量Xi=[xi,1,···,xi,n×m×L]轉(zhuǎn)換為工件的工序或操作序列πi=[πi,1,···,πi,n×m×L].根據(jù)RSOV規(guī)則,首先將Xi=[xi,1,···,xi,n×m×L]按升序排列后得到中間序列φi=[φi,1,···,φi,n×m×L],再將中間序列φi映射為工序編碼序列πi.這里πi,k=「(φi,k-1)/n×m×L」+1,其中「*」為取整操作,如「3.54」=3.表1 給出n=2,m=1,L=3時(shí)Xi到πi的轉(zhuǎn)換示例.

此外,工廠分配向量A和加工速度矩陣V的編碼為:A中第i個(gè)元素ai表示工件i分配至工廠ai加工,V中第i行第j列的元素vi,j表示工序Oi,j的機(jī)器加工檔位.圖1為n=5,m=3,L=2,F=2,A=[1,2,1,2,2]時(shí)一個(gè)調(diào)度解的甘特圖.

圖1 GDRJSSP調(diào)度解的甘特圖Fig.1 Gantt chart of GDRJSSP’s scheduling solution

3.2 解碼

傳統(tǒng)JSSP的解碼規(guī)則主要有無延遲解碼、半活動化解碼、活動化解碼.對于GDRJSSP的解,本文拓展現(xiàn)有的單工廠活動化解碼規(guī)則并用于對其解碼,以盡量縮減工序完工時(shí)間,具體步驟如下:

步驟1為使各工廠中工序的完工時(shí)間整體較小,每個(gè)工件在分配時(shí)優(yōu)先分配至當(dāng)前完工時(shí)間最小的工廠,依此規(guī)則確定工廠分配向量A.根據(jù)A將n個(gè)工件{J1,J2,···,Jn}依次分配到不同的工廠中.

步驟2各工廠內(nèi)每臺機(jī)器上的工序加工順序確定后,計(jì)算每個(gè)工序加工的開始時(shí)間和完工時(shí)間.

步驟3根據(jù)式(13)(17)分別計(jì)算問題解π的最大完工時(shí)間Cmax和總能耗指標(biāo)TEC.

3.3 概率學(xué)習(xí)模型

對于GDRJSSP的解(π,A,V),工序塊定義為工序序列π中連續(xù)相鄰的兩道工序.顯然,π由不同位置上的工序塊所組成.為能有效學(xué)習(xí)優(yōu)質(zhì)解中π內(nèi)部工序塊的分布信息,設(shè)計(jì)統(tǒng)計(jì)工序塊出現(xiàn)頻次的貝葉斯網(wǎng)絡(luò)(見圖2),并以此構(gòu)建工序塊分布概率學(xué)習(xí)模型.通過采樣該模型生成新種群來實(shí)現(xiàn)與DE不同的搜索,可豐富HDE-PL的全局搜索行為并增強(qiáng)其引導(dǎo)全局搜索到達(dá)優(yōu)質(zhì)解區(qū)域的能力.

圖2 N-1層貝葉斯網(wǎng)絡(luò)(工序塊頻次統(tǒng)計(jì)模型)Fig.2 N-1 layer Bayesian network(statistical model of process block frequency)

3.3.1 頻次統(tǒng)計(jì)矩陣

3.3.2 概率學(xué)習(xí)模型

為{BPop1,···,BPopG}的個(gè)體中第x位置和第x+1位置上工序塊的累計(jì)概率分布,

3.4 全局搜索

如前所言,全局搜索靠DE進(jìn)化機(jī)制和概率學(xué)習(xí)模型采樣機(jī)制分別生成新種群來實(shí)現(xiàn).DE生成新種群的過程見第2.6節(jié)的HDE-PL算法流程.概率學(xué)習(xí)模型采樣生成新種群的過程如下.

3.5 局部搜索

GDRJSSP屬于復(fù)雜的多目標(biāo)組合優(yōu)化問題.由于不同優(yōu)化目標(biāo)間的相互制約,優(yōu)質(zhì)非劣解通常聚集在龐大解空間中接近底部的不同區(qū)域,這增大了搜索難度.為提升算法性能,設(shè)計(jì)如下局部搜索對優(yōu)質(zhì)解區(qū)域進(jìn)行更加深入細(xì)致的搜索.

GDRJSSP的關(guān)鍵路徑為各工廠的關(guān)鍵路徑中最長的一條.以第3.1節(jié)中圖1和本節(jié)圖3為例,工廠1和工廠2的關(guān)鍵路徑分別為各自工廠中紅線所連工序.由于工廠1的關(guān)鍵路徑最長,故整個(gè)問題的關(guān)鍵路徑為工廠1 的關(guān)鍵路徑.結(jié)合甘特圖分析GDRJSSP的解內(nèi)部結(jié)構(gòu)可知,該問題任何解的最大完工時(shí)間Cmax等于其關(guān)鍵路徑的長度,故調(diào)整關(guān)鍵路徑上的工序有較大概率能減小Cmax.因此,設(shè)計(jì)基于關(guān)鍵路徑的4種鄰域搜索(對應(yīng)4種鄰域結(jié)構(gòu)),對每代種群中的部分個(gè)體分別執(zhí)行由這4種鄰域結(jié)構(gòu)構(gòu)成的變鄰域局部搜索,以盡量減小這些個(gè)體的Cmax.進(jìn)而,設(shè)計(jì)非關(guān)鍵路徑的節(jié)能策略,嘗試降低執(zhí)行過局部搜索的個(gè)體的總能耗TEC.

圖3 關(guān)鍵路徑和調(diào)速節(jié)能Fig.3 Critical path and speed regulation for saving energy

3.5.1 多鄰域貪婪搜索

基于關(guān)鍵路徑的4種鄰域搜索如下:

1) 關(guān)鍵工廠內(nèi)Interchange: 隨機(jī)選擇1個(gè)關(guān)鍵工序,并將其與該工廠內(nèi)所有的非關(guān)鍵工序逐一進(jìn)行交換,形成個(gè)鄰域,并輸出最好鄰域.

2) 關(guān)鍵工廠內(nèi)Insert: 隨機(jī)選擇1個(gè)關(guān)鍵工序,并將其分別插入到該工廠中每個(gè)非關(guān)鍵工序之前或之后,形成個(gè)鄰域,并輸出最好鄰域.

3) 工廠間Interchange: 隨機(jī)選擇1個(gè)關(guān)鍵工序,并將其與各非關(guān)鍵工廠中所有的工序逐一進(jìn)行交換,形成個(gè)鄰域,并輸出最好鄰域.

4) 工廠間Insert: 隨機(jī)選擇1個(gè)關(guān)鍵工序,并將其分別插入各非關(guān)鍵工廠中每個(gè)工序之前或之后,形成個(gè)鄰域,并輸出最好鄰域.

基于上述定義,設(shè)計(jì)如下變鄰域搜索.

步驟1為當(dāng)前非劣解集中的每個(gè)個(gè)體或解確定1條關(guān)鍵路徑,若有多條則隨機(jī)確定1條.

步驟2逐一選擇當(dāng)前非劣解集中的解,并對其執(zhí)行上述4種鄰域搜索.每執(zhí)行完1種鄰域搜索后,判斷新解(即輸出鄰域)是否支配舊解.如果是,舊解將被新解所取代,確定新解關(guān)鍵路徑后對新解從剛執(zhí)行過的鄰域搜索開始,繼續(xù)執(zhí)行剩余的鄰域搜索;若兩個(gè)解互不支配,則將新解直接加入非劣解集,繼續(xù)對舊解執(zhí)行剩余的鄰域搜索;若新解被舊解支配,則繼續(xù)對舊解執(zhí)行剩余的鄰域搜索.

步驟3非劣解集中解的數(shù)量超過ps時(shí),則刪除擁擠距離較小的解[17],保持非劣解集大小為ps.

3.5.2 基于非關(guān)鍵路徑工序降速的節(jié)能策略

對于GDRJSSP的任意解,通過保持各工廠中關(guān)鍵路徑上工序的加工速度不變,對非關(guān)鍵路徑上工序的加工速度進(jìn)行降檔調(diào)節(jié),有可能在最大完工時(shí)間Cmax不變的前提下,實(shí)現(xiàn)總能耗的降低.基于這一問題特點(diǎn),對執(zhí)行變鄰域搜索后的非劣解集中每個(gè)非劣解執(zhí)行如下的調(diào)速節(jié)能操作:

步驟1確定各工廠中的關(guān)鍵路徑.

步驟2判斷各工廠的非關(guān)鍵路徑上每道工序是否處于最低加工速度的檔位.若是則轉(zhuǎn)回步驟2繼續(xù)判斷下一道工序;若否則進(jìn)行下一步.

步驟3將該工序的當(dāng)前加工速度降低一檔,并判斷是否影響關(guān)鍵路徑.若是則保持檔位不變,轉(zhuǎn)到步驟2繼續(xù)判斷下一道工序;若否則降低一檔,轉(zhuǎn)到步驟2繼續(xù)判斷下一道工序.

執(zhí)行上述步驟對非關(guān)鍵路徑上的所有工序完成降檔嘗試后,更新該非劣解的加工速度矩陣V.

3.6 HDE-PL算法流程

從以上算法流程可知,在HDE-PL的迭代搜索過程中,非劣解集TΩ在步驟10由DE和概率學(xué)習(xí)模型共同引導(dǎo)的全局搜索(步驟3-9)進(jìn)行更新,同時(shí)在步驟12由結(jié)合變鄰域搜索和調(diào)速節(jié)能操作的局部搜索進(jìn)行更新.由于全局和局部搜索均得以加強(qiáng),HDE-PL可實(shí)現(xiàn)對GDRJSSP解空間范圍較廣且具有一定深度的搜索.

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

4.1 實(shí)驗(yàn)設(shè)置

選擇FT01,FT10,FT20,LA01,LA06,LA11,LA16,LA21,LA26,LA31這10個(gè)不同規(guī)模的JSSP標(biāo)準(zhǔn)測試算例,擴(kuò)展得到適用于GDRJSSP的測試集(拓展算例命名為標(biāo)準(zhǔn)測試算例名稱前加“E-”,見表2).在擴(kuò)展測試集中,所有工件的重入次數(shù)設(shè)置為2次,加工階段機(jī)器速度設(shè)置為5 個(gè)可調(diào)檔位(對應(yīng)加工速度為{1,1.3,1.55,1.75,2.10}),機(jī)器能耗系數(shù)設(shè)置為ψj=4,機(jī)器加工與待機(jī)能耗分別設(shè)置為EPj,z=4×vz2和EIj=1.所有算法采用Delphi XE10編程,運(yùn)行環(huán)境為16 GB內(nèi)存、i7處理器(3.20 GHz)的PC.采用如下指標(biāo)比較算法性能:

表2 NSGA-II,MOABC,IMMOGLS和HDE-PL的計(jì)算結(jié)果Table 2 Calculation results of NSGA-II,MOABC,IMMOGLS and HDE-PL

1) 距離指標(biāo)DIR,可度量非劣解集Ω′中的元素相對于參考集Ω*的距離,即

其中: 解x ∈Ω′與解y ∈Ω*在歸一化優(yōu)化目標(biāo)空間中的距離表示為d(x,y)[18].d(x,y)按式(29)計(jì)算:

式中:fi為第i個(gè)優(yōu)化目標(biāo),分別為參考集Ω*中fi的最小和最大值.Ω*由所有比較算法得到的非劣解集合并構(gòu)成.

2) 非劣解占比指標(biāo)ρr,可度量由算法獲得的非劣解集Ω′在Ω*中的比例.

DIR(Ω′)越小則表明算法獲得的非劣解集更接近Pareto最優(yōu)解集,而ρr越大則表明算法性能越強(qiáng).

本文將HDE-PL 與非劣排序遺傳算法(NSGAII)[17]、多目標(biāo)人工蜂群算法(MOABC)[19]、改進(jìn)多目標(biāo)遺傳局部搜索算法(IMMOGLS)[18]這3種高效多目標(biāo)優(yōu)化算法進(jìn)行比較.多目標(biāo)優(yōu)化算法NSGA-II在離散和連續(xù)優(yōu)化領(lǐng)域均應(yīng)用廣泛.MOABC在傳統(tǒng)人工蜂群算法中加入數(shù)種有效局部搜索算子和交叉操作算子,可高效求解綠色多目標(biāo)分布式作業(yè)車間調(diào)度問題.IMMOGLS采用隨機(jī)加權(quán)和的方式處理多個(gè)優(yōu)化目標(biāo),是公認(rèn)的求解多目標(biāo)流水車間調(diào)度問題的高效算法.在算法性能比較實(shí)驗(yàn)中,各算法運(yùn)行時(shí)間均設(shè)置為f×n×m×25 ms,并都獨(dú)立重復(fù)運(yùn)行20次.評價(jià)指標(biāo)DIR中的參考集Ω*由以上4種比較算法每次運(yùn)行結(jié)束時(shí)輸出的非劣解集合并得到.

4.2 仿真結(jié)果與比較

HDE-PL的關(guān)鍵參數(shù)為:種群規(guī)模ps、優(yōu)勢子種群比率φ、學(xué)習(xí)速率r1和r2、變異系數(shù)Fs、交叉概率CR.采用DOE實(shí)驗(yàn)設(shè)計(jì)法分析參數(shù)對HDE-PL全局搜索部分性能的影響.每個(gè)參數(shù)均選取5個(gè)不同水平值.對于每組參數(shù),算法均運(yùn)行10次,終止條件為f×n×m×25 ms.以算法在不同參數(shù)組合下各規(guī)模算例的ρr平均值作為評價(jià)指標(biāo),可得如圖4 所示的參數(shù)響應(yīng)圖,故HDE-PL 的推薦參數(shù)組合為:ps=30,φ=0.3,r1=0.2,r2=0.1,Fs=0.5,CR=0.2.類似地,可得NSGA-II的推薦參數(shù)組合為:種群規(guī)模ps=30,變異概率pm=0.1,交叉概率pc=0.8;MOABC的推薦參數(shù)組合為:種群規(guī)模ps=30,放棄解極限La=50;IMMOGLS的推薦參數(shù)組合為:種群規(guī)模ps=30,精英個(gè)體數(shù)Ne=10,局部搜索概率pLS=0.8.

圖4 HDE-PL各參數(shù)響應(yīng)趨勢圖Fig.4 Response trend graph of HDE-PL’s various parameters

各算法在評價(jià)指標(biāo)DIR和ρr下的測試結(jié)果如表2所示,其中最好值以粗體表示.由表2可知,HDE-PL的DIR值在所有問題上小于其他3種算法的DIR值,同時(shí)HDE-PL的ρr值也明顯大于其他3種算法的ρr值.這表明HDE_ PL獲得的非劣解集整體更接近于參考集,且獲得的優(yōu)質(zhì)非劣解數(shù)量更多.為直觀表現(xiàn)算法間的性能差異,圖5給出這4種算法在算例E_ LA16(F=2)上的非劣解占比指標(biāo)ρr對應(yīng)的小提琴圖(在其他算例上可得類似的圖).從圖5也可看出HDE PL在統(tǒng)計(jì)意義上顯著占優(yōu).

圖5 3種算法求解ELA16(F=2)算例的非劣解分布圖Fig.5 Distribution of non-inferior via three algorithms for solving the E-LA16(F=2)

相對于NSGA-II 僅靠全局搜索驅(qū)動算法尋優(yōu),HDE-PL采用全局搜索和局部搜索結(jié)合的混合模式,可以更好兼顧搜索的寬度和深度.此外,雖然MOABC和IM-MOGLS兩者也是包含全局搜索和局部搜索的混合算法,但是HDE PL的全局搜索部分結(jié)合分散搜索能力強(qiáng)的DE和引導(dǎo)性強(qiáng)的概率學(xué)習(xí)模型,有助于在更寬廣的范圍發(fā)現(xiàn)較多的優(yōu)質(zhì)解區(qū)域,同時(shí)在局部搜索部分采用基于關(guān)鍵路徑的變鄰域搜索,以便于執(zhí)行更為集中深入的挖掘.因此,HDE PL具有更強(qiáng)的搜索引擎.

5 結(jié)語

本文在可重入作業(yè)車間調(diào)度問題基礎(chǔ)上,進(jìn)一步考慮分布式工廠場景和節(jié)能減排需求,確立優(yōu)化目標(biāo)為總完工時(shí)間和總能耗同時(shí)最小,進(jìn)而建立綠色分布式可重入作業(yè)車間調(diào)度問題(GDRJSSP)模型.針對GDRJSSP,提出一種融入概率學(xué)習(xí)的混合DE(HDEPL)進(jìn)行求解.在HDE-PL的全局搜索部分,設(shè)計(jì)DE與多維概率學(xué)習(xí)結(jié)合的協(xié)作搜索框架,有利于提升算法引導(dǎo)全局搜索到達(dá)解空間中優(yōu)質(zhì)解區(qū)域的能力.在HDE-PL的局部搜索部分,為實(shí)現(xiàn)對優(yōu)質(zhì)解區(qū)域較深入的細(xì)致搜索,設(shè)計(jì)相應(yīng)的多鄰域局部搜索.同時(shí),為進(jìn)一步降低總能耗,設(shè)計(jì)非關(guān)鍵路徑工序加工降速的節(jié)能策略.仿真實(shí)驗(yàn)驗(yàn)證了HDE-PL的有效性.未來工作為設(shè)計(jì)高效HDE-PL 求解GDRJSSP 和物流集成的調(diào)度問題.