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

夏晶晶， 王 猛

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

?

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

夏晶晶*， 王 猛

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

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

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

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

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

1 JSP問(wèn)題描述及數(shù)學(xué)模型

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

(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為機(jī)器總數(shù)；Oi為第i個(gè)工件；Sik為Oi在機(jī)器k上的開(kāi)始時(shí)間；Cik為Oi在機(jī)器k上的完工時(shí)間；Cmax為車(chē)間內(nèi)的最大完工時(shí)間；α為一個(gè)很大的正數(shù)；xijk為0-1變量，若機(jī)器j先于機(jī)器k加工Oi，則xijk=1，否則xijk=0；yihk為0-1變量，若機(jī)器k上Oi先于Oh加工，則yihk=1，否則yihk=0.

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

2 基本蝙蝠算法

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

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

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

(7)

(8)

(9)

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

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

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

3 IBA算法求解JSP問(wèn)題

3.1調(diào)度解表示

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

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

3.2個(gè)體位置向量

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

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

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

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

3.3初始化方案

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

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

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

3.4變鄰域搜索

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

1) 交換操作N1.在個(gè)體位置編碼中隨機(jī)選擇兩個(gè)對(duì)應(yīng)不同工件的位置元素，并對(duì)二者進(jìn)行交換操作.

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

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

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

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

步驟2：設(shè)置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：設(shè)置ct←ct+1.若ct>ctmax，執(zhí)行步驟5；否則轉(zhuǎn)到步驟2.

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

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

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

(10)

(11)

3.6IBA算法步驟

IBA算法的具體步驟如下：

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

步驟2：評(píng)價(jià)初始個(gè)體，并找出當(dāng)前最優(yōu)個(gè)體.

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

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

步驟5：評(píng)價(jià)每一個(gè)新解，若優(yōu)于當(dāng)前最優(yōu)解且滿(mǎn)足rand

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

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

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

4 仿真分析

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

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

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

續(xù)表1

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

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

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

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

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

5 結(jié)論

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

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

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

[2] 趙良輝， 鄧飛其. 解決 Job Shop 調(diào)度問(wèn)題的模擬退火算法改進(jìn)[J]. 計(jì)算機(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)化問(wèn)題的可全局收斂蝙蝠算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2013， 30(5): 1323-1328．

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

[14] 陳紹煒， 柳光峰， 冶 帥， 等. 基于蝙蝠算法優(yōu)化ELM的模擬電路故障診斷研究[J]. 電子測(cè)量技術(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)度問(wèn)題中的應(yīng)用研究[J]. 工業(yè)工程， 2013， 16(1): 119-124．

[21] 馬邦雄， 葉春明. 基于蝙蝠退火算法的無(wú)等待流水線調(diào)度問(wèn)題研究[J]. 數(shù)學(xué)理論與應(yīng)用， 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] 趙詩(shī)奎， 方水良. 基于工序編碼和鄰域搜索策略的遺傳算法優(yōu)化作業(yè)車(chē)間調(diào)度[J]. 機(jī)械工程學(xué)報(bào)， 2013， 49(16): 160-169．

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

[25] 姚遠(yuǎn)遠(yuǎn)， 葉春明. 作業(yè)車(chē)間調(diào)度問(wèn)題的布谷鳥(niǎo)搜索算法求解[J]. 計(jì)算機(jī)工程與應(yīng)用， 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)項(xiàng)目(142102210440)．

1000-1190(2016)04-0536-08

TP18

A

*E-mail: xiajjhuahe@163.com．