應用新型螢火蟲算法求解Job-shop調度問題

上海理工大學 管理學院，上海 200093

上海理工大學 管理學院，上海 200093

1 引言

生產調度問題是在一定的時間內，進行可用共享資源的分配和生產任務的排序，以滿足某些指定的性能指標[1]，簡單地說，生產調度問題就是按時間分配資源來完成任務的問題。問題的求解目標就是找到一個將一組資源安排到設備上去，以最優某項加工性能指標的方案[2]。車間作業調度問題（Job-shop Scheduling Problem，JSP）是最著名的調度問題之一，已被證明是一個組合優化問題及典型的NP-hard難題[3]，對于此類問題的優化調度研究具很高的理論和實際工程應用價值，同時長時間來也一直是學術界和工程界的研究熱點。

目前，已有各種優化算法廣泛應用于處理JSP調度問題，主要分為精確算法和近似算法兩大類[4]：精確方法主要有分支定界法、數學規劃法、拉格朗日松弛法等，該類算法可求得問題的精確解，但計算量大、耗時長，只適合求解一些小規模調度問題，由于實際調度問題的復雜性，此類算法難以得到真正應用。近似算法是當前車間作業調度中應用最為廣泛的方法，主要有遺傳算法、模擬退火算法、禁忌搜索法等。通常在這些算法的搜索過程中采用隨機步長，對處理大規模的調度問題有很好的效果，但并不能保證得到最優解。螢火蟲算法（Firefly algorithm）是劍橋學者Yang[5]于2005年受自然界中螢火蟲的發光行為啟發而提出來的一種仿生智能群算法，目前，FA算法已應用于處理函數優化問題[6-9]及組合優化問題[10]，但在處理生產調度中的JSP問題國內還沒有相關文獻，本文將該算法應用于求解Job-shop調度問題，并通過實驗仿真對其可行性進行驗證，結果表明該方法的可行性和有效性。

2 車間作業調度問題JSP描述及數學模型

車間作業調度問題（Job-shop Scheduling Problem，JSP）是研究n個工件在m臺機器上進行加工的問題，已知各工件在各機器上的加工時間和加工次序（稱為技術約束條件），JSP的調度目標是在滿足各工序加工順序約束條件下，合理安排每個工件的各工序所需要的機器，同時確定在每臺機器上進行加工的所有工序的先后順序或加工開始或完成時間，使得某項調度指標達到最優。研究該問題時，通常還需要滿足以下基本約束條件：（1）每個工件在機器上的加工次序給定；（2）每一時刻每臺機器只能加工一個工件，每個工件只能被一臺機器加工，且工序一旦開始不能被中斷；（3）整個加工過程中每個工件在同一臺機器上只能加工一次；（4）不考慮工件加工優先權。本文研究的目標是使得所有作業加工完成時間（即Cmax）達最小。

該問題的數學模型可表示為：

其中，式（1）表示目標函數，即Makespan；式（2）表示工藝約束條件決定的各工件的各操作的先后加工順序；式（3）表示加工各工件的設備的先后順序；式（4）表示完工時間變量約束條件；cik和 pik分別為工件i在機器k上的完工時間和加工時間；M為足夠大的正數，aihk和xijk分別為指示系數和指示變量，其含義為：

3 螢火蟲算法應用于JSP問題

3.1 螢火蟲算法的仿生原理

螢火蟲算法是受自然界中螢火蟲成蟲發光的生物學特性啟發發展而來的，一般認為，螢火蟲成蟲發光的生物學意義是利用熒光來尋找配偶、吸引潛在獵物并保護它們免受捕食者的侵害。螢火蟲算法是在舍棄部分發光的生物學意義，只利用成蟲發光特性來根據其搜索區域尋找伙伴，并向領域結構內熒光強度更亮的更具有吸引力的螢火蟲移動，從而實現位置優化。該算法是基于群體搜索的一類隨機優化算法。

為簡化起見，在描述新的螢火蟲算法時，需考慮以下三個理想化條件[9]：（1）所有螢火蟲無性別之分，即性別對吸引力無任何影響。（2）螢火蟲吸引力和它們自身亮度成正比，并隨著它們距離的增加而減弱。最亮的螢火蟲即是最優吸引力的，它會使相鄰螢火蟲向它移動，如果亮度相同，則螢火蟲各自隨機移動。（3）熒光亮度可看作被優化問題的目標函數。亮度取決于螢火蟲自身所在位置的目標值，亮度越高表示所處位置越好。

螢火蟲算法的仿生原理為：用搜索空間中的點模擬自然界中螢火蟲的個體，將搜索和優化過程模擬為螢火蟲個體的吸引和位置移動過程，將所求優化問題的目標函數看作螢火蟲個體所處位置的好壞，將個體的優勝劣汰過程比作搜索和優化過程中用好的可行解替代較差可行解的迭代過程。

3.2 螢火蟲算法的數學描述

在螢火蟲算法中，螢火蟲彼此吸引主要取決于兩個因素：自身亮度和吸引度。自身亮度決定了螢火蟲所處位置的好壞及其移動方向，吸引度決定了螢火蟲移動的距離，通過亮度和吸引度的不斷更新，實現目標優化。螢火蟲算法的數學描述如下[8-9]：

定義1螢火蟲的相對熒光亮度為：

其中，I0為螢火蟲的最大熒光亮度，即自身（r=0）熒光亮度，與目標函數值有關，目標函數值越優則自身亮度越高；γ為光強吸收系數，光強會隨著距離的增加和介質的吸收而減弱，故設置該系數，可設為常數；rij為螢火蟲i與螢火蟲j之間的距離。

定義2螢火蟲之間的吸引度為：

其中，β0為最大吸引度，即光源處（r=0）的吸引度；γ，rij意義同上。

定義3螢火蟲i被吸引向螢火蟲j移動的位置更新公式為：

其中，xi、xj為螢火蟲i和螢火蟲j所處的空間位置；α為步長因子，是[0，1]上的常數；rand為[0，1]上服從均勻分布的隨機因子。

算法實現優化的過程是：先將螢火蟲群體隨機散布在解空間，每一只螢火蟲因為所處位置不同發出的熒光亮度也不同，通過式（6）比較螢火蟲亮度，亮度高的螢火蟲可以吸引亮度低的螢火蟲向自己移動，移動的距離主要取決于由式（7）得到的吸引度的大小。為了加大搜索區域，避免過早陷入局部最優，在位置更新過程中增加了擾動項α×(rand-1/2)，根據式（8）來計算更新后的位置。這樣通過多次移動后，所有個體都將聚集在亮度最高的螢火蟲的位置上，從而實現尋優。

3.3 FA算法流程圖及處理JSP問題具體步驟

螢火蟲算法（FA）求解JSP的具體步驟如下（可參照圖1的FA算法流程圖）：

（1）初始化種群大小。設置螢火蟲數目m，最大吸引度β0，光強吸收系數γ，隨機因子α，最大迭代次數maxT或搜索精度ε。對JSP問題，所有加工工件的工序都采用字符串編碼方法，隨機選擇并排序編碼工序，直到所有的工序都被編碼。一個螢火蟲代表一個獲選解；隨機產生一個螢火蟲種群，編碼中螢火蟲的位置長度等于優化問題中的所有工序數；螢火蟲種群的大小決定候選解的數量或者解空間里的搜索數量。

（2）隨機初始化螢火蟲的位置，計算螢火蟲的目標函數值作為各自最大螢光亮度。對JSP，所優化問題的目標函數即為則為最小化最大完成時間，即min Cmax決定，調度順序的優劣也是由Cmax決定的。

（3）由式（6）（7）計算群體中螢火蟲的相對亮度I和吸引度 β，根據相對亮度決定螢火蟲的移動方向，熒光強度弱的螢火蟲向熒光強的螢火蟲移動。

（4）根據式（8）更新螢火蟲的空間位置，對處在最佳位置的螢火蟲進行隨機擾動。

（5）根據更新后螢火蟲的位置，重新計算螢火蟲的亮度。

（6）當滿足搜索精度或達到最大搜索次數則轉下一步。否則，搜索次數增加，轉（3），進行下一次搜索。

（7）輸出全局極值點（min Cmax）和最優個體值（最優排序）。

圖1 FA算法流程圖

4 仿真實驗與結果分析

為了便于比較并驗證螢火蟲算法（FA）求解JSP的性能，現選用應用廣泛的OR-Library收錄的Job-shop調度問題的國際標準FT和LA兩類算例進行測試（如表1），并與基本遺傳算法（Genetic Algorithm）和標準粒子群算法（Particle Swarm Optimization，PSO）得到的結果進行對比。

表1 測試實例相關數據

實驗仿真環境為：Windows XP操作系統，Celeron?Dual-Core 2.10 GHz T3500 CPU和2 GB內存，采用Matlab R2011b編程實現該算法。參數設置如下：遺傳算法GA-迭代次數M=100，交叉概率Pc=0.8，變異概率Pm=0.2；粒子群算法PSO—粒子數m=30，學習因子c1=0.8，c2=1.2，慣性權重w=0.5，迭代次數maxT=100；螢火蟲算法FA—螢火蟲數目m=100，最大迭代次數maxT=100，光強吸收系數=1.0，隨機因子=0.5。算法均獨立運行10次，測試結果如表2所示。

表2 GA、PSO和FA算法比較結果

從測試結果可以看出，對以上選出的四個測試實例FA算法均能搜索到其已知最優值，說明該算法在處理JSP作業生產調度中的可行性，相比基本的遺傳算法和基本PSO算法，采用FA算法得到優化結果的平均值也較好。比較結果說明FA算法具有較快的收斂速度，較好的全局擇優能力和較高的求解精度。螢火蟲算法對以上實例的尋優曲線分別如圖2～5所示。

圖2 FA對FT06的尋優曲線

圖3 FA對LA05的尋優曲線

圖4 FA對LA06的尋優曲線

5 結束語

本文提出了一種新的仿生智能群算法—螢火蟲算法（FA）用于求解最小化最大完工時間的作業車間調度問題（Job-shop）。通過實驗仿真，驗證了該算法與基本的遺傳算法和PSO算法相比，具有實驗參數少；操作簡單易于實現；收斂速度快；具有本質可行性的特點，且能有效地解決較大規模的Job-shop生產調度問題。鑒于該算法是一種基本的螢火蟲算法優化，已能得到問題的最優解，表明了螢火蟲算法在解決生產調度問題中的可行性和有效性，并有著廣泛的應用前景。

圖5 FA對LA10的尋優曲線

[1]Rodammer F A，White K P.A recent survey of production scheduling[J].IEEE Trans on System，Man and Cybern， 1988，18（6）：841-851.

[2]劉勝輝，王麗紅.求解車間作業調度問題的混合遺傳算法[J].計算機工程與應用，2008，44（29）：73-75.

[3]王書峰，鄒益仁.車間作業調度技術問題簡明綜述[J].系統工程理論與實踐，2003（1）：49-55.

[4]王秀利，吳錫華，劉磊.一種求解單機成組作業優化調度的啟發式算法[J].計算機仿真，2003，20（2）：48-50.

[5]Yang X S.Nature-inspired metaheuristic algorithm[M].[S.l.]：Luniver Press，2008：83-96.

[6]Lukasik S，Zak S.Firefly algorithm forcontinuousconstrained optimization tasks[C]//ICCCI’09，2009，5796：97-106.

[7]Yang X S.Firefly algorithm，stochastic test functions and design optimization[J].Bio-Inspired Computation，2010，2：78-84.

[8]Yang X S，Deb S.Eagle strategy using levy walk and firefly algorithms for stochastic optimization[J].Studies in Computational Intelligence，2010，284：101-111.

[9]Yang X S.Firefly algorithms for multimodal optimization[C]// Lecture Notes in Computer Science，2009，5792：169-178.

[10]Sayadi M K，Ramezanian R，Ghaffari-Nasab N.A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems[J]. InternationalJournalofIndustrialEngineering Computations，2010.

應用新型螢火蟲算法求解Job-shop調度問題

楊 嬌，葉春明

YANG Jiao,YE Chunming

School of Business,University of Shanghai for Science and Technology,Shanghai 200093,China

Job-shop scheduling problem is a problem with high research and engineering application value.The paper presents a new novel algorithm（firefly algorithm）for solving job-shop scheduling problem and analyzes the bionic principle,then lists the solving steps using FA.Compared with GA and PSO,the simulation results for benchmark instances verify that firefly algorithm shows merits of fewer parameters,simple operation and fast convergence.

job-shop scheduling;firefly algorithm;bionics

Job shop調度問題是一類具有很高理論研究和工程應用價值的問題。針對該問題提出一種新型螢火蟲求解算法，分析了螢火蟲算法的仿生原理，給出了螢火蟲算法求解JSP問題的求解步驟，并通過典型基準測試實例對算法進行了仿真實驗，并與GA和PSO算法進行了比較，驗證了該算法參數少，操作簡單，收斂速度快，在生產調度中有廣泛的應用前景。

作業車間調度問題；螢火蟲算法；仿生原理

A

TP301.6

10.3778/j.issn.1002-8331.1205-0303

YANG Jiao,YE Chunming.Novel firefly algorithm for solving Job Shop scheduling problem.Computer Engineering and Applications,2013,49（11）：213-215.

教育部人文社會科學規劃基金項目（No.10YJA630187）；上海市教育委員會科研創新項目（No.12ZS133）；高等學校博士點基金（No.20093120110008）。

楊嬌（1986—），女，碩士研究生，主要研究方向為生產調度、智能優化；葉春明（1964—），男，博士，教授，博導，主要研究方向為生產調度、智能優化。E-mail：runwujiao@yahoo.com.cn

2012-05-28

2012-07-31

1002-8331（2013）11-0213-03

CNKI出版日期：2012-09-07 http://www.cnki.net/kcms/detail/11.2127.TP.20120907.1626.017.html