楊艷華,姚立綱

(1.福建江夏學(xué)院 工程學(xué)院,福建 福州 350108；2.福州大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，福建 福州 350116)

0 引言

隨著市場(chǎng)全球化和客戶需求的日益多樣化，多品種小批量的柔性制造方式已成為大量制造企業(yè)的主要生產(chǎn)模式。相比傳統(tǒng)的車間調(diào)度問題，柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)的靈活性和復(fù)雜性更高，是NP-難問題，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法和部分枚舉法只能在問題規(guī)模較小時(shí)求得最優(yōu)解[1]。近年來元啟發(fā)式算法的發(fā)展為FJSP的求解提供了新的技術(shù)途徑，大量的FJSP的研究論文采用了進(jìn)化算法(Evolutionary Algorithms, EAs)或多方法混合技術(shù)[2]。進(jìn)化算法框架下的諸多變體如遺傳算法(Genetic Algorithm, GA)、分布估計(jì)算法(Estimation of Distribution Algorithm, EDA)[3-6]都成功地應(yīng)用于FJSP的求解。其他元啟發(fā)式算法，如入侵性雜草優(yōu)化算法(Invasive Weed Optimization, IWO)[7]、免疫算法(Immunity Algorithm, IA)[8]、灰狼優(yōu)化算法(Grey Wolf Optimization, GWO)[9]以及禁忌搜索算法(Tabu Search, TS)[10]等也取得了很好的效果。近年來研究文獻(xiàn)表明，針對(duì)FJSP的研究逐漸由單目標(biāo)向多目標(biāo)拓展，但單目標(biāo)優(yōu)化的技術(shù)依然處于重要位置。研究的主要工作集中在對(duì)所使用優(yōu)化算法的改進(jìn)上，包括多策略混合算法[11-14]、并行化[4]和加強(qiáng)局部搜索[15]，其共同思想是在全局搜索和局部搜索之間權(quán)衡。全局搜索注重試探解的多樣性和分布廣泛性，局部搜索注重收斂性，從而在有限的時(shí)間內(nèi)獲得較理想的解。

與元啟發(fā)式算法不同，交叉熵(Cross Entropy, CE)算法[16-17]是基于概率模型采樣生成試探解的全局優(yōu)化算法，可通過監(jiān)控分布函數(shù)控制生成解的散布，克服一般啟發(fā)式算法生成試探解的盲目性。通過反饋更新概率分布模型，引導(dǎo)算法在優(yōu)質(zhì)解的區(qū)域內(nèi)采樣，使算法具有很強(qiáng)的全局搜索能力。然而，CE算法采樣的機(jī)理源于大數(shù)定律，所需樣本量大，這使得算法在局部搜索時(shí)效率不高，實(shí)際運(yùn)用中多和其他方法結(jié)合以提高整體效能，如LI等[18]將CE算法和螢火蟲算法兩套不同搜索機(jī)制進(jìn)行協(xié)同，設(shè)計(jì)了一種混合交叉熵螢火蟲算法(Cross-Entropy Firefly Algorithm, CEFA)，用于求解高維函數(shù)優(yōu)化問題。CE算法在求解調(diào)度問題方面的研究主要有：SANTOSA等[19]在CE算法的基礎(chǔ)上引入遺傳算法的交叉變異操作，設(shè)計(jì)出一種混合交叉熵遺傳算法，用于求解零等待作業(yè)車間調(diào)度問題；WANG等[20]針對(duì)煉鋼—連鑄生產(chǎn)調(diào)度問題，以最小化總能耗為優(yōu)化目標(biāo)，通過改進(jìn)交叉熵算法對(duì)部分精英個(gè)體執(zhí)行基于交換操作的局部搜索；佘明哲等[21]將CE算法結(jié)合自適應(yīng)變鄰域局部搜索，用于求解模糊分布式裝配流水線低碳調(diào)度問題。當(dāng)前CE算法的主流應(yīng)用方式是與其他機(jī)理的優(yōu)化算法或操作結(jié)合，發(fā)揮各自優(yōu)勢(shì)。然而，鮮有研究將CE算法與FJSP在模型層面結(jié)合，使得CE算法的潛力未能充分挖掘，多數(shù)方案只是將CE算法用于生成較好的初始種群。

本文將研究重點(diǎn)下沉到模型層面，通過對(duì)FJSP模型及其可行解的研究，發(fā)現(xiàn)已有研究中普遍采用的基于加工序列的解的表示方法不唯一，優(yōu)化算法計(jì)算效率降低。通過對(duì)模型和CE算法兩方面特點(diǎn)的研究，建立基于甘特圖的解的歸總表示，并構(gòu)造兩階段法的計(jì)算模型，融入CE算法的計(jì)算結(jié)構(gòu)，研究改造后的計(jì)算模型對(duì)整體算法效能的影響，從而開發(fā)實(shí)用的優(yōu)化算法。

1 柔性作業(yè)車間調(diào)度問題模型

1.1 問題表述

柔性生產(chǎn)車間包括多臺(tái)機(jī)器(柔性制造單元)，每臺(tái)機(jī)器具有對(duì)多種工件的不同工序進(jìn)行加工的能力，即機(jī)器具有“柔性”。但不同機(jī)器進(jìn)行不同作業(yè)的效率不同，如何為待加工工件安排機(jī)器、如何為機(jī)器的作業(yè)排序，使整體效率獲得優(yōu)化，即為柔性作業(yè)車間調(diào)度問題[1]。柔性作業(yè)車間調(diào)度問題的數(shù)學(xué)表述有多種方式，本文采用文獻(xiàn)[22]的記號(hào)，以最大完工時(shí)間最小化為目標(biāo)。

在m臺(tái)機(jī)器上加工n個(gè)工件，每個(gè)工件j需要nj道工序，各工序之間遵循工藝約束，工件j的每道工序Oji可由多臺(tái)具有相似功能的機(jī)器加工，可用機(jī)器集合設(shè)為Sji。若選定其中機(jī)器k加工，則將耗用pjik個(gè)單位的加工時(shí)間。目標(biāo)是希望所有工序都完成的時(shí)間盡可能早，得到優(yōu)化模型如下：

minCmax=min(max(Cji))。

(1)

s.t.

Cji-Cj(i-1)≥pjikXjik,i=2,3,…,nj，k=1,2,…,m;

(2)

(3)

∑Xjik=1,k∈Sij,?i,j;

(4)

Xjik∈{0,1};

(5)

Yghji∈{-1,0,1}。

(6)

其中：

j,g為工件號(hào)索引，j,g=1,2,…,n；

i,h為工序號(hào)索引，i,h=1,2,…,nj；

k為機(jī)器號(hào)索引，k=1,2,…,m；

Oji為工件j的第i道工序；Cji為工序Oji的完工時(shí)間；

Xjik為工序分配機(jī)器的決策變量，若工序Oji選擇在機(jī)器k上加工，則Xjik=1,否則Xjik=0；

Yghji為決定工序先后順序的決策變量，若工序Ogh為Oji相鄰的前一道工序，則Yghji=-1；若工序Ogh為Oji相鄰的后一道工序，則Yghji=1，否則Yghji=0；

Sji為工序Oji的可用機(jī)器集合Sji?{1,2,…,m}；

Cmax為調(diào)度方案的最大完工時(shí)間。

式(1)為目標(biāo)函數(shù)；約束條件(2)反映一個(gè)工件必須依從前向后的次序加工各工序，且只有前一工序完成才能加工下一工序；約束條件(3)限定同臺(tái)機(jī)器上不能同時(shí)加工兩個(gè)工件；約束條件(4)限定工序Oij只能在一臺(tái)機(jī)器上獨(dú)立完成，不能跨機(jī)器加工；約束條件(5)和約束條件(6)限定決策變量的取值范圍。

1.2 基于時(shí)間遞推關(guān)系的柔性作業(yè)車間調(diào)度問題模型構(gòu)建

minf(IP,P)。

s.t.

IP滿足工序約束;

P滿足機(jī)器可用約束。

(7)

其中f為目標(biāo)函數(shù)，本文以各工序最大完工時(shí)間為目標(biāo)，有f(IP,P)=Cmax。

設(shè)向量st∈RN為加工序列中各工序?qū)?yīng)的開始時(shí)間，如st(j)表示第j個(gè)位置所進(jìn)行工序的開始時(shí)間；相應(yīng)地，設(shè)ct∈RN為加工序列中各工序?qū)?yīng)的完成時(shí)間。由加工調(diào)度的內(nèi)在機(jī)理可知，st(j)取該工序所使用機(jī)器的上一次工作完成時(shí)間lastmachineT和該工序?qū)?yīng)零件上一道工序完成時(shí)間lastprocessT的最大值。由此可以得到每一個(gè)位置工序完成時(shí)間的遞推關(guān)系：

st(j)=max{lastmachineT,lastprocessT};

(8)

ct(j)=st(j)+q(IP(j),P(IP(j))。

(9)

其中q是矩陣，表示各個(gè)工序用不同機(jī)器加工所消耗的時(shí)間，由最初模型中的pjik演化而來，q(IP(j),P(IP(j))表示j位置的加工對(duì)應(yīng)的工序IP(j)在選擇使用機(jī)器P(IP(j))時(shí)所消耗的時(shí)間。只要工作排序滿足工序約束，則通過式(8)和式(9)的遞推關(guān)系，就可以得到整個(gè)系列工作的完工時(shí)間f(IP,P)=max(ct)。

1.3 解的等價(jià)性和歸總表示

由式(8)和式(9)的遞推關(guān)系可知，如果兩個(gè)相鄰位置j和j+1的工序既不是同一個(gè)零件的先后工序，又不使用同一臺(tái)機(jī)器加工，則它們二者各自的開始、完成時(shí)間不受對(duì)方影響，也即若二者交換IP中的順序，不會(huì)影響整套工作的進(jìn)度安排，兩個(gè)加工方案對(duì)應(yīng)的甘特圖相同。

基于此，定義FJSP可行解的等價(jià)關(guān)系如下：設(shè)[IP,P]是FJSP的一個(gè)可行解，若IP(j),IP(j+1)兩個(gè)工序不是同一個(gè)零件的工序，且P(IP(j))≠P(IP(j+1))，則將IP的j與j+1位置上的工序交換，并保持機(jī)器排序向量P不變，所得到的新解[IP′,P]也是一個(gè)可行解，并稱[IP′,P]為[IP,P]的一個(gè)相鄰對(duì)換。進(jìn)一步，若[IP2,P]可以由[IP1,P]經(jīng)過有限步相鄰對(duì)換得到，則稱[IP1,P]和[IP2,P]等價(jià)。

求解FJSP的元啟發(fā)式算法的實(shí)現(xiàn)方案中，對(duì)工序的編碼大都采用類似于本文中IP的向量形式，以表示工序優(yōu)先順序。這意味著這些算法對(duì)可行解的表示同樣存在著不唯一性，即不同的編碼向量對(duì)應(yīng)本質(zhì)相同的解，這會(huì)導(dǎo)致交叉、變異操作生成等價(jià)解，從而誤導(dǎo)改進(jìn)方向，降低算法效率。為解決這一問題，本文提出了等價(jià)解歸總表示的方式，即通過增加約束條件，使等價(jià)解中的某一個(gè)作為代表元。歸總表示的原則如下：

IP*=argminτ(IP);

s.t.

IP∈S。

(10)

其中：τ(·)表示排列的逆序數(shù)，S為等價(jià)解集，IP*為等價(jià)解的歸總表示，它是等價(jià)解中逆序數(shù)最小的一個(gè)。

由式(10)可知，對(duì)于采樣得到的每個(gè)精英樣本[IP,P]，只要對(duì)IP在工序約束下進(jìn)行減少逆序數(shù)的重排，即可得到等價(jià)解的歸總表示，下面的排序算法給出了一種簡(jiǎn)單的實(shí)現(xiàn)方式。

算法1排序算法。

置j=1，

步驟1若IP(j)>IP(j+1)且滿足前述可交換條件，則交換二者位置。

步驟2若j

步驟3當(dāng)進(jìn)行至一輪搜索中j=1,2,…,N-1時(shí)均未發(fā)生工序位置交換，迭代終止。

2 交叉熵優(yōu)化算法

2.1 交叉熵算法簡(jiǎn)介

算法2CE算法。

步驟1給定ρ∈(0,1)，單次采樣數(shù)N，終止參數(shù)d，采樣分布密度函數(shù)f(·;v)和初始抽樣分布參數(shù)v0，令t=1。

步驟2按照f(·;vt-1)在可行域X中進(jìn)行采樣，生成試探解x1,…,xN，計(jì)算相應(yīng)的函數(shù)值。

步驟3對(duì)樣本函數(shù)值排序S(1)≤S(2)≤…≤S(N)，并計(jì)算相應(yīng)的1-ρ分位數(shù)γt，即

γt=S(?(1-ρ)N?)。

(11)

步驟4記Nelite=N-?(1-ρ)N?+1為精英樣本數(shù)，選取S(?(1-ρ)N?),S(?(1-ρ)N?+1),…,S(N)對(duì)應(yīng)的Nelite個(gè)樣本，對(duì)分布密度函數(shù)進(jìn)行更新，更新公式為：

(12)

得到的解作為新的vt。

步驟5若對(duì)某個(gè)t≥d，滿足γt=γt-1=…=γt-d，則迭代終止，取值為S(N)的采樣點(diǎn)為最優(yōu)解；否則，置t=t+1，轉(zhuǎn)步驟2。

在實(shí)際的優(yōu)化計(jì)算中，vt的更新經(jīng)常采用平滑化處理，將式(12)的解(命名為wt)與上一次迭代的參數(shù)vt-1的加權(quán)平均作為更新的參數(shù)，即

vt=αwt+(1-α)vt-1。

(13)

其中平滑系數(shù)α∈[0,1]。通過平滑化處理，采樣分布的系數(shù)不會(huì)變化過于劇烈，以避免陷入局部最優(yōu)點(diǎn)。

CE算法的改進(jìn)版本FACE(fully automated CE)，其主要思想是自適應(yīng)地調(diào)整每次的采樣數(shù)Nt，使之在最小采樣數(shù)Nmin和最大采樣數(shù)Nmax之間變動(dòng)，這樣的改進(jìn)提高了算法的適應(yīng)性。本文采用改進(jìn)的FACE模式，以函數(shù)值最小化為目標(biāo)，用于求解FJSP。

2.2 隨機(jī)分布篩

根據(jù)CE算法的框架，試探解是根據(jù)一定的分布函數(shù)采樣獲得，采樣的試探解具有廣泛的分布性，且可以通過調(diào)整分布函數(shù)進(jìn)行重點(diǎn)采樣，這使得CE算法具有很強(qiáng)的全局搜索能力。然而，F(xiàn)JSP帶有工序約束，不能直接采樣。一般處理約束的方法有罰函數(shù)法和拒絕抽樣，這兩種方式都會(huì)生成不可行解并進(jìn)行處理，降低采樣效率。本文采用了一種“隨機(jī)分布篩”的工具，不是篩選采樣點(diǎn)，而是對(duì)采樣分布進(jìn)行篩選，從而使得生成的采樣點(diǎn)都是滿足約束的可行解。

設(shè)Pr1∈RN×N為用于生成IP的概率分布矩陣，Pr2∈RN×m為用于生成P的概率分布矩陣。Pr1中的元素Pr1(i,j)表示第i個(gè)位置選擇第j號(hào)工序的概率，Pr2中的元素Pr2(i,k)表示第i個(gè)位置選擇第k號(hào)機(jī)器的概率。由于同一工件工序的先后關(guān)系約束，第i個(gè)位置選擇的工序號(hào)，并不能取自{1,2,…,N}的任何數(shù)，而是與之前的選擇有關(guān)。

引入邏輯向量poslog∈RN，表示當(dāng)前位置可以選擇的工序號(hào)

(14)

這樣，可利用poslog向量對(duì)概率分布進(jìn)行篩選，去除不該選擇的工序的可能性。用MATLAB代碼表示如下：

pr=Pr1(i,:).*poslog，

pr=pr/sum(pr)。

(15)

其中符號(hào)“.*”表示對(duì)應(yīng)元素相乘。這樣篩選得到的pr就是概率分布向量，可直接根據(jù)它生成i位置上的可行解。這里起關(guān)鍵作用的是poslog向量，稱為隨機(jī)分布篩。一旦第i位置上的工序選定，則更新poslog，篩選i+1位置上的生成概率分布。

整個(gè)隨機(jī)生成可行的IP的過程命名為feasiblegenIP，用算法形式表示如下。

算法3feasiblegenIP算法。

輸入：初始化概率分布矩陣Pr1，初始poslog。

置i=1，

步驟1篩選生成概率分布pr=Pr1(i,:).*poslog;pr=pr/sum(pr)。

步驟2由pr生成當(dāng)前工序號(hào)，IP(i)。

步驟3更新poslog，poslog+=refresh(poslog)。

步驟4若i=N，停止循環(huán)，輸出IP；否則，置i=i+1，轉(zhuǎn)步驟1。

對(duì)于機(jī)器分配向量P，也可用類似方法處理，過程命名為feasiblegenP。通過隨機(jī)分布篩，求解FJSP的約束優(yōu)化模型式(7)可轉(zhuǎn)化為無約束優(yōu)化問題，從而納入到CE算法框架下求解，該過程命名為CEopt。根據(jù)式(15)可知，只要初始采樣分布矩陣元素都非零，則poslog只會(huì)消除不可行解的可能性，而保留所有可行解的生成可能性。這使得算法有一定的概率生成任何一個(gè)可行解，從而保證了試探解散布的廣泛性。

2.3 兩階段計(jì)算模型

CEopt優(yōu)化的目標(biāo)函數(shù)，以[IP,P]為決策變量，維數(shù)是2N，如果能降低決策變量的維數(shù)，相當(dāng)于壓縮了可行解集，同樣的采樣數(shù)目在可行域中的分布就更加稠密，從而在隨機(jī)采樣時(shí)能以更高的概率取得最優(yōu)解?；谶@樣的動(dòng)機(jī)，本文提出了兩階段計(jì)算模型：首先對(duì)給定的工序順序IP尋找到最優(yōu)的機(jī)器分配P，相當(dāng)于確定了二者之間的函數(shù)關(guān)系

(16)

然后求解以IP為決策變量的N維優(yōu)化問題

(17)

式(16)可以通過傳統(tǒng)優(yōu)化方法求解，而式(17)采用CE算法。理論上，問題式(16)和式(17)與傳統(tǒng)調(diào)度問題式(1)的最優(yōu)解對(duì)應(yīng)的決策是等價(jià)的，而問題的維數(shù)卻減少了一半。

2.4 半窮舉半貪婪算法

兩階段法實(shí)施的關(guān)鍵在于對(duì)式(16)問題的高效求解。給定工序順序后，對(duì)每個(gè)位置上的工序優(yōu)選機(jī)器，每個(gè)位置都有m種選擇(如果機(jī)器都可用)，N個(gè)位置共有mN種組合方式。貪婪算法計(jì)算量相對(duì)較小，雖然不能保證找到最優(yōu)解，但常用來尋找“不劣解”。其做法是：對(duì)第i個(gè)位置(相應(yīng)工序號(hào)IP(i))尋找最優(yōu)的機(jī)器，使得該位置對(duì)應(yīng)工序完成時(shí)間ct(i)最小，機(jī)器號(hào)記入P(IP(i))。當(dāng)i取遍所有位置時(shí)，就得到了機(jī)器分配P。貪婪算法最大的問題是它的短視性，作為改進(jìn)，提出半窮舉半貪婪算法，算法具體步驟如下：

算法4半窮舉半貪婪算法。

步驟1對(duì)排序的第1～K個(gè)位置，采用窮舉法，試探m種機(jī)器，共有mK種組合，計(jì)算每種組合導(dǎo)致的工序結(jié)束時(shí)間ct。

步驟2對(duì)每一種組合，從i=K+1開始，使用貪婪算法，為余下的N-K個(gè)位置尋找機(jī)器分配。

該算法是貪婪算法與窮舉法的結(jié)合，稱為“半窮舉半貪婪算法”。本文中的兩階段計(jì)算模型中，子問題式(16)采用K=1的半窮舉半貪婪算法；而子問題式(17)依然采用CE算法。整個(gè)兩階段計(jì)算過程記為twostage。

本節(jié)引入的幾個(gè)工具和計(jì)算模型，是基于FJSP和CE算法特點(diǎn)設(shè)計(jì)的：隨機(jī)分布篩解決工序約束條件下的隨機(jī)采樣問題；兩階段計(jì)算模型充分利用FJSP機(jī)器分配和工序排序表示上的可分離性實(shí)現(xiàn)降維，降低CE算法計(jì)算負(fù)擔(dān)；半窮舉半貪婪算法利用了小規(guī)模FJSP的啟發(fā)式方法的思想。這些改進(jìn)和等價(jià)解的歸總表示一起嵌入到CE算法框架中，與FJSP深度融合，具體在下一章闡述。

3 混合CE優(yōu)化算法

3.1 純隨機(jī)采樣的混合CE優(yōu)化算法

在保持CEopt的結(jié)構(gòu)框架的前提下，將兩階段計(jì)算模型嵌入到生成可行解步驟中，既保持了CEopt按概率收斂的特性，又利用了兩階段計(jì)算過程的快速性，得到混合CE優(yōu)化算法hybridCEopt1。設(shè)置算法切換的二維概率分布向量pswitch=[p,1-p]，以概率p生成1，以概率1-p生成0，0和1作為切換算法的依據(jù)。

算法5hybridCEopt1算法。

給定工件數(shù)、各工序數(shù)、各工序號(hào)矩陣，初始的概率生成矩陣Pr1、Pr2，概率分布篩poslog，算法切換概率分布向量pswitch，采樣數(shù)ns，置k=1。

步驟1對(duì)每個(gè)工作位置，利用Pr1和poslog生成ns個(gè)可行的加工順序IP(即執(zhí)行算法feasiblegenIP)。

步驟2利用pswitch按概率生成算法選擇標(biāo)志flag，若flag=1，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟4。

步驟3用步驟1生成的IP求解式(16)問題，得P；并計(jì)算函數(shù)值f(IP,P)。

步驟4利用Pr2生成ns個(gè)可行的機(jī)器分配P(即執(zhí)行算法feasiblegenP)，并計(jì)算函數(shù)值f(IP,P)。

步驟5根據(jù)ns個(gè)函數(shù)值，篩選精英樣本，更新概率分布矩陣Pr1和Pr2；poslog恢復(fù)為初始值。若滿足終止條件，程序終止；否則，置k=k+1，轉(zhuǎn)步驟1。

hybridCEopt1算法保持了CE算法的框架，只是在具體實(shí)現(xiàn)中嵌入了第2章中的改進(jìn)工具。1.3節(jié)引入的等價(jià)解歸總表示的排序算法，在上述步驟1后執(zhí)行，得到排序后的IP，它將在步驟5中影響概率分布矩陣Pr1的更新，使得生成非歸總表示的等價(jià)解概率降低，從而在下一次迭代中減少冗余解的生成。4.1節(jié)仿真實(shí)驗(yàn)中將通過實(shí)驗(yàn)對(duì)比直觀展現(xiàn)排序的影響。

3.2 局部尋優(yōu)的混合CE優(yōu)化算法

純隨機(jī)搜索的CE算法，每一次迭代的樣本通過一定概率模型的采樣獲得，這使得CE算法具有很強(qiáng)的全局搜索能力，但隨機(jī)采樣用于局部搜索計(jì)算負(fù)荷較大。針對(duì)該問題，采用了兩項(xiàng)加強(qiáng)措施：

(1)用啟發(fā)式方法找到一些非劣解加入到初始解集合中，加強(qiáng)hybridCEopt1算法的步驟1和步驟4，使得算法啟動(dòng)時(shí)就能將采樣分布矩陣更新到較好的分布。

(2)利用局部尋優(yōu)技術(shù)，對(duì)精英樣本進(jìn)行局部尋優(yōu)，加強(qiáng)hybridCEopt1算法的步驟5，提高獲得最優(yōu)解的概率。

措施(1)采用類似文獻(xiàn)[5]中的初始樣本選取方法：①在初始隨機(jī)采樣中選取1/8的樣本，固定機(jī)器分配P，改造工序順序IP：隨機(jī)采用最長(zhǎng)加工時(shí)間優(yōu)先(Longest Processing Time, LPT)規(guī)則和最多剩余工序優(yōu)先(Most Operations Remaining, MOR)規(guī)則;②在初始隨機(jī)采樣中另外選取1/8的樣本，固定工序順序IP，改造機(jī)器分配，將工序分配給工作量最小的機(jī)器。將改造后的樣本與剩余樣本一起用于更新分布。

措施(2)采用文獻(xiàn)[6]中搜索算子的思想，分別固定P和IP，搜索更好的IP和P，類似于2.3節(jié)中兩階段法。不同的是這里采用隨機(jī)方法。將精英樣本按照優(yōu)劣排序?yàn)閄1,X2,…,Xelite，先將下標(biāo)形如X4i+1,X4i+2的樣本用于搜索IP，將形如X4i+3,X4i+4的樣本用于搜索P，如有多余的精英就舍棄不用；然后交換搜索次序，再做一次。

搜索IP的方法是：對(duì)某兩個(gè)樣本X4i+1,X4i+2，固定P，隨機(jī)選取某些工件構(gòu)成集合J，固定X4i+1中非J工件對(duì)應(yīng)工序的位置，其他位置按照X4i+2中J工件的各工序排序，得到新的樣本Y4i+2。如果Y4i+2優(yōu)于X4i+2，則取代X4i+2。交換X4i+1,X4i+2二者地位，再進(jìn)行一次上述操作。

搜索P的方法是：對(duì)某兩個(gè)樣本X4i+3,X4i+4，固定IP，隨機(jī)選取P向量中的某幾個(gè)位置J，交換兩個(gè)樣本中P對(duì)應(yīng)位置的分量：P4i+3(j)?P4i+4(j),j∈J，得到兩個(gè)新樣本Y4i+3和Y4i+4。如果新樣本優(yōu)于原樣本，則取而代之。

局部搜索中，樣本向量中變動(dòng)的分量J通過隨機(jī)方法選取，但優(yōu)先選取關(guān)鍵路徑中的工序位置和機(jī)器。通過以上改進(jìn)的算法命名為hybridCEopt2算法。雖然局部尋優(yōu)依然采用隨機(jī)方法，但搜索區(qū)域不再是整個(gè)解空間，而是精英解集內(nèi)部各向量之間部分元素交叉互換后的可行解集，計(jì)算復(fù)雜度并沒有提升。

4 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)在Intel Core i7-8550U CPU、8 GB RAM 計(jì)算機(jī)的MATLAB R2016環(huán)境上進(jìn)行。仿真實(shí)驗(yàn)分為兩部分內(nèi)容：①在CEopt框架下，研究可行解的歸總表示對(duì)算法收斂速度的影響，以驗(yàn)證模型改進(jìn)的效果；②檢驗(yàn)帶局部尋優(yōu)的混合型算法hybridCEopt2有效性，與其他智能算法比較。

4.1 模型改進(jìn)對(duì)算法收斂速度的提升作用

采用KACEM等[25]所提算例，展現(xiàn)采用可行解的歸總表示排序?qū)λ惴ㄓ?jì)算效率的影響，使用原始框架下的CEopt算法。CEopt算法中的參數(shù)為：?jiǎn)未巫钌俨蓸訕颖緮?shù)300，精英樣本數(shù)50，初始采樣分布均采用離散均勻分布，平滑系數(shù)0.3。實(shí)驗(yàn)分兩組進(jìn)行：①對(duì)生成的可行解進(jìn)行歸總表示排序;②直接使用生成的可行解，不排序。每次實(shí)驗(yàn)分別使用CEopt迭代200次，記錄首次求得最優(yōu)解的迭代次數(shù)、采樣數(shù)量、求得最優(yōu)解總次數(shù)和總采樣數(shù)。進(jìn)行10次實(shí)驗(yàn)，求其平均值取整，結(jié)果如表1所示。

表1 可行解歸總表示排序?qū)E算法的影響

由實(shí)驗(yàn)可知，采用可行解排序處理的算法，首次取得最優(yōu)解所需迭代次數(shù)和采樣點(diǎn)都更少，減少20%。值得注意的是：根據(jù)表1中“首次獲得最優(yōu)解的迭代次數(shù)”和“200次迭代中求得最優(yōu)解次數(shù)”數(shù)據(jù)，可推算出排序處理后的算法在第27次迭代求得最優(yōu)解后，每次迭代都取得最優(yōu)解，說明采樣概率分布矩陣也已收斂；而未經(jīng)排序的算法，在第34次迭代求得最優(yōu)解后，有21次迭代沒有找到最優(yōu)解。

如圖1所示為工序生成概率分布矩陣隨迭代的變化情況。選擇第1次迭代，第5次迭代、第20次迭代和第50次迭代時(shí)的概率分布矩陣，以3維柱狀圖反映矩陣各元素的取值。在無排序情況下，概率矩陣p變化緩慢，而在有排序的情況下，概率矩陣p收斂迅速，50次迭代后，最低的概率也接近0.7。這說明可行解的歸總表示能提高收斂速度。當(dāng)機(jī)器和工序數(shù)目更大時(shí)，重復(fù)解的數(shù)量會(huì)變得更多，歸總表示的作用將更加突出。

值得注意的是，用元啟發(fā)式算法求解FJSP的方案中，如果工序排列的基因編碼也采用向量形式，則也會(huì)出現(xiàn)可行解表示不唯一的問題，這將導(dǎo)致一部分交叉、變異操作的無效——仍表示同一個(gè)解，從而使算法效率降低。如果采用歸總表示，并在交叉、變異操作時(shí)避開等價(jià)解，則可望提升種群的多樣性，提高算法效率。

4.2 局部尋優(yōu)的混合型CE算法hybridCEopt2的有效性

hybridCEopt2算法是純隨機(jī)搜索算法hybridCEopt1通過加強(qiáng)初始樣本選擇和局部尋優(yōu)后的改進(jìn)。為驗(yàn)證其有效性，本文通過兩組算例——Kacem1～Kacem5[25]和MK01～MK10[26]，與多種FJSP求解算法進(jìn)行比較。hybridCEopt2算法參數(shù)設(shè)置為：?jiǎn)未巫钌俨蓸訕颖緮?shù)Nmin=10×工件×機(jī)器，單次最多采樣樣本Nmax=10×Nmin，精英樣本數(shù)100，初始采樣分布都用等概率分布，平滑系數(shù)0.2，算法切換概率pswitch=[0.6,0.4]，當(dāng)連續(xù)10次迭代單次采樣點(diǎn)達(dá)到Nmax且最優(yōu)解沒有改善，算法終止。對(duì)算例Kacem1～Kacem5，分別進(jìn)行20次運(yùn)算，成功率和最優(yōu)值作為指標(biāo)列入表2,與文獻(xiàn)[6，13,22,27]中不同算法進(jìn)行比較。hybridCEopt2算法和其他算法一樣，求得同等最優(yōu)值的成功率都達(dá)到了100%。

表2 Kacem1～Kacem5算例計(jì)算結(jié)果

對(duì)算例MK01～MK10，CEopt算法和hybridCEopt2算法各進(jìn)行20次運(yùn)算，求得最優(yōu)值列入表3，與文獻(xiàn)[6，9，15，22，27]中的算法比較，最后兩列括號(hào)中數(shù)字表示平均的最優(yōu)值。其中CEopt算法采用純隨機(jī)搜索，沒有使用本文提出的改進(jìn)措施。由表3中的結(jié)果可看出，除算例MK10外，hybridCEopt2算法求得的最優(yōu)值能達(dá)到其他算法的最優(yōu)水平；文獻(xiàn)[15]的算法利用了關(guān)鍵路徑進(jìn)行精細(xì)的鄰域搜索，使得對(duì)算例MK10表現(xiàn)最好。主要原因在于兩種算法的出發(fā)點(diǎn)不同：文獻(xiàn)[15]的算法是遺傳算法和精選的鄰域結(jié)構(gòu)下局部搜索的結(jié)合，重點(diǎn)在鄰域結(jié)構(gòu)的精選；本文的hybridCEopt2算法沒有使用精細(xì)的局部搜索，是帶有局部搜索功能的隨機(jī)搜索算法，主要為了展現(xiàn)計(jì)算模型的改進(jìn)帶來的優(yōu)勢(shì)，重點(diǎn)在隨機(jī)搜索的模型改進(jìn)，相當(dāng)于更好地實(shí)現(xiàn)文獻(xiàn)[15]算法中遺傳算法的功能，而沒有使用鄰域結(jié)構(gòu)搜索。如果將鄰域搜索算法用于本文的改進(jìn)計(jì)算模型中，則可望有更好的性能。值得注意的是文獻(xiàn)[6]中的兩種算法——BEDA(雙種群EDA)和單種群EDA，和hybridCEopt2算法同屬于基于概率模型的算法。從它們的計(jì)算結(jié)果來看，hybridCEopt2表現(xiàn)普遍優(yōu)于EDA，而與BEDA相當(dāng)：對(duì)MK06算例hybridCEopt2較優(yōu)，而對(duì)MK10算例則BEDA較優(yōu)，對(duì)其他算例二者表現(xiàn)持平。原始的CEopt算法除了對(duì)MK03算例表現(xiàn)稍好以外，對(duì)其余的算例計(jì)算結(jié)果與hybridCEopt2相比差距都較大，這說明本文提出的模型改進(jìn)對(duì)CE算法性能有明顯的提升。表4給出了原始的CEopt算法與hybridCEopt2算法的計(jì)算時(shí)間，可以看出，盡管hybridCEopt2增加了排序和兩階段計(jì)算過程，每一次迭代計(jì)算量增加，但是整體效能高于原始的CEopt算法。特別是對(duì)MK01、MK02、MK03和MK04算例，hybridCEopt2算法所用時(shí)間不到CEopt算法的一半。主要原因是CE型算法采用按照概率分布生成隨機(jī)數(shù)的方式產(chǎn)生樣本，MATLAB程序在生成樣本時(shí)耗時(shí)較長(zhǎng)，而hybridCEopt2算法的改進(jìn)措施提高了樣本的質(zhì)量，減少了迭代次數(shù)，使因迭代次數(shù)減少而導(dǎo)致的計(jì)算量的減少量大于每次迭代計(jì)算量的增加量，總體效率提高。

表3 MK01～MK10算例計(jì)算結(jié)果

表4 CEopt與hybridCEopt2計(jì)算時(shí)間的比較 s

為防止只考慮求得最優(yōu)值而不考慮所遍歷的總體個(gè)數(shù)的局限性，采用基于總體個(gè)數(shù)的評(píng)價(jià)指標(biāo)[13]，以文獻(xiàn)[13]中提出的SMGAIWO(自適應(yīng)變級(jí)遺傳雜草算法)及其性能對(duì)比算法GA(遺傳算法)、IWO(遺傳雜草算法)作為比較對(duì)象，以算例Kacem2進(jìn)行測(cè)試，比較算法性能。結(jié)果如表5所示，其中GA、IWO和SMGAIWO算法的計(jì)算結(jié)果源自于文獻(xiàn)[13]。

表5 Kacem2算例的計(jì)算結(jié)果

續(xù)表5

表5數(shù)據(jù)顯示，GA在遍歷約360 000個(gè)樣本后，得到最優(yōu)解15，最優(yōu)解質(zhì)量不如其他算法的最優(yōu)解14。IWO算法找到最優(yōu)解14需遍歷約360 000個(gè)樣本，SMGAIWO只需約220 000個(gè)樣本。而hybridCEopt1算法不做局部搜索，僅需要18 558個(gè)樣本，hybridCEopt2算法所需樣本更少，效率優(yōu)勢(shì)明顯。圖2為hybridCEopt2求解Kacem2所得最優(yōu)解對(duì)應(yīng)甘特圖。

本文提出的算法hybridCEopt2可以簡(jiǎn)單地看成是全局搜索和局部搜索的結(jié)合，改進(jìn)點(diǎn)主要在全局搜索階段的CE算法，其主要效果是：在局部搜索之前就生成比一般全局搜索更好的可行解集，既提供了好的初始值，又減輕局部搜索的負(fù)擔(dān)，甚至對(duì)某些問題即使不采用局部搜索，也具有很高的效率(如表5)。主要原因是：CE算法根據(jù)概率分布生成的試探解具有廣泛的分布特性，可行解的歸總表示壓縮了搜索空間，而半窮舉半貪婪算法起到了部分局部搜索的功能，使得采用簡(jiǎn)單的局部搜索也能取得很好的效果。

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

通過對(duì)FJSP模型的研究發(fā)現(xiàn)，傳統(tǒng)的工序編碼方式存在不唯一性，使得同一套加工方案對(duì)應(yīng)很多可行解，從而直接影響優(yōu)化算法的求解效率。將FJSP數(shù)學(xué)模型和CE算法計(jì)算模型深度融合，提出了求解FJSP的CEopt算法、hybridCEopt1和hybridCEopt2混合算法，經(jīng)過仿真實(shí)驗(yàn)，得到主要結(jié)論如下：

(1)基于甘特圖的可行解歸總表示對(duì)使用CE方法求解FJSP的效率提升有顯著的作用，表現(xiàn)在采樣分布參數(shù)和最優(yōu)解收斂速度的提高。

(2)不同于拒絕抽樣和罰函數(shù)法，隨機(jī)分布篩處理約束問題可以避免生成不可行解，從而增加有效采樣率，相當(dāng)于將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題，提高CE算法的效率。

(3)使用兩階段計(jì)算模型可以降低問題的決策變量維數(shù)，提高計(jì)算速度。將兩階段計(jì)算模型嵌入CE算法框架得到的混合算法hybridCEopt1是有效且高效的，在不特意引入局部搜索的情況下，計(jì)算所需樣本數(shù)量遠(yuǎn)少于進(jìn)化算法。

(4)對(duì)采樣初始樣本的啟發(fā)式改進(jìn)、引入簡(jiǎn)單的局部尋優(yōu)的hybridCEopt2算法，優(yōu)化能力就能接近使用精細(xì)鄰域搜索的算法，說明對(duì)CE算法的一系列改進(jìn)可使之生成質(zhì)量更高的試探解，減輕后續(xù)局部搜索的負(fù)擔(dān)。

本文的重點(diǎn)在于改進(jìn)計(jì)算模型，在局部尋優(yōu)策略方面，沒有采用精細(xì)的鄰域搜索方法，二者融合是今后值得研究的方向。