基于混合化學(xué)反應(yīng)算法的柔性作業(yè)車間調(diào)度

肖華軍，柴子力，張超勇，孟磊磊，任亞平，梅慧文

(華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074)

0 引言

調(diào)度問題通常定義為“把有限的資源在時間上分配給若干個任務(wù)，以滿足或優(yōu)化一個或多個目標(biāo)”。在作業(yè)車間調(diào)度問題(Job-Shop Scheduling Problem, JSP)中，要加工的工序都必須在指定的機(jī)器上加工，然而在實(shí)際生產(chǎn)中要加工的工序往往可以在多臺機(jī)器上進(jìn)行加工，而且不同的機(jī)器加工同一工序所用時間不同，這一類問題稱為柔性作業(yè)車間調(diào)度問題(Flexible Job Shop Scheduling Problem, FJSP)。FJSP需要為工序選擇可加工機(jī)器，減少機(jī)器約束的同時，卻會增大搜索空間，是比JSP問題更復(fù)雜的NP-hard問題[1]。

自Brucher等[2]在1990年首次提出該問題以來，已經(jīng)出現(xiàn)很多算法用來解決該問題。求解FJSP的算法主要包括精確算法和近似算法兩大類。精確算法包括分支定界法、整數(shù)規(guī)劃法等。Torabietal等[3]在2005年提出了一種整數(shù)規(guī)劃方法用于求解確定性柔性作業(yè)車間中的共同周期多產(chǎn)品批量調(diào)度問題，需要同時確定機(jī)器分配，排序，批量調(diào)整和調(diào)度決策。Demir等[4]在2013年評估了幾種FJSP的數(shù)學(xué)模型。同年Roshanaei等[5]進(jìn)一步提出了兩種新穎的混合整數(shù)線性規(guī)劃(Mixed Integr Linear Programming, MILP)模型用于解決FJSP。精確算法可以獲得精確的優(yōu)化方案，然而不能有效地解決總工序較多的大規(guī)模FJSP。近似方法包括啟發(fā)式算法和元啟發(fā)式算法[6]。進(jìn)化算法是一種有效的元啟發(fā)式方法，包括遺傳算法，進(jìn)化策略和進(jìn)化規(guī)劃。Tay等[7]在2008年將遺傳算法與優(yōu)先分配規(guī)則結(jié)合使用來解決多目標(biāo)的FJSP。2014年，趙詩奎等[8]將基于機(jī)器空閑時間的鄰域搜索策略融入遺傳算法以求解作業(yè)車間調(diào)度優(yōu)化問題。2016年，張國輝等[9]針對FJSP的NP難特性提出解閾值的指標(biāo)，采用精英進(jìn)化策略對其進(jìn)行求解。群體智能算法是另外一種高效的元啟發(fā)式算法，包括蟻群優(yōu)化(Ant Colony Optimization, ACO)算法、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法和人工蜂群(Artificial Bee Colony, ABC)算法等。2009年Girish等[10]提出了解決以最大完工時間為目標(biāo)的FJSP的ACO算法，并且評估了算法的性能。Wang等[11]在2010年提出了求解FJSP的算法。2012年，張靜等[12]提出一種新的粒子位置更新方式以改進(jìn)粒子群算法，使之更有效地求解柔性作業(yè)車間批量調(diào)度問題。2015年，仲于江等[13]將小生境技術(shù)和粒子群算法相結(jié)合，求解多目標(biāo)的FJSP優(yōu)化問題。群體智能算法全局搜索能力較強(qiáng)，但是局部搜索能力較差，因此將群體智能算法與局部搜索算法結(jié)合起來能優(yōu)勢互補(bǔ)，獲得更好的搜索能力。局部搜索算法包括禁忌搜索(Tabu Search, TS)算法[14]，模擬退火(Simulated Annealing, SA)算法[15]和變鄰域搜索(Variable Neighborhood Search, VNS)算法[16]等。

化學(xué)反應(yīng)優(yōu)化(Chemical-Reaction Optimization, CRO)算法是一種模仿分子在化學(xué)反應(yīng)中變化情況的群體優(yōu)化智能算法[17]。CRO算法提出勢能、動能和能量中心等概念，避免算法陷入早熟。CRO算法在求解離散優(yōu)化問題，如二次分配[18]、模糊作業(yè)車間調(diào)度[19]和網(wǎng)格調(diào)度[20]等方面得到有效的應(yīng)用，并展現(xiàn)了良好的性能。本文針對FJSP的特點(diǎn)提出一種融合CRO算法與TS算法結(jié)合的混合算法(CROTS)?；旌纤惴ú捎糜行У木幋a、解碼、初始解產(chǎn)生機(jī)制和精英保留策略，設(shè)計了CRO算法的4種基本反應(yīng)；通過交叉算子實(shí)現(xiàn)了分子間的碰撞反應(yīng)，完成全局搜索；通過變異算子實(shí)現(xiàn)分子與墻壁的碰撞反應(yīng)，并釋放動能到能量中心；在滿足分解反應(yīng)條件時，將單個分子分解成多個分子；在滿足合成反應(yīng)條件時將多個分子合成單個分子，以此增加分子群的多樣性。最后再利用禁忌搜索，讓分子群跳出全局最優(yōu)，使混合算法在分散搜索和集中搜索之間達(dá)到更合理的平衡。

1 FJSP問題描述

FJSP模型建立如下:n個工件J={J1,J2,…,Jn}要在m臺機(jī)器M={M1,M2,…,Mm}上完成加工。任意工件Ji包含ni道工序{Oi,1,Oi,2,…,Oi,ni},同一工件上的不同工序必須按照確定的先后順序依次進(jìn)行加工。每道工序的可加工機(jī)器集為Mi,j={Mi,j,1,Mi,j,2,…,Mi,j,k}，Mi,j?M。記工序Oi,j在機(jī)器Mi,j,k上加工所需時間為pi,j,k(pi,j,k>0)。調(diào)度的任務(wù)是確定所有工序的加工順序和所選用的機(jī)器。本文考慮的優(yōu)化目標(biāo)為尋找一個可行調(diào)度方案使得最大完工時間(Makespan)最小。設(shè)Ci是工件Ji的完工時間，則最大完工時間Cmax最小的目標(biāo)函數(shù)為：Cmax=min{max(Ci)},(i=1,2,…,n)。

為了描述方便，定義以下符號：

Ci為工件Ji的完工時間;

n為工件總數(shù);

m為機(jī)器總數(shù);

M為總機(jī)器集;

ni為工件i的工序總數(shù);

Oi,j為工件i的第j道工序;

Mi,j為工序Oi,j的可選加工機(jī)器集;

mi,j為工序Oi,j的可選加工機(jī)器數(shù);

Mi,j,k為工序Oi,j在第k臺機(jī)器上加工;

pi,j,k為工序Oi,j在第k臺機(jī)器上加工所需時間;

Si,j為工序Oi,j的加工開始時間;

Ci,j為工序Oi,j的加工完成時間;

Ci為工件i的完工時間;

Cmax為最大完工時間;

L為一個足夠大的正數(shù)。

FJSP模型描述如下：

目標(biāo)函數(shù)Cmax=min{max(Ci)},i=1,2,…,n。

(1)

s.t.

Si,j+xi,j,k×pi,j,k≤Ci,j，

i=1,…,n,j=1,…,ni,k=1,…,mi,j;

(2)

Ci,j≤Si,j+1，i=1,…,n,j=1,…,ni-1;

(3)

Ci,ni≤Cmax，i=1,…,n;

(4)

Sg,h+pg,h,k≤Si,j+L(1-yghijk),

g=1,…,n,h=1,…,ng,

i=1,…,n,j=1,…,ni,k=1,…,m;

(5)

(6)

Si,j≥0,Ci,j≥0，i=1,…,n,j=1,…,ni。

(7)

式(2)和式(3)表示同一工件上的工序先后順序約束，式(4)表示工件的完工時間小于或等于總完工時間，式(5)表示在同一機(jī)器上加工的工序先后順序約束，式(6)表示每個工序只能在一臺機(jī)器上加工，式(7)表示開始加工時間和完工時間都得為正數(shù)。

表1為n=3,m=4的一個柔性作業(yè)車間調(diào)度問題時間表。

表1 柔性作業(yè)車間調(diào)度問題加工時間表

2 化學(xué)反應(yīng)優(yōu)化算法

CRO算法由LAM等[17]于2010年首次提出,是一種啟發(fā)式優(yōu)化算法，它模擬了密閉容器中分子間的碰撞情況。該算法中分子對應(yīng)問題的解，基元反應(yīng)對應(yīng)搜索過程。

分子是執(zhí)行算法操作的個體，每個分子包含分子結(jié)構(gòu)，勢能(PE)和動能(KE)。該算法用分子結(jié)構(gòu)ω來刻畫問題的解；勢能對應(yīng)當(dāng)前分子結(jié)構(gòu)所具有的目標(biāo)函數(shù)值；動能則體現(xiàn)了分子發(fā)生反應(yīng)的能力，動能越大分子發(fā)生碰撞的概率越大。本文設(shè)定的勢能為分子的目標(biāo)函數(shù)值，動能為分子的初始動能InitialKE減去父代分子的勢能與子代分子勢能的差值。則：

PEω=ObjFunc(ω),

(7)

KEω=InitialKE-(PEω-PEω′)。

(8)

式中ObjFunc指目標(biāo)函數(shù)，基元反應(yīng)對應(yīng)CRO算法操作算子。CRO算法定義了分子與墻壁的碰撞反應(yīng)、分子間的碰撞反應(yīng)、合成反應(yīng)以及分解反應(yīng)4種基本操作。其中：分子與墻壁的碰撞反應(yīng)和分解反應(yīng)在算法中為對單個個體的擾動；分子間碰撞反應(yīng)和合成反應(yīng)在算法中對應(yīng)多個個體的相互作用。CRO算法流程圖如圖1所示。

3 求解FJSP的混合算法

3.1 編碼和解碼

FJSP在給加工工序排序的同時還要給工序分配可加工機(jī)器，因此問題的可行解需要確定工序先后順序的編碼和給工序分配機(jī)器的編碼兩部分，如圖2所示。

基于機(jī)器的編碼長度也為l，表示為[g1,g2,…,gl]，其中第i個元素gi為第i道工序的加工機(jī)器。因此圖2所示的分子代表的工序和機(jī)器序列為(O2,1,M1)，(O1,1,M1)，(O3,1,M2)，(O1,2,M3)，(O2,2,M1)，(O1,3,M4)，(O3,2,M2)，(O3,3,M4)，加工時間序列為[3 2 1 4 4 2 2 3]。

解碼是編碼的逆過程，是將分子轉(zhuǎn)換成調(diào)度解的過程。設(shè)r為工序編碼中任意一工序Oi,j，加工時間為pr。記與工序r在同一工件上的前一道工序?yàn)镻J[r],后一道工序?yàn)镾J[r](如果它們存在)。記與工序r在同一臺機(jī)器上加工的前一道工序?yàn)镻M[r]，后一道工序?yàn)镾M[r](如果它們存在)。設(shè)工序r的最早開始加工時間為SE[r]，最早完工時間為CE[r]，則：

SE[r]=max{CE[PJ[r]],CE[PM[r]]}，

(9)

CE[r]=SE[r]+pr。

(10)

解碼之后得到問題的半主動調(diào)度解，其甘特圖如圖3所示。

由圖3可知，該解的最大完工時間為makespan=14，若將工序O3,3插入到O1,3之前，而不改變其加工機(jī)器，所得的解依然是可行解而且減少了最大完工時間，此時makespan=11優(yōu)化了目標(biāo)。因此本文引入插入式貪婪解碼算法來獲取主動調(diào)度解。該解碼方法描述如下：在滿足約束條件且不干擾其他工序的情況下將當(dāng)前工序安排在可加工機(jī)器上的最早的空閑時間段上。由此解碼得到的主動調(diào)度解的甘特圖如圖4所示。

3.2 種群初始化

為保證種群的多樣性，本文采用多種初始化方法來產(chǎn)生初始種群。第一種方法采用Kacem等[21]提出的局部化方法，種群中20%的個體通過該種方法產(chǎn)生;第二種初始化方法在給工序選擇加工機(jī)器時優(yōu)先選擇加工時間短的機(jī)器，該過程通過二元選擇操作來完成，而工序的加工順序隨機(jī)產(chǎn)生即可，種群中80%的個體通過該方法產(chǎn)生。

3.3 交叉算子

分子之間的碰撞是通過兩個分子的碰撞反應(yīng)生成兩個新的子代分子的過程。結(jié)合FJSP的特征，本文采用交叉操作來實(shí)現(xiàn)分子間的碰撞反應(yīng)。針對FJSP，分子中包含兩條編碼，對于這兩部分編碼本文分別采用不同的交叉算子。對基于工序的編碼，本文采用優(yōu)先工序交叉(Precedence Operation Crossover, POX)操作和改進(jìn)優(yōu)先工序交叉(Improved Precedence Operation Crossover, IPOX)操作。在交叉過程中各按50%的概率隨機(jī)選擇。兩種交叉操作介紹如下。

(1)POX交叉操作

設(shè)P1和P2為FJSP的兩個父代，通過POX交叉產(chǎn)生兩個子代C1和C2。交叉步驟如下：

步驟1將工件集J={J1,J2,…,Jn}隨機(jī)分成兩個集合G1和G2。

步驟2父代P1工序編碼中屬于集合G1的元素直接保留到C1中，且保持原有位置不變；同樣，父代P2工序編碼中屬于集合G1的元素直接保留到C2中，且保持原有位置不變。

步驟3父代P2工序編碼中屬于集合G2的元素按順序依次填補(bǔ)到C1中的空白處，同樣父代P1工序編碼中屬于集合G2的元素按順序依次填補(bǔ)到C2中的空白處。

POX交叉操作過程如圖5所示。

(2)IPOX交叉操作

記P1和P2為分子群中的兩個父代分子，C1和C2為父代分子經(jīng)由IPOX交叉得到的子代分子。IPOX交叉步驟如下：

步驟1將工件集J={J1,J2,…,Jn}隨機(jī)分成兩個集合G1和G2。

步驟2父代P1工序編碼中屬于集合G1的元素直接保留到C1中，且保持原有位置不變；同樣，父代P2工序編碼中屬于集合G2的元素直接保留到C2中，且保持原有位置不變。

步驟3父代P2工序編碼中屬于集合G2的元素按順序依次填補(bǔ)到C1中的空白處，同樣父代P1工序編碼中屬于集合G1的元素按順序依次填補(bǔ)到C2中的空白處。

IPOX交叉操作過程如圖6所示。

針對基于機(jī)器的編碼，本文采用多點(diǎn)交叉操作(Multi-point Preservative crossover, MPX)，即多點(diǎn)交叉操作。MPX交叉步驟如下：

步驟1產(chǎn)生隨機(jī)0,1數(shù)組R，數(shù)組長度為編碼長度l。

步驟2選出P1和P2中與數(shù)組R中元素1位置相同的元素，將它們互換。

步驟3P1和P2中其他元素保持不變。

由于交換的是同一道工序的加工機(jī)器，保證了生成的子代分子依然是可行解。MPX交叉過程如圖7所示。

3.4 變異操作

分子與墻壁之間的碰撞是一個分子通過與墻壁之間的碰撞反應(yīng)得到一個與其相近的子代分子的過程。結(jié)合FJSP問題特征，本文采用變異操作來實(shí)現(xiàn)分子與墻壁之間的碰撞。對于基于工序的編碼，本文采用兩種變異操作，在變異過程中各按50%的概率隨機(jī)選擇。

(1)隨機(jī)插入變異操作，如圖8所示，r1=5，r2=3。具體步驟如下：

步驟1產(chǎn)生兩隨機(jī)數(shù)r1和r2，r1∈[0,l],r2∈[0,l]且r1≠r2。

步驟2將編碼中位置r1處的元素插入到位置r2之前。

(2)鄰域變異操作，具體步驟如下：

步驟1在父代P中選擇3個不同的元素，生成它的全排列；

步驟2在生成的全排列中任意選擇一種代替原來的的排列，其他位置的元素保持不變。

鄰域變異操作如圖9所示。針對基于機(jī)器的編碼，本文采用多點(diǎn)變異操作。具體步驟如下：

步驟1產(chǎn)生隨機(jī)0,1數(shù)組R，數(shù)組長度為編碼長度l。

步驟2找出數(shù)組R中元素為1的位置，在對應(yīng)工序的可加工機(jī)器集中隨機(jī)選取機(jī)器替換之前的機(jī)器，其他位置的機(jī)器保持不變。

多點(diǎn)變異示意圖如圖10所示。

3.5 單分子反應(yīng)

在化學(xué)反應(yīng)算法中，分子與墻壁的碰撞反應(yīng)和分解反應(yīng)是針對單個個體進(jìn)行的操作。

3.5.1 分子與墻壁的輕微碰撞反應(yīng)

設(shè)分子ω為父代解，通過與墻壁碰撞產(chǎn)生子代分子ω′，本文采用上述變異操作來實(shí)現(xiàn)。分子與墻壁碰撞反應(yīng)步驟如下：

步驟1對ω進(jìn)行變異操作，得到子代ω′。

步驟2判斷是否滿足與墻壁碰撞條件，若滿足，則更新個體和能量中心的能量。

3.5.2 分解反應(yīng)

步驟1判斷是否滿足分解反應(yīng)的條件。本文設(shè)定的分解條件為在規(guī)定的迭代次數(shù)α內(nèi)分子的目標(biāo)函數(shù)值沒有更新。

步驟2產(chǎn)生一隨機(jī)整數(shù)r，r∈[-l,l]，其中l(wèi)為編碼長度。

步驟3若r<0,則將編碼中前r個元素移動到編碼末端，若r>0，則將編碼中最后r個元素移動到編碼前端。設(shè)r分別為-1和2，其針對工序編碼的移動過程如圖11所示。

3.6 多分子反應(yīng)

在CRO算法中，分子間的輕微碰撞反應(yīng)和合成反應(yīng)是兩種單分子反應(yīng)。

3.6.1 分子間的輕微碰撞反應(yīng)

分子間的碰撞反應(yīng)是兩個父代分子通過碰撞產(chǎn)生兩個子代分子的過程。本文采用上述交叉操作來實(shí)現(xiàn)。其步驟如下：

步驟2判斷是否滿足分子間碰撞反應(yīng)的條件，若滿足則修改分解后的兩個子代分子的動能并將這兩子代分子加入到新種群。

3.6.2 合成反應(yīng)

合成反應(yīng)是兩個分子合成一個分子的過程。本文采用距離保持交叉操作[17]來實(shí)現(xiàn)合成反應(yīng)?；诠ば蚓幋a的距離保持交叉操作如圖12所示，其步驟如下:

步驟1判斷是否滿足合成反應(yīng)的條件。本文設(shè)定的合成條件為兩父代分子ω1和ω2的動能同時小于設(shè)定的動能下限β，即KEω1≤β且KEω2≤β。

步驟2隨機(jī)選取兩父代分子，比對兩父代分子中各位置的元素。

步驟3將父代分子中同一位置相同的元素復(fù)制到子代，隨機(jī)產(chǎn)生其他位置的元素，得到子代分子。

3.7 精英保留機(jī)制

在CRO算法中，原本適應(yīng)度很高的分子也有可能生成新的適應(yīng)度很低的分子。這一現(xiàn)象保證了分子群的多樣性，使算法有很好的全局搜索能力，但是這也降低了算法的收斂速度。因此，在改進(jìn)的算法中引入了精英保留策略。該策略將父代中最優(yōu)的Popsize×Pr(Popsize為種群規(guī)模，Pr為保留概率)個個體直接保留到子代而不進(jìn)行分子操作。

另外本文還采用二元錦標(biāo)賽策略來完成選擇操作，即每次從分子群中隨機(jī)選擇兩個不同個體，同時產(chǎn)生1個0～1之間的隨機(jī)值，若隨機(jī)值小于選擇概率Ps(一般Ps=0.8),則選擇兩者中適應(yīng)度較高的個體，否則選擇另一個適應(yīng)度低的個體。被選中的個體放到下一代種群中參與分子操作。

3.8 禁忌搜索算法

TS算法是一種高效的局部搜索算法，目前，禁忌搜索在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域得到廣泛應(yīng)用。TS算法由鄰域結(jié)構(gòu)、移動評價策略、禁忌表、禁忌長度、特赦準(zhǔn)則和終止準(zhǔn)則等組成。

本文采用Gambardella等提出的鄰域結(jié)構(gòu)[14]和移動評價策略。本文中禁忌對象用(v,k)來表示，其中v表示被移動的工序，k表示移動之前工序v的加工機(jī)器。禁忌長度設(shè)置為TM(v,k)=P+Mv，其中P為當(dāng)前關(guān)鍵路徑長度，Mv為工序v的可加工機(jī)器數(shù)。當(dāng)?shù)玫降男陆鈨?yōu)于當(dāng)前最優(yōu)解時即滿足特赦準(zhǔn)則。當(dāng)禁忌搜索算法迭代次數(shù)達(dá)到最大迭代次數(shù)，或者在給定的迭代次數(shù)下仍沒有得到更優(yōu)解，則算法終止。

禁忌搜索算法程序框圖如圖13所示。

3.9 CROTS混合算法框架

本文針對FJSP的特點(diǎn)提出融合CRO算法與TS算法的混合算法(CROTS)。CRO算法負(fù)責(zé)全局搜索而TS算法進(jìn)行局部搜索，一方面讓問題能求得更優(yōu)的解，另一方面加快了種群收斂速度，使混合算法在分散搜索和集中搜索之間達(dá)到更合理的平衡。本文提出的CROTS混合算法步驟如下：

步驟1設(shè)置試驗(yàn)參數(shù)，初始化分子種群，并根據(jù)式(7)和式(8)分別計算每個分子的勢能和動能。

步驟2根據(jù)精英保留機(jī)制，從分子群中選擇分子進(jìn)行優(yōu)化操作。

步驟3生成0～1的隨機(jī)數(shù)r，若r>MoleColl則進(jìn)行單分子反應(yīng)，即執(zhí)行步驟5；否則進(jìn)行多分子反應(yīng)，即執(zhí)行步驟6。

步驟4判斷是否滿足分解條件，若滿足則進(jìn)行分解反應(yīng)，否則進(jìn)行分子與墻壁的輕微碰撞反應(yīng)。

步驟5判斷合成條件是否滿足，若滿足則進(jìn)行合成反應(yīng)，否則進(jìn)行分子間的輕微碰撞反應(yīng)。

步驟6對分子進(jìn)行禁忌搜索。

步驟7判斷是否滿足終止條件即是否達(dá)到最大迭代次數(shù)maxGen。若滿足，則跳轉(zhuǎn)到步驟8,否則，執(zhí)行步驟2。

步驟8算法結(jié)束。

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

CROTS算法的關(guān)鍵步驟的時間復(fù)雜度如表2所示，其中n為編碼長度，m為進(jìn)行操作的個數(shù)?；旌纤惴ㄖ?，每一代有Popsize個分子，其中有Popsize×MoleColl個分子進(jìn)行多分子反應(yīng)，Popsize×(1-MoleColl)個分子進(jìn)行單分子反應(yīng)，所有的分子都進(jìn)行禁忌搜索。因此混合化學(xué)反應(yīng)算法的總時間復(fù)雜度為：

Popsize×(1+MoleColl)×O(n2)+Popsize×(1-MoleColl)×O(n)。

可以看出，本文提出的混合化學(xué)反應(yīng)算法的時間復(fù)雜度與問題規(guī)模、種群大小、多分子反應(yīng)概率等參數(shù)有關(guān)。

表2 算法中關(guān)鍵步驟的時間復(fù)雜度

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

上述CROTS算法用C++語言編程，程序運(yùn)行環(huán)境為P4 CPU，主頻3.0 G，內(nèi)存為2 G。為了驗(yàn)證和比較本文所提算法的性能，選取Brandimarte[22]和Fattahi[23]基準(zhǔn)問題對算法進(jìn)行測試。算法的參數(shù)設(shè)置和實(shí)驗(yàn)結(jié)果分析如下。

4.1 參數(shù)設(shè)置

混合化學(xué)反應(yīng)算法的參數(shù)主要有：分子種群規(guī)模Popsize，多分子碰撞反應(yīng)概率MoleColl，初始動能InitialKE，保留概率Pr，選擇概率Ps，動能下限β，分子沒有改善的最大迭代次數(shù)α，最大迭代次數(shù)maxGen，其中對算法性能影響較大的有MoleColl，InitialKE，β和α。為了考察參數(shù)對算法性能的影響，本文采用試驗(yàn)設(shè)計方法進(jìn)行分析，選取Brandimarte[22]基準(zhǔn)問題中的MK06案例進(jìn)行測試，每個試驗(yàn)參數(shù)設(shè)置4個不同的水平值，如表3所示。選用正交表L16(45)的前四列，算法中分子種群規(guī)模Popsize=500，保留概率Pr=0.01，選擇概率Ps=0.8，最大迭代次數(shù)maxGen=200。為了評估算法的性能，計算算法所得最優(yōu)解ALG與參考最優(yōu)值OPT的相對百分偏差RPD=(ALG-OPT)/OPT×100%。算法在每組參數(shù)下獨(dú)立運(yùn)行20次，以20次實(shí)驗(yàn)所得RPD的均值作為影響值(RV)，統(tǒng)計結(jié)果如表4所示，使用Minitab 16進(jìn)行數(shù)據(jù)分析得到參數(shù)的水平值趨勢如圖14所示。

表3 CROTS算法中參數(shù)的水平值

表4 正交表和RV值

續(xù)表4

由圖14可見，設(shè)置不同的參數(shù)，CROTS算法的性能也有所不同，根據(jù)CROTS算法的設(shè)計思想可知，MoleColl，InitialKE，β和α這4個參數(shù)決定了算法的收斂速度和跳出局部最優(yōu)的能力。在算法參數(shù)選擇時應(yīng)根據(jù)問題對這4個參數(shù)取合理的值，根據(jù)試驗(yàn)結(jié)果本文設(shè)定這4個參數(shù)的值,如表5所示。

表5 CROTS算法的參數(shù)的參考值

4.2 基準(zhǔn)實(shí)例測試

表6和表7分別顯示了Brandimarte和Fattahi實(shí)例測試結(jié)果的比較，其中對于Brandimarte實(shí)例分別給出了與Mastrolilli等[14]采用的禁忌搜索算法;Gao等[16]的遺傳算法與變鄰域搜索結(jié)合的混合算法;Li等[24]的遺傳算法與禁忌搜索結(jié)合的混合算法HA,以及Wang等[11]的人工蜂群算法的比較。對于Fattahi實(shí)例，表8中的AIA算法和HHS算法來自于Yuan[25]等，M2算法來自于Demir和Isleyen[26]。此外，圖15～圖18分別顯示了實(shí)例Mk06、MK10、SFJS10和MFJS10的甘特圖，表8和表9顯示了不同算法對不同案例相對于最優(yōu)解的RPD值。

表6 對于Brandimarte基準(zhǔn)實(shí)例測試結(jié)果的比較

表7 對于Fattahi基準(zhǔn)實(shí)例測試結(jié)果的比較

表8 對于Brandimarte基準(zhǔn)實(shí)例不同算法的RPD

表9 對于Fattahi基準(zhǔn)實(shí)例不同算法的RPD

續(xù)表9

表6和表7中帶*的數(shù)字表示該問題的當(dāng)前最優(yōu)解。由表6和表8可知，對于Brandimarte基準(zhǔn)實(shí)例，本文所求的結(jié)果優(yōu)于M.G.的TS算法、Gao的VNS算法以及Wang的ABC算法，與Li的HA算法所求結(jié)果一致，本文效率稍高。這是因?yàn)镸.G.的TS算法沒有進(jìn)行全局搜索，而本文采用了化學(xué)反應(yīng)算法進(jìn)行全局搜索，提高了算法性能。本文設(shè)計的化學(xué)反應(yīng)算法既有兩個分子的相互作用又有分子與墻壁的作用，在傳統(tǒng)的交叉、變異操作上又加入了一個分子分解為兩個分子的操作，增強(qiáng)了算法的多樣性，提高了算法性能。本文算法中采用的交叉、變異等算子都是根據(jù)柔性作業(yè)車間調(diào)度問題的特征設(shè)計，本文采用鄰域結(jié)構(gòu)也被證明是當(dāng)前效果較好的，故本文能求出案例的當(dāng)前最優(yōu)解。由表7和表9可知，對于Fattahi基準(zhǔn)實(shí)例，本文所提算法也能求得當(dāng)前最優(yōu)解，證明了本文算法的有效性。

5 結(jié)束語

本文通過研究FJSP提出了一種結(jié)合CRO和TS兩種算法的混合算法，給出了算法的基本框架，并且擴(kuò)展了CRO的4種基本反應(yīng)，設(shè)計了有效的交叉、變異算子，采用了高效的鄰域函數(shù)。混合算法融合了CRO的全局搜索能力和TS的局部搜索能力。在解碼過程中采用了插入式貪婪解碼算法以生成主動調(diào)度解，使算法更加高效。此外，在算法中引入了精英保留機(jī)制以保留較優(yōu)個體，從而提高算法的收斂速度。最后，使用基準(zhǔn)實(shí)例測試了該算法，并與其他算法的結(jié)果進(jìn)行了比較，證實(shí)了所提算法的有效性。

未來將進(jìn)一步提高CRO算法的性能，深入分析FJSP問題的結(jié)構(gòu)特征提出更好的鄰域結(jié)構(gòu)函數(shù)以便減少算法的無效搜索，提高算法的收斂速度。另外，還考慮將所提出的混合算法用于求解多目標(biāo)的FJSP，以期獲得更好的結(jié)果。