劉 凱，黃輝先，趙 驥,2

(1.湘潭大學(xué) 信息工程學(xué)院,湖南 湘潭 411105;2.清華大學(xué) 清華大學(xué)國家CIMS工程技術(shù)研究中心,北京 100084)

0 引 言

作業(yè)車間調(diào)度問題(JSSP)是一個(gè)典型的NP-hard問題[1]，在過去的五十幾年里，一直受到許多學(xué)者的關(guān)注與研究，其研究成果被廣泛應(yīng)用于生產(chǎn)，工程管理，計(jì)算機(jī)等領(lǐng)域，因此研究JSSP具有重要的學(xué)術(shù)和實(shí)際意義。而作為JSSP的擴(kuò)充，模糊作業(yè)車間調(diào)度問題(fuzzy job-shop sche-duling problem,FJSSP)在JSSP的基礎(chǔ)上加入不確定性條件如模糊加工時(shí)間，使得問題更接近真實(shí)的生產(chǎn)情況，更具研究?jī)r(jià)值。Tsujimura Y等人[2]最先用遺傳算法(genetic alorithm,GA)解決帶模糊加工時(shí)間的FJSSP，Sakawa M等人[3]將GA進(jìn)行了改進(jìn)并應(yīng)用于具有模糊加工時(shí)間和模糊交貨期的FJSSP，Niu Q等人[4]通過將GA中的交叉和變異算子結(jié)合到粒子群優(yōu)化(PSO)算法中對(duì)PSO進(jìn)行改進(jìn)并應(yīng)用于FJSSP中，最后和GA進(jìn)行比較驗(yàn)證了算法的優(yōu)越性。Hu Y等人[5]用改進(jìn)的差分進(jìn)化算法(DE)對(duì)FJSSP進(jìn)行了求解。Bustos-Tellez C A等人[6]利用線性規(guī)劃(LP)的方法對(duì)FJSSP建立了模糊LP模型。然而，相比JSSP，對(duì)于FJSSP的研究還遠(yuǎn)遠(yuǎn)不夠，并且多元啟發(fā)式方法容易陷入局部最優(yōu)解，而LP方法又在求解大規(guī)模問題上太過復(fù)雜，難以計(jì)算，所以仍須研究人員能夠提出更多更好的解決方法來解決問題。

烏鴉搜索算法(crow search algorithm,CSA)是Askarzadeh A[7]提出的新群體智能算法。Sayed G I等人[8]對(duì)該算法引入了混沌機(jī)制,即混沌烏鴉搜索算法(chaotic crow search algorithm,CCSA)并成功應(yīng)用于二進(jìn)制特征選擇問題，最終對(duì)比發(fā)現(xiàn)該算法具有優(yōu)秀的全局優(yōu)化能力和求解速度。劉雪靜等人[9]將CCSA應(yīng)用于0—1背包問題上同樣得出其具有良好的全局尋優(yōu)能力和收斂速度，這些應(yīng)用都表現(xiàn)出CCSA值得在更多不同領(lǐng)域被研究，因此，本文提出將CCSA應(yīng)用于求解帶模糊加工時(shí)間的FJSSP上，并且通過對(duì)問題和算法的研究將算法做了改進(jìn)，最后進(jìn)行了對(duì)比仿真實(shí)驗(yàn)，驗(yàn)證了本文所提出的改進(jìn)策略的有效性以及所提算法能夠有效求解FJSSP。

1 FJSSP

FJSSP的描述和數(shù)學(xué)模型可參考文獻(xiàn)[4]。而目標(biāo)函數(shù)選用minCmax=max{C1,C2,…,Cj,…,Cn}，即最小化最大完成時(shí)間，其中Cj為工件j的模糊完成時(shí)間。

FJSSP中引入模糊三角數(shù)(triangular fuzzy number ,TFN)表示問題中的模糊加工時(shí)間[3]，TFN運(yùn)算比較參考文獻(xiàn)[3]。其中考慮到FJSSP的實(shí)際意義，本文提出如式(1)所示的取大運(yùn)算方式

C=max{A,B}

=(max{a1,b1},max{a2,b2},max{a3,b3})

(1)

圖1為兩個(gè)TFN的取大操作圖

圖1 TFN取大操作準(zhǔn)則

2 CCSA

CSA是受到烏鴉群藏匿食物的行為啟發(fā)而來的[7]，而CCSA在CSA的基礎(chǔ)上引入了混沌序列。假設(shè)烏鴉群的數(shù)量為N，yi,t為烏鴉i在第t次搜索之后的位置，此時(shí)它所找到的最佳藏匿食物的位置稱為烏鴉的記憶位置，記為Mi,t，其中,i=1,2,…，N;t=1，2…，tmax,tmax表示最大搜索次數(shù)。算法主要步驟如下：

步驟1 初始化。初始化yt,1，Mi,1=yi,1。

步驟2 搜索新位置。群體中每只烏鴉會(huì)隨機(jī)選擇另一只烏鴉作為目標(biāo)進(jìn)行位置搜索。假設(shè)在第t次迭代中，烏鴉i進(jìn)行跟隨的是烏鴉z，則這時(shí)會(huì)出現(xiàn)兩種情況：

1)烏鴉z沒有發(fā)現(xiàn)自己被烏鴉i跟隨

烏鴉i將靠近烏鴉z的記憶位置Mz,t，通過式(2)更新烏鴉i的位置

yi,t+1=yi,t+Ci×fl×(Mz,t-yi,t)

(2)

式中fl為表示搜索步長；Ci∈(0,1)，為混沌序列的第i個(gè)值，該混沌序列由Circle Map[10]來產(chǎn)生，其映射公式為

c=0.5,d=0.2

(3)

2)烏鴉z發(fā)現(xiàn)自己被烏鴉i跟隨了

此時(shí)烏鴉i無法靠近烏鴉z的記憶位置，只能隨機(jī)找一個(gè)新位置來更新自己的位置。

根據(jù)上述兩種情況的描述可將烏鴉i的位置更新公式總結(jié)如下

(4)

式中APi,t為烏鴉z在第t次搜索時(shí)能夠發(fā)現(xiàn)被烏鴉i跟隨的概率。

步驟3 更新記憶位置。群體中的烏鴉在每次搜索更新完自己的位置之后，通過一個(gè)評(píng)價(jià)函數(shù)Fn判斷是否替換記憶位置，具體更新公式為

(5)

步驟4 重復(fù)步驟(2)～步驟(3)搜索tMax次。

步驟5 輸出優(yōu)化結(jié)果。烏鴉群中最優(yōu)的記憶位置即為算法的最終優(yōu)化結(jié)果。

3 FJSSP的CCSA

基于針對(duì)FJSSP特點(diǎn)設(shè)計(jì)出可應(yīng)用于求解FJSSP的CCSA。算法的編碼策略采用基于工序的編碼[2]。

3.1 修補(bǔ)與變異

由于CCSA的變量是連續(xù)的，要想求解FJSSP這類離散問題便需設(shè)計(jì)一個(gè)修補(bǔ)算子對(duì)位置更新公式計(jì)算出的新解進(jìn)行修補(bǔ)操作，使算法能夠在正確的解空間中進(jìn)行搜索。同時(shí)，由于CCSA單單依靠式(4)進(jìn)行搜索過于單一，無法對(duì)目標(biāo)個(gè)體的鄰域充分搜索。因此引入變異算子以概率Pmutate將新解進(jìn)行變異，以此豐富個(gè)體的鄰域搜索行為。變異方式采用自身交換策略：隨機(jī)選擇解中的兩個(gè)編碼不同的位置進(jìn)行交換。具體算法描述如下：

算法1新解的修補(bǔ)與變異算法

輸入：CCSA按式(4)計(jì)算出的新解，ynew。

輸出：經(jīng)過修補(bǔ)與變異之后的解，ymutate。

1)將ynew向上取整得到y(tǒng)cell。

2)分別統(tǒng)計(jì)ycell中范圍在工件號(hào)內(nèi)的各個(gè)編號(hào)出現(xiàn)的次數(shù)。

3)將ycell中小于1的數(shù)從小到大修正為工件號(hào)統(tǒng)計(jì)次數(shù)小于工序數(shù)的最小工件號(hào)，同理將大于工件數(shù)的編號(hào)從大到小修正為工件號(hào)統(tǒng)計(jì)次數(shù)小于工序數(shù)的最大工件號(hào)，得到y(tǒng)correct。

4)在ycorrect中隨機(jī)選擇兩個(gè)不同的工件編號(hào)進(jìn)行交換，得到y(tǒng)mutate。

3.2 多樣最優(yōu)個(gè)體集

原始CCSA中引導(dǎo)更新的目標(biāo)個(gè)體為隨機(jī)選擇，為提高烏鴉的搜索效率并保證種群的多樣性，本文提出基于相似性度量的多樣性最優(yōu)選擇策略來優(yōu)化和豐富目標(biāo)集。

為了評(píng)估兩個(gè)個(gè)體間的相似度，本文引入經(jīng)常被用于信息檢索當(dāng)中的基于余弦(cosine)定理[11]的相似性度量方式。用X和Y來表示兩個(gè)個(gè)體，其中用xi表示X的第i個(gè)分量，yi表示y的第i個(gè)分量，則

(6)

由于在FJSSP中，個(gè)體X和Y中的每個(gè)元素都是正整數(shù)，因此,任何兩個(gè)個(gè)體之間的cosθ都在[0,1]之間，數(shù)值越接近1，則表示X和Y的相似度越大。因此，基于余弦相似度的多樣最優(yōu)個(gè)體集的選擇算法如算法2。

算法2多樣最優(yōu)個(gè)體集選擇算法

輸入：第t代群體的記憶位置，Mt；最優(yōu)的記憶位置個(gè)數(shù)，sp；多樣的記憶位置個(gè)數(shù)，div；相似度閾值，R。

輸出：多樣最優(yōu)個(gè)體目標(biāo)集，set。

1)隨機(jī)生成一個(gè)目標(biāo)集set。

2)從Mt中選擇評(píng)價(jià)值為前sp名的個(gè)體逐個(gè)對(duì)set進(jìn)行隨機(jī)替換。

3)從剩下的Mt中按順序選擇一個(gè)與Mt中所有個(gè)體的相似度平均值低于R的個(gè)體，然后隨機(jī)替換set中除步驟(2)選中之外的個(gè)體。

4)重復(fù)步驟(3)j次，直到j(luò)等于div或者M(jìn)t遍歷完成。

5)返回目標(biāo)集set。

3.3 基于機(jī)器空閑時(shí)間縮小的搜索方法

由于FJSSP解空間極大且復(fù)雜，使得CCSA群體的搜索效率不高、收斂慢。為了進(jìn)一步提升算法的搜索效率，本文提出一種基于機(jī)器空閑縮小的搜索方法以結(jié)合到CCSA中。在描述方法的具體步驟之前，先有如下定義：

令Stw和Etw分別表示任務(wù)w的開始時(shí)間和結(jié)束時(shí)間。

定義待優(yōu)任務(wù)、待優(yōu)工件、待優(yōu)工序。假設(shè)w1和w2為機(jī)器隊(duì)列中連續(xù)的兩個(gè)任務(wù)，若有Etw1

該搜索方法是通過優(yōu)先加工待優(yōu)工序的前續(xù)工序所在的任務(wù)，使得待優(yōu)任務(wù)的可開始加工時(shí)間提前來縮小機(jī)器的空閑時(shí)間。對(duì)于某個(gè)可行解，隨機(jī)選擇一個(gè)機(jī)器，對(duì)該機(jī)器的加工隊(duì)列進(jìn)行遍歷(首個(gè)任務(wù)不進(jìn)行調(diào)整)，判斷每個(gè)任務(wù)是否為待優(yōu)任務(wù)，若是則以一定的概率Prst進(jìn)行空閑時(shí)間縮小，縮小的算法如算法3。

算法3空閑時(shí)間縮小算法

輸入：?jiǎn)栴}的一個(gè)可行解，S；機(jī)器號(hào)，m；待優(yōu)任務(wù)號(hào)，w。

輸出：調(diào)整之后的新解，Snew。

1)尋找w所屬工件和工序分別記為Jw和pnw。

2)判斷Jw的工序pnw-1所在任務(wù)的可開始時(shí)間是否比當(dāng)前開始時(shí)間小且不在自身機(jī)器隊(duì)列的隊(duì)首，若是則該任務(wù)為可提前任務(wù)，執(zhí)行步驟(3)，否則執(zhí)行步驟(6)。

3)將該可提前任務(wù)和所在隊(duì)列中的前一個(gè)任務(wù)交換，刷新調(diào)度方案，若w之前的空閑時(shí)間為零，則退出計(jì)算返回新解Snew，否則執(zhí)行步驟(4)。

4)若待縮小的空閑時(shí)間減少則執(zhí)行步驟(5)，否則放棄此次交換并退出計(jì)算返回結(jié)果Snew。

5)若pnw-1>1，則保留此次交換，然后以Snew作為算法3的輸入遞歸執(zhí)行，否則保留交換，退出計(jì)算返回Snew。

6)令pnw=pnw-1，若pnw>1則重新執(zhí)行步驟(2)。

7)返回結(jié)果Snew。

為避免因?yàn)橐胍?guī)律導(dǎo)致種群個(gè)體過于集中，陷入局部最優(yōu)，本文采用隔代搜索，每間隔eg代從種群中選擇N×sr,(0

3.4 算法流程

根據(jù)上述設(shè)計(jì)，改進(jìn)后的算法總體流程如圖2所示。

圖2 算法總體流程圖

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

為了驗(yàn)證算法對(duì)于FJSSP的有效性，本文從文獻(xiàn)[13]中選取了Job Shop調(diào)度中的5個(gè)典型的Benchmark并做模糊化的處理，模糊化的方式為T=(t-rand,t,t+rand)，其中rand表示小于t的隨機(jī)整數(shù)，且當(dāng)t越大時(shí)，rand占t的比重越小。同時(shí)為了方便比較，結(jié)果比較都采用最大模糊完成時(shí)間的中間數(shù)作為參考。

實(shí)驗(yàn)環(huán)境：算法編程平臺(tái)為MATLAB R2016b,操作系統(tǒng)為Windows7_64位,CPU為Intel Core i7-7500U@2.70 GHZ,內(nèi)存為8 GB。

本文分別將原始的CCSA,加入變異算子和多樣最優(yōu)個(gè)體集的XD-CCSA(X-diversity-chaotic crow search algorithm),本文所提算法RST-CCSA(reducing spare time-chaotic crow search algorithm)以及GA在5個(gè)實(shí)例上測(cè)試了各10次。所有測(cè)試中種群數(shù)量都設(shè)置為N=200，均進(jìn)化2 000代，其余參數(shù)AP=0.2，fl=2.0，變異概率Pmutate=0.28，目標(biāo)集中最優(yōu)個(gè)體數(shù)sp=5，低相似度個(gè)體數(shù)div=20，相似度閾值R=0.86，基于機(jī)器空閑時(shí)間搜索方法的參數(shù)eg=50，sr=0.4，Prst=0.88。

實(shí)驗(yàn)結(jié)果如表1所示，表中給出了10次測(cè)試所得的最優(yōu)值、最差值、平均值以及所占CPU平均值時(shí)間，表中各個(gè)實(shí)例編號(hào)下面的加粗?jǐn)?shù)據(jù)為BKS值，即已知文獻(xiàn)中的最優(yōu)解。

表1 各算法的計(jì)算結(jié)果

從表中數(shù)據(jù)可看出相較于改進(jìn)前的CCSA，XD-CCSA的尋優(yōu)能力得到了加強(qiáng)，說明本文設(shè)計(jì)的變異算子和多樣最優(yōu)個(gè)體集為CCSA的搜索帶來了更多的信息，增強(qiáng)了種群的多樣性，提高了算法的尋優(yōu)能力。而RST-CCSA相較于包括GA在內(nèi)的其它三個(gè)，其尋優(yōu)能力最強(qiáng)，在FT06,FT10和LA11上達(dá)到BKS值，且在FT10上只有RST-CCSA達(dá)到了best know solution(BKS)值，在FT20和LA16上雖沒有達(dá)到BKS值，但較于GA來說表現(xiàn)更好，說明本文提出的基于機(jī)器空閑時(shí)間縮小的搜索方法能夠在進(jìn)化過程中提高種群個(gè)體的搜索能力，從而整體提高算法的尋優(yōu)能力。但不足的是需犧牲一定的算法效率。從表2中數(shù)據(jù)可看出，RST-CCSA相較于CCSA來說CPU time消耗都比較大，但是較于GA來說，RST-CCSA的時(shí)間消耗還是可以接受的，甚至在FT06這種規(guī)模較小的問題上消耗要小于GA。

表2 各算法CPU平均時(shí)間 s

本文還做了收斂性對(duì)比，如圖3中的進(jìn)化曲線所示，由于FT06規(guī)模較小，各算法表現(xiàn)都不錯(cuò)，可比性不強(qiáng)，因此只對(duì)FT10,FT20,LA11,LA16進(jìn)行了對(duì)比。從圖中可以看出混沌烏鴉算法有較強(qiáng)的持續(xù)進(jìn)化能力，而RST-CCSA雖然在前期的收斂速度上稍弱于GA，但是得益于CCSA的持續(xù)進(jìn)化能力，RST-CCSA的最終優(yōu)化結(jié)果要好于GA。同時(shí)也可以看出RST-CCSA相較于原始CCSA，其收斂速度有所提升，可見本文的改進(jìn)既保留了CCSA的持續(xù)進(jìn)化能力，同時(shí)還提高了收斂速度，從而使得算法整體性能有較大的提升。

圖3 算法進(jìn)化曲線

5 結(jié)束語

本文采用基于工序的編碼方式并設(shè)計(jì)修補(bǔ)算子,成功地將CCSA應(yīng)用于求解FJSSP上。并通過引入變異算子豐富了個(gè)體的搜索行為，通過設(shè)計(jì)多樣最優(yōu)個(gè)體集使算法在提高搜索效率的同時(shí)保證了種群信息的多樣性，通過設(shè)計(jì)一種基于機(jī)器空閑時(shí)間縮小的新搜索方法融合進(jìn)算法中進(jìn)一步提高了算法的搜索效率和求解質(zhì)量。通過對(duì)5個(gè)經(jīng)典實(shí)例的測(cè)試、對(duì)比和分析，驗(yàn)證了所做出的改進(jìn)有效提高了收斂速度和尋優(yōu)能力，而且比GA具有更好的求解質(zhì)量，為求解FJSSP提供了一種新的有效解決方式以及為求解其它類似問題提供了參考。本文所提算法在其收斂速度上還有提升的空間，值得進(jìn)一步研究。