上海理工大學(xué) 管理學(xué)院，上海 200093

上海理工大學(xué) 管理學(xué)院，上海 200093

1 引言

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

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

2 車間作業(yè)調(diào)度問題JSP描述及數(shù)學(xué)模型

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

該問題的數(shù)學(xué)模型可表示為：

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

3 螢火蟲算法應(yīng)用于JSP問題

3.1 螢火蟲算法的仿生原理

螢火蟲算法是受自然界中螢火蟲成蟲發(fā)光的生物學(xué)特性啟發(fā)發(fā)展而來的，一般認為，螢火蟲成蟲發(fā)光的生物學(xué)意義是利用熒光來尋找配偶、吸引潛在獵物并保護它們免受捕食者的侵害。螢火蟲算法是在舍棄部分發(fā)光的生物學(xué)意義，只利用成蟲發(fā)光特性來根據(jù)其搜索區(qū)域?qū)ふ一锇椋⑾蝾I(lǐng)域結(jié)構(gòu)內(nèi)熒光強度更亮的更具有吸引力的螢火蟲移動，從而實現(xiàn)位置優(yōu)化。該算法是基于群體搜索的一類隨機優(yōu)化算法。

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

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

3.2 螢火蟲算法的數(shù)學(xué)描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 FA算法流程圖

4 仿真實驗與結(jié)果分析

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

表1 測試實例相關(guān)數(shù)據(jù)

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

表2 GA、PSO和FA算法比較結(jié)果

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

圖2 FA對FT06的尋優(yōu)曲線

圖3 FA對LA05的尋優(yōu)曲線

圖4 FA對LA06的尋優(yōu)曲線

5 結(jié)束語

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

圖5 FA對LA10的尋優(yōu)曲線

[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]劉勝輝，王麗紅.求解車間作業(yè)調(diào)度問題的混合遺傳算法[J].計算機工程與應(yīng)用，2008，44（29）：73-75.

[3]王書峰，鄒益仁.車間作業(yè)調(diào)度技術(shù)問題簡明綜述[J].系統(tǒng)工程理論與實踐，2003（1）：49-55.

[4]王秀利，吳錫華，劉磊.一種求解單機成組作業(yè)優(yōu)化調(diào)度的啟發(fā)式算法[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.

應(yīng)用新型螢火蟲算法求解Job-shop調(diào)度問題

楊 嬌，葉春明

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調(diào)度問題是一類具有很高理論研究和工程應(yīng)用價值的問題。針對該問題提出一種新型螢火蟲求解算法，分析了螢火蟲算法的仿生原理，給出了螢火蟲算法求解JSP問題的求解步驟，并通過典型基準測試實例對算法進行了仿真實驗，并與GA和PSO算法進行了比較，驗證了該算法參數(shù)少，操作簡單，收斂速度快，在生產(chǎn)調(diào)度中有廣泛的應(yīng)用前景。

作業(yè)車間調(diào)度問題；螢火蟲算法；仿生原理

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.

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

楊嬌（1986—），女，碩士研究生，主要研究方向為生產(chǎn)調(diào)度、智能優(yōu)化；葉春明（1964—），男，博士，教授，博導(dǎo)，主要研究方向為生產(chǎn)調(diào)度、智能優(yōu)化。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