陶文華，侯萌萌

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順　113001）

求解作業(yè)車間調(diào)度問(wèn)題的改進(jìn)螢火蟲(chóng)算法

陶文華，侯萌萌

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順113001）

作業(yè)車間調(diào)度問(wèn)題是將多臺(tái)機(jī)器安排處理多個(gè)工件的組合優(yōu)化問(wèn)題，使最大完工時(shí)間達(dá)到最小。應(yīng)用傳統(tǒng)螢火蟲(chóng)算法求解時(shí)，螢火蟲(chóng)個(gè)體到達(dá)最優(yōu)解附近時(shí)，相對(duì)吸引力逐漸增強(qiáng)，導(dǎo)致局部搜索能力減弱，造成求解結(jié)果在最優(yōu)解附近震蕩，進(jìn)而使求解精度下降。為改善解的質(zhì)量，本文在螢火蟲(chóng)算法迭代過(guò)程中引入精英選擇策略，保護(hù)進(jìn)化過(guò)程中的優(yōu)秀個(gè)體，避免最優(yōu)解丟失；為提高算法收斂速度與求解精度，對(duì)螢火蟲(chóng)位置更新方法引入基于種群規(guī)模和迭代次數(shù)的動(dòng)態(tài)自適應(yīng)慣性權(quán)重；同時(shí)對(duì)每一代螢火蟲(chóng)種群最優(yōu)個(gè)體引入禁忌搜索算法，提高局部搜索能力。仿真結(jié)果表明本文所提出改進(jìn)算法在解決作業(yè)車間調(diào)度問(wèn)題上的有效性與實(shí)用價(jià)值。

作業(yè)車間調(diào)度；改進(jìn)螢火蟲(chóng)算法；精英選擇策略；慣性權(quán)重

生產(chǎn)調(diào)度可以被定義為尋找一個(gè)問(wèn)題的最優(yōu)序列，執(zhí)行一組有限操作來(lái)滿足約束條件［1］。這是一個(gè)決策分配資源的過(guò)程在時(shí)間上執(zhí)行所需任務(wù)的集合。有效調(diào)度對(duì)任何行業(yè)的增長(zhǎng)至重要的作用。不同文獻(xiàn)中討論的調(diào)度問(wèn)題的類型具有不同性能的措施，如單機(jī)排序［2］，流水車間調(diào)度［3］、并行機(jī)調(diào)度［4］等。而作業(yè)車間調(diào)度［5］是其中一種重要類型的調(diào)度環(huán)境。該問(wèn)題與很多組合優(yōu)化類問(wèn)題一樣，是NP難問(wèn)題。其求解方法分為精確算法與近似算法，精確算法需要大量的時(shí)間成本，對(duì)于較大規(guī)模的作業(yè)車間調(diào)度問(wèn)題，精確算法所需要的時(shí)間嚴(yán)重超出了實(shí)際過(guò)程可以接受的范圍。因而，依靠近似算法進(jìn)行作業(yè)車間調(diào)度問(wèn)題的研究成為近年來(lái)的一個(gè)熱門(mén)方向。近似算法主要包括優(yōu)先權(quán)規(guī)則調(diào)度算法，啟發(fā)式算法以及基于鄰域搜索的局部改進(jìn)算法等。使用啟發(fā)式算法求解作業(yè)車間調(diào)度問(wèn)題已迅速增長(zhǎng)，如遺傳算法［6］、粒子群算法［7］、人工免疫系統(tǒng)［8］、離散人工蜂群［9］、離散的帝國(guó)主義競(jìng)爭(zhēng)算法［10］、混合帝國(guó)主義競(jìng)爭(zhēng)算法［11］等。

螢火蟲(chóng)算法［12］是由楊新社教授在2008年根據(jù)螢火蟲(chóng)通過(guò)熒光進(jìn)行信息交流而提出的一種新型啟發(fā)式算法。該算法模擬自然界中螢火蟲(chóng)群體高效的覓食、擇偶的機(jī)制，原理簡(jiǎn)單，設(shè)置參數(shù)少，而且算法中螢火蟲(chóng)個(gè)體間依靠熒光進(jìn)行信息交換形成正反饋機(jī)制，具有快速地全局搜索能力。楊嬌等［13］首先將螢火蟲(chóng)算法直接應(yīng)用到作業(yè)車間調(diào)度問(wèn)題上，為解決作業(yè)車間調(diào)度問(wèn)題提供了一種新的思路。但在解決問(wèn)題過(guò)程中，算法易陷入局部最優(yōu)，求解精度低。包曉曉等［14］在基本的螢火蟲(chóng)算法基礎(chǔ)上增加了局部尋優(yōu)的過(guò)程，并融合了布谷鳥(niǎo)算法中生物移動(dòng)的萊維分布特點(diǎn)來(lái)求解具有退化效應(yīng)的作業(yè)車間調(diào)度問(wèn)題，但計(jì)算量大，求解效率低。

禁忌搜索算法（TS）［15］是一種自適應(yīng)的局部搜索算法，主要思路是利用禁忌表將已出現(xiàn)過(guò)的最優(yōu)值禁忌以達(dá)到避免算法陷入局部最優(yōu)的目的，黃志等［16］提出一種求解作業(yè)車間調(diào)度問(wèn)題的啟發(fā)式算法，該算法結(jié)合禁忌搜索技術(shù)和前瞻思想，在試探式禁忌搜索過(guò)程中，對(duì)一個(gè)給定的可行解，每次在鄰域中連續(xù)試走（移動(dòng)）兩步，對(duì)每?jī)蓚€(gè)連續(xù)的移動(dòng)都用禁忌搜索過(guò)程得到一個(gè)調(diào)度。但該算法是搜索性能依賴于給定的初始解，一個(gè)較好的初始解可以使TS算法較快的收斂于全局最優(yōu)解，但一個(gè)較差的初始解可能很大程度上降低算法的收斂速度。

結(jié)合禁忌搜索算法與螢火蟲(chóng)算法的優(yōu)點(diǎn)，文中提出一種解決作業(yè)車間調(diào)度問(wèn)題的改進(jìn)的螢火蟲(chóng)算法。首先利用參數(shù)少，易操作的螢火蟲(chóng)算法進(jìn)行全局搜索，并引入精英選擇策略，對(duì)每一代種群中的優(yōu)秀個(gè)體進(jìn)行保留并產(chǎn)生下一代種群，以提高算法尋優(yōu)速度；給出一種自適應(yīng)權(quán)重的螢火蟲(chóng)位置更新方法，提高求解精度；對(duì)螢火蟲(chóng)算法全局尋優(yōu)后得到的最優(yōu)位置螢火蟲(chóng)采用禁忌搜索算法進(jìn)行局部尋優(yōu)，加強(qiáng)算法跳出局部最優(yōu)的能力，有效地避免陷入局部最優(yōu)。同時(shí)，禁忌搜索算法每一次迭代的初始解均由螢火蟲(chóng)種群重新產(chǎn)生，可以有效改善禁忌搜索算法對(duì)于初值敏感的缺陷，提高了局部搜索能力。針對(duì)典型作業(yè)車間調(diào)度問(wèn)題的仿真實(shí)驗(yàn)表明本文所提出算法的有效性與實(shí)用價(jià)值。

1　作業(yè)車間調(diào)度問(wèn)題的描述

作業(yè)車間調(diào)度問(wèn)題是一類典型的組合優(yōu)化問(wèn)題。該問(wèn)題可描述為在一個(gè)加工系統(tǒng)中，有n個(gè)待加工的工件在m臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件的加工順序是確定的，但不要求一致。而且各操作的加工時(shí)間已知。一個(gè)工件完成一道工序過(guò)程中不能中斷，當(dāng)這個(gè)工序完成時(shí)，這臺(tái)機(jī)器才可以加工下一個(gè)工件。本文的調(diào)度目標(biāo)是確定每個(gè)機(jī)器上工序的加工順序和每個(gè)工序的開(kāi)工時(shí)間，使最大完工時(shí)間最小。

2　基于改進(jìn)螢火蟲(chóng)算法的作業(yè)車間調(diào)度實(shí)現(xiàn)

2.1基本螢火蟲(chóng)算法

螢火蟲(chóng)算法首先在問(wèn)題求解空間中隨機(jī)初始化N個(gè)螢火蟲(chóng)個(gè)體，每個(gè)螢火蟲(chóng)個(gè)體代表作業(yè)車間調(diào)度問(wèn)題的一個(gè)可行解，其中第i（i=1，2，L，N）個(gè)螢火蟲(chóng)在D維空間中的當(dāng)前位置并都帶有自身具有一定熒光亮度，大小與所求解具體問(wèn)題的目標(biāo)函數(shù)值有關(guān)。目標(biāo)函數(shù)值越好，螢火蟲(chóng)的亮度越強(qiáng)。亮度強(qiáng)的螢火蟲(chóng)吸引亮度弱的螢火蟲(chóng)，使亮度弱的螢火蟲(chóng)向亮度強(qiáng)的螢火蟲(chóng)移動(dòng)。螢火蟲(chóng)移動(dòng)后位置進(jìn)行更新。隨著迭代過(guò)程的進(jìn)行，種群中亮度弱的螢火蟲(chóng)不斷向比自己更亮的螢火蟲(chóng)靠近，最終大多數(shù)的螢火蟲(chóng)會(huì)聚集在最亮的螢火蟲(chóng)周圍，最亮的螢火蟲(chóng)的位置就是問(wèn)題的最優(yōu)解。

2.2禁忌搜索算法

禁忌搜索算法（TS）是一種具有記憶能力的局部搜索算法，用s表示一個(gè)可行解，V（s）表示其對(duì)應(yīng)的移動(dòng)集合，Cmax（s）表示完工時(shí)間，C*表示當(dāng)前最小完工時(shí)間，t表示當(dāng)前迭代次數(shù)。設(shè)s′表示禁忌搜索的初始解。禁忌搜索算法求解問(wèn)題的步驟為：

步驟1：設(shè)置禁忌搜索的最大步長(zhǎng)maxiternum，令迭代次數(shù)iternum=0，設(shè)置禁忌表T=?，C*=Cmax（s*），s=s*；

步驟2：iternum=iternum+1，找出移動(dòng)集合V（s），若V（s）=?，迭代停止，返回新解s*；

步驟3：應(yīng)用鄰域搜索程序，找到移動(dòng)v′∈V（s），求出新解s′和新的禁忌表T′，令s=s′，T=T′；

步驟4：如果Cmax（s）＜C*，則設(shè)置C*=Cmax（s），s*=s；

步驟5：如果未達(dá)到停止準(zhǔn)則，轉(zhuǎn)步驟2；否則停止迭代，得到新解s*。

停止準(zhǔn)則設(shè)置為：禁忌搜索次數(shù)達(dá)到10次或所得到的最優(yōu)解5次未改變。

2.3改進(jìn)的螢火蟲(chóng)算法

首先本文為了保護(hù)在進(jìn)化過(guò)程中曾經(jīng)出現(xiàn)的優(yōu)秀個(gè)體，引入精英選擇策略。將父代螢火蟲(chóng)種群和子代螢火蟲(chóng)種群合并成一個(gè)新的種群，并計(jì)算個(gè)體的適應(yīng)度，根據(jù)適應(yīng)度的大小選取新種群中前50%個(gè)體作為父代進(jìn)行新一輪進(jìn)化操作得到下一代螢火蟲(chóng)種群。

其次，考慮當(dāng)運(yùn)行至后期時(shí)，螢火蟲(chóng)個(gè)體會(huì)達(dá)到或接近最優(yōu)個(gè)體附近，此時(shí)，螢火蟲(chóng)的相對(duì)吸引力將會(huì)逐漸增強(qiáng)，導(dǎo)致算法局部搜索能力減弱并可能造成求解結(jié)果在最優(yōu)值附近震蕩，進(jìn)而導(dǎo)致求解精度下降，求解效率降低。為此，在位置更新公式中引入慣性權(quán)重，以提高螢火蟲(chóng)算法的局部搜索和全局搜索能力。

慣性權(quán)重設(shè)置為隨種群規(guī)模及算法迭代次數(shù)的增加而減小，為此，對(duì)螢火蟲(chóng)位置更新方式作如下改變：對(duì)于螢火蟲(chóng)更新前的位置，引入一個(gè)服從正態(tài)分布的隨機(jī)變量ω，使其與種群規(guī)模大小和迭代次數(shù)相關(guān)，其表達(dá)式如下：

其中，n是種群規(guī)模，k是迭代的最大次數(shù)，t是當(dāng)前迭代次數(shù)，σ是標(biāo)準(zhǔn)差，a是常數(shù)。

進(jìn)而得到引入慣性權(quán)重后的位置更新公式如下：

最后，將禁忌搜索 （TS）思想融入到螢火蟲(chóng)算法中，提出一種改進(jìn)的螢火蟲(chóng)優(yōu)化算法。新算法結(jié)合了FA和TS各自的優(yōu)點(diǎn)，在求解作業(yè)車間調(diào)度問(wèn)題前期利用螢火蟲(chóng)算法得到較好的初始值，同時(shí)種群最優(yōu)值放人禁忌表，在算法運(yùn)行后期，由于螢火蟲(chóng)種群聚集在最優(yōu)螢火蟲(chóng)附近導(dǎo)致算法搜索能力減弱，利用禁忌搜索算法中禁忌表的記憶功能，使其跳出局部最優(yōu)解，并且在搜索過(guò)程中允許接受劣解。

禁忌搜索算去的引入思路是：引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則以避免迂回搜索，并通過(guò)特赦準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)。禁忌表用于存儲(chǔ)最近幾次的迭代中螢火蟲(chóng)所到達(dá)過(guò)的求解空間中的位置，在之后的迭代過(guò)程中，已經(jīng)出現(xiàn)過(guò)的位置被禁忌而不能達(dá)到。當(dāng)禁忌表中記錄的位置達(dá)到所設(shè)計(jì)的禁忌表的最大長(zhǎng)度或是禁忌表中的某個(gè)候選解的位置優(yōu)于種群歷史最優(yōu)解的位置時(shí)，解禁該候選解，這個(gè)條件稱為特赦準(zhǔn)則。引入禁忌搜索的思想可以提高算法局部搜索能力與運(yùn)行效率，并有效避免算法進(jìn)行迂回搜索導(dǎo)致陷入局部最優(yōu)。

應(yīng)用本文所提出的改進(jìn)的螢火蟲(chóng)算法求解作業(yè)車間調(diào)度問(wèn)題的步驟為：

步驟1：初始化種群。設(shè)置螢火蟲(chóng)種群規(guī)模，最大的迭代次數(shù)，禁忌表的長(zhǎng)度，禁忌搜索的最大步長(zhǎng)，最大熒光亮度及光強(qiáng)吸收系數(shù)。加工工件的工序采用字符串編碼方法，隨機(jī)選擇并排序編碼工序直到所有工序都被編碼。編碼中螢火蟲(chóng)的位置長(zhǎng)度等于優(yōu)化問(wèn)題中的所有工序數(shù)；螢火蟲(chóng)種群大小決定候選解的數(shù)量或者解空間里的搜索數(shù)量。

步驟2：隨機(jī)初始化螢火蟲(chóng)的位置，計(jì)算螢火蟲(chóng)的目標(biāo)函數(shù)值作為各自最大熒光亮度。本文對(duì)于作業(yè)車間調(diào)度問(wèn)題，優(yōu)化問(wèn)題的目標(biāo)函數(shù)為最小化最大完工時(shí)間，即minCmax，調(diào)度順序的優(yōu)劣選擇也由Cmax決定。

步驟3：選取前50%個(gè)體計(jì)算螢火蟲(chóng)相對(duì)亮度，根據(jù)相對(duì)亮度決定螢火蟲(chóng)的移動(dòng)方向。

步驟4：根據(jù)式（2）更新螢火蟲(chóng)位置得到下一代螢火蟲(chóng)并與上一代螢火蟲(chóng)組成新的種群。根據(jù)螢火蟲(chóng)的新位置，重新計(jì)算螢火蟲(chóng)的亮度。

步驟5：選取當(dāng)前種群中的最優(yōu)個(gè)體按禁忌搜索算法進(jìn)行局部搜索，達(dá)到禁忌搜索停止準(zhǔn)則時(shí)轉(zhuǎn)步驟6。

步驟6：判斷是否滿足最大迭代次數(shù)，如果滿足則轉(zhuǎn)入下一步，否則，迭代次數(shù)增加，轉(zhuǎn)步驟3進(jìn)行下一次搜索。

步驟7：輸出全局最優(yōu)解（最小完成時(shí)間）和最優(yōu)個(gè)體（即最優(yōu)排序）。

3　仿真結(jié)果與實(shí)驗(yàn)分析

仿真實(shí)驗(yàn)環(huán)境為：Windows XP操作系統(tǒng)，CPU為P4，內(nèi)存為2 GB，采用Matlab R2011b編程實(shí)現(xiàn)該算法。

為了便于驗(yàn)證本文提出的改進(jìn)的螢火蟲(chóng)算法在解決作業(yè)車間調(diào)度問(wèn)題中的可行性，仿真對(duì)象采用國(guó)際標(biāo)準(zhǔn)實(shí)例FT10（10×10），LA06（15×5），LA10（15×5）。算法參數(shù)設(shè)置如下：種群大小設(shè)置為 N=40，迭代次數(shù)為200，光強(qiáng)吸收系數(shù)γ=0.1，禁忌表的長(zhǎng)度maxIterStep=5，禁忌搜索的最大步長(zhǎng)maxNoneNum=10。

為了說(shuō)明本文提出的改進(jìn)的螢火蟲(chóng)算法解決作業(yè)車間調(diào)度問(wèn)題的有效性，針對(duì)FT10、LA06、LA10兩種測(cè)試?yán)姆抡娼Y(jié)果如表1～3所示。

表1　針對(duì)FT10 20次仿真實(shí)驗(yàn)的結(jié)果比較

表2　針對(duì)LA06 20次仿真實(shí)驗(yàn)的結(jié)果比較

表3　針對(duì)LA10 20次仿真實(shí)驗(yàn)的結(jié)果比較

從測(cè)試結(jié)果可以看出，改進(jìn)的螢火蟲(chóng)算法和基本的螢火蟲(chóng)算法均能搜索到已知的最優(yōu)值，驗(yàn)證了改進(jìn)螢火蟲(chóng)算法在處理作業(yè)車間調(diào)度問(wèn)題上的可行性。

4　結(jié)束語(yǔ)

文中針對(duì)作業(yè)車間調(diào)度問(wèn)題，充分利用螢火蟲(chóng)算法簡(jiǎn)單易操作的特點(diǎn)，結(jié)合禁忌搜索算法，得到了一種高效，高求解精度，且能有效避免求解過(guò)程陷入局部最優(yōu)的禁忌-螢火蟲(chóng)算法，通過(guò)對(duì)幾類較大規(guī)模的標(biāo)準(zhǔn)作業(yè)車間調(diào)度問(wèn)題的仿真實(shí)驗(yàn)，驗(yàn)證其可行性與實(shí)用價(jià)值。不足之處在于算法中引進(jìn)了新的可調(diào)參數(shù)，對(duì)算法帶來(lái)了一定影響，因此，從理論上進(jìn)一步分析算法的收斂性及收斂速度及參數(shù)對(duì)結(jié)果的影響將是我們下一步的研究?jī)?nèi)容。

［1］Jacek B，Wolfgang D，Erwin P.The job shop scheduling problem：Conventional and new solution techniques［J］.European Journal of Operational Research，1996，93（1）：1-33.

［2］akar T.Single machine scheduling with unequal release date using neuro-dominance rule［J］.Journal of Intelligent Manufacturing，2011，22（4）：481-490.

［3］Mirabi M，Ghomi，S.M.T.F，Jolai，F(xiàn).A two-stage hybrid flowshopschedulingprobleminmachinebreakdown condition［J］.Journal of Intelligent Manufacturing，2013，24 （1）：193-199.

［4］Ying，K.C，Lee，Z.J，Lin，S.W.Makespan minimization for scheduling unrelated parallel machines with setup times［J］. Journal of Intelligent Manufacturing，2012，23（5）：1795-1803.

［5］Meeran S，Morshed M S.A hybrid genetic tabu search algorithm for solving job shop scheduling problems：A case study［J］.Journal of Intelligent Manufacturing，2012，23（4）：1063-1078.

［6］Hasnahmoin.N，Sin OC，Omar M.Hybrid genetic algorithm with multiparents crossover for job shop scheduling problems ［J］.Mathematical Problems in Engineering，2015：1-12.

［7］Lin T L，Horng S J，Ka T W，etal.An efficient job-shop scheduling algorithm based on particle swarm optimization［J］. Expert Systems with Applications，2010，37（3）：2629-2636.

［8］Qiu X，Lau H.K.An AIS-based hybrid algorithm for static job shop scheduling problem［J］.Journal of Intelligent Manu-facturing，2014，25（3）：489-503.

［9］Yin M，Li X，Zhou J.An efficient job shop scheduling algorithm based on artificial bee colony［J］.Scientific Research and Essays，2011，6（12）：2578-2596.

［10］Hosseini S，Khaled A A.A survey on the imperialist competitivealgorithmmetaheuristic：Implementationin engineering domain and directions for future research［J］. Applied Soft Computing，2014，24：1078-1094.

［11］HosseiniS，KhaledA，VadlamaniS.Hybridimperialist competitive algorithm，variable neighborhood search，and simulated annealing for dynamic facility layout problem［J］. NeuralComputingandApplications，2014，25（7-8）：1871-1885.

［12］Yang X S.Nature-inspired metaheuristic algorithm［M］. Luniver Press，2008.

［13］楊嬌，葉春明.應(yīng)用新型螢火蟲(chóng)算法求解Job-shop調(diào)度問(wèn)題［J］.計(jì)算機(jī)過(guò)程與應(yīng)用，2013，49（11）：213-216.

［14］包曉曉，葉春明.改進(jìn)的螢火蟲(chóng)算法求解具有學(xué)習(xí)退化效應(yīng)的JSP問(wèn)題［J］.數(shù)學(xué)理論與應(yīng)用，2014，9（3）：65-75

［15］Zhang C，Li P，Guan Z，Rao Y.A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem［J］.Computers and Operations Research，2007，34 （11）：3229-3242.

［16］黃志，黃文奇.一種基于禁忌搜索的作業(yè)車間調(diào)度算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006（3）：12-14．

Improved firefly algorithm for job-shop scheduling problem

TAO Wen-hua，HOU Meng-meng
（School of Information and Control Engineering，Liaoning Shihua University，F(xiàn)ushun 113001，China）

Job-shop Scheduling problem（JSP）is a combinatorial optimization problem to arrange muti workpiece on multi machines to obtain minimize the maximum completion time.Fireflies wander nearby the optimal solution at the late stage of traditional firefly algorithm to solve JSP，causing strong mutual attraction and weakening the local search ability and declining the solving precision.Elite selection strategy is introduced aiming at protecting the excellent individuals to improve the solution quality.Dynamic adaptive inertia weight corresponding with the population scale and iteration number is introduced to the location update method to improve the convergence speed and solution precision.Apply tabu search algorithm to the best individual of each generation to enhance the local search ability.Simulation results demonstrate the effectiveness and merits.

job-shop schedule；improved firefly algorithm；elite selection strategy；inertial weight

TP29

A

1674－6236（2016）09-0113-03

2016-02-01稿件編號(hào)：201602004

國(guó)家自然科學(xué)基金青年基金項(xiàng)目（61203021）

陶文華（1972—），女，浙江紹興人，碩士，教授。研究方向：生產(chǎn)調(diào)度優(yōu)化理論與應(yīng)用。