亓祥波,馬志強(qiáng),王宏偉

(沈陽(yáng)大學(xué)機(jī)械工程學(xué)院,沈陽(yáng) 110044)

0 引言

近年來(lái),置換流水車間調(diào)度問(wèn)題(permutation flow-shop scheduling problem,PFSP)因其在運(yùn)輸、采購(gòu)和通信等行業(yè)中占據(jù)重要地位而引起了研究人員的關(guān)注。由于PFSP是NP難題,求解難度巨大。因此,文獻(xiàn)中提出多種改進(jìn)算法來(lái)解決此問(wèn)題。JOHNSON[1]提出流水車間調(diào)度問(wèn)題,隨后NAWAZ等[2]提出NEH啟發(fā)式算法有效解決了該問(wèn)題。LIU等[3]在NEH算法基礎(chǔ)上,首次利用偏度構(gòu)造出一個(gè)新的優(yōu)先級(jí)規(guī)則和新的平局打破機(jī)制以進(jìn)一步提高其性能。由于NEH算法取得了成功,對(duì)于求解PFSP的元啟發(fā)式算法通常采用NEH算法初始化種群來(lái)提高解的質(zhì)量。秦旋等[4]提出混合共生生物搜索算法來(lái)改善其局部搜索能力。裴小兵等[5]提出一種基于分布估計(jì)算法的改進(jìn)貓群算法,大幅提高了解的精度。黎陽(yáng)等[6]提出的改進(jìn)模擬退火算法為大規(guī)模PFSP的求解提供了新思路。ABDEL等[7-9]將鯨魚(yú)優(yōu)化算法與局部搜索策略相結(jié)合來(lái)提高算法的求解精度并加快收斂速度,使用最大排序值(largest ranked value,LRV)規(guī)則[10]將連續(xù)值轉(zhuǎn)換為離散值來(lái)求解PFSP。此外,還研究了廣義正態(tài)分布算法和改進(jìn)遺傳算法,采用加擾變異等算子提高算法性能。

目前智能優(yōu)化算法得到了廣泛的研究,各種改進(jìn)方法在求解PFSP問(wèn)題上取得了不錯(cuò)的效果,但仍然存在一些缺陷,例如:易陷入局部最優(yōu)、魯棒性較差和時(shí)間復(fù)雜度較高等問(wèn)題[11]。尤其在解決中大規(guī)模問(wèn)題時(shí),算法的性能隨著問(wèn)題維度的增加而顯著降低,出現(xiàn)維數(shù)災(zāi)難[12]。為了克服上述問(wèn)題,本文提出一種集成多策略教學(xué)優(yōu)化算法(IMTLBO),在保留標(biāo)準(zhǔn)教學(xué)優(yōu)化算法優(yōu)點(diǎn)的基礎(chǔ)上,使用多種策略進(jìn)行尋優(yōu),實(shí)現(xiàn)算法探索和開(kāi)發(fā)兩階段的平衡。結(jié)果表明IMTLBO在求解不同規(guī)模PFSP問(wèn)題上可以得到較優(yōu)結(jié)果。

1 置換流水車間調(diào)度問(wèn)題模型

假設(shè)n個(gè)工件在流水線中的m臺(tái)機(jī)器上按照一定的順序加工,給出n個(gè)工件的加工排列順序使得最大完工時(shí)間最小。PFSP的環(huán)境的布局如圖1所示,PFSP的特點(diǎn)總結(jié)為:

圖1 PFSP的環(huán)境布局

在每臺(tái)機(jī)器上,每個(gè)工件jb|b=1…n只能被加工一次;在處理時(shí)間為PT的機(jī)器iz|z=1…m上每次只能加工一個(gè)工件;每個(gè)工件jb在機(jī)器iz上都有一個(gè)完成時(shí)間C(jb,iz);PFSP建模如下:

C(j1,i1)=PTj1,i1

(1)

C(jb,i1)=C(jb-1,i1)+PTjb,i1forb=2,…,n

(2)

C(j1,iz)=C(jb,iz-1)+PTj1,izforz=2,…,m

(3)

(4)

算法評(píng)估每個(gè)解決方案的目標(biāo)函數(shù)描述如下:

f(ji→)=C(jb,iz)

(5)

式中:ji→是第i個(gè)解的工件排序,并且完工時(shí)間最小的排序被認(rèn)為是最好的。

2 基本教學(xué)優(yōu)化算法

受教師對(duì)課堂學(xué)習(xí)者教學(xué)的啟發(fā),RAO等[13]提出教學(xué)優(yōu)化算法(TLBO)。TLBO分為教學(xué)和學(xué)習(xí)階段,教學(xué)階段引導(dǎo)種群逐漸向最優(yōu)個(gè)體收斂,學(xué)習(xí)階段賦予種群一定的勘測(cè)能力,避免算法早熟。

2.1 教學(xué)階段

TLBO中的教師是整個(gè)群體中知識(shí)水平最高的成員,該階段首先確定群體的均值(M),然后根據(jù)式(6)確定教師知識(shí)水平與群體平均值之間的差異(D)。根據(jù)式(7)更新群體中所有個(gè)體的知識(shí)水平。

D=rand×(Teacher-TF×M)

(6)

Xnew,i=Xold,i+D

(7)

TF=round[1+rand(0,1)]

(8)

式中:Xold,i是群體中第i個(gè)成員的當(dāng)前知識(shí)水平向量,Xnew,i是群體中第i個(gè)成員的更新知識(shí)水平向量,rand為0～1之間的隨機(jī)數(shù),Teacher表示適應(yīng)度最好的知識(shí)水平向量,TF為教學(xué)因子,通過(guò)式(8)隨機(jī)確定。每次計(jì)算后,如果個(gè)體的適應(yīng)度得到改善,則進(jìn)行個(gè)體更新,否則不更新。

2.2 學(xué)習(xí)階段

學(xué)生通過(guò)互動(dòng)來(lái)提高知識(shí),兩個(gè)個(gè)體之間的知識(shí)交換按式(9)進(jìn)行。每次迭代中,從群體中選擇兩個(gè)不同的個(gè)體,即Xi和Xj,計(jì)算目標(biāo)函數(shù)值(以求解最小化問(wèn)題為例),比較這兩個(gè)選定個(gè)體的值,如果f(Xnew)

(9)

式中:f(Xi)和f(Xj)分別是第i個(gè)和第j個(gè)成員的知識(shí)水平向量的目標(biāo)函數(shù)值。

3 求解PFSP的集成多策略教學(xué)優(yōu)化算法

3.1 LRV規(guī)則編碼

LRV規(guī)則[10]可以有效地將連續(xù)值映射為離散的工件排列,圖2a給出了無(wú)重復(fù)值的LRV排序,圖2b和圖2c給出了一個(gè)有重復(fù)值的排序及解決方案。因此,在LRV用于轉(zhuǎn)換工件排列之前,需通過(guò)插入此解決方案中未找到的其他值來(lái)刪除重復(fù)值。

(a) 正確的工件排序 (b) 錯(cuò)誤的工件排序

3.2 精英初始化種群

LIU等[3]首次通過(guò)引入偏度構(gòu)造出新的優(yōu)先級(jí)規(guī)則PRSKE,開(kāi)發(fā)出新的打破機(jī)制TBLJP1,并應(yīng)用于NEH啟發(fā)式算法,PRSKE和TBLJP1相結(jié)合后命名為NEHLJP1算法。本文初始種群的20%個(gè)體通過(guò)NEHLJP1算法產(chǎn)生,NEHLJP1算法步驟為:

步驟1:在新的優(yōu)先級(jí)規(guī)則PRSKE中,所有工件jb|b=1…n都按以下非遞增總和Cb來(lái)排序得到序列δ;Cb按下式計(jì)算:

Cb=AVGb+STDb+abs(SKEb)

(10)

(11)

(12)

(13)

式中:AVGb、STDb、abs(SKEb)分別為n個(gè)工件在m臺(tái)機(jī)器上加工時(shí)間的平均值、標(biāo)準(zhǔn)偏差和偏度的絕對(duì)值。

步驟2:令工件排序π={δ(1)},z=2;

步驟3:插入工件δ(z)到完工時(shí)間最小位置,若存在多個(gè)位置,則根據(jù)TBLJP1機(jī)制選取最終插入位置;

步驟4:令z=z+1,繼續(xù)執(zhí)行步驟3直到滿足終止條件,算法運(yùn)行結(jié)束。

其余個(gè)體采用反向?qū)W習(xí)法生成,具體步驟為:

步驟1:由于工件序列為1…n的序列,因此,設(shè)置工件編號(hào)的最小值為1,最大值為n,當(dāng)前工序的工件編號(hào)設(shè)為Ji,則Ji的反向?qū)W習(xí)編號(hào)為:

Jn=1+n-Ji

(14)

步驟2:對(duì)初始種群按照式(14)進(jìn)行如圖3所示的反向?qū)W習(xí)操作,生成對(duì)立種群;

圖3 初始種群反向?qū)W習(xí)

步驟3:將兩部分種群合并,計(jì)算合并后所有種群的適應(yīng)度值并從大到小進(jìn)行排列,選取前80%Np個(gè)體作為最終初始種群。

3.3 基于慣性權(quán)重的分組教學(xué)階段

在此階段,將學(xué)習(xí)者根據(jù)M分為兩組。第一組為頂級(jí)學(xué)習(xí)組(T),由成績(jī)高于M的學(xué)習(xí)者組成。第二組為弱勢(shì)學(xué)習(xí)組(W),由其余學(xué)習(xí)者組成。T組通過(guò)教師教學(xué)來(lái)提高知識(shí),該過(guò)程由式(15)表示。W組中的學(xué)習(xí)者根據(jù)M和教師來(lái)提高其知識(shí)水平,該過(guò)程用式(17)表示。

Xnew,i=Xold,i×W+rand(Teacher-Xold,i)

(15)

(16)

Xnew,i=(Xold,i+(rand-0.5)×1.5×(M-Xold,i))×W+D×W

(17)

D=rand×(Teacher-TF×M)

(18)

式中:W是根據(jù)式(16)計(jì)算的慣性權(quán)重參數(shù),其值從ωmax(0.9)非線性遞減到ωmin(0.4)。MaxIt是算法的最大迭代次數(shù),Wj是第j次迭代中的慣性權(quán)重。

3.4 正弦自適應(yīng)教學(xué)因子

基本TLBO算法中教學(xué)因子是2或1的隨機(jī)取值,這反映了兩種極端情況,即學(xué)習(xí)者100%或0%的從教師授課中學(xué)習(xí)。TF值較小時(shí),可在較小步長(zhǎng)中進(jìn)行局部搜索,但會(huì)導(dǎo)致全局收斂速度緩慢。TF值越大,表示全局搜索速度越快,但會(huì)降低局部搜索能力。因此,對(duì)基本TLBO算法的TF進(jìn)行正弦非線性自適應(yīng)的改進(jìn),既能保證算法局部搜索的精確性,也能平衡局部和全局的搜索速度。

(19)

式中:It為當(dāng)前迭代次數(shù),TFmax和TFmin分別為TF的最大值(取值為2)及最小值(取值為1)。

3.5 變鄰域搜索(VNS)

在改進(jìn)教學(xué)階段后采取多點(diǎn)變異的方式進(jìn)行局部搜索,采用如下兩種多點(diǎn)變異方式:

(1)三點(diǎn)交換變異算子。此算子通過(guò)交換從解中隨機(jī)選擇3個(gè)位置搜索比當(dāng)前最佳解具有更小完工時(shí)間的其他解,圖4a和圖4b分別為使用三點(diǎn)交換變異算子的前后順序。

(a) 使用三點(diǎn)交換變異算子前的位置順序

(2)兩點(diǎn)逆序變異算子。逆序變異算子是對(duì)兩個(gè)不同隨機(jī)位置之間的子序列進(jìn)行逆序排列,圖5a和圖5b分別為使用兩點(diǎn)逆序變異算子的前后順序。

(a) 使用兩點(diǎn)逆序變異算子前的位置順序

3.6 雙學(xué)習(xí)策略

學(xué)習(xí)階段是TLBO引導(dǎo)最優(yōu)解的關(guān)鍵階段,該階段可以保證算法精確的進(jìn)行全局搜索。但是,若成績(jī)均較低或?qū)W習(xí)水平基本相同的學(xué)生交流,相互學(xué)習(xí)將很難發(fā)揮作用。因此,引入雙學(xué)習(xí)策略來(lái)提高算法的尋優(yōu)精度,即在標(biāo)準(zhǔn)TLBO的學(xué)習(xí)階段進(jìn)化產(chǎn)生較優(yōu)個(gè)體后,再次從群體中隨機(jī)挑選兩個(gè)體進(jìn)行交流,該交流采用文獻(xiàn)[14]的學(xué)生混合變異,從而自適應(yīng)調(diào)配學(xué)生間的相互學(xué)習(xí),式(20)和式(21)為雙學(xué)習(xí)策略的更新表達(dá)式為:

(20)

(21)

(22)

(23)

式中:β為-1～1之間的隨機(jī)數(shù),It為當(dāng)前迭代次數(shù),θ(t)為高斯變異,G(0,1)表示標(biāo)準(zhǔn)高斯分布,δ(T)表示柯西變異,C(0,1)表示標(biāo)準(zhǔn)柯西分布。

3.7 雙局部搜索

雙局部搜索(double local search,DLS)為迭代貪婪算法(iterated greedy,IG)與改進(jìn)的引用插入方案(improved referenced insertion scheme,IRIS)協(xié)同搜索,表1為DLS偽代碼。

表1 DLS偽代碼

(1)基于IG的局部搜索(IGLS)。破壞和構(gòu)造過(guò)程是IG算法的關(guān)鍵部分。在破壞階段,從序列π中隨機(jī)選擇k個(gè)工件刪除,該過(guò)程產(chǎn)生兩個(gè)子序列。第一個(gè)序列為πD,由n-k個(gè)工件組成。第二個(gè)序列為πR,由k個(gè)工件組成,πR必須重新插入到πD中才能生成完整的候選序列。構(gòu)建階段需要利用改進(jìn)TLBO算法以貪婪的方式重新插入πR里。

通過(guò)大量實(shí)驗(yàn),針對(duì)不同規(guī)模問(wèn)題采取不同大小的破壞尺寸來(lái)重插入工件,具體改進(jìn)為:

(24)

(2)IRIS局部搜索。在IGLS之后,進(jìn)行IRIS局部搜索以進(jìn)一步提高解的質(zhì)量。關(guān)于IRIS,采用兩種非常有效的插入局部搜索策略。第一步是基于改進(jìn)的插入方案,此過(guò)程為插入工件πi(1…n)到目前序列π的所有可能位置,當(dāng)找到最佳改善位置時(shí),工件πi插入到該位置。對(duì)所有工件重復(fù)這些步驟。若有改進(jìn),將重新進(jìn)行局部搜索,直到?jīng)]有發(fā)現(xiàn)更好的解。第二步為RIS局部搜索[15]。在局部搜索之后,借鑒模擬退火算法中解的接收機(jī)制決定是否接受新解作為下一次迭代的解。其中,退火溫度T的值根據(jù)式(25)來(lái)確定。

(25)

式中:τp為調(diào)整的參數(shù),本文設(shè)為0.3。

3.8 集成多策略教學(xué)優(yōu)化算法運(yùn)行流程

為了求解PFSP,采用NEHLJP1算法和反向?qū)W習(xí)法結(jié)合的精英初始種群。將VNS操作、自適應(yīng)教學(xué)因子、改進(jìn)教學(xué)階段、雙學(xué)習(xí)策略和雙局部搜索與原始TLBO算法結(jié)合,集成多策略教學(xué)優(yōu)化算法(IMTLBO),圖6為IMTLBO流程圖。

圖6 IMTLBO流程圖

4 實(shí)驗(yàn)與分析

本文在CARLIER[16]、REEVES[17]和HELLER[18]提出的問(wèn)題上進(jìn)行實(shí)驗(yàn),算法編碼工具為MATLAB R2018b。運(yùn)行環(huán)境為:Win10,Intel Core i5處理器,4 G內(nèi)存,主頻2.5 GHz。為公平對(duì)比其它算法,對(duì)于Car和Reeves類問(wèn)題,本文算法種群數(shù)量設(shè)為40,迭代次數(shù)為200。對(duì)于Hel類問(wèn)題,種群數(shù)量設(shè)為20,迭代次數(shù)為100,與對(duì)比算法相比保持一致或更小,每個(gè)算例均運(yùn)行20次。對(duì)比指標(biāo)為最優(yōu)(BRE)和平均相對(duì)誤差(ARE),計(jì)算公式如下:

(26)

(27)

式中:Cbest和Cavg分別為運(yùn)行20次完工時(shí)間的最小值和平均值,C*為基準(zhǔn)實(shí)例的已知最優(yōu)解。

針對(duì)每類問(wèn)題選取不同算法比較,對(duì)比算法包括:基于貓群算法的改進(jìn)分布估計(jì)算法(EDA-CSO)[5]、變參數(shù)量子進(jìn)化算法(VP-QEA)[11]、混合回溯搜索算法(HBSA)[12]、高效的廣義正態(tài)分布算法(IHGNDO)[8]、混合共生生物搜索算法(HSOS)[4]、高效改進(jìn)的遺傳算法(HIEGA)[9]、混合鯨魚(yú)搜索算法(HWA)[7]。

4.1 Car類測(cè)試集比較

Car實(shí)例[16]均為小規(guī)模問(wèn)題,共有8種類型問(wèn)題,將IMTLBO與EDA-CSO、VP-QEA和HBSA算法對(duì)比。從表2分析得出(粗體表示各算法取得的最佳結(jié)果)。對(duì)于最優(yōu)值,所有算法均可在Car類實(shí)例取得最優(yōu)值。而對(duì)于平均值,只有IMTLBO的ARE均為0,可以體現(xiàn)提出IMTLBO求解的穩(wěn)定性。從上述分析來(lái)看,IMTLBO在小規(guī)模問(wèn)題上無(wú)論是精確性還是穩(wěn)定性都可以取得積極的成果。

表2 與其他算法針對(duì)Car實(shí)例的比較

4.2 Reeves類測(cè)試集比較

為驗(yàn)證IMTLBO的有效性,在Reeves的21個(gè)實(shí)例[17]進(jìn)行實(shí)驗(yàn)。將其與VP-QEA、IHGNDO和HSOS進(jìn)行比較,圖7和圖8分別給出了IMTLBO及對(duì)比算法的BRE和ARE的三維瀑布圖。在BRE的比較中,IMTLBO優(yōu)于所有對(duì)比算法。針對(duì)該指標(biāo)的平均值,IMTLBO的計(jì)算結(jié)果僅為0.21。在ARE的比較中,IMTLBO取得18個(gè)最優(yōu)值,數(shù)量上排名第一。針對(duì)該指標(biāo)的平均值,IMTLBO的計(jì)算結(jié)果為0.54,排名依舊第一。圖9為Reeves實(shí)例下不同規(guī)模的IMTLBO、IMTLBO-NL(無(wú)局部搜索)、IMTLBO-NG(無(wú)改進(jìn)相互學(xué)習(xí))和原始TLBO的迭代曲線,可以看出多種改進(jìn)策略的有效性,IMTLBO在Reeves實(shí)例下依舊具有優(yōu)勢(shì)。

圖7 與其他算法針對(duì)Reeves實(shí)例的BRE瀑布圖 圖8 與其他算法針對(duì)Reeves實(shí)例的ARE瀑布圖

圖9 Rec03、Rec09、Rec17、Rec19、Rec29、Rec33、Rec39和Rec41迭代曲線

此外,通過(guò)使用95%置信水平的配對(duì)t檢驗(yàn)來(lái)檢驗(yàn)比較算法之間的差異。表3給出了各個(gè)對(duì)比算法的統(tǒng)計(jì)比較,從表中可以得出結(jié)論,IMTLBO與所有比較的改進(jìn)算法在統(tǒng)計(jì)學(xué)上各不相同,有著明顯的統(tǒng)計(jì)顯著性差異。同時(shí),使用Cohen′s d 值表示效應(yīng)量大小(差異幅度大小),該值越大說(shuō)明算法之間差異越大(Cohen′s d 值表示效應(yīng)量大小時(shí),效應(yīng)量小、中、大的區(qū)分臨界點(diǎn)分別是:0.20、0.50和0.80),從表3可以看出Cohen′s d的值均大于0.80,呈現(xiàn)大的差異。通過(guò)以上結(jié)果分析表明,在比較的算法中,IMTLBO對(duì)于Reeves實(shí)例具有不錯(cuò)的性能,這使得它可以成為解決PFSP的現(xiàn)有算法的有力替代方案。

表3 Reeves實(shí)例上各種算法平均相對(duì)誤差配對(duì)t檢驗(yàn)分析結(jié)果-效應(yīng)量指標(biāo)

4.3 Hel類測(cè)試集比較

在Hel實(shí)例[18]中,將IMTLBO與HIEGA和HWA進(jìn)行比較,表4展示了各性能指標(biāo)值。對(duì)于Hel1實(shí)例,3種算法均可以求出新的上界值為515。對(duì)于Hel2實(shí)例,IMTLBO更新了新的上界為135,相比其它算法,各項(xiàng)指標(biāo)均達(dá)到最優(yōu),這表明了IMTLBO在求解Hel實(shí)例的有效性。為了進(jìn)一步驗(yàn)證IMTLBO的性能,將種群增加至40,迭代次數(shù)增加至200。在Hel1實(shí)例上,IMTLBO再一次更新了上界為514,從以上數(shù)據(jù)可以得出結(jié)論,IMTLBO能夠更加高效地求解Hel類問(wèn)題,改進(jìn)的多種策略是有效可行的。

表4 Hel1和Hel2實(shí)例各算法的比較

5 車間調(diào)度優(yōu)化實(shí)例的應(yīng)用

某汽車發(fā)動(dòng)機(jī)零部件公司的生產(chǎn)車間準(zhǔn)備制造100種不同型號(hào)的發(fā)動(dòng)機(jī)連桿部件,該部件主要有9道加工工序,該連桿部件制造為經(jīng)典的大規(guī)模PFSP,加工數(shù)據(jù)見(jiàn)文獻(xiàn)[6],目標(biāo)是求解這100種不同型號(hào)連桿的加工順序,使得總完工時(shí)間最短,從而提高企業(yè)生產(chǎn)效率。未優(yōu)化前,總完工時(shí)間是6284 s,利用IMTLBO優(yōu)化后,總完工時(shí)間為5320 s,大幅縮短了完工時(shí)間,新的帶有調(diào)度排序的甘特圖如圖10所示。優(yōu)化后,總的加工時(shí)間相比未優(yōu)化縮短15.34%左右,從生產(chǎn)實(shí)例中可以進(jìn)一步說(shuō)明IMTLBO對(duì)于實(shí)際生產(chǎn)的作用,再次提高生產(chǎn)效率,并增強(qiáng)了企業(yè)的核心競(jìng)爭(zhēng)力,進(jìn)一步說(shuō)明提出的IMTLBO的有效性。

圖10 最優(yōu)調(diào)度甘特圖

6 結(jié)論

本文提出了一種求解PFSP的IMTLBO算法,采用精英初始種群并集成多種改進(jìn)策略來(lái)提高算法的尋優(yōu)精度,提出了一種新的局部搜索DLS,并將其作為混合策略嵌入到TLBO算法中以進(jìn)一步增大其搜索范圍。使用三類典型基準(zhǔn)實(shí)例和一個(gè)大規(guī)模的實(shí)際工程問(wèn)題評(píng)估了提出算法的性能,仿真結(jié)果和算法比較表明了IMTLBO在搜索質(zhì)量和魯棒性方面的優(yōu)勢(shì)。在未來(lái)的研究中,將IMTLBO算法應(yīng)用于解決動(dòng)態(tài)環(huán)境下的其他調(diào)度問(wèn)題,如柔性維護(hù)活動(dòng)、機(jī)器故障和緊急作業(yè)等。