求解作業(yè)車間調度問題的混合帝國主義競爭算法

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

(1.云南大學 軟件學院，昆明 650091； 2.云南省軟件工程重點實驗室(云南大學)，昆明 650091)

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

求解作業(yè)車間調度問題的混合帝國主義競爭算法

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

(1.云南大學 軟件學院，昆明 650091； 2.云南省軟件工程重點實驗室(云南大學)，昆明 650091)

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

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

Job Shop調度問題；帝國主義競爭算法；遺傳算法；禁忌搜索；混合優(yōu)化算法

0 引言

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

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

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

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

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

1 問題模型

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

1) 每個工序有預先設置的加工時間與加工機器；

2) 每個工序有且只能在一臺機器上加工一次；

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

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

5) 每臺機器同一時刻只能加工一個作業(yè)；

6) 不計工序開始前布置時間和工序之間交接時間；

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

(1)

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

表1 一個3×3實例

2 HICATS算法

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

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

2.1 初始化帝國與殖民地

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

以表1中3×3實例為例，隨機生成一個初始解{1,2,1,2,1,3,2,3,3}，解對應的工序編號為{1,4,2,5,3,7,6,8,9}，其AS結果如圖1所示，調度結果為11。

圖1 AS調度結果

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

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

圖2 FAS調度結果

圖3 FAS與AS生成的初始解適應值對比

本文中帝國主義競爭算法的符號與Atashpaz-Gargari等[12]定義帝國主義競爭算法時保持一致。FAS調度生成的初始國家定義為Npop，從中選擇適應值最優(yōu)的Nimp個國家為帝國，剩下的Ncol個國家將作為殖民地并根據各帝國力量隨機分配到各個帝國旗下。按照式(2)標準化各帝國力量:

(2)

其中：cn是第n個帝國的適應度值；Cn是其標準化后的適應度值?；跇藴驶蟮倪m應度值，用式(3)計算出各個帝國的力量：

(3)

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

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

(4)

其中N.C.n就是每個帝國初始擁有的殖民地數(shù)，按照這個數(shù)量將殖民地隨機分配到各個帝國旗下。這樣就完成對所有帝國及殖民地的初始化。

2.2 同化操作

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

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

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

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

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

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

3)復制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)良特征，而且產生的子代又能保證是可行解，因此是一種高效的交叉算子。

圖4 POX交叉算子

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

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

1)關鍵塊中含有兩個工序，則直接交換。

2)關鍵塊中含有三個工序：

a)非首工序移至塊首；

b)非尾工序移至塊尾。

3)關鍵塊中含有四個及以上工序：

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

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

c)首工序移至隨機一個中間位置；

d)尾工序移至隨機一個中間位置；

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

通過以上的混合鄰域結構，既能獲得高質量的鄰域解，又能使算法高效運行。

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

L=iteration/cycle+1

(5)

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

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

圖5 禁忌搜索算法流程

當兩個適應度值相同的個體被選擇時，則對任一個體進行變異。變異算子的流程如圖6所示。首先隨機選擇K個位置，并且各個位置上的基因各不相同；再基于選擇的K個基因作隨機變換，從而得到變異個體。

圖6 變異算子

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

2.3 帝國競爭

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

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

(6)

帝國競爭是實現(xiàn)帝國之間優(yōu)勝劣汰的重要步驟。各帝國將基于各自的力量來爭奪最弱帝國中的最弱殖民地。首先按式(7)標準化各帝國集團的總力量：

(7)

其中N.T.C.n代表第n個帝國集團標準化后的力量?；跇藴驶α?，各帝國集團能夠獲得殖民地的概率如式(8)所示：

(8)

圖7 同化操作流程

為了將最弱帝國下最弱殖民地按各帝國集團所應該擁有的概率來分配，首先基于之前計算的概率初始化一個向量P：

P=[pp1,pp2,…,ppNimp]

然后隨機初始化一個與向量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中最大值對應的帝國將獲得一個新的殖民地。

在每一次迭代中，將檢查當前最弱帝國擁有的殖民地數(shù)，當其流失了所有的殖民地后，該帝國集團將被認為已崩塌，將刪除該帝國。

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

3 實驗分析

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

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

圖8 帝國主義競爭算法流程

表2 典型實例求解結果

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

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

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

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

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

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

表4 本文算法與ITNSGA[18]的平均求解時間和結果對比

4 結語

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

)

[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è)車間調度的空閑時間鄰域搜索遺傳算法[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。

國家自然科學基金資助項目(61462095);云南省軟件工程重點實驗室開放基金資助項目(2015SE103)。

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

1001- 9081(2017)02- 0517- 06

10.11772/j.issn.1001- 9081.2017.02.0517

TP301.6; TP18

A