求解異構并行機調度問題的混合多目標教-學優(yōu)化算法

宋 強

(肇慶學院計算機科學與軟件學院,廣東肇慶 526061;武漢理工大學信息工程學院,湖北武漢 430070)

1 引言

異構并行機調度(unrelated parallel machine scheduling,UPMS)在生產制造領域擁有廣泛的應用背景,例如:云計算、紡織生產和半導體制造等[1].傳統(tǒng)的UPMS以單目標優(yōu)化為主,側重于提高系統(tǒng)的運行效率,其優(yōu)化指標包括makespan,總加權完工時間和等.然而在實際生產過程中,企業(yè)決策層通常需要綜合考慮多方面的優(yōu)化目標.同時,準時化已經逐步構成企業(yè)的重要管理支撐,通過準時化生產降低訂單延誤是企業(yè)保持核心競爭力的重要手段[2].因此,在兼顧傳統(tǒng)優(yōu)化指標的同時,研究考慮準時化的多目標異構并行機調度問題具有較高的理論意義和工程應用價值.

本文以最小化makespan與提前/延誤懲罰成本總和為目標,研究了一類多目標異構并行機調度問題.UPMS問題具有非確定性多項式難(nondeterministic polynomial-hard,NP-hard)性質,而實際調度過程的多目標性質進一步加劇了問題的求解難度,因此如何設計高效的調度算法成為該領域的研究重點.目前解決UPMS問題的決策方法分為精確算法、啟發(fā)式算法和智能優(yōu)化算法3類[3].精確算法難以解決中大規(guī)模算例,工程應用價值低;而啟發(fā)式算法的普適性較弱,嚴重依賴于問題設置.近年來,智能優(yōu)化算法的快速發(fā)展為解決UPMS問題提供了新思路,學者們廣泛采用粒子群算法、模擬退火算法等求解UPMS問題,且優(yōu)化效能令人滿意[4].同時,多目標優(yōu)化問題不存在唯一的最優(yōu)解,而是尋求多個不同量綱目標之間的權衡.因此,基于Pareto支配概念的方法獲得了廣泛應用,該類方法致力于獲得一組靠近Pareto最優(yōu)前端且分布均勻的非支配解[5].智能優(yōu)化算法普遍采用基于種群的進化方法,一次運行即可獲得一組非支配解,因此非常適合于解決多目標優(yōu)化問題.依據no free lunch定理可知[6],尚不存在一種決策方法能夠高效地解決所有調度問題.基于以上研究背景,本文設計了混合多目標教-學優(yōu)化算法(hybrid multi-objective teachinglearning-based optimization,HMTLBO)用于解決當前的多目標異構并行機調度問題.

HMTLBO算法采用分解機制將Pareto前沿逼近問題轉化為一系列單目標子問題,并借助教-學優(yōu)化算法(teaching-learning-based optimization,TLBO)對各子問題進行優(yōu)化求解.利用分解機制構建多目標決策方法能夠降低算法在多樣性保持和適應度分配方面的難度,且該機制能夠充分融合各種高效的智能優(yōu)化算法和局部搜索方法用于單目標子問題的尋優(yōu)[7].TLBO算法是Rao等學者提出的高效智能優(yōu)化算法,該方法受課堂教學行為的啟發(fā),通過模擬教師課堂教學和學生相互學習這一現象來實現迭代進化[8].TLBO算法具有控制參數少、收斂速度快等優(yōu)點,目前已經在車間調度、電力系統(tǒng)調度、神經網絡訓練等多個領域獲得了應用[9].考慮到TLBO算法解決單目標優(yōu)化問題的高效性能,本文將其與分解機制相結構,進而構建了多目標優(yōu)化算法用于求解當前研究的UPMS問題.此外,為確保算法的高效運行,本文結合UPMS問題的特點設計了序列編碼方式,并據此融合多種交叉算子對個體進化過程的教學階段和學習階段進行重新定義,同時構建了變鄰域下降搜索以增強HMTLBO算法的局部搜索能力.最后進行了仿真實驗,測試結果驗證了本文提出的HMTLBO算法的可行性和有效性.

2 數學建模

2.1 問題描述

在當前UPMS問題中,有n項訂單需要在m臺機器上進行加工,所有訂單和機器均在零時刻就緒,同一訂單在不同機器上的加工時間不同.同時,各項訂單均存在自身的交貨期,提前或延誤交付均產生一定的懲罰成本.

UPMS問題的決策內容包括:1)訂單分配,將n項訂單劃分給m臺機器;2)訂單排序,確定每臺機器上的訂單加工順序.當前模型選用makespan以及提前/延誤懲罰成本總和作為優(yōu)化目標,前者用于改善系統(tǒng)的運行效率,后者側重于訂單交付的準時性.研究表明[10],在實際調度過程中,二者往往相互沖突,難以同時達到最優(yōu).

2.2 數學模型

為了構建當前調度問題的數學模型,首先定義符號如表1所示.

結合以上數學符號,對本文所研究的UPMS問題建模如下:

其中:式(1)為最小化所有訂單的最大完工時間Cmax,式(2)表示最小化提前/延誤懲罰成本總和;約束(3)用于確保各項訂單僅被加工一次,約束(4)表示每一項訂單最先被加工或者構成其他訂單的緊后加工訂單,約束(5)用于計算各項訂單的完工時間,約束(6)表示每臺機器最先被加工的訂單數目至多為1,式(7)表示虛擬訂單0的完工時間為0,式(8)-(9)計算了各訂單的提前和延誤時長,式(10)計算了調度方案的Cmax值;最后,約束(11)定義了所有變量的取值范圍.

2.3 ε約束法

為了獲取小規(guī)模算例的Pareto最優(yōu)前沿,在此建立ε約束法.該方法將上述雙目標優(yōu)化模型中的某一目標將轉化為約束,通過構建一系列單目標ε約束問題并借助CPLEX精確求解這些單目標ε約束問題來獲取當前雙目標UPMS調度問題的Pareto最優(yōu)前沿[11].以?和ε分別表示問題的搜索空間和一個較小的正數,ε約束法的實現流程歸納如下:

步驟1選取f1作為優(yōu)化目標,轉步驟2;

步驟2令h ←1,并轉步驟3;

步驟3獲取邊界點:利用CPLEX求解以下模型,并記最優(yōu)解記為πh,

若該模型存在可行解,轉步驟5;否則,轉步驟7;

步驟4求解ε約束問題:利用CPLEX求解以下模型,并記最優(yōu)解記為πh,

步驟5將πh置于當前非劣解集(pareto font,PF)中,并轉步驟6;

步驟6令h ←h+1,并轉步驟4;

步驟7終止迭代,輸出PF.

3 TLBO算法

TLBO采用種群表示待優(yōu)化問題的一組解,當前種群中的最優(yōu)解稱為教師個體,其他的解為學生個體.該算法采用隨機的方法構建初始種群,并通過教學階段和學習階段進行種群進化,圖1給出了TLBO算法的實現流程.

圖1 TLBO算法流程Fig.1 Flowchart of TLBO

TLBO算法主要包括初始化、教學階段和學習階段3部分,各部分的實現過程歸納如下:

1) 初始化.

給定種群規(guī)模N,問題的編碼長度D和各個維自變量的取值范圍(d=1,2,···,D),TLBO算法利用隨機的方法生成N個初始解,每個解以D維向量表示,初始化公式為

其中:xid表示當前種群中的第i個解xi在維度d上的取值,rand(0,1)為[0,1]上的隨機數.

2) 教學階段.

該階段將借助教師個體xteacher和平均個體xm對當前種群進行一輪更新,在平均個體xm={m1,···,md,···,mD}中,md表示當前種群中所有個體每一維自變量取值的均值.給定父代個體xold,教學階段采用以下公式生成新個體:

其中:教師個體xteacher表示算法迭代到當前階段所尋得的最優(yōu)解;教學因子κ為隨機整數,κ ∈{1,2}.比較xnew和xold的目標函數值,將二者之中較優(yōu)的解作為子代個體.

3) 學習階段.

該階段將利用候選個體與其他個體解向量之間的差分量xm對當前種群進行第2輪更新.以最小化問題為例,用f(·)表示當前優(yōu)化問題的目標函數,給定父代個體xold,采用隨機的方法從當前種群中選擇解xr(xrold),學習階段通過以下公式生成新個體xnew:

生成新個體后,算法將比較xnew和xold的目標函數值,將二者之中較優(yōu)的解作為子代個體.

4 HMTLBO算法

HMTLBO算法采用分解機制將Pareto前沿逼近問題轉化為一系列單目標子問題,并借助TLBO算法對各子問題進行優(yōu)化求解.為確保算法的高效運行,結合UPMS問題的特點設計了序列編碼方式,并據此對個體進化過程的教學階段和學習階段進行重新定義,同時構建了變鄰域下降搜索以增強算法的局部搜索能力.

4.1 分解機制

HMTLBO算法將多目標并行機調度問題分解成N個多目標子問題,權重向量采用混料均勻設計,與第i個子問題相關的權重向量λi=設置如下:

其中子問題總數N與算法的種群規(guī)模相等.

同時,本文采用歸一化Tchebycheff聚合方法建立各子問題的評價函數,對于第i個子問題,聚合函數設置如下[7]:

其中:f1和f2表示解x目標1和目標2的取值,ˉf1和為相應的歸一化數值,分別表示目標1和目標2迭代至目前為止的最小值和最大值.Z?=為參考點,取值為(0,0),函數Fi(x|λi)用于評價解x對于第i個子問題適應度.圖2展示了該聚合方法的運行機理,對于與λ1掛鉤的子問題,算法將在可行解空間中逐步搜得λ1與Pareto前沿的交點xa.同理,算法將在可行解空間中逐步搜得λ2與Pareto前沿的交點xb.因此,對于N個均勻分布的權重向量,HMTLBO算法將獲取Pareto前沿上一組均勻分布的非劣解.

圖2 Tchebycheff聚合方法運行機理Fig.2 Mechanism of Tchebycheff approach

4.2 算法框架

在初始階段,HMTLBO算法采用混料均勻設計生成N個權重向量λ1,λ2,···,λN,將其中距向量λi最近的T個權重向量下標構成的集合記為Bi={i1,i2,···,iT};同時,算法采用隨機的方法生成N個初始解x1,x2,···,xN,并為每一個權重向量分配一個解.在進化過程中,分別采用教學階段,學習階段和變鄰域下降搜索對種群進行更新.此外,算法采用外部檔案Archive 來保存非劣解集,Archive用初始種群中的非劣解進行初始化;在迭代過程中,依據帕累托支配關系更新Archive集合.

基于以上描述,HMTLBO算法的實現步驟歸納如下:

步驟1初始化.

步驟1.1利用混料均勻設計生成權重向量λ1,λ2,···,λN,基于各向量間的歐式距離確定各子問題的鄰居,以Bi={i1,i2,···,iT}表示距λi最鄰近的T個向量;

步驟1.2采用隨機的方法生成x1,x2,···,xN,并計算各個解的目標函數值;

步驟1.3隨機為每個權重向量分配一個解;

步驟1.4確定初始種群中的非劣解,并載入外部檔案Archive.

步驟2更新.

步驟2.1教學階段:針對第i個子問題,利用教學階段的解更新方法獲得xnew,若

步驟2.5更新Archive:去除Archive 中被xi支配的解.判斷xi是否被Archive中的解支配,若不被支配,將xi載入Archive;end for.

步驟3終止條件判斷.若滿足HMTLBO算法的終止條件,終止迭代并輸出Archive;否則,轉步驟2.

4.3 編碼與解碼

TLBO算法最初用于解決連續(xù)變量優(yōu)化問題,種群中的個體均采用實數編碼方式.對于當前研究的UPMS問題,采用實數編碼盡管能夠通過合理的解碼規(guī)則獲得問題的解,但實數編碼存在冗余信息大的缺陷,這一定程度上限制了算法的搜索效率.為此,HMTLBO算法采用序列編碼表示UPMS問題的解,編解碼過程歸納如下:已知訂單總數為n,機器總數為m,采用1～(n+m-1)所構成的一個隨機序列表示當前問題的解,其中1～n為訂單編號,(n+1)～(n+m-1)表示分割符號,據此可知m-1個分割符能夠將訂單1～n的排列分成m個子序列(包含空序列),每個子序列構成相應機器的訂單加工序列.

假設訂單總數和機器總數為分別為7和3,圖3展示了當前算例的編解碼過程.編碼〈5,4,6,9,2,1,8,7,3〉中,1-7為訂單編號,8和9表示分割符號,據此可得各機器的訂單加工序列:機器1,訂單5→訂單4→訂單6;機器2,訂單2→訂單1;機器3,訂單7→訂單3.

圖3 編解碼示意圖Fig.3 Schematic diagram of coding and decoding

4.4 教學階段與學習階段

在教學階段,對當前種群中的每個個體進行一次更新,更新過程為:對于解xi,從外部檔案Archive中隨機選擇一個解作為教師個體,二者進行交叉操作生成新解xnew;倘若

如前所述,HMTLBO 算法采用序列編碼表示UPMS問題的解.鑒于部分匹配交叉(partial-mapped crossover,PMX)、順序交叉(order crossover,OX)和基于位置的交叉(position-based crossover,PBX)3種算子在解決以序列編碼為特征的組合優(yōu)化問題方面的突出性能[12],本文將上述3種交叉算子融合于HM TLBO算法的進化過程中,力求借助不同交叉算子的搜索能力提高HMTLBO算法在整個解空間的尋優(yōu)效率.每次個體更新過程通過隨機的方式選擇其中一種算子進行交叉操作,3種算子的實現過程歸納如下:

1) PMX:如圖4(a)所示,首先,隨機選擇兩個父代個體中多個連續(xù)的編碼位置;其次,將父代個體2中所選的編碼置于父代個體1的相同位置生成臨時子代個體;最后,進行沖突檢測,依據所選位置上的編碼數值建立映射關系,將臨時子代個體中重復的編碼映射為其他編碼,從而生成新個體.

2) OX:如圖4(b)所示,首先,隨機選擇父代個體1中多個連續(xù)的編碼位置;其次,保留父代個體1中所選的編碼生成臨時子代個體;最后,確定臨時子代中的基因在父代個體2中的位置并將其余編碼按順序放入臨時子代中,從而生成新個體.

3) PBX:如圖4(c)所示,首先,隨機選擇父代個體1中多個編碼位置(可以不連續(xù));其次,保留父代個體1中所選的編碼置生成臨時子代個體;最后,找出臨時子代中的基因在父代個體2中的位置,將其余編碼按順序放入臨時子代中,從而生成新個體.

圖4 交叉算子示意圖Fig.4 Schematic diagram of crossover operators

4.5 變鄰域下降搜索

為了增強算法的局部搜索能力,在HMTLBO算法中嵌入變鄰域下降搜索.變鄰域下降搜索具有較強的局部開發(fā)能力,該方法通過系統(tǒng)地改變候選解從而獲得問題的局部最優(yōu),該優(yōu)化技術的核心在于當前問題的鄰域結構設計[13].對于UPMS問題,本文利用交換,逆轉和插入3種鄰域結構生成變異解,3種變異操作的實現過程描述如下:

1) 交換:如圖5(a)所示,隨機選擇候選解的兩處位置,交換相應的編碼從而生成新的解.

2) 翻轉:如圖5(b)所示,隨機選擇候選解的兩處位置,逆轉這兩處位置間的編碼從而生成新的解.

3) 插入:如圖5(c)所示,隨機選擇候選解的兩處位置,將其中一處位置上的編碼插入到另一處位置前面從而生成新的解.

圖5 鄰域結構示意圖Fig.5 Schematic diagram of neighborhood Structure

分別將上述3種變異算子記作N1,N2和N3,據此可得鄰域總數kmax=3.給定候選解x及其對應的權重向量λi,HMTLBO算法中的變鄰域下降搜索環(huán)節(jié)通過以下流程進行尋優(yōu):

步驟1分別令x?←x,k←1和l←1,轉步驟2;

步驟2使用鄰域結構Nk對當前解x進行擾動,進而生成變異解x′;

步驟3若Fi(x′|λi)

步驟4若l

步驟5若k≤kmax,分別令k ←k+1和l ←1,轉步驟2;否則,轉步驟6;

步驟6終止迭代搜索,輸出x?.

其中:參數LS用于控制搜索深度,變量x?用于記錄尋優(yōu)過程中所得的最優(yōu)解.

5 仿真實驗及結果分析

5.1 實驗準備

在1.6 GHz,內存8 GB,Intel Core i5-8250UCPU的計算機上進行仿真,選用MATLAB 2016a編程實現各個測試算法.參考文獻[10]生成本文的測試數據集,小規(guī)模情形下訂單數n ∈{10,12,14,16,18,20},機器數m=2;中大規(guī)模情形下n ∈{30,50,80,100,150,200},m ∈{5,8,10}.以符號(m,n)表示不同規(guī)模的算例,生成共計24組算例.加工時間參數pkj服從離散均勻分布DU(10,100),提前懲罰成本系數ej ∈{0.1,0.2,···,0.5},延誤懲罰成本系數tj ∈{0.6,0.7,···,1.0},交貨期dj ∈DU(0,0.4·P),其中P=

測試實驗包含3部分:首先,為了驗證相關改進措施對算法效果的影響,進行了HMTLBO算法的縱向對比實驗;其次,為了驗證當前算法的高效性,將HMTLBO 與MOTLBO(multi-objective teachinglearning-based optimization)[14]和ε-MOABC(multiobjective artificial bee colony based onIε+)[15]兩 種算法進行對比;最后,針對具體案例進行了優(yōu)化求解,從而驗證調度模型的有效性以及HMTLBO算法的工程應用價值.

對于每個算例,所有測試算法分別獨立運行15次,并采用世代距離(generational distance,GD)、分布指標(spread)和反世代距離(inverted generational distance,IGD)作為評價指標[14],各個測試指標的定義歸納如下:

定義1GD為收斂性指標,用于衡量算法求得的非劣解集中各個點和真實前沿的平均距離,其計算公式為

其中:PF表示算法求得的非劣解集,di為PF中第i個解與真實前沿中最近點的歐式距離.GD越小,算法的性能越好.為了消除不同目標量綱的影響,GD指標采用歸一化處理技術進行處理.對于小規(guī)模算例,采用ε約束法和CPLEX求解雙目標混合整數規(guī)劃模型即可獲得Pareto最優(yōu)前沿;對于中大規(guī)模算例,將所有測試算法優(yōu)化結果集合中的非劣解作為近似Pareto最優(yōu)前沿.

定義2Spread為均勻性指標,用于衡量算法所求得的非劣解集的分布均勻性,其計算公式為

其中:PF表示算法求得的非劣解集,?i為PF中第i個解與第i+1個解之間的歐式距離,為平均距離,?f和?l分別表示PF兩個端點與真實前沿兩個端點之間的距離.Spread越小,算法的性能越好,Spread為0表明PF中的解是完全均勻分布的.為了消除目標量綱不同產生的影響,Spread指標采用歸一化處理技術進行處理.

定義3IGD為綜合性指標,用于衡量測試問題的真實前沿中各個點與算法所求得的非劣解集之間的平均距離,其計算公式為

其中:PF表示算法求得的Pareto解集,PF?表示測試問題的Pareto真實前沿,d(x,PF)表示PF?中一點x與PF中最近點的歐式距離.IGD 越小,算法的性能越好.為了消除目標量綱不同產生的影響,IGD指標采用歸一化處理技術進行處理.

各測試算法的種群規(guī)模和外部檔案集合均設為30,每個算法求解小規(guī)模算例的最大運行時間為30s,相應求解中大規(guī)模算例的最大運行時間為90s.MOTLBO和ε-MOABC算法的其他參數分別維持與文獻[14-15]相同的取值,相應的編解碼方法參考文獻[16].HMTLBO算法的鄰居規(guī)模T設和變鄰域搜索的迭代次數LS為12和8.

5.2 改進措施有效性驗證

在種群進化過程中,HMTLBO算法采用PMX,OX和PBX三種交叉算子相融合的進化方法生成子代個體,力求借助不同交叉算子的搜索能力提高當前算法在整個解空間的尋優(yōu)效率;同時,變鄰域下降搜索的嵌入用于提高HMTLBO算法的局部搜索能力,進而提高解的質量.為了驗證以上做法的有效性,在此進行改進措施有效性驗證.對于各個測試算例,首先采用HMTLBO算法進行15次獨立求解;隨后,調整HMTLBO算法,分別將僅包含PMX,OX和PBX交叉算子的多目標算法對當前算例進行15次獨立求解,并對3種算子的平均優(yōu)化效果(以HMTLBO1表示)進行統(tǒng)計分析;最后,將去除變鄰域下降搜索部分的HMTLBO算法對當前算例進行15次獨立求解,并對測試結果進行統(tǒng)計分析(以HMTLBO2表示).如圖6-8所示,分別給出了GD,Spread和IGD指標的箱線圖.

圖6 GD指標箱線圖Fig.6 Boxplot of GD

圖7 Spread指標箱線圖Fig.7 Boxplot of Spread

圖8 IGD指標箱線圖Fig.8 Boxplot of IGD

對于GD指標,HTLBO,HMTLBO1和HMTLBO2的優(yōu)勝率分別為.具體言之,在共計24組測試算例中,本文提出的HTLBO算法在18組算例中取得了最優(yōu)的GD指標均值和方差.同時,在HTLBO算法僅使用一種交叉算子或未使用變鄰域下降搜索的情況下,僅能在3組算例中獲得GD指標最優(yōu)的非劣解集.對于Spread指標,HTLBO,HMTL BO1和HMTLBO2的優(yōu)勝率分別達到對于IGD指標,相應的優(yōu)勝率分別為顯然,在絕大多數測試算例中,3種交叉算法的混合使用以及變鄰域下降搜索的嵌入使得HTLBO算法的尋優(yōu)效果獲得了顯著提升,這表明上述兩點措施對于改善所提出算法的性能具有積極意義.

考慮到多目標進化算法的隨機性,在此對測試結果進行顯著性檢測.本文采用Wilcoxon符號秩檢測法檢驗HTLBO與其對比算法之間是否具有顯著性差別,顯著性水平設為5%,R+或R-表示HTLBO算法求解所有算例的平均效果優(yōu)于(或劣于)其競爭者的秩和[17].對于各測試指標,表1展示了24組算例測試指標均值的Wilcoxon符號秩檢測結果.據此可知,各項顯著性概率值均小于顯著性水平5%.換而言之,相比于HMTLBO1和HMTLBO2的優(yōu)化結果,HMTLBO算法所尋的非劣解集的平均質量更優(yōu),即3種交叉算子的混合使用以及變鄰域下降搜索的嵌入使得HTLBO算法的優(yōu)化性能獲得了顯著提升.

表1 改進措施Wilcoxon符號秩檢測結果Table 1 Results of Wilcoxon’s signed rank test for algorithm adaptations

5.3 算法有效性驗證

為了驗證本文所建立的多目標算法的高效性,將HMTLBO與MOTLBO和ε-MOABC兩種算法進行對比.其中:MOTLBO是以TLBO進化算法為基礎,通過結合非支配解排序和擁擠度概念建立的多目標進化算法;ε-MOABC是近年提出的最新的多目標進化算法,該算法通過融合人工蜂群算法和基于指標的個體評價方法構建而成.對于各個測試算例,測試算法均獨立運行15次,表2-4分別對比了3種測試算法的GD,Spread和IGD指標的均值和方差,3種算法所得的最優(yōu)指標加粗顯示.

由表2可知,就收斂性指標GD而言,HMTLBO算法在24組測試算例中20次取得最優(yōu);在其余的4組算例中,MOTLBO算法兩次取得最優(yōu),ε-MOABC算法兩次取得最優(yōu).就分布性指標Spread而言(見表3),HMTLBO算法在24組測試算例中19次取得最優(yōu),MOTLBO算法和ε-MOABC算法取得最優(yōu)的次數分別為3和2.對于綜合性指標IGD(見表4),HMT LBO,MOTLBO和ε-MOABC算法的優(yōu)勝率分為19/24,4/24和1/24.

表2 3種算法GD指標的均值和標準差Table 2 Means and standard deviations of GD obtained by three algorithms

表3 3種算法Spread指標的均值和標準差Table 3 Means and standard deviations of Spread obtained by three algorithms

表4 3種算法IGD指標的均值和標準差Table 4 Means and standard deviations of IGD obtained by three algorithms

在此基礎上,圖9展示了3種算法求解中大規(guī)模算例所得的非劣解集,據此可知HMTLBO算法所求得的非劣解集在收斂性和分布均勻性方面表現更為良好,優(yōu)化效果更令人滿意.

鑒于多目標進化算法的隨機性,故采用Wilcoxon符號秩檢測法檢驗HTLBO與MOTLBO以及ε-MOA BC算法之間的顯著性差異,顯著性水平設為5%.對于各測試指標,表5給出了24組算例測試指標均值的Wilcoxon符號秩檢測結果.由此可知,各項顯著性概率值均小于顯著性水平5%,換而言之,HMTLBO算法所尋得的非劣解集相比于MOTLBO和ε-MOA BC算法的優(yōu)化結果平均質量更具競爭性,優(yōu)勢更為顯著.

綜合而言,HMTLBO算法在多數情況下相較于對比算法能提供更好的解決方案,其優(yōu)化性能和穩(wěn)定性更為良好.HMTLBO算法的高效性歸結于以下4個方面:1)采用基于分解機制的多目標算法框架,并通過歸一化聚合函數以及混料均勻權重設計方法來確保優(yōu)化結果的分布均勻性;2)有效利用TLBO算法求解單目標優(yōu)化問題的高效性實現子問題的優(yōu)化求解;3)采用序列編解碼方法,有效減少了算法的信息冗余度,并借助PMX,OX和PBX三種交叉算子相融合的個體進化方法提高HMTLBO算法在整個解空間的尋優(yōu)效率;4)通過嵌入變鄰域下降搜索確保HMTLBO算法的局部搜索能力.

表5 對比算法Wilcoxon符號秩檢測結果Table 5 Results of Wilcoxon’s signed rank test for benchmark algorithms

圖9 3種算法所得非劣解集Fig.9 Pareto sets obtained by three algorithms

5.4 案例分析

為了進一步驗證調度模型的有效性和HMTLBO算法的高效性,在此給出案例分析.表6歸納了相關參數設置,包括加工時間pkj,提前懲罰成本系數ej,延誤懲罰成本系數tj和交貨期dj.在此基礎上,以訂單1-30和機器1-3構建算例(30,3),以訂單1-40和機器1-4構建算例(40,4),以訂單1-50和機器1-5構建算例(50,5),分別利用HTLBO,MOTLBO以及ε-MOABC算法對上述3個算例進行求解,圖10展示了測試算法求解3組算例所得的非劣解集,表7則給出了3種測試算法所得測試結果的GD,Spread和IGD指標的均值和方差.

觀察圖10可知,當前模型的兩個優(yōu)化目標相互沖突,makespan較小的調度方案對應的提前/延誤懲罰成本總和較大,makespan較大的調度方案,對應的提前/延誤懲罰成本總和指標更令人滿意,這在一定程度上驗證了調度模型的有效性.同時,相較于MOTLBO和ε-MOABC算法,圖10的測試結果直觀顯示出本文提出的HMTLBO算法所求得的非劣解集在收斂性和分布均勻性方面表現更令人滿意.而表7中的數據則進一步表明HMTLBO算法所求得測試結果的各項指標均優(yōu)于對比算法MOTLBO和ε-MOABC,這有效地驗證了當前調度算法的高效性和實用性.此外,圖11利用甘特圖展示了HMT LBO求解案例(50,5)得結果中3個解的調度過程.其中,解A的目標函數1為最小,目標函數2為最大,取值分別為289和11649.7;解B較為折中,兩個目標函數分別為469和6885.5;解C的目標函數1為最大,目標函數2為最小,取值分別為760和4038.7.

6 結論

本文針對異構并行機調度問題,以最小化makespan和提前/延誤懲罰成本為目標建立了數學優(yōu)化模型,并提出了混合多目標教-學優(yōu)化算法.HMTL BO算法借助分解機制將Pareto前沿逼近問題轉化為一系列單目標子問題,并通過TLBO算法求解各子問題.針對問題特點設計了序列編碼方式,并據此融合PMX,OX和PBX算子構筑了個體更新方法,同時構建了變鄰域下降搜索以增強算法的局部搜索能力.開展了HMTLBO算法的橫縱向對比實驗,并給出了案例分析,測試結果驗證了HMTLBO算法求解本文所研究的多目標異構并行機調度問題的高效性.

表6 測試案例參數設置Table 6 Problem settings in case studies

圖10 案例分析中3種算法所得非劣解集Fig.10 Pareto sets obtained by three algorithms in case studies

表7 案例測試結果Table 7 Simulation results of case studies

圖11 甘特圖Fig.11 Gantt charts