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

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

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

1 引言

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

目前，已有各種優(yōu)化算法廣泛應(yīng)用于處理JSP調(diào)度問題，主要分為精確算法和近似算法兩大類[4]：精確方法主要有分支定界法、數(shù)學(xué)規(guī)劃法、拉格朗日松弛法等，該類算法可求得問題的精確解，但計(jì)算量大、耗時(shí)長，只適合求解一些小規(guī)模調(diào)度問題，由于實(shí)際調(diào)度問題的復(fù)雜性，此類算法難以得到真正應(yīng)用。近似算法是當(dāng)前車間作業(yè)調(diào)度中應(yīng)用最為廣泛的方法，主要有遺傳算法、模擬退火算法、禁忌搜索法等。通常在這些算法的搜索過程中采用隨機(jī)步長，對處理大規(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)文獻(xiàn)，本文將該算法應(yīng)用于求解Job-shop調(diào)度問題，并通過實(shí)驗(yàn)仿真對其可行性進(jìn)行驗(yàn)證，結(jié)果表明該方法的可行性和有效性。

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

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

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

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

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

3.1 螢火蟲算法的仿生原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 FA算法流程圖

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

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

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

實(shí)驗(yàn)仿真環(huán)境為：Windows XP操作系統(tǒng)，Celeron?Dual-Core 2.10 GHz T3500 CPU和2 GB內(nèi)存，采用Matlab R2011b編程實(shí)現(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，光強(qiáng)吸收系數(shù)=1.0，隨機(jī)因子=0.5。算法均獨(dú)立運(yùn)行10次，測試結(jié)果如表2所示。

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

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

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

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

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

5 結(jié)束語

本文提出了一種新的仿生智能群算法—螢火蟲算法（FA）用于求解最小化最大完工時(shí)間的作業(yè)車間調(diào)度問題（Job-shop）。通過實(shí)驗(yàn)仿真，驗(yàn)證了該算法與基本的遺傳算法和PSO算法相比，具有實(shí)驗(yàn)參數(shù)少；操作簡單易于實(shí)現(xiàn)；收斂速度快；具有本質(zhì)可行性的特點(diǎn)，且能有效地解決較大規(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].計(jì)算機(jī)工程與應(yīng)用，2008，44（29）：73-75.

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

[4]王秀利，吳錫華，劉磊.一種求解單機(jī)成組作業(yè)優(yōu)化調(diào)度的啟發(fā)式算法[J].計(jì)算機(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)用價(jià)值的問題。針對該問題提出一種新型螢火蟲求解算法，分析了螢火蟲算法的仿生原理，給出了螢火蟲算法求解JSP問題的求解步驟，并通過典型基準(zhǔn)測試實(shí)例對算法進(jìn)行了仿真實(shí)驗(yàn)，并與GA和PSO算法進(jìn)行了比較，驗(yàn)證了該算法參數(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.

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

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