夏晶晶， 王 猛

(河南牧業(yè)經(jīng)濟學院 信息工程系， 鄭州 450011)

?

面向作業(yè)車間調(diào)度問題的改進型蝙蝠算法

夏晶晶*， 王 猛

(河南牧業(yè)經(jīng)濟學院 信息工程系， 鄭州 450011)

針對作業(yè)車間調(diào)度問題(Job shop scheduling problem， JSP)，提出了一種改進型蝙蝠算法(Improved bat algorithm， IBA)以優(yōu)化車間內(nèi)工件的最大完工時間.根據(jù)作業(yè)車間調(diào)度問題的特點以及基本蝙蝠算法的搜索機制，首先對個體位置向量進行了設計，實現(xiàn)了蝙蝠算法中離散問題的連續(xù)編碼；然后分別采用G&T 算法和隨機生成兩種方法對算法種群進行初始化，以提高初始解的質(zhì)量.此外，采用三種鄰域結(jié)構(gòu)，并在此基礎上設計了變鄰域搜索策略作用于最優(yōu)個體，以避免算法出現(xiàn)早熟收斂，提高IBA算法的性能.最后，針對JSP問題的基準算例進行了大量的仿真實驗，計算結(jié)果驗證了本文所提出的IBA算法的可行性和有效性.

作業(yè)車間； 生產(chǎn)調(diào)度； 最大完工時間； 蝙蝠算法； 變鄰域搜索策略

車間調(diào)度問題一直是制造領(lǐng)域中的一個研究熱點和難點，是實現(xiàn)生產(chǎn)運作與管理的核心，在很大程度上影響著企業(yè)的生存和發(fā)展.作業(yè)車間調(diào)度問題(Job shop scheduling problem， JSP)是一種典型的車間調(diào)度問題，絕大多數(shù)JSP問題均具有NP難特性.元啟發(fā)式算法為JSP問題的求解提供了一種有效可行的方案，這些算法雖無法保證達到全局最優(yōu)解，但通常能在可行的時間內(nèi)得到問題的近似解，其中包括模擬退火算法、遺傳算法、免疫算法以及粒子群算法等等.文獻[1]將一種并行模擬退火算法應用于求解JSP問題，給出了有效的鄰域搜索規(guī)則.文獻[2]給出了一種基于模擬退火算法的車間調(diào)度問題模型.文獻[3]提出了一種基于遺傳算法和模擬退火算法的混合算法求解以最小化最大完工時間為目標的JSP問題.文獻[4]針對零等待時間的作業(yè)車間調(diào)度問題，設計了一種混合型遺傳算法.文獻[5]將局部搜索算法和遺傳算法相結(jié)合用于求解機器調(diào)整時間與工序順序相關(guān)的作業(yè)車間調(diào)度問題.文獻[6]針對以總權(quán)重拖期時間為目標的作業(yè)車間調(diào)度問題，設計了一種免疫退火算法.文獻[7]基于人工免疫算法研究了具備路徑柔性特征的作業(yè)車間調(diào)度問題.文獻[8]將蟻群算法和禁忌搜索相結(jié)合，提出了一種混合型算法求解JSP問題，利用禁忌搜索加強蟻群算法的局部搜索能力.文獻[9]將粒子群算法、模擬退火算法和啟發(fā)式機制三者結(jié)合，提出一種有效的混合算法.文獻[10]考慮了實際生產(chǎn)中存在的機器調(diào)整時間和可用性約束，結(jié)合類電磁機制算法和模擬退火算法求解作業(yè)車間調(diào)度問題.

隨著元啟發(fā)式算法的迅速崛起和不斷發(fā)展，近些年又涌現(xiàn)出一些新興的算法.蝙蝠算法(Bat algorithm， BA)[11]是2010年由Yang根據(jù)自然界中蝙蝠所具備的回聲定位能力而提出的.它具有模型簡單、收斂速度快以及并行處理等特點，從而得到了學者們的關(guān)注和認可，已被廣泛用于自然科學與工程科學領(lǐng)域[12-17]，但是目前將蝙蝠算法運用于車間調(diào)度問題的研究文獻還相對較少，并且大都集中于流水車間內(nèi)的生產(chǎn)調(diào)度問題[18-22].與流水車間調(diào)度問題相比，作業(yè)車間調(diào)度問題更加復雜，并且具有很強的工程應用背景.因此，本文針對作業(yè)車間調(diào)度問題的特點，對基本蝙蝠算法進行改進，提出了一種改進型的蝙蝠算法(Improved bat algorithm， IBA).運用IBA算法對JSP問題基準算例求解，并將其結(jié)果與現(xiàn)有文獻中的算法結(jié)果進行對比，驗證了本文算法在求解JSP問題方面的可行性和有效性.

1 JSP問題描述及數(shù)學模型

JSP問題一般可描述為：車間內(nèi)n個工件要在m臺機器上進行操作，各工件均有其自身固定的加工路徑，并且各道工序具有已知確定的加工時間.該問題的目標是確定機器上各工件加工先后順序，使得期望的生產(chǎn)指標最優(yōu)化.車間內(nèi)任一工序一旦開始，則不可被中斷，而且每臺機器在同一個時刻只能加工一道工序.本文考慮以最小化最大完工時間作為JSP問題的優(yōu)化目標，其數(shù)學模型為

(1)

i=1，2，…，n;j，k=1，2，…，m，

(2)

i，h=1，2，…，n;k=1，2，…，m，

(3)

Cik≥0，i=1，2，…，n;k=1，2，…，m，

(4)

(5)

(6)

模型中n為工件總數(shù)；m為機器總數(shù)；Oi為第i個工件；Sik為Oi在機器k上的開始時間；Cik為Oi在機器k上的完工時間；Cmax為車間內(nèi)的最大完工時間；α為一個很大的正數(shù)；xijk為0-1變量，若機器j先于機器k加工Oi，則xijk=1，否則xijk=0；yihk為0-1變量，若機器k上Oi先于Oh加工，則yihk=1，否則yihk=0.

各表達式可解釋為，式(1)表示以最小化最大完工時間作為優(yōu)化目標；式(2)表示工件各工序間的先后關(guān)系；式(3)表示機器在同一時刻只能加工一個工件；式(4)表示工件完工時間大于零；式(5)和式(6)表示0-1變量.

2 基本蝙蝠算法

自然界中的蝙蝠擁有一個非常復雜的回聲定位系統(tǒng).在捕食的過程中，蝙蝠通過發(fā)出具有較大脈沖響度和較低的脈沖頻度的聲波來尋找獵物，當找到目標并向目標靠近的時候，會逐漸降低響度和升高頻度，甚至進入靜音狀態(tài).基本蝙蝠算法正是模擬這種特性對目標函數(shù)進行優(yōu)化的.算法中每個個體代表一只蝙蝠，通過調(diào)整頻率fri∈[frmin，frmax]對目標進行定位.按照脈沖頻度ri和響度Ldi發(fā)出聲波脈沖，定位的過程中若發(fā)現(xiàn)目標則更新脈沖頻度ri和響度Ldi，從而逼近目標.基本蝙蝠算法的具體步驟如下[21].

步驟1：算法初始化，即初始化種群、算法參數(shù)和終止條件.

fri=frmin+(frmax-frmin)×rand，

(7)

(8)

(9)

步驟3：局部搜索.若rand>ri，則進行局部搜索產(chǎn)生新解，其規(guī)則為xnew=xold+εLdt，其中xold為當前最優(yōu)個體位置中的任意一個，ε為[-1，1]間服從均勻分布的隨機數(shù)向量，Ldt為t時刻種群中所有個體響度的平均值.

步驟5：找到蝙蝠種群中當前最優(yōu)個體位置向量x*.若滿足終止條件，轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟2.

步驟6：算法結(jié)束.

3 IBA算法求解JSP問題

3.1調(diào)度解表示

采用基于工件編碼的方式表示每一個調(diào)度解，即每個元素的值均為工件的編號.整個調(diào)度解的長度為車間內(nèi)工序的總數(shù)，如圖1所示.圖中包含3個工件，每個工件包含3道工序.相同的元素值表示同一工件的不同工序，例如，第3個‘3’表示工件3的第3道工序.

圖1 調(diào)度解的表示
Fig.1 Expression of Scheduling Solution

3.2個體位置向量

基本蝙蝠算法個體位置向量中元素為一系列連續(xù)值，通過在搜索過程中不斷更新以尋求優(yōu)化問題的解.本文改進型蝙蝠算法中個體位置向量的元素仍采用一定范圍內(nèi)的連續(xù)值表示，其長度與調(diào)度解的長度相同，各元素值按照工序編號的順序存儲，如圖2所示.

圖2 個體位置向量的表示Fig.2 Expression of Individual Position Vector

考慮到基本蝙蝠算法中每個個體位置均為連續(xù)值，而作業(yè)車間調(diào)度問題則屬于離散型組合優(yōu)化問題，因此運用蝙蝠算法求解JSP問題時，首先要明確的是解空間和問題空間之間的映射關(guān)系，即如何對算法的轉(zhuǎn)換機制進行合理設計，使其適用于作業(yè)車間調(diào)度問題的求解.本文中提出的轉(zhuǎn)換機制為，首先根據(jù)個體位置向量中元素數(shù)值的大小進行升序排列，并找到各數(shù)值對應的工序編號，由此即可將連續(xù)型個體位置向量轉(zhuǎn)換為離散型工序排序序列，得到問題的調(diào)度解，該過程如圖3所示.

圖3 個體位置向量轉(zhuǎn)換為工序排序Fig.3 Individual Position Vector Converts to Process Scheduling

3.3初始化方案

目前在許多運用智能優(yōu)化算法求解JSP問題的研究中，學者們多采用基于調(diào)度規(guī)則或啟發(fā)式算法的種群初始化方法，其目的是改善算法中初始種群的質(zhì)量，以至達到改善算法計算性能的目的.本文將G&T算法產(chǎn)生的主動調(diào)度方案和無延遲調(diào)度方案[23]以及由隨機生成方式得到的調(diào)度方案作為初始調(diào)度解.這3種方案按一定的比例(如40%、40%和20%)生成初始個體，最終構(gòu)成算法的初始種群.

根據(jù)蝙蝠算法的搜索機制，初始調(diào)度解生成后還需經(jīng)過一些列的轉(zhuǎn)換，將其轉(zhuǎn)換成個體位置向量后，才能進行下一步搜索.本文設計的轉(zhuǎn)換方法為：假設存在一組隨機數(shù)序列，首先將其按升序排列，并將排列后序列與初始工序排序?qū)?，然后對照工序編號的順序找到各工序?qū)臄?shù)值，由此即可得到所需的個體位置向量，該過程如圖4所示.

圖4 初始排序轉(zhuǎn)換成個體位置向量Fig.4 Initial Scheduling Converts to Individual Position Vector

3.4變鄰域搜索

變鄰域搜索策略通過改變算法搜索的鄰域結(jié)構(gòu)來尋找最優(yōu)解.在IBA算法中，采用變鄰域搜索策略搜索當前最優(yōu)個體位置的鄰域，然后轉(zhuǎn)換成新的調(diào)度解.本文包含以下3種鄰域搜索操作，均用于變鄰域搜索算法中振動和局部搜索兩個環(huán)節(jié).

1) 交換操作N1.在個體位置編碼中隨機選擇兩個對應不同工件的位置元素，并對二者進行交換操作.

2) 插入操作N2.在個體位置編碼中隨機選擇兩個對應不同工件的位置元素，將后一個元素插到前一個元素前面.

3) 逆序操作N3.在個體位置編碼中隨機選擇一段序列，將該段序列內(nèi)的元素根據(jù)原來的順序逆序排列.

變鄰域搜索策略中局部搜索的具體步驟如下：

步驟1：獲取由振動環(huán)節(jié)得到的解作為初始解π，并設置ct←1和終止條件ctmax.

步驟2：設置l←1.

步驟3：執(zhí)行如下代碼直到l>lmax.

if l=1 then π′∈N1(π)；else if l=2 then π′∈N2(π)；else if l=3 then π′∈N3(π) end if

if Cmax(π′)

步驟4：設置ct←ct+1.若ct>ctmax，執(zhí)行步驟5；否則轉(zhuǎn)到步驟2.

步驟5：局部搜索結(jié)束.

3.5脈沖頻度ri和響度Ldi的更新

基本蝙蝠算法在搜索的過程中若發(fā)現(xiàn)新解則需對脈沖頻度和脈沖響度進行更新.本文采用文獻[22]中的更新方式，如式(10)和式(11)所示.t為迭代次數(shù)，tmax為最大迭代次數(shù)，fi為個體i當前目標值，fmax和fmin為當前種群中最大和最小的目標值.式(10)得到的曲線形式類似于Sigmoid函數(shù)[24]，這樣可使算法在運行早期以較大概率搜索較優(yōu)個體，加快收斂速度；算法后期由于脈沖頻度較大，保證了算法中解的多樣性，防止陷入局部最優(yōu)解；式(11)為響度更新公式，使得較優(yōu)個體具有更低的響度.

(10)

(11)

3.6IBA算法步驟

IBA算法的具體步驟如下：

步驟1：算法初始化，即初始化種群，設置算法中參數(shù)及終止條件.

步驟2：評價初始個體，并找出當前最優(yōu)個體.

步驟3：根據(jù)式(7)～(9)更新蝙蝠個體的位置和速度.

步驟4：對于每個個體，若rand>ri，則采用3.4節(jié)局部搜索算法對當前最優(yōu)個體進行局部搜索產(chǎn)生一個新解.

步驟5：評價每一個新解，若優(yōu)于當前最優(yōu)解且滿足rand

步驟6：更新當前最優(yōu)個體位置，并對其執(zhí)行變鄰域搜索操作.

步驟7：終止條件檢查.若滿足，轉(zhuǎn)到步驟8，否則轉(zhuǎn)到步驟3.

步驟8：算法結(jié)束.

4 仿真分析

采用Fortran語言對IBA算法進行編程，程序的運行環(huán)境為WinXP系統(tǒng)下內(nèi)存4G的Intel Core (TM) i5-2400 CPU 3.10GHz的計算機.仿真過程中IBA算法參數(shù)設置為：種群規(guī)模為80，最大迭代次數(shù)為200，變鄰域搜索和局部搜索中最大迭代次數(shù)為10.

為了測試IBA算法的性能，選取JSP問題的23個基準算例，采用IBA算法對各算例均進行10次仿真計算，并將計算結(jié)果與其他文獻中幾種算法所得的最優(yōu)結(jié)果進行對比，這些算法包括文獻[24]中改進的遺傳規(guī)劃算法(Improved GP)、文獻[25]中的布谷鳥搜索算法(CS)、文獻[26]中的基于PR優(yōu)先規(guī)則的Memetic算法(MA(PR))、文獻[27]中基于鄰域搜索的混合差分進化和分布估計算法(NS-HDE/EDA)以及本文設計的基本蝙蝠算法(BA)，其中BA算法與IBA算法的主要區(qū)別在于，BA算法采用隨機方式生成初始種群，并且不包含變鄰域搜索策略.算法計算結(jié)果如表1所示，表中‘-’表示文獻中未給出相應的數(shù)據(jù)；標準解表示現(xiàn)有文獻中得到的各算例的最佳結(jié)果；粗體表示各算法得到的最優(yōu)解等于標準解.

表1 算法結(jié)果對比

續(xù)表1

由表1數(shù)據(jù)可以看出，IBA算法獨立運行10次所得各算例平均值和最差值相差不大甚至相等，表明其具有較好的魯棒性.通過與BA算法的結(jié)果比較，可以看出IBA算法最終解的質(zhì)量優(yōu)于BA算法，并且從圖5和圖6可以看出，IBA算法的收斂特性同樣也明顯優(yōu)于BA算法.因此，采用本文提出的種群初始化方法和變鄰域搜索策略能夠有效地改善算法的性能.

圖5 算例LA04的收斂曲線Fig.5 Convergence curves of LA04

此外，與其他算法相比，IBA算法可以得到23個算例中19個算例的標準解，并且在算例相同的情況下，IBA算法獲得標準解的算例的個數(shù)均多于其他算法.因此，本文提出的IBA算法在求解JSP問題方面具有一定的有效性.圖7和圖8分別表示由IBA算法得到的LA01和LA14兩個算例的甘特圖，其中每個方框?qū)坏拦ば?，方框下方對應工序的名稱，如圖7中‘10-1’表示工件10的第一道工序.

圖7 算例LA01的甘特圖Fig.7 Gantt chart of LA01

圖8 算例LA14的甘特圖Fig.8 Gantt chart of LA14

5 結(jié)論

本文提出了改進型的蝙蝠算法求解以最大完工時間為優(yōu)化目標的作業(yè)車間調(diào)度問題.首先對算法的個體位置向量進行設計，實現(xiàn)車間調(diào)度問題的連續(xù)編碼；然后基于G&T算法和隨機生成規(guī)則對種群進行了初始化.此外，還引入了變鄰域搜索策略以防止早熟情況的出現(xiàn)，提高算法尋優(yōu)能力.最后，針對基準算例進行仿真實驗，結(jié)果驗證了IBA算法在解決作業(yè)車間調(diào)度問題方面的有效性.

蝙蝠算法是一種新型的元啟發(fā)式算法，目前還較少地被應用于車間調(diào)度問題的研究，今后還需進一步將其運用于其他更復雜的車間調(diào)度問題的求解，并與其他智能優(yōu)化算法結(jié)合，取長補短，獲得更加高效的求解算法.

[1] 吳大為， 陸濤棟， 劉曉冰， 等. 求解作業(yè)車間調(diào)度問題的并行模擬退火算法[J]. 計算機集成制造系統(tǒng)， 2005， 11(6): 847-850．

[2] 趙良輝， 鄧飛其. 解決 Job Shop 調(diào)度問題的模擬退火算法改進[J]. 計算機工程， 2006， 32(21): 38-40．

[3] TAMILARASI A. An enhanced genetic algorithm with simulated annealing for job-shop scheduling[J]. International Journal of Engineering， Science and Technology， 2010， 2(1): 144-151．

[4] PAN J C H， HUANG H C. A hybrid genetic algorithm for no-wait job shop scheduling problems[J]. Expert Systems with Applications， 2009， 36(3): 5800-5806．

[5] VELA C R， VARELA R， GONZALEZ M A. Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times[J]. Journal of Heuristics， 2010， 16(2): 139-165．

[6] ZHANG R， WU C. A hybrid immune simulated annealing algorithm for the job shop scheduling problem[J]. Applied Soft Computing， 2010， 10(1): 79-89．

[7] GOLMAKANI H R， NAMAZI A. An artificial immune algorithm for multiple-route job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology， 2012， 63(4): 77-86．

[8] HUANG K L， LIAO C J. Ant colony optimization combined with taboo search for the job shop scheduling problem[J]. Computers & Operations Research， 2008， 35(4): 1030-1046．

[9] LIN T L， HORNG S J， KAO T W， et al. An efficient job-shop scheduling algorithm based on particle swarm optimization[J]. Expert Systems with Applications， 2010， 37(3): 2629-2636．

[10] TAVAKKOLI M R， KHALILI M， NADERI B. A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness[J]. Soft Computing， 2009， 13(10): 995-1006．

[11] YANG X S， HOSSEIN G A. Bat algorithm: a novel approach for global engineering optimization[J]. Engineering Computations， 2012， 29(5): 464-483．

[12] 黃光球， 趙魏娟， 陸秋琴. 求解大規(guī)模優(yōu)化問題的可全局收斂蝙蝠算法[J]. 計算機應用研究， 2013， 30(5): 1323-1328．

[13] 李枝勇， 馬 良， 張惠珍. 求解最小比率旅行商問題的離散蝙蝠算法[J]. 計算機應用研究， 2015， 32(2): 356-359．

[14] 陳紹煒， 柳光峰， 冶 帥， 等. 基于蝙蝠算法優(yōu)化ELM的模擬電路故障診斷研究[J]. 電子測量技術(shù)， 2015， 20(2): 138-141．

[15] GANDOMI A H， YANG X S， ALAVI A H， et al. Bat algorithm for constrained optimization tasks[J]. Neural Computing and Applications， 2013， 22(6): 1239-1255．

[16] BORA T C， COELHO L S， LEBENSZTAJN L. Bat-inspired optimization approach for the brushless DC wheel motor problem[J]. Magnetics， IEEE Transactions， 2012， 48(2): 947-950．

[17] BAHMANI F B， AZIZIPANAH A R. Optimal sizing of battery energy storage for micro-grid operation management using a new improved bat algorithm[J]. International Journal of Electrical Power & Energy Systems， 2014， 56(1): 42-54．

[18] MARICHELVAM M K， PRABAHARAM T， YANG X S， et al. Solving hybrid flow shop scheduling problems using bat algorithm[J]. International Journal of Logistics Economics and Globalisation， 2013， 5(1): 15-29．

[19] MARICHELVAM M K， PRABAHARAM T. A bat algorithm for realistic hybrid flowshop scheduling problems to minimize makespan and mean flow time[J]. ICTACT Journal on Soft Computing， 2012， 3(1): 428-433．

[20] 盛曉華， 葉春明. 蝙蝠算法在PFSP調(diào)度問題中的應用研究[J]. 工業(yè)工程， 2013， 16(1): 119-124．

[21] 馬邦雄， 葉春明. 基于蝙蝠退火算法的無等待流水線調(diào)度問題研究[J]. 數(shù)學理論與應用， 2014， 34(1): 92-101．

[22] LUO Q， ZHOU Y， XIE J， et al. Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling[J]. The Scientific World Journal， 2014， 24(1):35-45．

[23] 趙詩奎， 方水良. 基于工序編碼和鄰域搜索策略的遺傳算法優(yōu)化作業(yè)車間調(diào)度[J]. 機械工程學報， 2013， 49(16): 160-169．

[24] 張國輝， 高 亮， 李培根. 基于遺傳規(guī)劃的作業(yè)車間調(diào)度算法研究[J]. 控制與決策， 2008， 23(8): 924-928．

[25] 姚遠遠， 葉春明. 作業(yè)車間調(diào)度問題的布谷鳥搜索算法求解[J]. 計算機工程與應用， 2015， 51(5): 255-260．

[26] HASAN S M K， SARKER R， ESSAM D， et al. Memetic algorithms for solving job-shop scheduling problems[J]. Memetic Computing， 2009， 1(1): 69-83．

[27] ZHAO F， SHAO Z， WANG J， et al. A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems[J]. International Journal of Production Research， 2015， 25 (1): 1-22．

Improved bat algorithm for job shop scheduling problem

XIA Jingjing, WANG Meng

(Department of Information Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450054)

For the job shop scheduling problem (JSP), an improved bat algorithm (IBA) is proposed to optimize the makespan of jobs in the workshop. According to the characteristics of JSP and the searching mechanism of the basic bat algorithm, the individual position vector is designed firstly to realize the continuous encoding of the discrete problem. Then the G&T algorithm and the random rule are adopted to initialize the population of the algorithm in order to improve the quality of the initial solutions. In addition, three neighborhood structures are introduced. On the basis of them, a variable neighborhood search strategy is designed for applying to the best individual to avoid the premature convergence and enhance the performance of the proposed IBA. Finally, extensive simulations are conducted for some benchmark instances of the JSP. The computational results demonstrate that the proposed IBA is feasible and effective.

job shop; production scheduling; makespan; bat algorithm; variable neighborhood search strategy

2015-12-16.

河南省科技攻關(guān)項目(142102210440)．

1000-1190(2016)04-0536-08

TP18

A

*E-mail: xiajjhuahe@163.com．