楊小東，康 雁,2，柳 青,2，孫金文

(1.云南大學(xué) 軟件學(xué)院，昆明 650091； 2.云南省軟件工程重點(diǎn)實(shí)驗(yàn)室(云南大學(xué))，昆明 650091)

(*通信作者電子郵箱kangyan@ynu.edu.cn)

求解作業(yè)車間調(diào)度問題的混合帝國(guó)主義競(jìng)爭(zhēng)算法

楊小東1，康 雁1,2*，柳 青1,2，孫金文1

(1.云南大學(xué) 軟件學(xué)院，昆明 650091； 2.云南省軟件工程重點(diǎn)實(shí)驗(yàn)室(云南大學(xué))，昆明 650091)

(*通信作者電子郵箱kangyan@ynu.edu.cn)

針對(duì)最小化最大完工時(shí)間的作業(yè)車間調(diào)度問題(JSP)，提出一種結(jié)合帝國(guó)主義競(jìng)爭(zhēng)算法(ICA)和禁忌搜索(TS)算法的混合算法?；旌纤惴ㄒ缘蹏?guó)主義競(jìng)爭(zhēng)算法為基礎(chǔ)，在同化操作中融入遺傳算法中的雜交算子和變異算子，使算法全局搜索能力更強(qiáng)。為了克服帝國(guó)主義競(jìng)爭(zhēng)算法局部搜索能力弱的缺點(diǎn)，引入禁忌搜索算法進(jìn)一步優(yōu)化同化操作后的后代。禁忌搜索算法采用混合鄰域結(jié)構(gòu)和新型選擇策略，使得算法能夠更有效地搜索鄰域解?；旌纤惴婢呷炙阉髂芰途植克阉髂芰?，通過對(duì)13個(gè)經(jīng)典的Benchmark調(diào)度問題進(jìn)行仿真測(cè)試，并與近年4種新型混合算法進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果表明了所提算法求解Job Shop調(diào)度問題的有效性和穩(wěn)定性。

Job Shop調(diào)度問題；帝國(guó)主義競(jìng)爭(zhēng)算法；遺傳算法；禁忌搜索；混合優(yōu)化算法

0 引言

作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem, JSP)是最困難的組合優(yōu)化問題之一，也是經(jīng)典的NP-hard問題[1]。作業(yè)車間調(diào)度問題可以簡(jiǎn)單描述如下：給定n個(gè)作業(yè)，每個(gè)作業(yè)包含m個(gè)有預(yù)定加工順序、加工機(jī)器和加工時(shí)間的工序。調(diào)度的目標(biāo)就是合理安排所有工序在m臺(tái)機(jī)器上的加工順序，最小化最大完工時(shí)間，亦即最小化最后一個(gè)工序的完工時(shí)間。作業(yè)車間調(diào)度問題是許多實(shí)際生產(chǎn)調(diào)度問題的簡(jiǎn)化模型，具有廣泛應(yīng)用背景，如工業(yè)生產(chǎn)、交通規(guī)劃、物流和網(wǎng)絡(luò)通信等諸多方面的問題，都可借助于作業(yè)車間調(diào)度問題的求解結(jié)果。所以，高效、快速地求解作業(yè)車間調(diào)度問題，既有重要的理論意義，也有重大的應(yīng)用價(jià)值。

求解作業(yè)車間調(diào)度問題的方法目前可以分為兩大類型：精確算法和近似算法。精確算法主要通過運(yùn)籌學(xué)的求解方法尋求問題的理論最優(yōu)解，主要有分支定界方法(BranchandBound,B&B)[2]、整數(shù)規(guī)劃方法(IntegerLinearProgramming,ILP)[3]和拉格朗日松弛法(LagrangianRelaxation,LR)[4]等。精確算法雖然能得到理論最優(yōu)解，但由于其計(jì)算復(fù)雜，運(yùn)算時(shí)間長(zhǎng)，因此只適用于小型實(shí)例。而對(duì)于大規(guī)模的調(diào)度問題，近似算法是更好的選擇，近似算法主要有優(yōu)先分配規(guī)則法(PriorityDispatchRule,PDR)、瓶頸移動(dòng)法(ShiftingBottleneckProcedure,SBP)、人工智能和元啟發(fā)式算法等。優(yōu)先分配規(guī)則法是最早提出的近似算法，Giffler等[5]提出的構(gòu)造主動(dòng)高度和無延遲調(diào)度的算法被認(rèn)為是優(yōu)先分配規(guī)則法的基礎(chǔ)。瓶頸移動(dòng)法由Adams等[6]提出，并且是首次求出經(jīng)典的FT10問題最優(yōu)解的近似算法。隨后人們嘗試將人工智能的研究成果，如約束滿足技術(shù)、專家系統(tǒng)和人工神經(jīng)網(wǎng)絡(luò)等應(yīng)用到解決調(diào)度問題中，其中比較經(jīng)典的有文獻(xiàn)[7-9]中應(yīng)用Hopfield模型以及文獻(xiàn)[10]中應(yīng)用反向傳播(BackPropagation,BP)神經(jīng)網(wǎng)絡(luò)模型求解調(diào)度問題。元啟發(fā)式算法[11]是近些年求解調(diào)度問題最熱門、最高效的算法，主要包括基于生物啟發(fā)的群體算法和局部搜索算法。其中基于生物啟發(fā)的群體算法有遺傳算法(GeneticAlgorithm,GA)、蟻群優(yōu)化(AntColonyOptimization,ACO)算法和粒子群優(yōu)化(ParticleSwarmOptimization,PSO)算法等；局部搜索算法有禁忌搜索(TabuSearch,TS)算法和模擬退火(SimulatedAnnealing,SA)算法等。

帝國(guó)主義競(jìng)爭(zhēng)算法(ImperialistCompetitiveAlgorithm,ICA)是Atashpaz-Gargari等[12]在2007年受歷史上帝國(guó)之間的競(jìng)爭(zhēng)啟發(fā)而提出的一種新型進(jìn)化算法。算法中的初始種群被分成兩類：帝國(guó)和殖民地。殖民地通過不斷向帝國(guó)學(xué)習(xí)進(jìn)化自身，而帝國(guó)之間的競(jìng)爭(zhēng)使得所有殖民地最終歸附到一個(gè)最強(qiáng)的帝國(guó)之下。禁忌搜索(TS)算法是Glover[13]在1986年提出的一種經(jīng)典的局部搜索算法。禁忌搜索算法基于局部鄰域搜索方法，通過設(shè)置禁忌表來避免迂回搜索，利用藐視準(zhǔn)則來特赦被禁忌的優(yōu)解，能夠高效地求解優(yōu)化問題。

近些年的研究顯示，混合算法比單一算法能提供更高質(zhì)量的解和更好的搜索效率。因此，將單一算法有機(jī)組合以彌補(bǔ)各自的不足成為了研究者關(guān)注的熱點(diǎn)。文獻(xiàn)[14]將樹搜索算法與人工蜂群算法進(jìn)行結(jié)合，強(qiáng)化對(duì)JSP的搜索能力；文獻(xiàn)[15]在文化算法中融入了局部搜索，對(duì)求解JSP進(jìn)行了研究；文獻(xiàn)[16]將人工免疫系統(tǒng)與禁忌算法混合求解JSP，提出了帶禁忌搜索的人工免疫系統(tǒng)(ArtificialImmuneSystemwithTabuSearch,AIS-TS)算法；文獻(xiàn)[17]將局部搜索和遺傳算法結(jié)合求解JSP；文獻(xiàn)[18]將空閑時(shí)間的鄰域搜索融入到遺傳算法中求解JSP。

本文將基于帝國(guó)主義競(jìng)爭(zhēng)算法和禁忌搜索算法提出一種新型混合算法HICATS(HybridImperialistCompetitiveAlgorithmwithTabuSearch)。帝國(guó)主義競(jìng)爭(zhēng)算法擁有很強(qiáng)的全局優(yōu)化能力，但缺乏局部搜索能力，而禁忌搜索算法雖然缺乏全局搜索能力，但具有很強(qiáng)的局部搜索能力，因此兩者的結(jié)合能夠達(dá)到優(yōu)勢(shì)互補(bǔ)。針對(duì)問題特性，混合算法還融入遺傳算法的交叉和變異算子，使算法能夠更高效地求解JSP。

1 問題模型

經(jīng)典的作業(yè)車間調(diào)度問題可以描述如下：給定m臺(tái)機(jī)器，n個(gè)作業(yè)，每個(gè)作業(yè)按指定順序，依次在m臺(tái)機(jī)器上加工，即每個(gè)作業(yè)都包含m個(gè)工序。對(duì)作業(yè)和機(jī)器的約束如下：

1) 每個(gè)工序有預(yù)先設(shè)置的加工時(shí)間與加工機(jī)器；

2) 每個(gè)工序有且只能在一臺(tái)機(jī)器上加工一次；

3) 不同作業(yè)之間無先后約束關(guān)系；

4) 每個(gè)工序一旦開始就不能中斷；

5) 每臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)作業(yè)；

6) 不計(jì)工序開始前布置時(shí)間和工序之間交接時(shí)間；

本文約定符號(hào)如下：m臺(tái)機(jī)器表示為{M1,M2,…,Mm}，n個(gè)作業(yè)表示為{J1,J2,…,Jn}，第i個(gè)作業(yè)的第j個(gè)工序表示為oij，工序oij對(duì)應(yīng)的加工機(jī)器表示為pij，對(duì)應(yīng)的加工時(shí)間表示為tij。每個(gè)作業(yè)最后一道工序的完工時(shí)間即是該作業(yè)的完成時(shí)間，表示為Ci。求解作業(yè)車間調(diào)度問題即是最小化所有作業(yè)的最大完工時(shí)間Cmax，目標(biāo)函數(shù)如式(1)所示：

(1)

一個(gè)3×3的JSP實(shí)例如表1所示，其中“—”代表工序在機(jī)器上無加工數(shù)據(jù)。

表1 一個(gè)3×3實(shí)例

2 HICATS算法

帝國(guó)主義競(jìng)爭(zhēng)算法是新型的進(jìn)化算法，其中所有的國(guó)家將被分為兩類：一是帝國(guó)；二是殖民地。具有較優(yōu)適應(yīng)度值的國(guó)家將成為帝國(guó)，擁有較差適應(yīng)度值的國(guó)家將成為帝國(guó)的殖民地。各帝國(guó)之間不斷展開競(jìng)爭(zhēng)，強(qiáng)帝國(guó)以大幾率從弱帝國(guó)中奪得殖民地。整個(gè)競(jìng)爭(zhēng)過程到只剩一個(gè)帝國(guó)、達(dá)到算法迭代次數(shù)或找到最優(yōu)解時(shí)停止。

本文提出的混合帝國(guó)主義禁忌搜索算法HICATS是一種新型的元啟發(fā)式算法，算法集成了帝國(guó)主義競(jìng)爭(zhēng)算法與禁忌搜索算法的優(yōu)點(diǎn)，且融合了遺傳算法的雜交算子和變異算子，使得該算法能夠高效求解JSP。

2.1 初始化帝國(guó)與殖民地

本文使用基于工序的編碼方式，并采用Zhang等[19]提出的全主動(dòng)調(diào)度(Full-ActiveSchedule,FAS)來提高初始解的質(zhì)量。傳統(tǒng)主動(dòng)調(diào)度(ActiveScheduling,AS)能夠在不破壞優(yōu)先順序以及不延遲其他工序的條件下，使得沒有工序可以提前；而全主動(dòng)調(diào)度則是在主動(dòng)調(diào)度的基礎(chǔ)中，增加了反轉(zhuǎn)調(diào)度，使得不僅可以將允許左移的工序左移，也可以將允許右移的工序右移，因此全主動(dòng)調(diào)度的最大完工時(shí)間小于或者等于其對(duì)應(yīng)的主動(dòng)調(diào)度的最大完工時(shí)間。

以表1中3×3實(shí)例為例，隨機(jī)生成一個(gè)初始解{1,2,1,2,1,3,2,3,3}，解對(duì)應(yīng)的工序編號(hào)為{1,4,2,5,3,7,6,8,9}，其AS結(jié)果如圖1所示，調(diào)度結(jié)果為11。

圖1 AS調(diào)度結(jié)果

而對(duì)于同樣的初始解，采用FAS調(diào)度結(jié)果如圖2所示。圖2(a)是將允許右移的工序右移的反轉(zhuǎn)調(diào)度，即以初始解反向開始調(diào)度，調(diào)度順序?yàn)閧9,8,6,7,3,5,2,4,1}，同時(shí)也是基于主動(dòng)調(diào)度方式，最終調(diào)度的結(jié)果是8；圖2(b)為基于反轉(zhuǎn)調(diào)度結(jié)果的主動(dòng)調(diào)度，使能夠左移的工序左移，同時(shí)也得到各個(gè)工序正確的開工和結(jié)束時(shí)間，并形成最終的調(diào)度結(jié)果。從圖2中可知，對(duì)于同樣的初始解，AS的調(diào)度結(jié)果是11，而FAS的調(diào)度結(jié)果是8。

示例演示了FAS的有效性，而在FT10實(shí)例上的實(shí)驗(yàn)進(jìn)一步驗(yàn)證了FAS生成初始解的高質(zhì)量。實(shí)驗(yàn)分別用FAS和AS隨機(jī)生成100個(gè)FT10的初始解，從圖3的實(shí)驗(yàn)結(jié)果中可以看出，不論最優(yōu)適應(yīng)值還是平均適應(yīng)值，F(xiàn)AS生成的初始國(guó)家都優(yōu)于AS生成的初始國(guó)家。

圖2 FAS調(diào)度結(jié)果

圖3 FAS與AS生成的初始解適應(yīng)值對(duì)比

本文中帝國(guó)主義競(jìng)爭(zhēng)算法的符號(hào)與Atashpaz-Gargari等[12]定義帝國(guó)主義競(jìng)爭(zhēng)算法時(shí)保持一致。FAS調(diào)度生成的初始國(guó)家定義為Npop，從中選擇適應(yīng)值最優(yōu)的Nimp個(gè)國(guó)家為帝國(guó)，剩下的Ncol個(gè)國(guó)家將作為殖民地并根據(jù)各帝國(guó)力量隨機(jī)分配到各個(gè)帝國(guó)旗下。按照式(2)標(biāo)準(zhǔn)化各帝國(guó)力量:

(2)

其中：cn是第n個(gè)帝國(guó)的適應(yīng)度值；Cn是其標(biāo)準(zhǔn)化后的適應(yīng)度值?；跇?biāo)準(zhǔn)化后的適應(yīng)度值，用式(3)計(jì)算出各個(gè)帝國(guó)的力量：

(3)

其中pn是一個(gè)比值，越大代表這個(gè)帝國(guó)擁有的力量越強(qiáng)，因此應(yīng)該擁有的殖民地也就越多?；趐n，按式(4)給每個(gè)帝國(guó)劃分應(yīng)該擁有的殖民地?cái)?shù)：

N.C.n=round{pn×Ncol}

(4)

其中N.C.n就是每個(gè)帝國(guó)初始擁有的殖民地?cái)?shù)，按照這個(gè)數(shù)量將殖民地隨機(jī)分配到各個(gè)帝國(guó)旗下。這樣就完成對(duì)所有帝國(guó)及殖民地的初始化。

2.2 同化操作

在Atashpaz-Gargari等[12]提出的帝國(guó)主義競(jìng)爭(zhēng)算法中，采用距離公式實(shí)現(xiàn)殖民地向帝國(guó)的學(xué)習(xí)移動(dòng)過程，而本文則根據(jù)問題特性借鑒遺傳算法的雜交思想作為學(xué)習(xí)過程。在一個(gè)帝國(guó)集團(tuán)中，每一組殖民地將按照概率Ps從以下兩種雜交方式隨機(jī)選擇一種：

1)任一殖民地與所在帝國(guó)按照優(yōu)先工序交叉(Precedence Operation crossover, POX)算法交叉T次；

2)兩個(gè)殖民地按照POX算法交叉T次。

其中優(yōu)先工序交叉(POX)算法是Zhang等[19]在2008年提出的一種高效交叉算子。假設(shè)有父代Parent1和Parent2，POX產(chǎn)生兩個(gè)子代的流程如下：

1)隨機(jī)劃分工件集{1,2,…,n}為兩個(gè)非空子集S1和S2；

2)復(fù)制Parent1包含在S1中的工件到Child1，Parent2包含在S1中的工件到Child2，分別保留它們的位置；

3)復(fù)制Parent2包含在S2中的工件到Child1，Parent1包含在S2中的工件到Child2，分別保留它們的順序。

如圖4所示，Parent1={1,2,1,2,1,3,2,3,3}，Parent2={2,1,3,1,2,2,3,1,3}，S1={2}，S2={1,3}。最后生成的Child1={1,2,3,2,1,3,2,1,3}，Child2={2,1,1,1,2,2,3,3,3}。通過POX方法既能很好地保留父代的優(yōu)良特征，而且產(chǎn)生的子代又能保證是可行解，因此是一種高效的交叉算子。

圖4 POX交叉算子

交叉結(jié)束后對(duì)最優(yōu)的后代使用禁忌搜索算法，進(jìn)一步探索鄰域中更優(yōu)的個(gè)體。

禁忌搜索算法中最重要的部分就是鄰域結(jié)構(gòu)，其中比較有效的結(jié)構(gòu)有N4、N5、N6鄰域結(jié)構(gòu)[20-22]。N4鄰域結(jié)構(gòu)要求把關(guān)鍵塊內(nèi)工序盡可能地移至塊首或塊尾位置；N5鄰域結(jié)構(gòu)僅交換塊首和塊尾兩相鄰工序以避免交換關(guān)鍵塊內(nèi)的工序；N6鄰域結(jié)構(gòu)是把內(nèi)部工序移至塊首之前和塊尾之后。本文在N4、N5、N6鄰域結(jié)構(gòu)的基礎(chǔ)上，采用混合的鄰域結(jié)構(gòu)，具體如下：

1)關(guān)鍵塊中含有兩個(gè)工序，則直接交換。

2)關(guān)鍵塊中含有三個(gè)工序：

a)非首工序移至塊首；

b)非尾工序移至塊尾。

3)關(guān)鍵塊中含有四個(gè)及以上工序：

a)隨機(jī)選擇部分非首工序移至塊首；

b)隨機(jī)選擇部分非尾工序移至塊尾；

c)首工序移至隨機(jī)一個(gè)中間位置；

d)尾工序移至隨機(jī)一個(gè)中間位置；

e)塊首和塊尾同時(shí)與其相鄰工序交換位置。

通過以上的混合鄰域結(jié)構(gòu)，既能獲得高質(zhì)量的鄰域解，又能使算法高效運(yùn)行。

選擇策略是禁忌搜索算法中下次迭代的開始。通常禁忌搜索算法會(huì)從非禁忌的最優(yōu)解中選擇最優(yōu)的一個(gè)解作為下次算法的初始解，但在算法的后期容易陷入局部最優(yōu)。本文禁忌搜索算法受模擬退火算法中以一定概率選擇差解啟發(fā)，提出一種新型選擇策略，即下次初始解的產(chǎn)生是從L個(gè)非禁忌的最優(yōu)解中隨機(jī)選擇，L是一個(gè)隨迭代次數(shù)增加而增加的值，按式(5)計(jì)算：

L=iteration/cycle+1

(5)

其中：iteration是算法運(yùn)行代數(shù)，cycle是自定義的一個(gè)遞增周期。通過此方法可使算法在初期加速收斂，而在后期擴(kuò)大解的搜索范圍，避免過早陷入局部最優(yōu)。

禁忌搜索算法的流程如圖5所示。

圖5 禁忌搜索算法流程

當(dāng)兩個(gè)適應(yīng)度值相同的個(gè)體被選擇時(shí)，則對(duì)任一個(gè)體進(jìn)行變異。變異算子的流程如圖6所示。首先隨機(jī)選擇K個(gè)位置，并且各個(gè)位置上的基因各不相同；再基于選擇的K個(gè)基因作隨機(jī)變換，從而得到變異個(gè)體。

圖6 變異算子

同化操作是帝國(guó)主義競(jìng)爭(zhēng)算法的核心。針對(duì)JSP特性，采用遺傳算法的交叉思想實(shí)現(xiàn)進(jìn)化；同時(shí)為了避免陷入局部最優(yōu)，引入變異算子擴(kuò)大搜索空間；最后再使用局部搜索能力強(qiáng)的禁忌搜索算法進(jìn)一步優(yōu)化后代，從而實(shí)現(xiàn)更全、更快的個(gè)體進(jìn)化。當(dāng)新的個(gè)體適應(yīng)度值優(yōu)于當(dāng)前帝國(guó)時(shí)，則將更優(yōu)個(gè)體取代舊帝國(guó)。此后該帝國(guó)下的同化操作將以新的帝國(guó)為基礎(chǔ)，直到該帝國(guó)內(nèi)的同化操作結(jié)束或有更優(yōu)的后代取代該帝國(guó)。同化操作的整個(gè)流程如圖7所示。

2.3 帝國(guó)競(jìng)爭(zhēng)

在帝國(guó)互相競(jìng)爭(zhēng)之前，需要衡量各個(gè)帝國(guó)集團(tuán)的力量，不僅需要考慮帝國(guó)的適應(yīng)度值，還需要考慮其所擁有的殖民地對(duì)帝國(guó)集團(tuán)力量的影響。而這個(gè)影響系數(shù)本文定義為ξ，第n個(gè)帝國(guó)集團(tuán)的總力量定義為T.C.n，計(jì)算公式如式(6)所示：

T.C.n=Cost(imperialistn)+ξ·mean{Cost(coloniesofempiren)}

(6)

帝國(guó)競(jìng)爭(zhēng)是實(shí)現(xiàn)帝國(guó)之間優(yōu)勝劣汰的重要步驟。各帝國(guó)將基于各自的力量來爭(zhēng)奪最弱帝國(guó)中的最弱殖民地。首先按式(7)標(biāo)準(zhǔn)化各帝國(guó)集團(tuán)的總力量：

(7)

其中N.T.C.n代表第n個(gè)帝國(guó)集團(tuán)標(biāo)準(zhǔn)化后的力量。基于標(biāo)準(zhǔn)化力量，各帝國(guó)集團(tuán)能夠獲得殖民地的概率如式(8)所示：

(8)

圖7 同化操作流程

為了將最弱帝國(guó)下最弱殖民地按各帝國(guó)集團(tuán)所應(yīng)該擁有的概率來分配，首先基于之前計(jì)算的概率初始化一個(gè)向量P：

P=[pp1,pp2,…,ppNimp]

然后隨機(jī)初始化一個(gè)與向量P同樣大小的向量R：

R=[r1,r2,…,rNimp];r1,r2,…,rNimp～U(0,1)最后通過將向量P與向量R相減來獲得向量D:

D=P-R=[D1,D2,…,DNimp]= [pp1-r1,pp2-r2,…,ppNimp-rNimp]

向量D中最大值對(duì)應(yīng)的帝國(guó)將獲得一個(gè)新的殖民地。

在每一次迭代中，將檢查當(dāng)前最弱帝國(guó)擁有的殖民地?cái)?shù)，當(dāng)其流失了所有的殖民地后，該帝國(guó)集團(tuán)將被認(rèn)為已崩塌，將刪除該帝國(guó)。

算法終止準(zhǔn)則是滿足以下三個(gè)條件之一：一是找到最優(yōu)解；二是算法達(dá)到最大迭代數(shù)；三是只剩一個(gè)帝國(guó)。帝國(guó)主義競(jìng)爭(zhēng)算法的流程如圖8所示。

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

為了驗(yàn)證本文算法的實(shí)際效果，在3.3GHzCPU和4.0GB內(nèi)存的計(jì)算機(jī)上，采用Java編程進(jìn)行實(shí)驗(yàn)；算法參數(shù)設(shè)置為：國(guó)家總數(shù)為100，其中初始帝國(guó)數(shù)為10，初始殖民地為90，帝國(guó)競(jìng)爭(zhēng)次數(shù)為200，交叉概率Pc為0.8，變異率Pm為0.1，每代POX交叉次數(shù)T為200，每個(gè)實(shí)例求解20次。

本文算法選用13個(gè)經(jīng)典實(shí)例與其他算法進(jìn)行對(duì)比分析，這些實(shí)例在文獻(xiàn)[22]中被認(rèn)定為“難”級(jí)別，因此更具有代表性。對(duì)比結(jié)果如表2所示，其中：Instance是實(shí)例名；Size是由作業(yè)數(shù)和機(jī)器數(shù)表示的實(shí)例規(guī)模；BKS*代表實(shí)例已知的最優(yōu)解；Cmax代表各算法求得實(shí)例的最優(yōu)解；Re為Cmax與BKS*的相對(duì)偏差，即Re=(Cmax-BKS*)/BKS*×100%；Av(Re)為各算法對(duì)13個(gè)實(shí)例相對(duì)偏差的平均值；“—”表示無對(duì)應(yīng)數(shù)據(jù)。對(duì)比算法分別為文獻(xiàn)[14]的混合人工蜂群(HybridArtificialBeeColony,HABC)算法、文獻(xiàn)[15]的文化基因算法(MemeticAlgorithm,MA)、文獻(xiàn)[17]的混合遺傳算法(HybridGeneticAlgorithm,HGA)和文獻(xiàn)[18]的空閑時(shí)間鄰域搜索遺傳算法(IdleTimeNeighborhoodSearchGeneticAlgorithm,ITNSGA)。

圖8 帝國(guó)主義競(jìng)爭(zhēng)算法流程

表2 典型實(shí)例求解結(jié)果

Tab.2Computationalresultsofclassicinstances

InstanceSizeBKS?HICATSCmaxRe/%ITNSGA[18]CmaxRe/%HGA[17]CmaxRe/%MA[15]CmaxRe/%HABC[14]CmaxRe/%FT1010×109309300．009300．009300．009300．009350．54LA0210×56556550．006550．006550．006550．006550．00LA1910×108428420．008420．008440．248420．008420．00LA2115×10104610520．5710520．5710460．0010550．8610520．57LA2415×109359410．649410．649531．939400．539400．53LA2515×109779840．729770．009810．419840．729820．51LA2720×10123512551．6212460．8912360．0812612．1112430．65LA2920×10115211762．0811651．1311600．6911903．3011802．43LA3615×15126812811．0312790．8712871．5012811．0312740．47LA3715×15139714252．0014070．7214070．7214312．4314080．79LA3815×15119612141．5112131．4211960．0012161．6711960．00LA3915×15123312491．3012440．8912330．0012410．6512380．41LA4015×15122212421．6412330．9012290．5712330．9012330．90Av(Re)———1．01—0．62—0．47—1．09—0．60

從表2中可以看出本文算法能夠求解出13個(gè)實(shí)例中的3個(gè)最優(yōu)解。與ITNSGA[18]相比，除了結(jié)果相等的實(shí)例，并沒有發(fā)現(xiàn)更優(yōu)的實(shí)例，但與其他算法的對(duì)比可以發(fā)現(xiàn)各有優(yōu)劣。進(jìn)一步統(tǒng)計(jì)分析，本文算法與對(duì)比算法的求解優(yōu)劣數(shù)統(tǒng)計(jì)對(duì)比如表3所示。其中:AS表示本文算法求解的13個(gè)實(shí)例中優(yōu)于對(duì)比算法的數(shù)量，LS表示本文算法差于對(duì)比算法的實(shí)例數(shù)，ES表示本文算法與對(duì)比算法相同的求解實(shí)例數(shù)。從表中可知，本文算法求解的實(shí)例質(zhì)量是具有一定競(jìng)爭(zhēng)力的，但是從LS列中也可以看出，本文算法除了優(yōu)于MA算法外，與其他三個(gè)混合算法都有些差距，還有待完善。

表3 優(yōu)于解和差于解數(shù)目對(duì)比分析

根據(jù)表2的Av(Re)結(jié)果也可以看出，本文算法的整體性能還有待進(jìn)一步提高。

圖9給出了本文算法在解決FT10(10×10)基準(zhǔn)問題時(shí)的收斂曲線，從圖中可以看出算法在第20代左右收斂到近似最優(yōu)解，隨后在第110代左右求得最優(yōu)解，說明算法具有較快的收斂性。

圖9 FT10(10×10)基準(zhǔn)問題的收斂曲線

在求解速度和平均結(jié)果方面，將本文算法與ITNSGA[18]進(jìn)行對(duì)比，結(jié)果如表4所示，其中ITNSGA的求解環(huán)境是CPU主頻為2.6GHz、內(nèi)存為2.0GB的個(gè)人計(jì)算機(jī)。表4中：pSize表示初始種群大??；Av(Cmax)表示20次獨(dú)立實(shí)驗(yàn)的平均結(jié)果；Av(t)表示20次獨(dú)立實(shí)驗(yàn)的平均運(yùn)行時(shí)間；γ是本文算法與對(duì)比算法在實(shí)例平均結(jié)果(Av(Cmax))上的比值；λ是本文算法與對(duì)比算法在實(shí)例平均運(yùn)行時(shí)間(Av(t))上的比值；Av(γ/λ)表示13個(gè)實(shí)例γ值的平均值和λ值的平均值；“—”表示無對(duì)應(yīng)數(shù)據(jù)。從表4中可見，盡管本文算法使用的CPU主頻和內(nèi)存較大，但在整體硬件環(huán)境相差不大的情況下，求得Av(λ)=0.34，說明本文算法的平均求解速度大約是對(duì)比算法的3倍，驗(yàn)證了本文算法的高效性。同時(shí)本文算法的初始種群在遠(yuǎn)小于對(duì)比算法初始種群的情況下，由Av(γ)=1可知兩者算法的平均求解能力幾乎相等，驗(yàn)證了算法的穩(wěn)定性。

表4 本文算法與ITNSGA[18]的平均求解時(shí)間和結(jié)果對(duì)比

4 結(jié)語

本文針對(duì)作業(yè)車間調(diào)度問題展開研究，提出一種新型算法HICATS，混合了帝國(guó)主義競(jìng)爭(zhēng)算法全局搜索能力和禁忌搜索算法的局部搜索能力。HICATS算法首先在帝國(guó)主義競(jìng)爭(zhēng)算法的同化操作中融入了遺傳算法的交叉算子和變異算子，有效地提高殖民地的學(xué)習(xí)能力；然后應(yīng)用禁忌搜索算法進(jìn)一步地優(yōu)化后代，利用混合鄰域結(jié)構(gòu)使禁忌搜索更為有效；并借鑒模擬退火算法以一定概率接受差解的思想，提出一種新型選擇策略克服禁忌搜索算法易陷入局部最優(yōu)的缺陷。該混合算法在最后的實(shí)例驗(yàn)證中表現(xiàn)出了高效的求解能力，驗(yàn)證了算法的有效性和穩(wěn)定性。今后將進(jìn)一步研究該算法在大型實(shí)例中的設(shè)計(jì)與實(shí)現(xiàn)，進(jìn)一步優(yōu)化算法性能，并探索算法在相類似問題領(lǐng)域中的應(yīng)用。

)

[1]GAREYMR,JOHNSONDS,SETHIR.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch, 1976, 1(2): 117-129.

[2]BALASE.Machinesequencingviadisjunctivegraphs:animplicitenumerationalgorithm[J].OperationsResearch, 1968, 17(6): 941-957.

[3]VANHULLEMM.Agoalprogrammingnetworkformixedintegerlinearprogramming:acasestudyforthejob-shopschedulingproblem[J].InternationalJournalofNeuralSystems, 1991, 2(3): 201-209.

[4]LUHPB,HOITOMTDJ.SchedulingofmanufacturingsystemsusingtheLagrangianrelaxationtechnique[J].IEEETransactionsonAutomaticControl, 1993, 38(7): 1066-1079.

[5]GIFFLERB,THOMPSONGL.Algorithmsforsolvingproductionschedulingproblems[J].OperationsResearch, 1960, 8(4): 487-503.

[6]ADAMSJ,BALASE,ZAWACKD.Theshiftingbottleneckprocedureforjobshopscheduling[J].ManagementScience, 1988, 34(3): 391-401.

[7]SIMONFY-P,TAKEFUJIY.Stochasticneuralnetworksforsolvingjob-shopscheduling.Ⅰ.problemrepresentation[C]//Proceedingsofthe1988IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1988: 275-282.

[8]SIMONFY-P,TAKEFUJIY.Stochasticneuralnetworksforsolvingjob-shopscheduling.Ⅱ.architectureandsimulations[C]//Proceedingsofthe1988IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1988: 283-290.

[9]SIMONFY-P,TAKEFUJIY.Integerlinearprogrammingneuralnetworksforjob-shopscheduling[C]//Proceedingsofthe1988IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1988: 341-348.

[10]REMUSW.Neuralnetworkmodelsofmanagerialjudgment[C]//Proceedingsofthe23rdAnnualHawaiiInternationalConferenceonSystemSciences.Piscataway,NJ:IEEE, 1990: 340-344.

[11]GLOVERF.Newapproachesforheuristicsearch:abilaterallinkagewithartificialintelligence[J].EuropeanJournalofOperationalResearch, 1989, 39(2): 119-130.

[12]ATASHPAZ-GARGARIE,LUCASC.Imperialistcompetitivealgorithm:analgorithmforoptimizationinspiredbyimperialisticcompetition[C]//CEC2007:Proceedingsofthe2007IEEECongressonEvolutionaryComputation.Piscataway,NJ:IEEE, 2007: 4661-4667.

[13]GLOVERF.Futurepathsforintegerprogrammingandlinkstoartificialintelligence[J].Computers&OperationsResearch, 1986, 13(5): 533-549.

[14]ZHANGR,SONGS,WUC.Ahybridartificialbeecolonyalgorithmforthejobshopschedulingproblem[J].InternationalJournalofProductionEconomics, 2013, 141(1): 167-178.

[15]GAOL,ZHANGG,ZHANGL,etal.Anefficientmemeticalgorithmforsolvingthejobshopschedulingproblem[J].Computers&IndustrialEngineering, 2011, 60(4): 699-705.

[16] ZUO X, WANG C, TAN W.Two heads are better than one: an AIS- and TS-based hybrid strategy for job shop scheduling problems [J].International Journal of Advanced Manufacturing Technology, 2012, 63(1): 155-168.

[17] REN Q-D-E-J, WANG Y.A new hybrid genetic algorithm for job shop scheduling problem [J].Computers & Operations Research, 2012, 39(10): 2291-2299.

[18] 趙詩奎,方水良,顧新建.作業(yè)車間調(diào)度的空閑時(shí)間鄰域搜索遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(8):1930-1940.(ZHAO S K, FANG S L, GU X J.Idle time neighborhood search genetic algorithm for job shop scheduling [J].Computer Integrated Manufacturing Systems, 2014, 20(8): 1930-1940.)

[19] ZHANG C, RAO Y, LI P.An effective hybrid genetic algorithm for the job shop scheduling problem [J].International Journal of Advanced Manufacturing Technology, 2008, 39(9): 965-974.

[20] DELL’AMICO M, TRUBIAN M.Applying tabu-search to the job shop scheduling problem [J].Annals of Operations Research, 1993, 41(3): 231-252.

[21] NOWICKI E, SMUTNICKI C.A fast taboo search algorithm for the job shop problem [J].Management Science, 1996, 42(6): 797-813.

[22] BALAS E, VAZACOPOULOS A.Guided local search with shifting bottleneck for job shop scheduling [J].Management Science, 1998, 44(2): 262-275.

This work is partially supported by the National Natural Science Foundation of China (61462095), the Open Foundation of Key Laboratory in Software Engineering of Yunnan Province (2015SE103).

YANG Xiaodong, born in 1991, M.S.candidate.His research interests include intelligent shop scheduling.

KANG Yan, born in 1972, Ph.D., associate professor.Her research interests include intelligent shop scheduling, data mining.

LIU Qing, born in 1963, M.S., professor.His research interests include software hierarchical architecture, massive data processing and analysis.

SUN Jinwen, born in 1989, M.S.candidate.His research interests include fuzzy decision-making.

Hybrid imperialist competitive algorithm for solving job-shop scheduling problem

YANG Xiaodong1, KANG Yan1,2*, LIU Qing1,2, SUN Jinwen1

(1.CollegeofSoftware,YunnanUniversity,KunmingYunnan650091,China;2.KeyLaboratoryinSoftwareEngineeringofYunnanProvince(YunnanUniversity),KunmingYunnan650091,China)

For the Job-shop Scheduling Problem (JSP) with the objective of minimizing the makespan, a hybrid algorithm combining with Imperialist Competitive Algorithm (ICA) and Tabu Search (TS) was proposed.Based on imperialist competitive algorithm, crossover operator and mutation operator of Genetic Algorithm (GA) were applied in the hybrid algorithm as assimilation to strengthen its global search ability.To overcome the weakness of imperialist competitive algorithm in local search, TS algorithm was used to improve the offspring of assimilation.The hybrid neighborhood structure and a novel selection strategy were used by TS to make the search more efficient.By combining with the ability of global search and local search, testing on the 13 classic benchmark scheduling problems and comparing with other four hybrid algorithms in recent years, the experimental results show that the proposed hybrid algorithm is effective and stable.

Job-shop Scheduling Problem (JSP); Imperialist Competitive Algorithm (ICA); Genetic Algorithm (GA); Tabu Search (TS); hybrid optimization algorithm

2016- 08- 20;

2016- 09- 25。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61462095);云南省軟件工程重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(2015SE103)。

楊小東(1991—)，男，福建連城人，碩士研究生，CCF會(huì)員，主要研究方向：智能車間調(diào)度； 康雁(1972—)，女，四川綿陽人，副教授，博士，主要研究方向：智能車間調(diào)度、數(shù)據(jù)挖掘； 柳青(1963—)，男，云南祥云人，教授，碩士，主要研究方向：軟件體系結(jié)構(gòu)、海量數(shù)據(jù)處理和分析； 孫金文(1989—)，男，山西朔州人，碩士研究生，主要研究方向：模糊決策。

1001- 9081(2017)02- 0517- 06

10.11772/j.issn.1001- 9081.2017.02.0517

TP301.6; TP18

A