史雙元 熊禾根

武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院,武漢,430081

0 引言

制造系統(tǒng)優(yōu)化調(diào)度是實(shí)現(xiàn)制造資源優(yōu)化利用和提高生產(chǎn)運(yùn)作效率的重要和關(guān)鍵技術(shù)之一。在諸多的制造系統(tǒng)優(yōu)化調(diào)度目標(biāo)中,對(duì)于面向訂單型制造企業(yè),滿足客戶訂單的交貨期是最重要的目標(biāo)之一。然而,由于企業(yè)內(nèi)部生產(chǎn)能力相對(duì)穩(wěn)定與外部訂單任務(wù)隨機(jī)性之間的矛盾,當(dāng)制造系統(tǒng)負(fù)荷率較高時(shí),常規(guī)工作時(shí)間的生產(chǎn)作業(yè)可能導(dǎo)致某些訂單的拖期交貨,進(jìn)而造成因拖期懲罰而帶來的經(jīng)濟(jì)損失和影響企業(yè)商譽(yù)。為了盡可能避免上述不利情況的發(fā)生,企業(yè)管理者通常在采用生產(chǎn)優(yōu)化調(diào)度的同時(shí),通過加班作業(yè)的方式擴(kuò)充常規(guī)生產(chǎn)能力,從而盡力保證訂單無拖期交貨。顯然,一方面,加班作業(yè)可以擴(kuò)充生產(chǎn)能力,但另一方面也會(huì)產(chǎn)生額外的生產(chǎn)費(fèi)用。如若加班作業(yè)在時(shí)間和資源對(duì)象上安排不恰當(dāng)不合理,可能不但無法有效和針對(duì)性地提前訂單的完成時(shí)間,還會(huì)增加企業(yè)生產(chǎn)成本。如何將加班作業(yè)與優(yōu)化調(diào)度進(jìn)行融合,從而實(shí)現(xiàn)企業(yè)損失的最小化和效益的最大化,是面向訂單型企業(yè)生產(chǎn)運(yùn)作管理亟待解決的重要問題。為此,本文提出了一種考慮加班作業(yè)的多目標(biāo)無拖期作業(yè)車間調(diào)度問題(multi-objective no-tardiness job shop scheduling problem with overtime consideration,MONTJSSP/O),以期通過問題的研究,在生產(chǎn)負(fù)荷較重但處于有限范圍內(nèi)的狀況下,充分和優(yōu)化地利用加班作業(yè),從而實(shí)現(xiàn)訂單的無拖期交貨。

MONTJSSP/O問題的關(guān)鍵特征在于無拖期交貨和考慮加班作業(yè)。在大量與拖期有關(guān)的作業(yè)車間調(diào)度問題研究中,絕大多數(shù)研究對(duì)問題進(jìn)行數(shù)學(xué)建模時(shí),將交貨期考慮在優(yōu)化的目標(biāo)函數(shù)中,如最小化(加權(quán))總拖期和/或總提前、最小化最大拖期、最小化(加權(quán))拖期工件數(shù)量等[1-5]。這些研究只是降低了拖期程度,并不能保證訂單的無拖期交付。現(xiàn)有研究中,在作業(yè)車間調(diào)度問題中考慮無拖期約束的研究尚未見到,與無拖期相關(guān)的調(diào)度問題研究報(bào)道也比較少,且基本是針對(duì)單機(jī)調(diào)度問題[6-8]的。CHAND等[6]針對(duì)無拖期單機(jī)調(diào)度問題,以總加權(quán)提前量為優(yōu)化目標(biāo),設(shè)計(jì)了精確算法和近似方法進(jìn)行求解;ZHAO等[7]分析了具有劣化作業(yè)(即工件加工時(shí)間隨著開工時(shí)間線性遞減)的單機(jī)調(diào)度問題,在滿足無拖期工件的前提下,提出了以最小化總提前懲罰為目標(biāo)的優(yōu)化算法。加班作業(yè)是制造企業(yè)應(yīng)對(duì)客戶需求激增常采用的一種短期擴(kuò)大產(chǎn)能的方法[9-10]。查閱已有文獻(xiàn)發(fā)現(xiàn),針對(duì)作業(yè)車間調(diào)度問題,通過加班作業(yè)擴(kuò)大產(chǎn)能的研究不是很多。ZHANG等[11]通過加班作業(yè)提高產(chǎn)能,以單機(jī)調(diào)度問題研究了無拖期交付的問題。HOLLOWAY等[9]提出了一種考慮工件交貨期和加班作業(yè)的靜態(tài)和動(dòng)態(tài)作業(yè)車間調(diào)度問題解決方法,以找出加班與總拖期之間的關(guān)系。YODA等[12]通過在每個(gè)常規(guī)班次中延長(zhǎng)加班時(shí)間來調(diào)整產(chǎn)能,并以最小化總拖期和總加班時(shí)間為優(yōu)化目標(biāo)。上述文獻(xiàn)或者不是基于作業(yè)車間調(diào)度問題進(jìn)行的研究,或者不是真正意義上的無拖期交付。

問題求解方面,本文提出了基于精英保留策略的非支配排序金鷹優(yōu)化算法(elitist non-dominated sorting golden eagle optimizer,NSGEO)。金鷹優(yōu)化算法(golden eagle optimizer,GEO)是一種基于群體的新型智能優(yōu)化算法[13]。自GEO算法被提出以來,已被應(yīng)用于諸多領(lǐng)域[14-17]。針對(duì)多目標(biāo)問題,MOHAMMADI-BALANI等[13]擴(kuò)展單目標(biāo)GEO算法提出了多目標(biāo)金鷹優(yōu)化算法,在10個(gè)標(biāo)桿測(cè)試函數(shù)上對(duì)算法性能進(jìn)行了測(cè)試和驗(yàn)證,結(jié)果表明所提算法的性能優(yōu)于其他用于對(duì)比的常見多目標(biāo)算法(包括多目標(biāo)灰狼算法、帶精英保留策略的非支配排序遺傳算法、多目標(biāo)粒子群算法、多目標(biāo)樽海鞘群算法)。從上述文獻(xiàn)中可以看出,多目標(biāo)金鷹優(yōu)化算法在求解多目標(biāo)優(yōu)化問題時(shí)能表現(xiàn)出較好的性能。

綜上所述,本文研究的創(chuàng)新點(diǎn)主要體現(xiàn)在:①已有拖期相關(guān)作業(yè)車間調(diào)度問題研究主要將拖期作為目標(biāo)函數(shù),以實(shí)現(xiàn)訂單拖期的最小化,本研究將訂單無拖期交付作為問題約束,構(gòu)建了相應(yīng)的數(shù)學(xué)規(guī)劃模型;②在調(diào)度時(shí)間域上設(shè)置加班時(shí)間區(qū)間,以區(qū)別常規(guī)工作時(shí)間,進(jìn)而采用加班作業(yè)擴(kuò)大常規(guī)生產(chǎn)能力,通過優(yōu)化調(diào)度實(shí)現(xiàn)訂單無拖期交付;③關(guān)于多目標(biāo)金鷹優(yōu)化算法的研究主要側(cè)重于連續(xù)多目標(biāo)優(yōu)化問題的求解,本研究通過有效的編碼和解碼設(shè)計(jì)將其用于求解無拖期作業(yè)車間調(diào)度組合優(yōu)化問題,并通過仿真調(diào)度實(shí)驗(yàn)驗(yàn)證了算法的有效性和優(yōu)越性能。

1 MONTJSSP/O問題描述與建模

1.1 MONTJSSP/O問題描述

所提MONTJSSP/O問題可描述如下:有n個(gè)獨(dú)立的待加工工件和m臺(tái)可用機(jī)器;每個(gè)工件都有若干道具有工藝約束的工序,每道工序需要在一臺(tái)事先確定的機(jī)器上加工,且加工時(shí)間已知;每個(gè)工件都有嚴(yán)格的交貨期;在整個(gè)計(jì)劃時(shí)間區(qū)間內(nèi),除了常規(guī)的工作時(shí)間外,還有一些可拓展使用的時(shí)間片段(加班時(shí)間);若加班時(shí)間被利用,則將產(chǎn)生額外的生產(chǎn)成本;工件交貨期不能處于加班時(shí)間區(qū)間。問題求解目標(biāo)是優(yōu)化安排加班時(shí)間,確定各工序的加工順序和開工時(shí)間,從而使完成所有工件的工期和總加班時(shí)間最小。

此外,MONTJSSP/O問題還遵從以下假設(shè)條件:①所有工件和機(jī)器零時(shí)刻可用;②不單獨(dú)考慮裝設(shè)時(shí)間和轉(zhuǎn)序時(shí)間;③同一時(shí)刻下,每臺(tái)機(jī)器只能加工一個(gè)工件,每個(gè)工件只能被一臺(tái)機(jī)器加工;④工件的加工過程不允許被中斷,即不允許工時(shí)拆分,不允許被搶占;⑤工件間相互獨(dú)立,且不存在優(yōu)先級(jí)關(guān)系;⑥不考慮機(jī)器故障、訂單變化和急件插入等動(dòng)態(tài)事件;⑦所有加班時(shí)間區(qū)間內(nèi)的單位時(shí)間加班成本相同;⑧工件的交貨期設(shè)置合理,考慮加班作業(yè)情況下不至于絕對(duì)超負(fù)荷。其中,假設(shè)①～⑥是研究作業(yè)車間調(diào)度問題的基本假設(shè)[1-4,18];假設(shè)⑦主要是為了簡(jiǎn)化加班成本的計(jì)算;假設(shè)⑧約定了本研究適用范圍,如果交貨期設(shè)置不合理,則存在不使用加班作業(yè)也能實(shí)現(xiàn)無拖期交付,或者使用所有加班時(shí)間也無法實(shí)現(xiàn)無拖期交付的情況。

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

為了方便建立問題數(shù)學(xué)模型,定義本文中用到的數(shù)學(xué)符號(hào)如表1所示。

表1 數(shù)學(xué)符號(hào)定義

基于表1所示的符號(hào)定義,MONTJSSP/O問題的數(shù)學(xué)模型可表示如下:

(1)

minf2=Cmax

(2)

滿足約束如下:

Ci-di≤0i=1,2,…,n

(3)

Si,j+Pi,j≤Si,j+1

(4)

i=1,2,…,nj=1,2,…,ni-1

Si,j≥0i=1,2,…,nj=1,2,…,ni

(5)

Si,j+Pi,j=Ci,j

(6)

i=1,2,…,nj=1,2,…,ni

(7)

i=1,2,…,nj=1,2,…,ni

(8)

i=1,2,…,nj=1,2,…,ni

(9)

i=1,2,…,nj=1,2,…,ni

Si,j,k+Pi,j,k≤Sh,l,k+A(1-zi,j,h,l,k)

(10)

i,h=1,2,…,nj,l=1,2,…,ni

k=1,2,…,m

其中,式(1)和式(2)表示兩個(gè)目標(biāo)函數(shù),分別為最小化總加班時(shí)間和最小化最大完工時(shí)間;式(3)定義無拖期約束;式(4)和式(5)約束一個(gè)工件的工序只能在它的緊前工序加工完成后才能開始加工,且開工時(shí)間須在零時(shí)刻以后;式(6)表示工序一旦開工就不能被中斷;式(7)和式(8)表示工序可在一個(gè)或多個(gè)時(shí)間區(qū)間內(nèi)進(jìn)行加工,且加工時(shí)間等于各時(shí)間區(qū)間內(nèi)花費(fèi)時(shí)間的總和;式(9)和式(10)約束一道工序只能在一臺(tái)機(jī)器上加工,且一臺(tái)機(jī)器同時(shí)只能加工一道工序。

2 算法設(shè)計(jì)

與傳統(tǒng)作業(yè)車間調(diào)度問題相比,MONTJSSP/O具有更大的求解難度,主要體現(xiàn)在:①增加了無拖期約束,提高了獲得可行解的難度;②增加了加班時(shí)間的優(yōu)化使用決策。本文以期通過對(duì)基本多目標(biāo)金鷹優(yōu)化算法[13]進(jìn)行適應(yīng)性改造來有效求解MONTJSSP/O問題并獲得優(yōu)越性能。

基于精英保留策略的非支配排序金鷹優(yōu)化算法(NSGEO)對(duì)基本多目標(biāo)金鷹優(yōu)化算法進(jìn)行了如下改進(jìn):①采用離散編碼方式,以實(shí)現(xiàn)金鷹優(yōu)化算法連續(xù)空間至MONTJSSP/O離散解空間的映射;②采用兩階段解碼方案,以增加滿足無拖期約束可行解的數(shù)量,并盡可能減少最大完工時(shí)間和總加班時(shí)間;③嵌入基于精英保留策略的非支配排序選擇算子,以加速算法的收斂速度和提高解質(zhì)量;④引入自適應(yīng)新個(gè)體生成策略,以均衡算法的全局搜索能力和局部尋優(yōu)能力。NSGEO算法的偽代碼如算法1所示。

算法1 NSGEO算法偽代碼輸入:初始種群Pinit;種群規(guī)模Fpop;最大迭代次數(shù)Imax;攻擊傾向參數(shù)[p(0)a,pmaxa];巡航傾向參數(shù)[p(0)c,pmaxc]。輸出:Pareto最優(yōu)解集(Pbest)。1 設(shè)置當(dāng)前迭代次數(shù)g=0;2 for g in Imax do3 設(shè)置當(dāng)前種群個(gè)體序號(hào)φ=0;4 采用兩階段解碼方案計(jì)算所有個(gè)體的適應(yīng)度值;5 對(duì)所有個(gè)體按適應(yīng)度值進(jìn)行非支配排序;6 for φ in Fpop do7 if第φ個(gè)個(gè)體為精英個(gè)體then8 保留該個(gè)體不變;9 else10 計(jì)算攻擊概率pa和巡航概率pc;11 if pc>pa then ∥ exploration phase12 使用交叉和變異組合操作生成新個(gè)體;13 else ∥exploitation phase

2.1 編碼方式

基本多目標(biāo)金鷹優(yōu)化算法通常被用于求解連續(xù)優(yōu)化問題。在算法中,金鷹個(gè)體根據(jù)文獻(xiàn)[13]中式(6)迭代更新自己的位置。由于MONTJSSP/O是離散型優(yōu)化問題,因此,需要設(shè)計(jì)有效編碼方法將問題解空間映射至算法空間。受遺傳算法等進(jìn)化類優(yōu)化算法啟發(fā),本文采用已廣泛使用的基于工件序號(hào)的編碼方式。圖1為2臺(tái)機(jī)器4個(gè)工件的編碼示意圖,案例具體信息如表2所示,其中第1列表示工件序號(hào);第2、3列表示加工信息,圓括號(hào)外數(shù)字表示工序序號(hào),圓括號(hào)內(nèi)數(shù)字表示加工工時(shí);第4列表示各工件交貨期。圖1所示為該案例的一個(gè)編碼結(jié)果,加工序列中每個(gè)基因位上的整數(shù)表示工件編號(hào),從左往右,整數(shù)編號(hào)在加工序列中第j次出現(xiàn)就代表該工件的第j道工序。加工序列的長(zhǎng)度為所有工件所有工序數(shù)的總和。

圖1 編碼方式示例

表2 2臺(tái)機(jī)器和4個(gè)工件案例信息

2.2 兩階段解碼方案

以圖1所示的編碼為例,采用傳統(tǒng)解碼方法得到的活動(dòng)調(diào)度解如圖2所示,其中d1、d2、d3、d4分別為工件J1、J2、J3、J4的交貨期,[8,16]表示加班時(shí)間區(qū)間,最大完工時(shí)間Cmax=31。由圖2可以看出,該活動(dòng)調(diào)度解為非法解,工件J1的完工時(shí)間(C1=31)超過了其交貨期(d1=23),不滿足無拖期約束。

圖2 傳統(tǒng)解碼方式調(diào)度結(jié)果

為此,本文基于問題特征提出了一種兩階段解碼方案,具體流程如下:

(1)第一階段解碼。該階段旨在讓所有工序盡早開工,使所有工件最大完工時(shí)間盡可能地短。圖3所示為第一階段解碼流程。具體方法是:從左往右依次對(duì)加工序列上所有基因進(jìn)行排序,待排工序開工時(shí)間需滿足同工件工序間的前后約束關(guān)系。加工機(jī)器上任何加工間隙如果時(shí)間足夠長(zhǎng),則可在該時(shí)間段安排加工該工序。如果該機(jī)器上有多個(gè)時(shí)間區(qū)間可用,則選擇使用加班時(shí)間最少的時(shí)間區(qū)間。如圖3a所示,待排工序O1,2有三種可排位置,但第②種方案既能滿足工件J1無拖期交付,也能盡量減少加班時(shí)間,所以選擇此方案。經(jīng)過第一階段解碼后的調(diào)度結(jié)果如圖3b所示。若經(jīng)過第一階段解碼后的排序結(jié)果為非法解(即存在拖期),則刪除該個(gè)體,然后隨機(jī)生成新個(gè)體,并繼續(xù)執(zhí)行第一階段解碼過程,如此循環(huán)直至得到可行解。若前述循環(huán)過程執(zhí)行30次后仍未得到可行解,則直接結(jié)束當(dāng)前個(gè)體的解碼過程,繼續(xù)執(zhí)行下一個(gè)個(gè)體的解碼過程。

(b)第一階段解碼結(jié)果

(2)第二階段解碼。該階段是在第一階段解碼結(jié)果的基礎(chǔ)上,保持工件最大完工時(shí)間不變,并滿足無拖期約束,將所有工序盡量往右移(推遲工序開工時(shí)間),將處于加班時(shí)間區(qū)間的工序盡量移動(dòng)至常規(guī)工作時(shí)間區(qū)間,從而減少總加班時(shí)間。若某道工序右移后加班時(shí)間會(huì)增加,則保持工序開工時(shí)間不變。如圖4a所示,在第一階段解碼結(jié)果的基礎(chǔ)上搜索可以右移的工序。從圖4a中可以看出,在滿足無拖期約束和Cmax不變的情況下,工序O3,2和O1,2可往右移。當(dāng)工序O3,2和O1,2移動(dòng)完成后,工序O4,2也可往后移。由此可知,在此階段共有三個(gè)工序可往右移,工序O4,2右移后減少了總加班時(shí)間。第二階段解碼結(jié)果如圖4b所示。

(b)第二階段解碼結(jié)果

將兩階段解碼方式和傳統(tǒng)解碼方式得到的解碼結(jié)果進(jìn)行對(duì)比可知,通過兩階段解碼方式得到的解碼結(jié)果不僅滿足了無拖期約束,而且減少了最大完工時(shí)間和總加班時(shí)間。由圖2和圖4可以看出,采用傳統(tǒng)解碼方式得到調(diào)度解的最大完工時(shí)間為31,總加班時(shí)間為10;采用兩階段解碼方案得到調(diào)度解的最大完工時(shí)間為30,總加班時(shí)間為9。與傳統(tǒng)解碼方式對(duì)比可知,采用兩階段解碼方案使最大完工時(shí)間和總加班時(shí)間分別減少了1。

2.3 基于精英保留策略的選擇算子

受文獻(xiàn)[19]的啟發(fā),本研究在改進(jìn)金鷹優(yōu)化算法中嵌入了基于精英保留策略的選擇算子來選擇種群中表現(xiàn)更優(yōu)的個(gè)體進(jìn)入下一代:首先通過非支配等級(jí)劃分方法按適應(yīng)度值將種群中所有個(gè)體分為若干個(gè)非支配等級(jí),然后根據(jù)擁擠度距離對(duì)同一支配等級(jí)下的個(gè)體進(jìn)行排序,最后選擇支配等級(jí)低、擁擠度大的個(gè)體構(gòu)造新的種群?；诰⒈Ａ舨呗缘倪x擇算子具體執(zhí)行步驟如下。

(1)設(shè)當(dāng)前種群為Pnow,種群規(guī)模為Fpop,初始化下代種群Pnext為空集。

(2)計(jì)算種群Pnow中個(gè)體的非支配等級(jí)。首先找出Pnow中非支配最優(yōu)解,構(gòu)成第一個(gè)非支配最優(yōu)解層,記為R1,然后將R1中個(gè)體從Pnow中去除,再?gòu)挠嘞聜€(gè)體{Pnow-R1}中找出新的非支配解,記為R2,依次類推,直到所有個(gè)體被分級(jí)。

(3)對(duì)步驟(2)得到的各等級(jí)集合Ri(i≥1)分別計(jì)算其中每個(gè)個(gè)體的擁擠度距離,并按照該距離從大到小對(duì)其中的個(gè)體進(jìn)行排序。

(4)遍歷當(dāng)前種群Pnow所有個(gè)體,執(zhí)行如下操作:若當(dāng)前個(gè)體為精英個(gè)體(判定依據(jù):種群中所有個(gè)體按非支配等級(jí)從小到大和各等級(jí)中按擁擠度距離從大到小綜合排序,排序位于前Fpop×50%的個(gè)體被定義為精英個(gè)體),則直接將該個(gè)體存入集合Pnext;若不是精英個(gè)體,則生成新個(gè)體并存入集合Pnext。

2.4 自適應(yīng)子代個(gè)體生成策略

在每次迭代過程中,如果個(gè)體不是精英個(gè)體,則需要重新生成新個(gè)體用于下輪迭代。為了兼顧算法的全局搜索和局部尋優(yōu)能力,本文引入了自適應(yīng)個(gè)體更新策略,具體步驟如下。

(2)計(jì)算當(dāng)前攻擊概率pa和當(dāng)前巡航概率pc,其計(jì)算表達(dá)式分別如下:

(11)

(12)

(3)如果pc>pa,則采用POX交叉[20]和兩點(diǎn)交換變異組合操作生成新個(gè)體;否則,使用基于N5鄰域結(jié)構(gòu)的局部搜索[21]方法生成新個(gè)體。

基于以上步驟,在迭代初期使用交叉和變異組合操作生成相似度不高的新個(gè)體,擴(kuò)大種群搜索范圍,防止算法陷入局部最優(yōu);進(jìn)入迭代后期時(shí),使用局部搜索產(chǎn)生相似度較高的個(gè)體,以提高局部搜索能力。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證NSGEO算法性能,所有算法采用C語言進(jìn)行編程,并在配置了Intel Core i3 CPU和8G RAM的Windows 10系統(tǒng)中進(jìn)行了測(cè)試。

3.1 算例生成

由于MONTJSSP/O問題不存在標(biāo)準(zhǔn)測(cè)試集數(shù)據(jù),因此對(duì){FT06、FT10、FT20},{LA01、LA06、LA11、LA16、LA21、LA26、LA31、LA36},{SWV01、SWV06、SWV11、SWV16},{TA01、TA11、TA21、TA31、TA41、TA51、TA61、TA71}共23個(gè)作業(yè)車間調(diào)度問題基準(zhǔn)算例進(jìn)行了改造以滿足本問題的研究。為區(qū)別于標(biāo)準(zhǔn)算例,改造后的算例名稱為在原算例名稱前面加上符號(hào)m,如mFT06、mLA01、mSWV01和mTA01等。

算例改造體現(xiàn)在時(shí)間域的離散化和交貨期的設(shè)置這兩方面。時(shí)間域的離散化主要指加班時(shí)間和常規(guī)工作時(shí)間區(qū)間的設(shè)定,具體規(guī)則為:每24小時(shí)為一個(gè)循環(huán)周期,每個(gè)循環(huán)周期包含16小時(shí)的常規(guī)工作時(shí)間和8小時(shí)的加班時(shí)間,即[0,16]為常規(guī)工作時(shí)間區(qū)間,[16,24]為加班時(shí)間區(qū)間。工件交貨期采用常用的總工作量(total work content,TWK)規(guī)則,具體計(jì)算公式為

(13)

式中,i、j分別為工件索引和工序索引,di為第i個(gè)工件的交貨期;Fi為第i個(gè)工件的交貨期寬裕度系數(shù);Pi,j為第i個(gè)工件第j道工序的加工時(shí)間。每個(gè)工件的交貨期寬裕度系數(shù)的取值取決于問題的規(guī)模,確定方法將在3.3.1節(jié)中介紹。

3.2 性能評(píng)價(jià)指標(biāo)

本研究采用三個(gè)性能指標(biāo)來評(píng)價(jià)算法的優(yōu)劣性。由于本問題引入了無拖期約束,采用啟發(fā)式算法求解時(shí)極易產(chǎn)生非法解,而可行解的數(shù)量直接影響最優(yōu)解的好壞,因此本文將可行解數(shù)量作為一個(gè)評(píng)價(jià)指標(biāo)。此外,為了綜合評(píng)價(jià)多目標(biāo)算法的收斂性和解的分布性,本文選擇反世代距離(inverted generational distance,IGD)和超體積(hypervolume,HV)兩個(gè)常用的多目標(biāo)評(píng)價(jià)指標(biāo)。上述兩個(gè)評(píng)價(jià)指標(biāo)的計(jì)算方法和評(píng)價(jià)規(guī)則可參考文獻(xiàn)[2,5]。

理論上,種群規(guī)模和迭代次數(shù)的乘積為所有可能解的數(shù)量,如種群規(guī)模為100,迭代次數(shù)為100,則所有可能解的數(shù)量為10 000。在問題求解過程中,得到的可行解數(shù)量(number of feasible solutions,NFS)越多,則搜索到最優(yōu)解的可能性越大,表明算法性能越好。

3.3 實(shí)驗(yàn)結(jié)果及性能分析對(duì)比

為了驗(yàn)證NSGEO算法求解MONTJSSP/O問題的性能,本節(jié)首先驗(yàn)證了改進(jìn)項(xiàng)對(duì)算法性能的影響,然后將NSGEO算法與其他三種多目標(biāo)優(yōu)化算法進(jìn)行了對(duì)比實(shí)驗(yàn)分析。

3.3.1兩階段解碼的性能分析

為了驗(yàn)證兩階段解碼方案的有效性,使用基本遺傳算法進(jìn)行了實(shí)驗(yàn),將求解過程中產(chǎn)生的可行解數(shù)量(NFS)作為評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)中,設(shè)置種群規(guī)模為100,迭代次數(shù)為100。由于交貨期的設(shè)置會(huì)直接影響訂單是否能按期交付,因此在不同交貨期寬裕度系數(shù)F(F=2,4,6,8)下進(jìn)行了實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表3所示,其中SD列和TD列分別表示通過傳統(tǒng)解碼(standard decoding,SD)方式和兩階段解碼(two-stage decoding,TD)方式實(shí)驗(yàn)后得到的可行解數(shù)量。

表3 傳統(tǒng)解碼和兩階段解碼方案下得到的可行解數(shù)量對(duì)比

從表3中可以發(fā)現(xiàn),在合理F值下,兩階段解碼方案比傳統(tǒng)解碼方式更加有效。比如:F=2時(shí),所有23個(gè)測(cè)試算例中,通過SD方式只有mFT06算例能得到3個(gè)可行解,但TD方式有mFT06、mFT10、mLA16和mLA36共4個(gè)算例能得到可行解,且mFT06算例能得到542個(gè)可行解;F=4時(shí),通過SD方式只有30%的算例能得到可行解,但通過TD方式有70%的算例能得到可行解,且TD方式得到的可行解數(shù)量遠(yuǎn)大于SD方式得到的可行解數(shù)量;F=8時(shí),所有算例可通過TD方式得到可行解,但通過SD方式還有5個(gè)算例未能得到可行解。

通過以上分析可以看出,兩階段解碼方案在得到可行解數(shù)量方面是有效的,與傳統(tǒng)解碼方式相比具有很大的優(yōu)勢(shì)。此外,從表3中還可以看出交貨期寬裕度系數(shù)對(duì)可行解數(shù)量的影響很大。若F值過小,可行解數(shù)量太少或?yàn)榱?說明交貨期太緊,無法通過優(yōu)化實(shí)現(xiàn)無拖期;若F值太大,則交貨期太松,與實(shí)際生產(chǎn)情況不符。為此,本文以兩階段解碼方案下產(chǎn)生的可行解數(shù)目大于50為依據(jù),確定了各測(cè)試算例下的交貨期寬裕度系數(shù)。顯然,按此方法確定的工件交貨期可滿足本文1.1節(jié)中的問題假設(shè)⑧。

3.3.2不同配置多目標(biāo)金鷹優(yōu)化算法的性能比較

為檢驗(yàn)NSGEO算法中各項(xiàng)改進(jìn)對(duì)問題求解性能的影響,采用三種不同配置的多目標(biāo)金鷹優(yōu)化算法(MOGEO)進(jìn)行了仿真調(diào)度實(shí)驗(yàn)(兩階段解碼方案的有效性在3.3.1節(jié)已得到驗(yàn)證,本節(jié)實(shí)驗(yàn)在三種比較算法中均加入兩階段解碼方案)。三種多目標(biāo)金鷹優(yōu)化算法的配置情況見表4。

表4 三種多目標(biāo)金鷹優(yōu)化算法配置項(xiàng)

為確定較好的算法控制參數(shù),通過田口實(shí)驗(yàn)進(jìn)行了先導(dǎo)性試驗(yàn),所得較優(yōu)的算法控制參數(shù)為:種群規(guī)模取100,最大迭代次數(shù)取2000,攻擊傾向參數(shù)pa取[0.5,2],巡游傾向參數(shù)pc取[1,0.5]。

針對(duì)所有算例,各算法獨(dú)立運(yùn)行10次,采用IGD、HV兩個(gè)評(píng)價(jià)指標(biāo)比較算法的性能,對(duì)比結(jié)果如表5和圖5所示,其中F列表示各改造算例中交貨期寬裕度系數(shù)的取值。

(a)IGD均值減小率曲線

表5 算法改進(jìn)項(xiàng)有效性分析

通過表5數(shù)據(jù)和圖5曲線可見:

(1)MOGEO2算法與MOGEO1算法相比,前者得到的IGD均值更小,減小率最大達(dá)到了82.5%,如圖5a所示;前者得到的HV均值也更大,56%的算例中HV均值增長(zhǎng)率超過100%,如圖5b所示。統(tǒng)計(jì)數(shù)據(jù)表明自適應(yīng)子代個(gè)體生成策略有效地提升了算法性能。

(2)NSGEO算法與MOGEO2算法相比,在23個(gè)測(cè)試算例中,前者相比于后者有11個(gè)算例的IGD均值減小率超過60%,如圖5a所示;14個(gè)算例中的HV均值增長(zhǎng)率超過100%,如圖5b所示。由此可知,帶精英保留策略的非支配排序選擇算子對(duì)算法性能提升很大。

綜合以上分析,各改進(jìn)項(xiàng)對(duì)多目標(biāo)金鷹優(yōu)化算法求解MONTJSSP/O問題的性能提升有效,且效果明顯。

3.3.3NSGEO算法與其他多目標(biāo)優(yōu)化算法的性能比較

為進(jìn)一步驗(yàn)證NSGEO算法求解MONTJSSP/O問題的優(yōu)越性,本文將NSGEO算法和當(dāng)前求解多目標(biāo)優(yōu)化問題常用的基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition,MOEA/D)[22-23]、帶精英保留策略的非支配排序遺傳算法(non-dominated sorting genetic algorithm-Ⅱ,NSGA-Ⅱ)[21, 24]和混合遺傳禁忌搜索算法(hybrid genetic algorithm-tabu search,HGATS)[18,25]三種算法的性能進(jìn)行了對(duì)比。算法具體參數(shù)設(shè)置如表6所示。為了保證公平性,四種算法的共有參數(shù)設(shè)置相同值,種群規(guī)模均為100,最大迭代次數(shù)均取2000。

表6 對(duì)比算法參數(shù)設(shè)置

本節(jié)采用3.2節(jié)描述的IGD和HV兩個(gè)性能評(píng)價(jià)指標(biāo)來對(duì)比分析四種算法的性能。表7和表8分別給出了四種算法在每個(gè)算例上獨(dú)立運(yùn)行10次后兩個(gè)性能指標(biāo)的均值和標(biāo)準(zhǔn)差,粗體字部分表示均值最佳值。

表7 NSGEO、MOEA/D、NSGA-Ⅱ和HGATS四種算法IGD對(duì)比

表8 NSGEO、MOEA/D、NSGA-Ⅱ和HGATS四種算法HV對(duì)比

表7所示為四種算法得到的IGD指標(biāo)結(jié)果,從表中可以看出,與其他三種算法相比,NSGEO算法在23個(gè)測(cè)試算例中的IGD均值最小,說明NSGEO算法在所有算例中求解得到的Pareto前沿面與真實(shí)Pareto前沿面更加接近,即NSGEO算法所得到解的質(zhì)量更高。

為更加清楚地展示各測(cè)試算例通過不同算法所得到的IGD均值及標(biāo)準(zhǔn)差的分布,圖6給出了四種對(duì)比算法得到的IGD均值和標(biāo)準(zhǔn)差分布曲線。從圖6a中可以明顯看出:MOEA/D算法和HGATS算法得到的IGD值比NSGA-Ⅱ算法和NSGEO算法得到的IGD值相對(duì)更大;雖然NSGA-Ⅱ算法在56%的算例上得到的IGD值與NSGEO算法對(duì)應(yīng)得到的IGD值相近,但在其他算例上與NSGEO算法相差較大,如mLA01、mSWV11和mTA11?？傮w來說,對(duì)于所有測(cè)試算例,NSGEO算法比其他三種算法得到的IGD值更小。此外,從圖6b中可以發(fā)現(xiàn)NSGEO算法在大多數(shù)測(cè)試算例上標(biāo)準(zhǔn)差更小。對(duì)于算例mFT20、mLA21、mTA01和mTA41,與MOEA/D算法和NSGA-Ⅱ算法相比,NSGEO算法得到的IGD標(biāo)準(zhǔn)差更大,但該算法得到的IGD均值更小。綜合上述分析,NSGEO算法在IGD評(píng)價(jià)指標(biāo)上明顯優(yōu)于其他三種對(duì)比算法,具備更好的收斂性、多樣性和穩(wěn)定性。

表8和圖7分別展示了四種算法得到的HV指標(biāo)結(jié)果數(shù)據(jù)以及HV均值和標(biāo)準(zhǔn)差分布曲線。從圖7a中可以看出,NSGEO算法得到的HV均值比其他三種算法得到的HV均值大很多,有近74%的算例增長(zhǎng)率超過50%,可見NSGEO算法相較于其他三種算法有明顯的優(yōu)勢(shì)。對(duì)于HV標(biāo)準(zhǔn)差,由圖7b可見,少數(shù)算例NSGEO算法得到的HV標(biāo)準(zhǔn)差比其他算法得到的HV標(biāo)準(zhǔn)差稍大,但差值并不明顯,總體來看,NSGEO算法得到的HV標(biāo)準(zhǔn)差更小,算例間的波動(dòng)也較小。從上述分析不難看出,NSGEO算法的HV指標(biāo)值優(yōu)勢(shì)比較明顯,表明NSGEO算法比其他三種算法得到的解質(zhì)量更高,性能更加穩(wěn)定。

(a)HV均值曲線

為比較直觀地觀察到各算法得到的Pareto解集的分布情況,對(duì)所選擇的6個(gè)不同規(guī)模算例某次運(yùn)行的結(jié)果進(jìn)行了展示,如圖8所示,其中不同形狀的點(diǎn)代表不同算法獲得的解集。從圖8中可以看出,本文研究的兩個(gè)目標(biāo)之間存在沖突關(guān)系。從Pareto解集的分布可以定性發(fā)現(xiàn),NSGEO算法得到的Pareto解基本都支配著其他三種算法得到的Pareto解,而其他三種算法得到的Pareto解集之間存在相互支配關(guān)系。這種分布說明NSGEO算法得到的Pareto解集更接近真實(shí)Pareto前沿,解的質(zhì)量更優(yōu)。從解的多樣性來說,對(duì)于算例mTA51,雖然NSGEO算法得到的Pareto解集相對(duì)于NSGA-Ⅱ算法稍差,但NSGEO算法得到的Pareto解集更接近真實(shí)的Pareto前沿,收斂性更好。從實(shí)用性角度來看,對(duì)于6個(gè)展示的算例,NSGEO算法得到的解的個(gè)數(shù)相對(duì)更多,說明供決策者可選擇的方案越多。

(a)mFT20 (b)mLA21 (c)mLA36

綜上所述,NSGEO算法能夠求解本文所提出的問題,并且在求解過程中具備比MOEA/D、NSGA-Ⅱ和HGATS三種算法更好的全局搜索和局部尋優(yōu)能力。

4 結(jié)論

為了有效解決面向訂單型制造企業(yè)合理使用加班時(shí)間實(shí)現(xiàn)無拖期交付的問題,本文以最小化加班時(shí)間和最大完工時(shí)間為目標(biāo)建立了問題的數(shù)學(xué)模型,提出了一種基于精英保留策略的非支配排序金鷹優(yōu)化算法(NSGEO)對(duì)問題進(jìn)行了求解,得出了以下結(jié)論:

(1)通過分析考慮加班作業(yè)的多目標(biāo)無拖期作業(yè)車間調(diào)度問題(MONTJSSP/O)和基本多目標(biāo)金鷹優(yōu)化算法特點(diǎn),設(shè)計(jì)了一種離散編碼方式,將金鷹優(yōu)化算法連續(xù)空間映射至問題離散解空間,使問題易于通過啟發(fā)式算法進(jìn)行求解。

(2)與傳統(tǒng)解碼方式進(jìn)行了對(duì)比實(shí)驗(yàn),結(jié)果表明,在合理交貨期設(shè)置情況下,本文提出的兩階段解碼方案得到的可行解數(shù)量遠(yuǎn)大于傳統(tǒng)解碼方式得到的可行解數(shù)量,表明采用所提出的解碼方式求解MONTJSSP/O問題是有效的,且效果顯著。

(3)通過比較不同配置下的多目標(biāo)金鷹優(yōu)化算法性能可得,基于精英保留策略的非支配排序選擇算子和自適應(yīng)子代個(gè)體生成策略對(duì)多目標(biāo)金鷹優(yōu)化算法的性能均有顯著提升。

(4)通過比較不同測(cè)試算例上的仿真調(diào)度實(shí)驗(yàn)和算法,驗(yàn)證了采用所提NSGEO算法在求解MONTJSSP/O問題時(shí),既保證了算法的收斂性又很好地兼顧了Pareto解集的分布性,而且對(duì)解決不同規(guī)模問題的穩(wěn)定性上也明顯優(yōu)于其他對(duì)比算法。

通過加班作業(yè)擴(kuò)充生產(chǎn)能力是保證訂單無拖期交貨的有效措施。然而,若訂單過于密集和交貨期設(shè)置太緊,進(jìn)而使得制造系統(tǒng)負(fù)荷超過一定極限時(shí),則需結(jié)合其他資源擴(kuò)展方式以實(shí)現(xiàn)訂單的無拖期交付,如機(jī)器柔性、工藝柔性和外協(xié)加工等。為此,后續(xù)可對(duì)融合多種可擴(kuò)展資源的作業(yè)車間無拖期調(diào)度問題進(jìn)行進(jìn)一步的研究。此外,實(shí)際制造系統(tǒng)中的調(diào)度問題大多屬于動(dòng)態(tài)調(diào)度問題,為此,在本文研究基礎(chǔ)上,需對(duì)動(dòng)態(tài)作業(yè)車間無拖期調(diào)度問題進(jìn)行進(jìn)一步的相關(guān)研究。