鄭小操，龔文引

(中國地質(zhì)大學(xué)(武漢)計(jì)算機(jī)學(xué)院，湖北武漢 430074)

1 引言

調(diào)度在生產(chǎn)系統(tǒng)的決策和現(xiàn)代制造業(yè)中資源的分配中都起著至關(guān)重要的作用[1].柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是現(xiàn)今許多實(shí)際問題的抽象，具有很強(qiáng)的現(xiàn)實(shí)意義，因此一直是運(yùn)籌學(xué)領(lǐng)域研究的熱點(diǎn).FJSP是由車間調(diào)度問題(job-shop scheduling problem，JSP)發(fā)展而來的，是一種典型的非確定性多項(xiàng)式(nondeterministic polynomial，NP)難問題.對于傳統(tǒng)的作業(yè)車間調(diào)度問題，工序在加工過程中可選擇的機(jī)器只有一個(gè)，而FJSP中有的工序可能有多個(gè)機(jī)器可供選擇，這更符合現(xiàn)代制造業(yè)和交通運(yùn)轉(zhuǎn)的實(shí)際特點(diǎn).因此在對FJSP進(jìn)行求解的過程中不僅要考慮工序的加工順序問題，還要考慮機(jī)器的選擇問題.所以FJSP要比傳統(tǒng)的JSP要復(fù)雜得多.

FJSP在現(xiàn)代制造業(yè)和智能交通系統(tǒng)的調(diào)度中都起著至關(guān)重要的作用.近些年來，群智能算法和智能技術(shù)得到了迅猛的發(fā)展，這些方法被廣泛應(yīng)用于FJSP的求解中，Nouiri等[2]提出了一種高效的分布式粒子群算法來求解FJSP，該算法以最小化最大完工時(shí)間為目標(biāo)，并通過多個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集驗(yàn)證了算法的有效性.針對工序可重疊的FJSP，Meng等[3]設(shè)計(jì)了一種混合人工蜂群算法，并通過實(shí)驗(yàn)證明了改進(jìn)算法具有良好的收斂性.李等[4]提出了一種新型的帝國競爭算法來解決高維多目標(biāo)柔性作業(yè)車間調(diào)度問題，該算法采用新方法構(gòu)建初始帝國使得大多數(shù)殖民國家分配數(shù)量相近的殖民地.Gao等[5]提出的離散和聲搜索算法同樣能非常高效地求解FJSP.

現(xiàn)實(shí)中的調(diào)度問題是多種多樣的，不同調(diào)度問題的結(jié)合，又能產(chǎn)生許多復(fù)雜多樣的調(diào)度問題.在實(shí)際進(jìn)行調(diào)度的過程中，可能會(huì)遇到一些突發(fā)情況和一些實(shí)際需求，例如機(jī)器出現(xiàn)故障[6-7]、綠色低碳調(diào)度[8-10]、工件在加工的過程中需要消耗資源[11]、在調(diào)度的過程中有運(yùn)輸約束等[12-13]，由此又可以形成許多實(shí)時(shí)調(diào)度問題.還有許多多目標(biāo)調(diào)度問題[14-15]、分布式車間調(diào)度問題[16].在這些復(fù)雜多樣的調(diào)度問題中，工序在機(jī)器上加工的時(shí)間往往是一個(gè)確定的值，但是在實(shí)際的生產(chǎn)調(diào)度過程中，工序加工的時(shí)間往往是不確定的.例如在搭乘高鐵的時(shí)候，有些車次會(huì)出現(xiàn)晚點(diǎn)的情況.機(jī)器在運(yùn)轉(zhuǎn)的過程中會(huì)發(fā)生故障等.因此，加工和運(yùn)行時(shí)間的模糊性是現(xiàn)代制造業(yè)和交通系統(tǒng)調(diào)度中的一個(gè)普遍特點(diǎn)，具有很重要的研究價(jià)值.Sakawa等[17]首次采用遺傳算法(genetic algorithm，GA)來求解模糊作業(yè)車間調(diào)度問題，采用了三角模糊數(shù)來表示加工的時(shí)間，并通過特定的規(guī)則來進(jìn)行三角模糊數(shù)的運(yùn)算.模糊柔性作業(yè)車間調(diào)度問題(fuzzy flexible job-shop scheduling problem，F(xiàn)FJSP)是FJSP與模糊作業(yè)車間調(diào)度問題的結(jié)合[18]，F(xiàn)FJSP更加符合實(shí)際生產(chǎn)調(diào)度的需求.許多研究者針對FFJSP做了大量的研究.Lei提出了一種協(xié)同進(jìn)化的遺傳算法(co-evolutionary genetic algorithm，CGA)[19]能非常高效地求解FFJSP.該算法應(yīng)用了一種新穎的交叉操作和改進(jìn)的錦標(biāo)賽選擇策略.Wang等[20]設(shè)計(jì)了一種高效的分布式估計(jì)算法(estimation of distribution algorithm，EDA)，在解碼的過程中采用了左移策略，很好地利用了機(jī)器的空閑等待時(shí)間.Gao等[21]提出了一種離散和聲搜索算法(discrete harmony search algorithm，DHS)來求解FFJSP，該算法提出了一種有效的啟發(fā)式規(guī)則來初始化和聲庫.Huang等[22]采用6種啟發(fā)式規(guī)則來初始化工序序列，提出了一種改進(jìn)的離散粒子群算法(improved discrete particle swarm optimization，IDPSO)求解FFJSP.

人工蜂群算法(artificial bee colony algorithm，ABC)[23]是一種新穎的群智能算法，因其具備良好的優(yōu)化性能以及需要設(shè)定的參數(shù)較少[24]，所以一直以來都是研究者們研究的熱點(diǎn).Sharma等[25]提出了一種啤酒泡沫人工蜂群算法(beer artificial bee colony algorithm，BeFABC)來求解JSP，該算法在觀察蜂階段，將啤酒泡沫現(xiàn)象引入到位置更新的過程中，這樣可以很好地平衡算法的勘探與開采能力.Wang等[26]設(shè)計(jì)了一種高效的ABC來求解FJSP，該算法在觀察蜂階段采用基于關(guān)鍵路徑的局部搜索(local search，LS)來改善蜜源.Gao等[27]采用分兩階段的人工蜂群算法來求解有新工件插入的柔性作業(yè)重調(diào)度問題，該論文提出了一種高效的機(jī)器選擇策略.針對FFJSP，Wang等[28]提出了一種混合人工蜂群算法(hybrid artificial bee colony algorithm，HABC)，該算法采用多種策略來初始化種群，并且通過變鄰域搜索來提升算法的局部搜索能力.Gao等[29]設(shè)計(jì)了一種改進(jìn)的人工蜂群算法(improved artificial bee colony algorithm，IABC)求解FFJSP，該算法以最小化最大模糊完工時(shí)間和機(jī)器總負(fù)載為優(yōu)化目標(biāo).

現(xiàn)有的求解FFJSP的算法往往存在著一定不足，例如需要設(shè)定的參數(shù)較多，初始種群的多樣性太低，局部搜索能力較差等.針對這些缺點(diǎn)和不足，本文提出了一種基于鄰域搜索(neighborhood search，NS)的ABC，該算法以最小化最大模糊完工時(shí)間為目標(biāo).首先采用混沌初始化的方式來初始化種群，保證了種群的多樣性.然后利用4種鄰域結(jié)構(gòu)對種群中的個(gè)體進(jìn)行鄰域搜索，以此來增強(qiáng)其局部搜索能力.并且提出了一種新穎的交叉策略，使種群中的個(gè)體總是與種群最優(yōu)個(gè)體進(jìn)行交叉，這樣既可以有效地改善當(dāng)前個(gè)體的適應(yīng)度值，又能加快種群的收斂速度.在解碼的過程中采用左移策略，盡可能地利用機(jī)器上的空閑時(shí)間，能有效地減小最大模糊完工時(shí)間.通過實(shí)驗(yàn)驗(yàn)證了本文算法具有良好的優(yōu)化性能.

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

2.1 問題描述

FFJSP一般由n個(gè)工件Ji(i=1，2，3，…，n)和m臺(tái)機(jī)器Mk(k=1，2，…，m)組成，每個(gè)工件Ji包括hi道工序，工序Oij表示工件Ji的第j道工序.每道工序可以在一臺(tái)或多臺(tái)機(jī)器上進(jìn)行加工.工序在機(jī)器上加工的時(shí)間用三角模糊數(shù)tijk=(t1，t2，t3)表示，其中t1表示工序最早能完成的時(shí)間，t2表示工序最有可能完成的時(shí)間，t3表示工序最晚完成的時(shí)間.hi表示工件Ji的總工序數(shù).FFJSP的優(yōu)化目標(biāo)是最小化最大模糊完成時(shí)間，這個(gè)時(shí)間是三角模糊數(shù)，如下式所示:

其中:CM表示最大完成時(shí)間，Ci是工件Ji的完成時(shí)間.表1展示了一個(gè)規(guī)模為3個(gè)工件，3個(gè)機(jī)器的FFJSP實(shí)例.表中的各行代表的是工序，各列表示的是機(jī)器.表中的條目是各工序在相對應(yīng)的機(jī)器上加工的模糊時(shí)間.O11對應(yīng)的是第1個(gè)工件的第1道工序.

表1 規(guī)模為3×3的FFJSP實(shí)例Table 1 Example of FFJSP

2.2 三角模糊數(shù)的運(yùn)算

對于FFJSP，所涉及的三角模糊數(shù)的操作包括3種:加法操作，比較操作和模糊取大操作[1].給定兩個(gè)三角模糊數(shù):A=(a1，a2，a3)，B=(b1，b2，b3).

加法操作如下所示:

比較操作:

1) 如果

則A ＞B，反之A ＜B.

2) 如果F1(A)=F1(B)，則當(dāng)

A ＞B，反之A ＜B.

3) 如果F2(A)=F2(B)，則當(dāng)

A ＞B，反之A ＜B.

模糊取大操作:

如果A ＞B，則A ∨B=A，反之A ∨B=B.

3 引入鄰域搜索的人工蜂群算法

3.1 人工蜂群算法

人工蜂群算法(ABC)[23]是一種新穎的群體智能算法，它的基本思想來源于自然界中蜜蜂的覓食過程.在ABC中總共有3類蜜蜂:雇傭蜂、觀察蜂和偵查蜂.每個(gè)蜜源代表一個(gè)可行解，蜜源的質(zhì)量對應(yīng)可行解的適應(yīng)度[30].ABC的主要步驟如下:

1) 初始化參數(shù)和種群階段.

ABC的參數(shù)有:蜜源的個(gè)數(shù)(SN)，控制次數(shù)(limit)，雇傭蜂和觀察蜂的數(shù)目，假設(shè)蜜源的維度為n，蜜源的產(chǎn)生如下所示:

式中:j∈{1，2，…，n}，i∈{1，2，…，SN}，Xij對應(yīng)的是第i個(gè)蜜源，第j維的變量，r1是范圍為(0，1)的隨機(jī)數(shù)，Ubj，Lbj分別是第j維變量的上界和下界.

2) 雇傭蜂階段.

在雇傭蜂階段，每個(gè)雇傭蜂會(huì)在與之對應(yīng)的蜜源附近產(chǎn)生一個(gè)新的蜜源，如下所示:

其中:j∈{1，2，…，n}，k∈{1，2，…，SN}且k/=i，r2是[-1，1]中均勻分布的實(shí)數(shù)，如果新蜜源的適應(yīng)度值優(yōu)于或等于原蜜源的適應(yīng)度值，則新蜜源取代原蜜源.否則保留原蜜源.

3) 觀察蜂階段.

觀察蜂通過概率Pi選擇一個(gè)蜜源Xi進(jìn)行操作，Pi的計(jì)算式如下所示:

式中:fi表示蜜源Xi的適應(yīng)度值，蜜源的適應(yīng)度值越大，被選擇的概率就越大.蜜源被選擇后，通過式(4)得到一個(gè)新蜜源，如果新蜜源的適應(yīng)度值大于或等于Xi的適應(yīng)度值，則新蜜源替代Xi.

4) 偵查蜂階段.

如果蜜源Xi經(jīng)過limit次迭代操作后都沒有改進(jìn)，則舍棄這個(gè)蜜源并啟用偵查蜂.偵查蜂通過式(3)產(chǎn)生一個(gè)新蜜源.

3.2 編碼與解碼

本文的編碼采用基于工序的編碼.假設(shè)表1的FFJSP實(shí)例的一種基于工序的編碼為(1 2 1 3 1 3 2)，其中的第1個(gè)數(shù)1表示的是第1個(gè)工件的第1道工序，第2個(gè)數(shù)2表示的是第2個(gè)工件的第1道工序，第3個(gè)數(shù)1表示的是第1個(gè)工件的第2道工序.在機(jī)器的選擇中，采用最小完成時(shí)間原則[31].計(jì)算工序在其所有可選機(jī)器上的完成時(shí)間，選擇完成時(shí)間最小的機(jī)器對該工序進(jìn)行加工.所以一旦工序碼改變了，有些工序所選擇的機(jī)器將會(huì)隨之改變.

為了提升解碼性能，本文采用左移策略[32]，通過這種策略，盡可能利用機(jī)器空閑的時(shí)間段，從而減小最大完工時(shí)間.左移策略的操作如圖1所示.圖1針對的是表1中的具體實(shí)例的一種調(diào)度方案，在解碼的過程中，大多數(shù)采用的是后接的方式，也就是在所選機(jī)器的最后一道工序的后面進(jìn)行加工.例如圖1中工序O32，如果選擇機(jī)器2進(jìn)行加工，它將接在O22的后面，則其完成時(shí)間為(17，24，28).如果選擇機(jī)器3進(jìn)行加工，它將接在O12的后面，則O32完成時(shí)間為(20，27，29).如果選擇第3個(gè)機(jī)器進(jìn)行加工，它將接在O22的后面，則O32完成時(shí)間為(17，24，28).如果采用左移策略進(jìn)行解碼，在機(jī)器1中，在O21和O13之間有足夠大的空閑時(shí)間可供加工O32，此時(shí)O32的完成時(shí)間為(4，9，12)，通過這種解碼方式，可以有效地減小最終的最大完工時(shí)間.

圖1 通過左移策略進(jìn)行解碼Fig.1 Decoding by left-shift scheme

假設(shè)工序Oi，j需要在機(jī)器M上進(jìn)行加工，且加工時(shí)間為T，M中存在空閑時(shí)間段為[tS，tE]，tS是空閑開始時(shí)間，tE是空閑結(jié)束時(shí)間.工序Oi，j的前一道工序Oi，j-1的完成時(shí)間為Ci，j-1.如果滿足式(6)的條件，則工序Oi，j可以安排在M的空閑時(shí)間段[tS，tE]內(nèi)進(jìn)行加工.

3.3 種群初始化

在用啟發(fā)式算法求解多元問題時(shí)，初始種群的質(zhì)量往往對種群的收斂速度以及最終的結(jié)果影響非常大，因此生成一個(gè)高質(zhì)量的初始種群非常關(guān)鍵.本文采用混沌初始化的方式來進(jìn)行種群初始化[33].

混沌是非線性動(dòng)力學(xué)系統(tǒng)中的一種運(yùn)動(dòng)形式，具有隨機(jī)性，遍歷性及對初始值敏感性的特點(diǎn)[34].采用混沌初始化可以使初始種群的個(gè)體離散地分布在解空間內(nèi)，能夠非常有效地提高種群的多樣性.在眾多的混沌系統(tǒng)當(dāng)中，Logistic 混沌映射是最典型的混沌系統(tǒng).Logistic混沌映射的系統(tǒng)方程如下:

式中 X(k)是混沌變量，它的取值范圍是(0，1)，當(dāng)u=4時(shí)，系統(tǒng)處于完全混沌狀態(tài).混沌初始化的步驟如下:

步驟1隨機(jī)生成與總工序數(shù)相等數(shù)目的混沌變量，如表2所示.表2中所有工件的總工序數(shù)為7，所以隨機(jī)生成7個(gè)混沌變量.混沌變量序列與工序序列一一對應(yīng).

步驟2將混沌變量序列按從小到大的順序排列.

步驟3將原來與混沌變量相對應(yīng)的工序隨之移動(dòng)，例如混沌變量0.65與工序O11對應(yīng)，0.65經(jīng)過升序排列后位置為5，所以將工序O11也移動(dòng)到第5位.

步驟4將變動(dòng)后的工序序列生成對應(yīng)的工序碼.

通過以上過程便可以生成一個(gè)工序序列，將以上操作的混沌變量序列的每一維經(jīng)過式(7)的變換生成新的混沌變量序列，然后繼續(xù)上面的步驟就可以生成第2個(gè)工序序列，以此類推，就可以完成種群初始化的過程.

表2 初始化工序序列過程Table 2 Proceure of initial operation sequence

3.4 鄰域搜索

在利用群智能優(yōu)化算法求解組合優(yōu)化問題時(shí)，鄰域搜索是一種非常簡單有效的元啟發(fā)式算法.通過對一個(gè)個(gè)體進(jìn)行交換、插入、逆轉(zhuǎn)等操作，可以發(fā)掘出該蜜源附近更加優(yōu)質(zhì)的蜜源，提高算法的局部搜索能力.本文主要采用了4種鄰域結(jié)構(gòu).

1) 鄰域結(jié)構(gòu)N1:隨機(jī)在工序序列中選擇工序碼不同的兩道工序進(jìn)行交換.

2) 鄰域結(jié)構(gòu)N2:在工序序列中隨機(jī)選擇兩道工序，將這兩道工序之間的工序進(jìn)行逆轉(zhuǎn).

3) 鄰域結(jié)構(gòu)N3:隨機(jī)選擇一道工序，將這道工序與其后面的工序進(jìn)行交換.如果這道工序是工序序列中的最后一道工序，則重新選擇.

4) 鄰域結(jié)構(gòu)N4:在工序序列P中隨機(jī)選擇一個(gè)工序O，將其抽離出來形成P1，然后將O插入到P1中所有能插入的位置，形成多個(gè)不同的蜜源，取所有蜜源中最優(yōu)的蜜源.

以上操作按序進(jìn)行，如果采用鄰域結(jié)構(gòu)N1形成的新蜜源優(yōu)于當(dāng)前蜜源，則將新蜜源取代當(dāng)前蜜源，然后繼續(xù)采用鄰域結(jié)構(gòu)N1，直到不能改變當(dāng)前蜜源時(shí)轉(zhuǎn)向下一個(gè)操作.

3.5 交叉操作

交叉操作可以交換兩個(gè)個(gè)體之間的信息，能在一定程度上避免個(gè)體陷入局部最優(yōu).由于每個(gè)工件的工序數(shù)是確定的，所以不能像實(shí)數(shù)域中的交叉方式那樣直接交換兩個(gè)工序片段，文獻(xiàn)[27]中提出了一種新的交叉策略:隨機(jī)生成一個(gè)小于最大工件數(shù)的正整數(shù)N，將當(dāng)前個(gè)體中小于或等于N的工序碼固定不變，將大于N的工序碼移除.然后將與之交叉的個(gè)體中的大于N的工序編碼依次填入當(dāng)前個(gè)體.這種交叉策略可操作的范圍太小，如果有10個(gè)工件，最多只有9種情況.根據(jù)這種交叉策略，本文提出了一種新的交叉方法，在這種方法中，當(dāng)前個(gè)體總是與種群最優(yōu)個(gè)體進(jìn)行交叉.如圖2所示.交叉操作的步驟如下:

步驟1隨機(jī)確定需要固定的工件數(shù)目，圖2中需要固定的工件的數(shù)目為3.

步驟2隨機(jī)確定固定的工件編號，圖2中需要固定的工件為3，4，5.

步驟3移除編號不是3，4，5的工序碼.

步驟4將全局最優(yōu)個(gè)體中編號不是3，4，5的工序碼依次填充到當(dāng)前個(gè)體中.

通過這種交叉方法，可以生成兩個(gè)新蜜源，取這兩個(gè)新蜜源中較好的蜜源與當(dāng)前蜜源進(jìn)行比較，如果新蜜源優(yōu)于當(dāng)前蜜源，則將其替換.

圖2 交叉操作Fig.2 Crossover operation

3.6 算法流程

引入NS的ABC在求解FFJSP時(shí)，采用混沌初始化的方式來初始化蜜源，以此來提高初始蜜源的多樣性.蜜源的編碼采用的是基于工序的編碼，在解碼的過程中，通過左移策略來提升解碼的性能.為了提高算法的局部搜素能力，引入了NS，采用4種鄰域操作來發(fā)掘當(dāng)前蜜源附近的優(yōu)質(zhì)蜜源.通過交叉操作進(jìn)一步提高蜜源的質(zhì)量，加快種群的收斂速度，在一定程度上避免蜜源陷入局部最優(yōu).算法的基本流程如下:

步驟1設(shè)置參數(shù)，包括蜜源的數(shù)目，雇傭蜂的數(shù)目，觀察蜂的數(shù)目以及控制次數(shù)(limit).其中蜜源的個(gè)數(shù)與雇傭蜂的數(shù)目相等.

步驟2采用第4.2節(jié)中的混沌初始化方法初始化蜜源，并計(jì)算各蜜源的適應(yīng)度值，求出最優(yōu)蜜源.

步驟3雇傭蜂階段，對于所有的個(gè)體，重復(fù)以下步驟:

1) 對于每一個(gè)蜜源，采用第4.3節(jié)中的鄰域搜索發(fā)掘出當(dāng)前蜜源附近的優(yōu)質(zhì)蜜源;

2) 通過第4.4節(jié)中交叉操作進(jìn)一步優(yōu)化當(dāng)前蜜源.

步驟4觀察蜂階段，對于所有個(gè)體，重復(fù)以下步驟:

1) 采用錦標(biāo)賽選擇法選擇一個(gè)蜜源;

2) 采用第4.3節(jié)中的鄰域搜索發(fā)掘出該蜜源附近的優(yōu)質(zhì)蜜源;

3) 通過第4.4節(jié)中交叉操作進(jìn)一步優(yōu)化當(dāng)前蜜源.

步驟5偵查蜂階段，如果一個(gè)蜜源經(jīng)過limit次迭代操作后還沒有改進(jìn)，則重新初始化一個(gè)蜜源.

步驟6如果達(dá)到了最大迭代次數(shù)，就終止算法，輸出最優(yōu)蜜源.否則返回到步驟3.

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

本文算法在迭代過程中主要由兩部分組成，第1部分是局部搜索階段，該階段的復(fù)雜度為O(3nk+mn).第2部分為交叉操作階段，其時(shí)間復(fù)雜度為O(10n).因此本文算法的時(shí)間復(fù)雜度為O((3k+m+10)n).

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

為了測試本文算法的性能，對一組小規(guī)模的實(shí)例和兩組標(biāo)準(zhǔn)的數(shù)據(jù)進(jìn)行了測驗(yàn).第一組小規(guī)模的數(shù)據(jù)來源于文獻(xiàn)[1].這組數(shù)據(jù)總共包含3個(gè)實(shí)例，規(guī)模最小的實(shí)例的工件數(shù)是3，機(jī)器數(shù)是3，總工序數(shù)為15.規(guī)模最大的實(shí)例的工件數(shù)是5，機(jī)器數(shù)是4，總工序數(shù)為20.本文程序采用MATLAB程序設(shè)計(jì)語言，在配置為core i7-4790 CPU@3.60 GHz 3.60 GHz和8 GB RAM的電腦上運(yùn)行.在試驗(yàn)中蜜源與觀察蜂的個(gè)數(shù)設(shè)定為200，控制次數(shù)limit為5，最大迭代次數(shù)為100.每次迭代過程中進(jìn)行10次交叉操作.對每個(gè)實(shí)例獨(dú)立運(yùn)行20次.本文算法求出的結(jié)果與文獻(xiàn)[1]中的混合多元優(yōu)化(hybrid multi-verse optimization，HMVO)算法的結(jié)果對比如表3所示.表3中的基于鄰域搜索的人工蜂群算法(artificial bee colony algorithm neighborhood search，ABCNS)對應(yīng)的是本文算法，表中列出了兩個(gè)算法所求出的最優(yōu)結(jié)果、平均結(jié)果、最差結(jié)果.由表3的結(jié)果可知，本文算法和HMVO算法一樣總是能找到最優(yōu)結(jié)果，且平均結(jié)果和最差結(jié)果都與最優(yōu)結(jié)果相同，說明了算法的穩(wěn)定性較好.

表3 小規(guī)模數(shù)據(jù)比較Table 3 Small-scale data comparison

第2組數(shù)據(jù)來源于文獻(xiàn)[17-18]，這組數(shù)據(jù)總共有5個(gè)實(shí)例，規(guī)模最小的實(shí)例的工件數(shù)是10，機(jī)器數(shù)是10，總工序數(shù)為40.規(guī)模最大的實(shí)例的工件數(shù)是15，機(jī)器數(shù)是10，總工序數(shù)為80.這5個(gè)實(shí)例都是完全模糊柔性作業(yè)車間調(diào)度，各工序在所有機(jī)器上都可以進(jìn)行加工.

為了驗(yàn)證本文算法的有效性，本文算法的結(jié)果與其他已經(jīng)發(fā)表的文獻(xiàn)中的7個(gè)算法的結(jié)果進(jìn)行了對比.這些算法包括文獻(xiàn)[1]中的HMVO算法、文獻(xiàn)[29]中的IABC算法、文獻(xiàn)[22]中的IDPSO算法、文獻(xiàn)[21]中的DHS算法、文獻(xiàn)[35]中的教學(xué)優(yōu)化算法(teaching learning based optimization，TLBO)、文獻(xiàn)[20]中的EDA算法、文獻(xiàn)[28]中的HABC算法.在這些算法中，設(shè)定的種群規(guī)模都不一樣.HMVO算法和TLBO算法的種群大小為200，IABC算法、DHS算法和EDA算法的種群大小為150，IDPSO和HABC算法的種群大小只有100.本文算法的種群大小與HMVO算法一致，設(shè)定為200.控制次數(shù)(limit)為5，每次迭代過程中進(jìn)行10次交叉操作.對每個(gè)實(shí)例獨(dú)立運(yùn)行20次.雖然本文的種群大小比一些算法要大，但是本文算法的進(jìn)化代數(shù)只有100代，也就是總共需要運(yùn)行20000次，比HMVO算法的100000次要小的多.

表4中列出了各算法的平均結(jié)果，最優(yōu)結(jié)果以及最差結(jié)果.表中的標(biāo)黑字體表示的是所對比算法中求得的最好結(jié)果，由表中的結(jié)果可知，本文算法運(yùn)行第1個(gè)實(shí)例的結(jié)果要優(yōu)于其他的算法，雖然本文算法相對于第1個(gè)實(shí)例的最優(yōu)結(jié)果與HMVO算法的最優(yōu)結(jié)果相等，但是本文算法的平均結(jié)果與最差結(jié)果都與最優(yōu)結(jié)果相等，說明了本文算法的穩(wěn)定性比HMVO算法的要好.對于第2個(gè)實(shí)例，本文算法的結(jié)果與HMVO算法的結(jié)果都一樣，優(yōu)于其他算法的結(jié)果.對于剩下的3個(gè)實(shí)例，本文算法的結(jié)果都優(yōu)于這些算法.圖3給出了實(shí)例4的最優(yōu)調(diào)度結(jié)果的甘特圖.

為了驗(yàn)證本文算法中各部分對試驗(yàn)結(jié)果的影響，針對第2組標(biāo)準(zhǔn)數(shù)據(jù)集，做了3組分離試驗(yàn).分離試驗(yàn)的結(jié)果如表5所示.表5中算法ABCNS(1)表示的是采用隨機(jī)初始化所得的結(jié)果，由表中結(jié)果可知隨著總工序數(shù)的增加，采用混沌初始化的優(yōu)勢更加明顯.算法ABCNS(2)對應(yīng)的是不采用交叉操作后所得的結(jié)果，由結(jié)果可知采用交叉操作后，平均結(jié)果、最優(yōu)結(jié)果、最差結(jié)果都有所改善，體現(xiàn)了采用交叉操作的優(yōu)越性.為了驗(yàn)證采用領(lǐng)域搜索的效果，將本文算法與傳統(tǒng)的ABC算法的結(jié)果進(jìn)行了對比.結(jié)果顯示本文算法的結(jié)果明顯優(yōu)于傳統(tǒng)的ABC算法.

第3組數(shù)據(jù)來源于文獻(xiàn)[21]，這組數(shù)據(jù)總共有8個(gè)實(shí)例，規(guī)模最小的實(shí)例的工件數(shù)是5，機(jī)器數(shù)是4，總工序數(shù)為23.規(guī)模最大的實(shí)例的工件數(shù)是20，機(jī)器數(shù)是15，總工序數(shù)為355.這組數(shù)據(jù)是部分模糊柔性作業(yè)車間調(diào)度，有些工序只能在部分機(jī)器上進(jìn)行加工.對于這組數(shù)據(jù)，本文算法與文獻(xiàn)[1]中的HMVO算法以及文獻(xiàn)[36]中的4種啟發(fā)式方法進(jìn)行了對比.這4種方法包括局部最小加工時(shí)間原則(LS)、全局最小加工時(shí)間原則(GS)、剩余工件最多原則(MReW)和隨機(jī)原則(Random).在試驗(yàn)時(shí)，本文算法的蜜源與觀察蜂的個(gè)數(shù)設(shè)定為200，控制次數(shù)limit為5，最大迭代次數(shù)為100.每次迭代過程中進(jìn)行10次交叉操作對于前4組數(shù)據(jù)，HMVO算法的種群大小設(shè)置為100，迭代次數(shù)為500.對于后4組數(shù)據(jù)，迭代次數(shù)設(shè)定為1000.5種啟發(fā)式算法的種群大小設(shè)定為150，對于前4組數(shù)據(jù)，最大迭代次數(shù)設(shè)置為1000.對于后4 組數(shù)據(jù)，最大迭代次數(shù)為4000.而本文算法的種群大小設(shè)定為200，最大迭代次數(shù)設(shè)定為100，所以本文算法總的運(yùn)行次數(shù)要遠(yuǎn)遠(yuǎn)小于與之對比的算法.

表4 各種算法對第2組數(shù)據(jù)的計(jì)算結(jié)果Table 4 Computational results of various algorithms on the second data set

圖3 第2組數(shù)據(jù)中實(shí)例4的最優(yōu)結(jié)果甘特圖Fig.3 Gantt chart of optimal results for example 4 in the second set of data

表5 分離試驗(yàn)結(jié)果Table 5 Separation test results

表6中列出了各算法相對于各個(gè)實(shí)例的平均結(jié)果、最優(yōu)結(jié)果和最差結(jié)果.由表中結(jié)果可知，對于所有的實(shí)例，本文算法與HMVO算法的結(jié)果都要遠(yuǎn)遠(yuǎn)優(yōu)于其他5種算法的結(jié)果.對于前5個(gè)實(shí)例的結(jié)果，無論是最優(yōu)結(jié)果，還是平均結(jié)果和最差結(jié)果，本文算法的結(jié)果都比HMVO算法的結(jié)果好.尤其對于第1個(gè)和第2個(gè)實(shí)例，本文算法求得的最優(yōu)結(jié)果、平均結(jié)果以及最差結(jié)果都相等，說明了本文算法的穩(wěn)定性較好.但是對于第6個(gè)實(shí)例和第8個(gè)實(shí)例，本文算法求得的結(jié)果只有平均結(jié)果和最差結(jié)果優(yōu)于HMVO算法，達(dá)不到HMVO算法求得的最優(yōu)結(jié)果，但是與HMVO求得的最優(yōu)結(jié)果的差距不大.對于第7個(gè)實(shí)例，本文算法的平均結(jié)果、最優(yōu)結(jié)果和最差結(jié)果都比HMVO算法的差.原因可能是對于像實(shí)例6-8這些大規(guī)模的實(shí)例，本文算法易陷入局部最優(yōu).

圖4展示了第3組數(shù)據(jù)中4個(gè)實(shí)例的進(jìn)化曲線，分別為第1個(gè)實(shí)例、第3個(gè)實(shí)例、第5個(gè)實(shí)例和第8個(gè)實(shí)例.第1個(gè)實(shí)例的進(jìn)化曲線是一條直線，說明在種群初始化完成后就可以達(dá)到最優(yōu)結(jié)果，體現(xiàn)了采用混沌初始化的優(yōu)越性.第3個(gè)實(shí)例的進(jìn)化曲線在30代左右的時(shí)候達(dá)到最優(yōu)，第5個(gè)實(shí)例的結(jié)果在40代左右的時(shí)候收斂到最優(yōu)結(jié)果，第8個(gè)實(shí)例在40代左右的時(shí)候也達(dá)到了較好的結(jié)果，在70代左右的時(shí)候達(dá)到最優(yōu)，而與之比較的HMVO算法要進(jìn)化900次左右才能達(dá)到最優(yōu)結(jié)果，所以本文算法在求解FFJSP時(shí)，具有很好的收斂性.

表6 各種算法對第3組數(shù)據(jù)的計(jì)算結(jié)果Table 6 Computational results of various algorithms on the third data set

圖4 第3組數(shù)據(jù)中4個(gè)實(shí)例的進(jìn)化曲線Fig.4 Evolving processes of four instances in third data set

5 結(jié)論

本文提出了一種基于NS的ABC來求解FFJSP，它以最小化最大模糊完工時(shí)間為優(yōu)化目標(biāo).為了測試本文算法的性能，對3組標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行了測驗(yàn)，并將結(jié)果與一些文獻(xiàn)中算法的結(jié)果進(jìn)行了對比.結(jié)果表明，對于大部分的數(shù)據(jù)實(shí)例，本文算法所求出的結(jié)果都要優(yōu)于與之對比的算法.為了直觀地反映最優(yōu)的調(diào)度方案，將第2組數(shù)據(jù)中的第4個(gè)實(shí)例的最優(yōu)結(jié)果通過甘特圖的形式展示了出來.并通過4幅種群的進(jìn)化曲線圖來反映算法的收斂情況.后期會(huì)將一些機(jī)器學(xué)習(xí)的經(jīng)典算法與群智能算法相結(jié)合來求解多目標(biāo)柔性作業(yè)車間調(diào)度問題.