求解作業(yè)車間調度問題的改進螢火蟲算法

陶文華，侯萌萌

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

求解作業(yè)車間調度問題的改進螢火蟲算法

陶文華，侯萌萌

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

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

作業(yè)車間調度；改進螢火蟲算法；精英選擇策略；慣性權重

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

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

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

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

1　作業(yè)車間調度問題的描述

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

2　基于改進螢火蟲算法的作業(yè)車間調度實現

2.1基本螢火蟲算法

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

2.2禁忌搜索算法

禁忌搜索算法（TS）是一種具有記憶能力的局部搜索算法，用s表示一個可行解，V（s）表示其對應的移動集合，Cmax（s）表示完工時間，C*表示當前最小完工時間，t表示當前迭代次數。設s′表示禁忌搜索的初始解。禁忌搜索算法求解問題的步驟為：

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

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

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

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

步驟5：如果未達到停止準則，轉步驟2；否則停止迭代，得到新解s*。

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

2.3改進的螢火蟲算法

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

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

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

其中，n是種群規(guī)模，k是迭代的最大次數，t是當前迭代次數，σ是標準差，a是常數。

進而得到引入慣性權重后的位置更新公式如下：

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

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

應用本文所提出的改進的螢火蟲算法求解作業(yè)車間調度問題的步驟為：

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

步驟2：隨機初始化螢火蟲的位置，計算螢火蟲的目標函數值作為各自最大熒光亮度。本文對于作業(yè)車間調度問題，優(yōu)化問題的目標函數為最小化最大完工時間，即minCmax，調度順序的優(yōu)劣選擇也由Cmax決定。

步驟3：選取前50%個體計算螢火蟲相對亮度，根據相對亮度決定螢火蟲的移動方向。

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

步驟5：選取當前種群中的最優(yōu)個體按禁忌搜索算法進行局部搜索，達到禁忌搜索停止準則時轉步驟6。

步驟6：判斷是否滿足最大迭代次數，如果滿足則轉入下一步，否則，迭代次數增加，轉步驟3進行下一次搜索。

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

3　仿真結果與實驗分析

仿真實驗環(huán)境為：Windows XP操作系統，CPU為P4，內存為2 GB，采用Matlab R2011b編程實現該算法。

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

為了說明本文提出的改進的螢火蟲算法解決作業(yè)車間調度問題的有效性，針對FT10、LA06、LA10兩種測試例的仿真結果如表1～3所示。

表1　針對FT10 20次仿真實驗的結果比較

表2　針對LA06 20次仿真實驗的結果比較

表3　針對LA10 20次仿真實驗的結果比較

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

4　結束語

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

［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.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］楊嬌，葉春明.應用新型螢火蟲算法求解Job-shop調度問題［J］.計算機過程與應用，2013，49（11）：213-216.

［14］包曉曉，葉春明.改進的螢火蟲算法求解具有學習退化效應的JSP問題［J］.數學理論與應用，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è)車間調度算法［J］.計算機工程與應用，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，Fushun 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稿件編號：201602004

國家自然科學基金青年基金項目（61203021）

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