巴智勇,袁逸萍,裴國(guó)慶,王 波

(1.新疆大學(xué) 機(jī)械工程學(xué)院,新疆 烏魯木齊 830017;2.卓郎新疆智能機(jī)械有限公司,新疆 烏魯木齊 830057)

0 引言

作業(yè)車間調(diào)度問(wèn)題(Job Shop Scheduling Problem, JSP)不僅是典型的NP-hard問(wèn)題,還是管理領(lǐng)域中許多優(yōu)化問(wèn)題的通用模型,如項(xiàng)目計(jì)劃調(diào)度、岸橋調(diào)度優(yōu)化[3]、軌道列車時(shí)刻表調(diào)度優(yōu)化[4]等。另外,JSP模型能以一種明確的方式對(duì)問(wèn)題添加各種側(cè)約束和目標(biāo),使其應(yīng)用范圍不限于調(diào)度優(yōu)化問(wèn)題[5]。

學(xué)者們針對(duì)JSP提出了大量高效的求解方法,如數(shù)學(xué)規(guī)劃[6]、調(diào)度規(guī)則[7]、啟發(fā)式和元啟發(fā)式算法。由于JSP的NP-hard特性,精確求解方法只適合求解小規(guī)模問(wèn)題,難以應(yīng)用于實(shí)際生產(chǎn),當(dāng)前主流研究方向是采用近似方法求解JSP。近似求解方法包括大量經(jīng)典和新型的元啟發(fā)式方法,如粒子群優(yōu)化[8]、遺傳算法[9]、差分進(jìn)化[10]、蟻群算法[11]、細(xì)菌覓食算法[12]、教與學(xué)優(yōu)化算法[13]和灰狼優(yōu)化算法[14]等。然而,受限于基本理論和算法框架,單一的元啟發(fā)式算法在JSP上的求解效果并不理想,越來(lái)越多學(xué)者利用兩個(gè)或多個(gè)算法的互補(bǔ)特征開(kāi)發(fā)更為先進(jìn)的混合算法。REN等[15]提出一種混合局部搜索策略的遺傳算法求解JSP,通過(guò)引入多樣化的種群更新機(jī)制防止算法過(guò)早收斂;REHAB等[16]設(shè)計(jì)了基于鄰域多樣化強(qiáng)化策略的粒子群優(yōu)化算法,實(shí)現(xiàn)了對(duì)JSP解空間的廣泛搜索;PENG等[17]提出基于路徑重連的禁忌算法,采用路徑重連方法產(chǎn)生更多樣的候選解,同時(shí)在禁忌搜索中應(yīng)用更復(fù)雜的N7鄰域,改進(jìn)了多個(gè)JSP基準(zhǔn)算例的上界;CHENG等[5]提出一種基于機(jī)器最長(zhǎng)公共子序列的新型交叉算子,并設(shè)計(jì)基于質(zhì)量與相似性的種群替代策略來(lái)保持種群多樣性,更新了多個(gè)JSP基準(zhǔn)算例的已知最優(yōu)解;LIANG等[18]提出一種基于新型鄰域結(jié)構(gòu)的自適應(yīng)遺傳算法求解JSP,該算法的交叉概率和變異概率可以根據(jù)種群適應(yīng)度的離散程度進(jìn)行非線性和自適應(yīng)調(diào)整,實(shí)驗(yàn)結(jié)果表明算法在求解精度和收斂效率方面均有顯著提升;ALKHATEEB等[19]設(shè)計(jì)了一種集成模擬退火搜索的混合離散布谷鳥(niǎo)算法求解JSP,該算法首先采用基于對(duì)抗學(xué)習(xí)的方法生成多樣性的初始解,通過(guò)集成變鄰域搜索與萊維飛行方法實(shí)現(xiàn)廣泛的局部搜索,并設(shè)計(jì)了基于精英對(duì)抗的學(xué)習(xí)方法跳出局部最優(yōu)解;SHAHED等[20]提出性能驅(qū)動(dòng)的元啟發(fā)式切換方法求解JSP,該方法將多算子差分進(jìn)化和粒子群優(yōu)化集成在單一算法框架中,并引入性能驅(qū)動(dòng)的切換機(jī)制將搜索性能不佳的算法切換為其他可能的算法。

大多數(shù)先進(jìn)的JSP混合算法通過(guò)局部搜索組件來(lái)強(qiáng)化對(duì)有潛力解空間的深度搜索,而鄰域結(jié)構(gòu)作為局部搜索的核心,極大地影響著算法的效率和質(zhì)量。JSP局部搜索中較為常用的是基于關(guān)鍵路徑的工序塊鄰域結(jié)構(gòu),通過(guò)交換關(guān)鍵工序塊中任意兩工序可以形成新解。當(dāng)前研究者大多從減少鄰域結(jié)構(gòu)的規(guī)模和保證可行鄰域移動(dòng)兩方面構(gòu)建有效的鄰域結(jié)構(gòu)。VAN LAARHOVEN等[25]交換同一臺(tái)機(jī)器上相鄰關(guān)鍵工序的鄰域結(jié)構(gòu),記作N1,然而N1鄰域結(jié)構(gòu)不但規(guī)模大,而且包含大量非改進(jìn)的移動(dòng)操作;GRABOWSKI等[26]首先提出塊的概念,并將鄰域結(jié)構(gòu)定義為把一個(gè)內(nèi)部關(guān)鍵工序插入其塊首之前或塊尾之后的一種機(jī)制。此后,NOWICKI等[27]、BALAS等[28]和ZHANG等[29]提出更具競(jìng)爭(zhēng)力的N4,N5,N6,N7鄰域結(jié)構(gòu);趙詩(shī)奎等[30-32]通過(guò)分析機(jī)器上空閑時(shí)間的利用機(jī)理,擴(kuò)大了關(guān)鍵工序的移動(dòng)范圍,并在此基礎(chǔ)上進(jìn)一步提出多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)和近似評(píng)價(jià)方法。

本文結(jié)合JSP的特性,設(shè)計(jì)了一種3對(duì)工序精確聯(lián)動(dòng)的鄰域結(jié)構(gòu)。針對(duì)進(jìn)化算法中存在的種群早熟現(xiàn)象,設(shè)計(jì)了基于鄰域懲罰的交叉父本配對(duì)選擇算子與基于動(dòng)態(tài)懲罰閾值的種群更新策略,并將基于新型鄰域結(jié)構(gòu)的禁忌搜索嵌入進(jìn)化算法框架,設(shè)計(jì)了兼具全局與局部搜索能力的JSP求解算法。最后,將本文所提算法與其他先進(jìn)算法在基準(zhǔn)算例上進(jìn)行對(duì)比分析,驗(yàn)證了所提算法的有效性。

1 問(wèn)題描述

JSP問(wèn)題可描述為:n個(gè)工件J={J1,J2,…,Jn}在m臺(tái)機(jī)器M={M1,M2,…,Mn}上加工,每個(gè)工件Ji由m個(gè)連續(xù)工序{Oi,1,Oi,2,…,Oi,m}組成,相應(yīng)的加工機(jī)器集合為{σi,1,σi,2,…,σi,m},工序Oi,j在機(jī)器σi,j上的加工時(shí)間為pti,j,以最小化最大完工時(shí)間(Cmax)為優(yōu)化目標(biāo)。

對(duì)JSP問(wèn)題作以下假設(shè):

(1)所有工件零時(shí)刻達(dá)到,所有機(jī)器零時(shí)刻可用。

(2)同一工件同一時(shí)刻最多只能在一臺(tái)機(jī)器上加工,一臺(tái)機(jī)器同一時(shí)刻最多只能加工一個(gè)工件。

(3)工序在機(jī)器上一旦開(kāi)始加工就不能中斷。

(4)工序之間的運(yùn)輸時(shí)間和生產(chǎn)準(zhǔn)備時(shí)間都包含在加工時(shí)間中。

以最小化最大完工時(shí)間為優(yōu)化目標(biāo)建立JSP混合整數(shù)規(guī)劃模型,模型構(gòu)建過(guò)程中涉及的參數(shù)符號(hào)及說(shuō)明如下:

sti,j為工序Oi,j的開(kāi)工時(shí)間;

eti,j為工序Oi,j的完工時(shí)間;

JSP混合整數(shù)規(guī)劃模型為:

min(Cmax)=min(max(eti,j)),?Oi,j;

(1)

sti,j≥sti,j-1+pti,j-1,?{Oi,j,Oi,j-1};

(2)

eti,j=sti,j+pti,j,?Oi,j;

(3)

(sti,j-etr,s)yr,s,i,j(1-yi,j,r,s)+(str,s-eti,j)·

yi,j,r,s(1-yr,s,i,j)≥0,?{Oi,j,Or,s};

(4)

yi,j,r,s+yr,s,i,j=0;

(5)

sti,j≥0。

(6)

其中:式(1)為目標(biāo)函數(shù);式(2)為同一工件的緊鄰工序的順序約束;式(3)為計(jì)算工序的完工時(shí)間;式(4)與式(5)定義了同一機(jī)器上緊鄰兩道工序的加工時(shí)間不能重疊,即同一臺(tái)機(jī)器上后加工工序的開(kāi)始時(shí)間不能早于前一道工序的完工時(shí)間;式(6)定義了工序開(kāi)工時(shí)間的非負(fù)性。

2 多工序精確聯(lián)動(dòng)的鄰域結(jié)構(gòu)

鄰域結(jié)構(gòu)的本質(zhì)在于如何引導(dǎo)關(guān)鍵工序更充分地利用機(jī)器空閑時(shí)間,作為最有效的鄰域結(jié)構(gòu)之一,N7鄰域結(jié)構(gòu)雖然通過(guò)在較大范圍內(nèi)移動(dòng)單個(gè)關(guān)鍵工序?qū)υ桨府a(chǎn)生較強(qiáng)擾動(dòng)來(lái)生成鄰域解[33],但因缺乏足夠的理論分析,可能會(huì)產(chǎn)生大量無(wú)效的移動(dòng)操作。為此,本文對(duì)N7鄰域結(jié)構(gòu)進(jìn)行理論分析,提出關(guān)鍵工序無(wú)效移動(dòng)的條件并進(jìn)行證明,進(jìn)而對(duì)N7鄰域結(jié)構(gòu)進(jìn)行擴(kuò)展優(yōu)化。相關(guān)符號(hào)說(shuō)明如表1所示。

表1 符號(hào)表示及其說(shuō)明

2.1 N7鄰域無(wú)效移動(dòng)的理論分析

N7鄰域結(jié)構(gòu)存在4類關(guān)鍵工序移動(dòng)操作,如圖1所示,當(dāng)工序移動(dòng)后,采用近似求解[34]方法重新計(jì)算受影響工序新的頭尾長(zhǎng)度,則鄰域解的近似值C′max為受影響工序的頭尾長(zhǎng)度之和的最大值,若C′max大于原方案的最大完工時(shí)間Cmax,則可證明該工序移動(dòng)是無(wú)效的。

定理1關(guān)鍵塊中存在兩個(gè)工序u和v,分別為塊首與塊中工序,對(duì)于u與MS[v]之間的任意工序wi,若rJP[wi]+dJP[wi]+du≥rwi,則工序u移動(dòng)到工序v之后不會(huì)減少最大完工時(shí)間。

證明如圖2所示,將工序u移動(dòng)至v后,得到受影響工序{w1,…,wi,…,wn,v,u},采用近似評(píng)估方法重新計(jì)算各受影響工序的頭尾長(zhǎng)度和C′max,計(jì)算如下:

(7)

C′max=max{r′w1+q′w1,…,r′wi+q′wi,…,
r′wn+q′wn,r′v+q′v,r′u+q′u}。

(8)

移動(dòng)前,從工序wi角度,

Cmax=rwi+dwi+…+dwn+dv+qMS[v]。

(9)

移動(dòng)后,工序MP[u]與v之間的工序?qū)⒅苯踊蜷g接利用塊前原有機(jī)器空閑時(shí)間以及u移動(dòng)后產(chǎn)生的新的機(jī)器空閑時(shí)間,從工序wi的角度,近似最大完工時(shí)間C′max(wi)=r′wi+q′wi,由式(7)遞推可得:

r′wi≥rJP[wi]+dJP[wi];

(10)

q′wi≥qMS[v]+du+dv+dwn+…+dwi。

(11)

整理式(10)和式(11)可得

C′max(wi)≥rJP[wi]+dJP[wi]+du+dv+dwi+…
+dwn+qMS[v]。

(12)

若rJP[wi]+dJP[wi]+du≥rwi成立,則必有

C′max(wi)≥

rwi+dwi+…+dwn+dv+qMS[v]。

(13)

與式(9)相比,有C′max(wi)≥Cmax,則C′max≥Cmax必成立。證畢。

定理2關(guān)鍵塊中存在兩個(gè)工序u和v,分別為塊中與塊尾工序,若qJS[u]≥qJS[v],則工序u移動(dòng)到v之后不會(huì)減少最大完工時(shí)間。

證明如圖3所示,移動(dòng)后,從工序u的角度,近似最大完工時(shí)間C′max(u)=r′u+q′u,由式(7)遞推可得:

r′u≥rMP[u]+dMP[u]+dw1+…+dwn+dv;

(14)

q′u≥qJS[u]+du。

(15)

整理式(14)和式(15)可得C′max(u)≥rMP[u]+dMP[u]+du+dw1+…+dwn+dv+qJS[u],若qJS[u]≥qJS[v]成立,則

C′max(u)≥rMP[u]+dMP[u]+du+dw1+…
+dwn+dv+qJS[v]=Cmax,

(16)

C′max≥Cmax必成立。證畢。

定理3關(guān)鍵塊中存在兩個(gè)工序u和v,為塊首與塊尾工序,若rJP[wi]+dJP[wi]+du≥rwi且qJS[v]≤qJS[u],則工序u移動(dòng)到v之后不會(huì)減少最大完工時(shí)間。

證明如圖4所示,移動(dòng)后,從工序u的角度,近似最大完工時(shí)間C′max(u)=r′u+q′u,由式(7)遞推可得

r′u≥rJP[wi]+dJP[wi]+dwi+…+dwn+dv。

(17)

當(dāng)rJP[wi]+dJP[wi]+du≥rwi成立時(shí),由式(17)可得

r′u≥rwi+(dwi+…+dwn+dv)-du

=rv+dv-du。

(18)

由式(7)推得q′u≥qJS[u]+du必成立,結(jié)合式(18)可得C′max(u)≥rv+dv+qJS[u],若qJS[v]≤qJS[u],則C′max(u)≥rv+dv+qJS[v]>Cmax,有C′max≥Cmax必成立。證畢。

定理4關(guān)鍵塊中存在兩個(gè)工序u和v,分別為塊中與塊尾工序,對(duì)于u與MS[v]之間的任意工序wi,若qJS[wi]+dv≥qwi-dwi,則工序v移動(dòng)到u之前不會(huì)減少最大完工時(shí)間。

證明如圖5所示,將工序v移動(dòng)到u之前,得到受影響工序{v,u,w1,…,wi,…,wn},各自近似頭尾長(zhǎng)度計(jì)算如下:

(19)

從工序wi的角度來(lái)看,移動(dòng)后的最大完工時(shí)間C′max(wi)=r′wi+q′wi。由式(19)推導(dǎo)得到工序wi的近似頭尾長(zhǎng)度:

r′wi≥qMP[u]+dMP[u]+dv+du+dw1+…
+dwi-1=rwi+dv;

(20)

q′wi≥qJS[wi]+dwi。

(21)

結(jié)合式(20)和式(21)可得C′max(wi)≥rwi+dv+qJS[wi]+dwi,若qJS[wi]+dv≥qwi-dwi成立,則C′max(wi)≥rwi+(qwi-dwi)+dwi=rwi+qwi=Cmax必成立,進(jìn)一步可得C′max≥Cmax。證畢。

定理5關(guān)鍵塊中存在兩個(gè)工序u和v,分別為塊首與塊中工序,若rJP[v]+dJP[v]≥ru,則將工序v移動(dòng)到工序u之前不會(huì)減少最大完工時(shí)間。

證明如圖6所示,從工序v的角度,移動(dòng)后的近似最大完工時(shí)間C′max(v)=r′v+q′v,由式(19)推導(dǎo)可得:

r′v≥rJP[v]+dJP[v];

(22)

q′v≥qMS[v]+dwn+…+dw1+du+dv。

(23)

當(dāng)rJP[v]+dJP[v]≥ru成立時(shí),結(jié)合式(22)和式(23)可得C′max(v)≥ru+du+dw1+…+dwn+dv+qMS[v]=Cmax,進(jìn)一步可得C′max≥Cmax。證畢。

定理6關(guān)鍵塊中存在兩個(gè)工序u和v,分別為塊首與塊尾工序,對(duì)于MP[u]與v之間的任意工序wi,如果qJS[wi]+dv≥qwi-dwi且rJP[v]+dJP[v]≥ru,則將工序v移動(dòng)至工序u之前不會(huì)減少Cmax。

證明如圖7所示,移動(dòng)后,從工序v的角度,近似最大完工時(shí)間C′max(v)=r′v+q′v,由式(19)推導(dǎo)得

q′v≥qJS[wi]+(dwi+…+dw1+du)+dv。

(24)

若qJS[wi]+dv≥qwi-dwi成立,則q′v≥qwi+(dwi-1+…+dw1+du)=qu必成立。由式(19)推導(dǎo)得r′v≥rJP[v]+dJP[v],若rJP[v]+dJP[v]≥ru成立,則r′v≥ru必成立。由以上結(jié)果可得C′max(v)≥ru+qu=Cmax必成立,進(jìn)一步可得C′max≥Cmax。證畢。

可見(jiàn),N7鄰域結(jié)構(gòu)中參與移動(dòng)的工序數(shù)量多且移動(dòng)范圍廣,能從多個(gè)角度利用機(jī)器空閑時(shí)間,但也存在不能減少Cmax的無(wú)效移動(dòng)操作。以上基礎(chǔ)理論分析為識(shí)別N7鄰域結(jié)構(gòu)中的無(wú)效移動(dòng)操作提供了理論支撐,同時(shí)也為更加復(fù)雜的多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)設(shè)計(jì)指明了方向。

2.2 多工序精確聯(lián)動(dòng)鄰域

本文將文獻(xiàn)[32]提出的多工序聯(lián)動(dòng)的觸發(fā)條件與N7鄰域無(wú)效移動(dòng)判定條件結(jié)合,構(gòu)建更為強(qiáng)化的鄰域結(jié)構(gòu)PN7+2MT,具體實(shí)現(xiàn)如下:

情形1塊首工序u移動(dòng)至塊尾工序v后,聯(lián)動(dòng)工序的移動(dòng)方式如圖8所示,具體步驟如下:

(1)令msu=MS[u],如果JP[msu]≠?,且滿足rJP[msu]+dJP[msu]>rMP[u]+dMP[u],則按照工序的最早完工時(shí)間查找工序msu的某一道工件前序工序msu′,如果存在工序msu′滿足條件MP[msu′]≠?,且rMP[msu′]+dMP[msu′]=r′msu,則交換工序MP[msu′]和msu′。

(2)如果JS[u]≠?,且滿足qJS[u]>qMS[v],則按照工序的最晚開(kāi)工時(shí)間查找工序u的工件維某一道后序工序u′,如果存在工序u′滿足條件MS[u′]≠?,且q′u-d′u=qMS[u′],則交換工序u′和MS[u′]。

情形2塊首工序u移動(dòng)到塊中工序v之后,聯(lián)動(dòng)工序的移動(dòng)方式如圖9所示,具體步驟如下:

(1)令msu=MS[u],如果JP[msu]≠?,且滿足rJP[msu]+dJP[msu]>rMP[u]+dMP[u],則按照工序的最早完工時(shí)間查找工序msu的某一道工件前序工序msu′,如果存在工序msu′滿足條件MP[msu′]≠?,且rMP[msu′]+dMP[msu′]=r′msu,則交換工序MP[msu′]和msu′。

(2)若MS[u]與MS[v]之間的任意工序w均滿足rJP[w]+dJP[w]+duqMS[v]均成立,則按照工序的最晚開(kāi)工時(shí)間查找工序u的某一道工件后序工序u′,如果存在工序u′滿足條件MS[u′]≠?,且qu′-du′=qMS[u′],則交換工序u′和MS[u′]。

情形3塊中工序u后移到塊尾工序v之后,聯(lián)動(dòng)工序的移動(dòng)方式如圖10所示,具體步驟如下:

(1)令msu=MS[u],如果JP[msu]≠?,且滿足rJP[msu]+dJP[msu]>ru,則按照工序的最早完工時(shí)間查找工序msu的某一道工件前序工序msu′,如果工序msu′滿足條件MP[msu′]≠?,且rMP[msu′]+dMP[msu′]=r′msu,則交換工序MP[msu′]和msu′。

(2)如果JS[u]≠?,且滿足qJS[u]>qMS[v],則按照工序的最晚開(kāi)工時(shí)間查找工序u的某一道工件的后序工序u′,如果存在工序u′滿足條件MS[u′]≠?,且qu′-du′=qMS[u′],則交換工序u′和MS[u′]。

情形4塊尾工序v移動(dòng)到塊首工序u之前,聯(lián)動(dòng)工序的移動(dòng)方式如圖11所示,具體步驟如下:

(1)令mpv=MP[v],如果JS[u]≠?,且滿足qJS[mpv]>qMS[v],則按照工序的最晚開(kāi)工時(shí)間查找工序mpv的某一道工件后序工序mpv′,如果存在工序mpv′滿足條件MS[mpv′]≠?,且qmpv′-dmpv=qMS[mpv′],則交換工序mpv′和MS[mpv′]。

(2)如果JP[v]存在,且滿足rJP[v]+dJP[v]>rMP[u]+dMP[u],則按照工序的最早完工時(shí)間查找工序v的某一道工件前序工序v′,如果存在工序v′滿足條件MP[v′]≠?,且rMP[v′]+dMP[v′]=r′v,則交換工序MP[v′]和v′。

情形5塊尾工序v移動(dòng)到塊中工序u之前,聯(lián)動(dòng)工序的移動(dòng)方式如圖12所示,具體步驟如下:

(1)令mpv=MP[v],如果JS[u]≠?,且滿足qJS[mpv]>qMS[v],則按照工序的最晚開(kāi)工時(shí)間查找工序mpv的某一道工件的后序工序mpv′,如果存在工序mpv′滿足條件MS[mpv′]≠?,且qmpv′-dmpv=qMS[mpv′],則交換工序mpv′和MS[mpv′]。

(2)對(duì)于MP[u]與v之間的任意工序w滿足qJS[w]+dvrMP[u]+dMP[u]同時(shí)成立,則按照工序的最早完工時(shí)間查找工序v的某一道工件的前序工序v′,如果存在工序v′滿足條件MP[v′]≠?,且rMP[v′]+dMP[v′]=r′v,則交換工序MP[v′]和v′。

情景6塊中工序v移動(dòng)到塊首u(yù)之前,聯(lián)動(dòng)工序的移動(dòng)方式如圖13所示,具體步驟如下:

(1)令mpv=MP[v],如果JS[u]≠?,且滿足qJS[mpv]>qMS[v],則按照工序的最晚開(kāi)工時(shí)間查找工序mpv的某一道工件的后序工序mpv′,如果存在工序mpv′滿足條件MS[mpv′]≠?,且qmpv′-dmpv=qMS[mpv′],則交換工序mpv′和MS[mpv′]。

(2)如果JP[v]存在,且滿足rJP[v]+dJP[v]>rMP[u]+dMP[u],則按照工序的最早完工時(shí)間查找工序v的某一道工件的前序工序v′,如果存在工序v′滿足條件MP[v′]≠?,且rMP[v′]+dMP[v′]=r′v,則交換工序MP[v′]和v′。

2.3 鄰域結(jié)構(gòu)復(fù)雜度分析

對(duì)于n個(gè)工件m臺(tái)機(jī)器的JSP,根據(jù)N7鄰域結(jié)構(gòu)的4類移動(dòng)方式,當(dāng)工序塊有n個(gè)工序時(shí),總的交換次數(shù)最多,為(n-1)×4×m,其計(jì)算復(fù)雜度為O(nm)。對(duì)于PN7+2MT,在N7鄰域結(jié)構(gòu)的基礎(chǔ)上查找另外兩對(duì)交換工序,兩次交換的最大查找次數(shù)為2×(m-1),同時(shí)因?yàn)閴K首工序后移與塊尾工序前移產(chǎn)生的聯(lián)動(dòng)工序交換只需計(jì)算一次,所以PN7+2MT的最多查找次數(shù)為(n-1)×2×m×2×(m-1)+(n-1)×2×m+2×m×2×(m-1),計(jì)算復(fù)雜度為O(nm2)。

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

3.1 算法框架

進(jìn)化算法不但具有良好的理論研究基礎(chǔ),而且在工程領(lǐng)域應(yīng)用廣泛。然而進(jìn)化算法偏重全局搜索,需要與基于問(wèn)題特征的局部搜索集成才能獲得高質(zhì)量的解。禁忌搜索算法側(cè)重于局部搜索,可以很好地結(jié)合JSP特征信息的鄰域結(jié)構(gòu),引導(dǎo)算法進(jìn)行有效搜索。為了將全局搜索和局部搜索相結(jié)合,本文提出一種基于多工序精確聯(lián)動(dòng)鄰域結(jié)構(gòu)的混合進(jìn)化算法(Hybrid Evolutionary Algorithm with Multi-operation precise joint movement Neighborhood Structure,HEA-MNS)。在進(jìn)化算法部分引入基于新型個(gè)體距離的配對(duì)選擇算子,防止近親繁殖;然后,采用基于動(dòng)態(tài)懲罰閾值的種群更新機(jī)制構(gòu)建下一代種群,通過(guò)動(dòng)態(tài)調(diào)整懲罰閾值實(shí)現(xiàn)集中性與多樣性搜索的動(dòng)態(tài)平衡。禁忌搜索采用多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)PN7+2MT對(duì)大鄰域空間進(jìn)行精確搜索,提高了HEA-MNS的局部搜索能力。

算法1為HEA-MNS的基本框架,算法首先從一個(gè)初始隨機(jī)種群開(kāi)始,采用禁忌搜索優(yōu)化每個(gè)染色體(4行～6行);然后,采用配對(duì)選擇算子選擇交叉父本,通過(guò)交叉算子生成新的子代染色體(8行～9行);再次,采用禁忌搜索對(duì)新生成的子代染色體進(jìn)行優(yōu)化(10行～11行);最后,采用種群更新算子從原種群與子代染色體的集合中選擇下一代種群(12行)。下面詳細(xì)介紹HEA-MNS的主要組件。

算法1HEA-MNS偽代碼。

1 輸入:J,M,D。

2 輸出:算法終止時(shí)的最優(yōu)調(diào)度方案s*與完工期Cmax。

3 初始化種群P={s1,…,sp}

4 For i={1,…,p} do

5 si←Tabu_Search(si)

6 end for

7 While終止條件未滿足do

8 (sj,sk)= Select_Parents(P)

9 (sp+1,sp+2)←Crossover(sj,sk)

10 sp+1← Tabu_Search(sp+1)

11 sp+2← Tabu_Search(sp+2)

12 {s1,…,sp}←Population_Updating(s1,…,sp,sp+1,sp+2)

13 end while

14 s*=argmim{f(si)|i=1,…,p}

15 Return s*

3.2 編碼與解碼

本文采用文獻(xiàn)[35]的編碼方法,即一條染色體由m個(gè)基因串組成,每個(gè)基因串表示各工件在機(jī)器上的加工序列,基因串的工序基因用相應(yīng)的工件序號(hào)表示,因此染色體的長(zhǎng)度為n×m。

對(duì)于JSP,以最大完工時(shí)間為優(yōu)化目標(biāo)的最優(yōu)調(diào)度必在主動(dòng)調(diào)度集合中[36],因此本文選擇GONG等[37]提出的插入式貪婪主動(dòng)解碼算法。

3.3 禁忌搜索

作為車間調(diào)度問(wèn)題最有效的求解方法之一,禁忌搜索能夠有效引導(dǎo)算法深入搜索有潛力的區(qū)域,為了加強(qiáng)局部搜索的擾動(dòng)強(qiáng)度和有效性,本文采用第2章提出的精確多工序聯(lián)動(dòng)鄰域結(jié)構(gòu)PN7+2MT生成鄰域解。

(1)移動(dòng)評(píng)估 當(dāng)一組可行鄰域解被構(gòu)造出來(lái)后,每個(gè)鄰域解都需要被重新計(jì)算或評(píng)估其最大完工時(shí)間,本文采用趙詩(shī)奎等[32]提出的快速評(píng)估方法對(duì)鄰域解進(jìn)行近似計(jì)算。

(2)禁忌表 禁忌表作為禁忌搜索的短期記憶,可以有效避免搜索過(guò)程出現(xiàn)死循環(huán)。算法采用與TSSA(tabu search and simulatecl annealing)算法[38]相同的禁忌表結(jié)構(gòu)。具體來(lái)說(shuō),如果一次移動(dòng)包含交換工序u和v,則u和v之間的所有工序及其位置都存儲(chǔ)在禁忌表中。禁忌表長(zhǎng)度根據(jù)決策變量規(guī)模動(dòng)態(tài)調(diào)整[38],即在兩個(gè)給定的極值[Lmin,Lmax]之間隨機(jī)選取。

(3)鄰域解選擇 在每次迭代中,禁忌搜索過(guò)程首先考慮不在禁忌表中的移動(dòng),并從中選擇產(chǎn)生最優(yōu)目標(biāo)值的鄰域解。若兩種或兩種以上的移動(dòng)都具有相同的最優(yōu)目標(biāo)值,則從中隨機(jī)選擇一個(gè)移動(dòng);如果一個(gè)移動(dòng)能夠帶來(lái)比當(dāng)前最優(yōu)解更好的解,且該移動(dòng)在禁忌表中,則對(duì)該移動(dòng)進(jìn)行特赦。

(4)終止準(zhǔn)則 當(dāng)找到最優(yōu)解或禁忌搜索的連續(xù)未改善迭代次數(shù)超過(guò)給定極限值時(shí),禁忌搜索過(guò)程停止。

3.4 基于鄰域懲罰的配對(duì)選擇與交叉操作

在進(jìn)化算法中,配對(duì)選擇操作的主要任務(wù)是從父代種群中選擇用于生成子代個(gè)體的配對(duì)父本,其選擇標(biāo)準(zhǔn)在很大程度上影響算法的收斂性與多樣性。為了增強(qiáng)算法產(chǎn)生多樣化后代的能力,本文提出基于鄰域懲罰的配對(duì)選擇操作,其基本思想為:算法隨機(jī)從父代種群中選取一個(gè)染色體,另一個(gè)染色體從其懲罰鄰域外隨機(jī)選擇,如果懲罰鄰域外無(wú)其他染色體,則從懲罰鄰域內(nèi)選擇距離最遠(yuǎn)的一個(gè)染色體。為方便后續(xù)論述,本文給出以下定義:

定義1兩個(gè)解之間的距離。對(duì)于給定的兩個(gè)解x=(x1,…,xi,…,xm)和y=(y1,…,yi…,ym),解x與y的距離為各機(jī)器上工序排列的偏差距離的總和,記作Dpos(x,y),

Dpos(x,y)=

(25)

式中:n和m分別為工件數(shù)量與機(jī)器數(shù)量;xi和yi分別為解x與y的第i機(jī)器上的工序序列;pos(a,b[])為a在b序列中的位置。

定義2解與種群的距離。對(duì)于給定的種群P={s1,…,sp}與一個(gè)解I,I與種群P的距離為I與種群P中所有個(gè)體距離的最小值,記為DCI(I,P),

DCI(I,P)=min{Dpos(I,sj)|sj∈P}。

(26)

定義3種群的密度。對(duì)于給定的種群P={s1,…,sp},種群P的密度為種群的各個(gè)解si相對(duì)于P{si}距離的平均值,記作DCIav(P),

(27)

算法2中給出了交叉算子的偽代碼,對(duì)于當(dāng)前種群P={s1,…,sp},采用以下規(guī)則選取交叉父本{sj,sk}。首先,根據(jù)當(dāng)前種群的密度設(shè)定父本選擇的懲罰距離D,并初始化候選集合Candidate與懲罰集Penalized(3行),從當(dāng)前種群Candidate中隨機(jī)選擇一個(gè)染色體作為第1個(gè)父本sj,將其從Candidate刪除(4行～5行);然后,通過(guò)不斷迭代,將與父本sj距離小于D的染色體從Candidate刪除,并添加至Penalized中(6行～11行);最后,若Candidate不為空,則從Candidate中隨機(jī)選擇一個(gè)染色體作為第2個(gè)父本,否則從Penalized中選擇距離sj最遠(yuǎn)的染色體作為第2個(gè)父本(12行～16行)。

算法2基于動(dòng)態(tài)閾值的父本選擇算子。

1 輸入:種群P={s1,…,sp}。

2 輸出:{sj,sk}。

4 從Candidate中隨機(jī)選擇一個(gè)染色體sj

5 Candidate=Candidate{sj}

6 foreach I∈P{sj} do

7 if Dpos(I,sj)

8 Candidate=Candidate{I},

9 Penalized=Penalized∪{I}

10 end if

11 end foreach

12 if Candidate≠? then

13 從Candidate中隨機(jī)選擇一個(gè)個(gè)體sk

14 else

15 sk= argmax{Dpos(si,sj)|si∈Penalized}

16 end if

17 return{sj,sk}

作為混合進(jìn)化算法的重要組件,交叉算子不僅要生成多樣化的子代,還要將父輩的精英成分遺傳給子代,因此本文不再采用單一的交叉方式,而是將基于最長(zhǎng)相同子序列的交叉算子[5]與基于機(jī)器工序串的交叉算子[15]混合使用。每次交叉均隨機(jī)選擇一種交叉方法進(jìn)行染色體重組。

3.5 種群更新算子

為進(jìn)一步增強(qiáng)種群的多樣性,設(shè)計(jì)了一種基于動(dòng)態(tài)懲罰閾值的種群更新策略。該策略的主要設(shè)計(jì)原則是在算法的初始階段通過(guò)設(shè)定較大的懲罰閾值誘導(dǎo)更多樣化的搜索,而在算法后期通過(guò)設(shè)定較小的懲罰閾值來(lái)強(qiáng)化集中搜索。

算法3給出了種群更新算法的偽代碼,對(duì)于禁忌算法優(yōu)化的兩個(gè)子代{sp+1,sp+2}與當(dāng)前種群P={s1,…,sp},本文采用以下規(guī)則來(lái)確定sp+1,sp+2是否應(yīng)該替換原有種群的個(gè)體:首先,計(jì)算種群更新的懲罰閾值(3行),將{sp+1,sp+2}與P合并構(gòu)建初始候選集合Candidate,選擇目標(biāo)值最小的個(gè)體添加到新種群中,并將該個(gè)體從Candidate中刪除(4行～7行),初始化懲罰解集合Penalized(8行);然后,不斷迭代,直到新種群的規(guī)模與原種群相同(9行～26行)。新種群個(gè)體選擇過(guò)程如下:首先,計(jì)算候選集合中個(gè)體與新種群的距離(11行),然后將距離小于選擇閾值D的個(gè)體從Candidate中刪除并添加至Penalized(12行～16行);最后,若Candidate不為空,則從Candidate中選取目標(biāo)值最優(yōu)的個(gè)體進(jìn)入新種群,否則從Penalized選擇與新種群距離最遠(yuǎn)的個(gè)體進(jìn)入新種群(17行～26行)。

算法3種群更新算子。

1 輸入:種群P={s1,…,sp}和{sp+1,sp+2}。

2 輸出:新種群NewPop。

3 計(jì)算當(dāng)前種群的懲罰閾值D

4 初始化候選集合Candidate=P∪{sp+1,sp+2}

5 選擇最優(yōu)解Best=argmin{f(si)|si∈Candidate}

6 構(gòu)建新種群NewPop={best}

7 Candidate=Candidate{best}

8 初始化懲罰解集合Penalized=?

9 while|NewPop|

10 foreach I∈Candidate do

11 I.dci=DCI(I,NewPop)

12 if I.dci

13 Candidate=Candidate{I}

14 Penalized=Penalized∪{I}

15 end if

16 end foreach

17 if Candidate≠? then

18 NewSelected =argmin{f(si)|si∈Candidate}

19 else

20 foreach I∈Penalized do

21 I.dci=DCI(I,NewPop)

22 end foreach

23 NewSelected=argmax{s.dci|s∈Penalized}

24 end if

25 NewPop=NewPop∪{NewSelected}

26 end while

27 Return NewPop

當(dāng)懲罰閾值D較大時(shí)有利于增強(qiáng)搜索的廣度,D值較小時(shí)有利于在有潛力的區(qū)域進(jìn)行集中搜索。綜合考慮以上特征,將D設(shè)定為隨算法運(yùn)行時(shí)間線性減少的動(dòng)態(tài)值,使算法逐漸從多樣化搜索轉(zhuǎn)化為集中化搜索,

(28)

式中:Tcur為當(dāng)前運(yùn)行時(shí)間;Ttotal為算法設(shè)定的最大運(yùn)行時(shí)間;β為縮放系數(shù),β=0.5;P0為初始種群。

3.6 算法復(fù)雜度分析

假設(shè)種群個(gè)體數(shù)為N、工件數(shù)量為n、機(jī)器數(shù)量為m。算法步驟包括種群的初始化、交叉父本匹配選擇操作、交叉操作、禁忌搜索操作、解碼操作、種群更新操作。算法采用隨機(jī)生成方法構(gòu)建初始種群,該過(guò)程的時(shí)間復(fù)雜度為O(n×m×N);由于交叉父本匹配選擇操作與種群更新操作均需計(jì)算種群密度,根據(jù)個(gè)體之間的距離計(jì)算公式可得其在最壞情況下的復(fù)雜度為O(n2×m),個(gè)體與種群其他個(gè)體的距離最小值計(jì)算的時(shí)間復(fù)雜度為O(N×n2×m),進(jìn)而可得種群密度的計(jì)算復(fù)雜度為O(N2×n2×m);交叉匹配選擇操作將種群隨機(jī)分為兩組的時(shí)間復(fù)雜度為O(N),最壞情況下,查找另一組中距離第1個(gè)父本最遠(yuǎn)個(gè)體的時(shí)間復(fù)雜度為O(N);算法隨機(jī)執(zhí)行兩種交叉操作,每種交叉操作均需訪問(wèn)父染色體兩次,同時(shí)每次迭代只執(zhí)行1次交叉操作,因此交叉操作的時(shí)間復(fù)雜度為O(n×m);禁忌搜索操作中鄰域操作的時(shí)間復(fù)雜度為O(n×m2),近似評(píng)價(jià)的時(shí)間復(fù)雜度為O(n×m),因此禁忌搜索操作的時(shí)間復(fù)雜度為O(n2×m3);在解碼過(guò)程中,每道工序需要從前后獲取空閑時(shí)間段,因此最壞情況下,該操作的時(shí)間復(fù)雜度為O(n2×m);在種群更新過(guò)程中,由于每次迭代只產(chǎn)生兩個(gè)子代個(gè)體,需要重新計(jì)算子代個(gè)體與原種群個(gè)體之間的距離,該過(guò)程的時(shí)間復(fù)雜度為O(N×n2×m),依次添加個(gè)體進(jìn)入新種群過(guò)程的時(shí)間復(fù)雜度為O(N2)。由于初始種群構(gòu)建與初始種群密度計(jì)算只執(zhí)行一次,對(duì)算法整體性能影響不大,從以上分析可知,算法迭代過(guò)程中在禁忌搜索操作與種群更新操作上消耗的時(shí)間最多。

4 算法測(cè)試

HEA-MNS采用C++編程實(shí)現(xiàn),并在Linux操作系統(tǒng)的計(jì)算機(jī)(CPU主頻2.3 GHz,內(nèi)存16 GB)上使用g++編譯運(yùn)行。算法參數(shù)設(shè)置如下:算法執(zhí)行的總時(shí)間為10 min,種群規(guī)模為50,禁忌搜索的終止條件為未改進(jìn)迭代次數(shù)達(dá)到1 000次;禁忌長(zhǎng)度在兩個(gè)極值之間隨機(jī)選取,極值的設(shè)置分別為L(zhǎng)min=0.5(10+n/m)和Lmax=1.5(10+n/m),其中n和m分別為工件數(shù)和機(jī)器數(shù)。考慮到HEA-MNS的隨機(jī)特性,本文獨(dú)立求解每個(gè)問(wèn)題算例10次。測(cè)試實(shí)驗(yàn)包括兩組JSP基準(zhǔn)算例,均來(lái)源于JSP基準(zhǔn)算例庫(kù)(http://jobshop.jjvh.nl/)。第1組為L(zhǎng)AWRENCE[39]設(shè)計(jì)的40個(gè)算例(LA01～LA40),第2組為ADAMS等[40]設(shè)計(jì)的5個(gè)基準(zhǔn)算例(ABZ05～ABZ09)。

4.1 鄰域結(jié)構(gòu)測(cè)試

ImpNS=

(29)

采用N5,sCET+2MT,N6,N7,PN7+2MT 5種鄰域結(jié)構(gòu)對(duì)45個(gè)JSP算例的測(cè)試結(jié)果進(jìn)行統(tǒng)計(jì),如表2所示。表中算例順序按照PN7+2MT鄰域結(jié)構(gòu)的相對(duì)改進(jìn)百分比Imp降序排列得到,并以該順序?qū)λ憷M(jìn)行編號(hào)。按照該順序,繪制sCET+2MT,N6,N7,PN7+2MT 4種鄰域結(jié)構(gòu)的相對(duì)改進(jìn)百分比曲線,如圖14所示。對(duì)于所有45個(gè)JSP算例,PN7+2MT的相對(duì)改進(jìn)百分比曲線均位于N6與N7鄰域結(jié)構(gòu)之上,說(shuō)明多工序精確聯(lián)動(dòng)可有效改善鄰域結(jié)構(gòu)性能。與sCET+2MT鄰域結(jié)構(gòu)相比,PN7+2MT的相對(duì)改進(jìn)百分比曲線具有明顯優(yōu)勢(shì),說(shuō)明更大范圍的工序參與聯(lián)動(dòng)操作可以大幅提升鄰域結(jié)構(gòu)的搜索能力。

表2 4種鄰域結(jié)構(gòu)的相對(duì)改進(jìn)百分比對(duì)比

同一規(guī)模下,對(duì)各算例應(yīng)用不同鄰域結(jié)構(gòu)產(chǎn)生鄰域解的數(shù)量(SNS)av進(jìn)行統(tǒng)計(jì)分析,結(jié)果如表3所示,其中:CR表示PN7+2MT相對(duì)于N7鄰域結(jié)構(gòu)的鄰域解數(shù)量的消減率,計(jì)算公式如式(30)。因?yàn)閟CET+2MT鄰域結(jié)構(gòu)是在N5的基礎(chǔ)上聯(lián)動(dòng)另外兩對(duì)工序,其鄰域解的數(shù)量相同,所以只列出N5的鄰域解數(shù)量。從表3可見(jiàn),PN7+2MT的鄰域解數(shù)量大于N5和N6,表明PN7+2MT對(duì)解空間具有廣泛搜索的能力。相對(duì)于N7,PN7+2MT的鄰域規(guī)模減小約14%,說(shuō)明所提無(wú)效移動(dòng)判定條件可有效減少鄰域規(guī)模。

表3 4種鄰域結(jié)構(gòu)的鄰域解數(shù)量對(duì)比

(30)

4.2 算法性能測(cè)試

從LA算例集中選取10個(gè)求解比較困難的算例測(cè)試算法性能,結(jié)果如表4所示,表中參數(shù)的詳細(xì)描述如下:Best為10次求解結(jié)果的最優(yōu)值;Mav為10次求解結(jié)果的平均值;Tav(s)為10次獲得求解結(jié)果的平均用時(shí)(單位:s);MRE為求解結(jié)果UBsolve與已知下界LB相對(duì)偏差的平均值,其中相對(duì)偏差RE的計(jì)算如式(31)所示。表4的4個(gè)對(duì)比算法分別為文獻(xiàn)[41]具有局部搜索策略和多交叉算子的改進(jìn)遺傳算法(Multi-Crossover Local Search Genetic Algorithm,MXLSGA)、文獻(xiàn)[42]基于多算子通信的序列禁忌搜索差分進(jìn)化(Multi-operator Communication based Differential Evolution with sequential Tabu Search approach,MCDE/TS)算法、文獻(xiàn)[21]基于無(wú)延遲調(diào)度路徑重連與回溯禁忌搜索算法(Path Relinking based on Non-Delay scheduling and Backtracking Tabu Search algorithm,PRND/BTS)、文獻(xiàn)[22]基于切換策略的混合進(jìn)化算法(Switching strategy-based Hybrid Evolutionary Algorithms,SHEA)。

表4 10個(gè)困難LA算例測(cè)試結(jié)果與其他算法結(jié)果比較

RE=(UBsolve-LB)/LB×100

(31)

從表4可知,HEA-MNS求得的最優(yōu)結(jié)果Best與LB相對(duì)偏差的平均值b-MRE為0.01,且均低于其余4種算法的b-MRE。同時(shí),HEA-MNS對(duì)其中9個(gè)算例的最優(yōu)結(jié)果均優(yōu)于或等于其他4種算法,僅對(duì)LA29算例的求解結(jié)果劣于SHEA算法。HEA-MNS求得的最優(yōu)結(jié)果平均值Mav與LB相對(duì)偏差的平均值av-MRE均小于其他4種算法的b-MRE。

表5總結(jié)了HEA-MNS與其他4種算法求解全部LA算例的比較結(jié)果。實(shí)驗(yàn)結(jié)果表明,HEA-MNS對(duì)每組算例求得的b-MRE優(yōu)于或等于MXLSGA,MCDE/TS,PRND/BTS 3種算法,由于HEA-MNS未能求得LA29算例的已知最優(yōu)解,使其在LA26-30算例組獲得的b-MRE值劣于SHEA算法,同時(shí)HEA-MNS對(duì)全部LA算例的av-MRE均小于其他4種算法的b-MRE,驗(yàn)證了本文算法的穩(wěn)定性。

表5 LA算例測(cè)試結(jié)果與其他算法結(jié)果比較

表6所示為對(duì)5個(gè)ABZ基準(zhǔn)算例的測(cè)試結(jié)果,4種對(duì)比算法包括文獻(xiàn)[41]的MXLSGA算法、文獻(xiàn)[43]基于增強(qiáng)Lévy飛行和差分進(jìn)化的混合鯨魚(yú)優(yōu)化算法(hybrid Whale Optimization Algorithm enhanced with Lévy Flight and Differential Evolution,WOA-LFDE)、文獻(xiàn)[22]的SHEA算法、文獻(xiàn)[44]基于頻率分析算子的遺傳算法(Genetic Algorithm based on Frequency Analysis operator,FAGA)。從MRE角度進(jìn)行統(tǒng)計(jì)對(duì)比分析,由于SHEA 算法未給出ABZ7算例的測(cè)試結(jié)果,在計(jì)算b-MRE時(shí),設(shè)置該基準(zhǔn)算例的相對(duì)偏差RE=0。HEA-MNS的b-MRE和av-MRE分別為0.62和0.73,其余3種算法的b-MRE分別為4.46,0.92,1.07,2.10,均大于本文算法。HEA-MNS求得了3個(gè)基準(zhǔn)算例(ABZ5,ABZ6,ABZ9)的下界值,算例ABZ8的求解最優(yōu)結(jié)果為667,其余4種算法分別為713,669,669,713,算例ABZ9的求解最優(yōu)結(jié)果為678,其余4種算法分別為721,683,685,680,驗(yàn)證了本文算法的有效性。圖15和圖16所示分別為HEA-MNS獲得ABZ8和ABZ9基準(zhǔn)算例最優(yōu)調(diào)度結(jié)果的甘特圖。

表6 ABZ算例測(cè)試結(jié)果與其他算法結(jié)果比較

4.3 參數(shù)敏感度分析

為了維持種群多樣性,通常需要在進(jìn)化算法設(shè)計(jì)中添加額外的參數(shù)。在HEA-MNS中需要設(shè)置懲罰閾值D,該值越高,對(duì)決策空間的多樣化探索能力越強(qiáng)。由式(29)可知,懲罰閾值D由算法執(zhí)行時(shí)間、初始種群密度與縮放系數(shù)β共同決定,上述測(cè)試中的β均設(shè)置為0.5。為了探討β對(duì)HEA-MNS性能的影響,將其設(shè)置6個(gè)級(jí)別{0,0.2,0.4,0.6,0.8,1.0},選用比較困難的ABZ8,LA29,LA40作為測(cè)試算例,算法其他參數(shù)設(shè)置與4.2節(jié)相同,圖17所示為不同β值下HEA-MNS求解3個(gè)測(cè)試算例的MRE曲線圖。

從圖17可知,3個(gè)測(cè)試算例的MRE值在β=0時(shí)最差,說(shuō)明當(dāng)HEA-MNS缺乏有效的種群多樣性控制策略時(shí),算法性能會(huì)受到明顯影響;當(dāng)β≥0.4時(shí),算法均能保持較優(yōu)的性能,說(shuō)明在保證算法性能的前提下,β的取值范圍很大,HEA-MNS具有較強(qiáng)的穩(wěn)定性。

5 結(jié)束語(yǔ)

本文提出一種HEA-MNS算法,通過(guò)將基于多工序精確聯(lián)動(dòng)鄰域結(jié)構(gòu)的禁忌搜索算法與多樣化控制的進(jìn)化算法相結(jié)合,有效地解決了傳統(tǒng)進(jìn)化算法在求解JSP中出現(xiàn)的局部搜索能力差、易早熟等問(wèn)題。

本文從理論上給出了N7鄰域結(jié)構(gòu)中工序無(wú)效移動(dòng)的判定條件,據(jù)此設(shè)計(jì)了3對(duì)工序精確聯(lián)動(dòng)的鄰域結(jié)構(gòu),有效擴(kuò)展了鄰域搜索的范圍。為了解決傳統(tǒng)進(jìn)化算法的種群多樣性隨進(jìn)化過(guò)程快速下降的問(wèn)題,本文提出基于鄰域懲罰的父本選擇算子與基于動(dòng)態(tài)懲罰閾值的種群更新策略,有效提高了子代與種群的多樣性。

通過(guò)對(duì)比HEA-MNS與多種先進(jìn)算法對(duì)不同規(guī)模JSP基準(zhǔn)算例的測(cè)試結(jié)果,證明了算法的穩(wěn)定性與有效性。然而,當(dāng)前工作僅對(duì)算法進(jìn)行了改進(jìn),并在靜態(tài)基準(zhǔn)算例上進(jìn)行了測(cè)試,初步驗(yàn)證了HEA-MNS的可行性與有效性,下一步擬將HEA-MNS應(yīng)用于實(shí)際生產(chǎn)調(diào)度場(chǎng)景,并考慮不確定因素的影響。