盧冰原,程八一

(1.南京工程學(xué)院 經(jīng)濟管理學(xué)院,江蘇 南京,211167;2.中國科學(xué)技術(shù)大學(xué) 管理學(xué)院,安徽 合肥 230026)

●實務(wù)·方法

基于混合蟻群算法的企業(yè)車間作業(yè)計劃問題研究

盧冰原1,程八一2

(1.南京工程學(xué)院 經(jīng)濟管理學(xué)院,江蘇 南京,211167;2.中國科學(xué)技術(shù)大學(xué) 管理學(xué)院,安徽 合肥 230026)

文章研究了以最小化制造跨度為目標的,具有模糊加工時間的車間作業(yè)計劃問題。針對該問題,采用三角模糊數(shù)來表征時間參數(shù),并在此基礎(chǔ)上構(gòu)建問題目標函數(shù)。之后給出了一種混合蟻群求解算法,將模擬退火算法的全局優(yōu)化特性嵌入蟻群算法來避免局部最優(yōu)的問題。最后通過實例驗證了算法的有效性。

車間作業(yè)計劃;蟻群算法;模擬退火算法;組合優(yōu)化

一、引 言

車間作業(yè)計劃 (Job-Shop Scheduling,JSS)問題是離散型制造企業(yè)生產(chǎn)調(diào)度問題的一種簡化模型,屬于典型的NP-hard問題,至今仍然是研究的熱點。目前針對 JSS問題的研究大多集中在理想的確定性環(huán)境下,相關(guān)參數(shù)為確定值。然而現(xiàn)實生產(chǎn)過程中,存在機器因素、人力因素和系統(tǒng)因素的影響,致使包括時間參數(shù)和約束條件在內(nèi)的相關(guān)信息存在著模糊性。

在古典 JSS問題的求解算法研究方面,基于知識的方法和算法技術(shù)相結(jié)合的趨勢越來越明顯,如遺傳算法、禁忌搜索、進化規(guī)劃、神經(jīng)網(wǎng)絡(luò)方法、蟻群算法 (Ant Colony Optimization,ACO)、模擬退火算法 (S imulated Annealing,SA)等[1-2]。1994年,Colorni[3]等人首先將 ACO應(yīng)用于 JSS問題,但結(jié)果較差。Blum和 Samples[4]對 ACO進行了改進并進一步應(yīng)用在開放式車間調(diào)度問題中,改善了近似解的質(zhì)量。為進一步提高ACO的性能,一些學(xué)者將 ACO和其他算法混合利用,取得了較好的效果,Heinonen[5]等采用了局部搜索技術(shù)對 ACO方法獲得的解進行改進,Kuo-Ling Huang[6]等使用了變換瓶頸機器的方法,并結(jié)合禁忌搜索,來提高 ACO的搜索效率。

本文將 JSS問題擴展到接近現(xiàn)實的模糊環(huán)境中,用三角模糊數(shù) (Trigangular Fuzzy Number,TFN)來表征時間參數(shù)。同時針對 JSS問題,將蟻群算法和模擬退火算法結(jié)合起來,給出了一種混合蟻群求解算法 SA-ACO,通過 ACO完成路徑的搜索,在迭代過程中不斷產(chǎn)生新的可行解,采用 SA在迭代過程中,控制搜索范圍,避免搜索過程陷入局部最優(yōu)。該算法的有效性已經(jīng)得到實例驗證。

二、企業(yè)車間作業(yè)計劃問題模型

在一個規(guī)模為 m×n的 JSS問題中,包括待加工的作業(yè)集合 J={J1,J2,…,Jn}和機器集合M= {M1,M2,…,Mm}。各作業(yè)的工藝路線和作業(yè)每道工序的加工時間已知,每道工序都必須在指定的機器上加工,且必須在前一道工序完成后才能開始加工,一臺機器最多同時處理一個作業(yè)。要求確定各機器上所有作業(yè)的加工次序,使得某些加工性能指標達到最優(yōu)。

為了直觀描述 JSS問題,同時和 ACO的實現(xiàn)過程相匹配,本文中采用圖模型[2]來表示。在 JSS的圖模型中,G=(V,C∪D);V= (O∪σ0,σN+1)。其中,C為有向弧集合,對應(yīng)同一作業(yè)上的不同工序,弧的方向表示工序的先后關(guān)系;D是無向弧集合,由無向弧連接的結(jié)點對應(yīng)在同一機器上加工的工序;G中每一條弧的權(quán)值為其所對應(yīng)起點工序的加工時間,兩邊分別加上不占加工時間的起始頂點σ0和終止頂點σN+1。每個作業(yè)包含若干道工序,表示作業(yè) j在機器Mi上加工的工序;O表示所有集合;N表示集合 O中工序的總數(shù);σi表示在一個可行解π中,位于人工蟻搜索路徑上的第 i個工序 (0≤i≤N+1)。

要獲得JSS問題的可行解,便需要確定各無向弧的方向,即每臺機器上工序的先后關(guān)系。制造跨度 (makespan)是JSS問題中最常用的性能指標,而對于一個可行解π=(σ0,σ1,σ2,…,σN+1),制造跨度 f(π)就是從源點 σ0到終點σN+1的最長路徑。

例如圖 1中,G所代表的 JSS問題,|J|=3,|M|=3,N=8,有向弧用實線表示,無向弧為虛線。由圖 1可知,作業(yè) 1包含兩個工序,分別在 M1、M2上加工,對應(yīng)為、在機器M3上加工的工序共有、兩個。表示工序的開始時間、加工時間和結(jié)束時間。Sijk、Tijk和Cijk同樣用 TFN三元組表示,可通過 TFN函數(shù)進行計算。對應(yīng)三元組中三個參數(shù),有{1,…,3}。

圖1 一個 3×3JSS的圖模型

對于三角模糊數(shù) T=(to,tm,tp),用 Vω(T)、VL(T)和 VR(T)分別表示 T的全積分和左、右積分值。VL(T)代表 T的樂觀狀態(tài),VR(T)代表 T的最壞可能,則 T的全積分 Vω(T)可定義為 VL(T)和 VR(T)的加權(quán)和[7-8],即 Vω(T)=ωVL(T)+(1-ω)VR(T),ω是樂觀系數(shù),ω∈[0,1]。μ(t)為 T的隸屬函數(shù)。

三、SA-ACO混合算法

ACO是一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法,它充分利用蟻群行為中所體現(xiàn)的正反饋機制進行求解,同時利用分布并行計算方式在全局的多點進行解的搜索,但存在著容易陷入局部最優(yōu)的問題。SA在局部搜索技術(shù)的基礎(chǔ)上,增加了概率控制,很好地避免了局部搜索方法容易進入局部優(yōu)化的情形。在 SA-ACO執(zhí)行中,對于 ACO每次迭代得到的結(jié)果,通過 SA從中選擇優(yōu)秀解,然后對這些優(yōu)秀解的路徑進行激勵。隨著迭代次數(shù)增加,模擬退火的溫度降低,狀態(tài)逐漸趨于穩(wěn)定,每次迭代所接受的優(yōu)秀解減少,算法執(zhí)行趨于收斂,在達到終止條件時,搜索過程結(jié)束。

(一 )初始化

在 SA中,相關(guān)參數(shù)有:初始溫度 T0,T的衰減系數(shù) B;ACO的參數(shù)設(shè)置主要包括:控制參數(shù)α、β,最大迭代數(shù) Im,人工蟻數(shù)量m0。在執(zhí)行搜索過程之前,人工蟻的位置均在初始結(jié)點σ0處。

(二)信息素更新

工序加工時間用 TFN表示,制造跨度 f(π)也是 TFN,表示為 Cmax=(maxjmaxi(Cij)),Cij=Sij+Tij。 Sij、Tij和 Cij分別

在搜索過程中,人工蟻從當前結(jié)點σi移動至后續(xù)結(jié)點σj(0≤i,j≤N+1),σj的選擇依據(jù)下屬的偽隨機比例狀態(tài)遷移規(guī)則:

其中,q∈(0,1),為隨機數(shù);q0∈(0,1)為預(yù)設(shè)的數(shù);α、β表示人工蟻對路徑的選擇權(quán)重,α表示人工蟻對經(jīng)驗的利用,β表示獨立探索 ;τ(σi,σ)為弧 (σi,σ)上信息素濃度 ;η(σ)為(σi,σ)上的啟發(fā)式信息值;J(σi)為結(jié)點σi處的可行路徑集合,其約束包括作業(yè)約束和機器加工約束。除按 (1)選擇路徑之外,人工蟻以概率 (1-q0)進行有偏向的搜索,s為選擇的隨機結(jié)點,人工蟻選擇路徑 (σi,s)的概率為:

人工蟻在搜索的過程中,路徑上的信息素發(fā)生局部更新,更新規(guī)則為:

在 (3)式中,傳統(tǒng) ACO將ρ設(shè)置為常數(shù),這樣對τ(σi,σj)無法進行動態(tài)約束,容易導(dǎo)致算法的過早停滯,降低了搜索空間。本文中采用動態(tài)ρ值的設(shè)置:ρ=kτ(σi,σj)(k≥0,為常數(shù))。在所有人工蟻到達σN+1之后,首先更新全局最優(yōu)解π＊,其制造跨度為 f(π＊),然后對信息素進行全局更新:

上述的信息素更新結(jié)束后,調(diào)整模擬退火的溫度:T=BT。在迭代過程的前期,得到優(yōu)化的路徑較多,解決了非優(yōu)秀解路徑上信息素過多累積的問題,在算法執(zhí)行的后期,Metropolis準則的約束增強,除了當前最優(yōu)解π＊,其它得到激勵的路徑明顯減少,強化了算法向全局最優(yōu)解集中的趨勢。

(三)搜索終止規(guī)則

若迭代次數(shù)滿足 I=Im,算法的迭代過程結(jié)束。得到的π＊為最終解。然后根據(jù)π＊確定各機器上的加工順序,從而求出制造跨度 f(π＊)。

四、案例分析

以圖 1中的 JSS問題為例,在 ACO的參數(shù)體系中,本文采用 m0=100,α=β=10,q0=0.8,并對模擬退火的參數(shù)進行調(diào)節(jié),隨著問題規(guī)模增大,迭代次數(shù)增多,模擬退火的初始溫度T0也相對較高,衰減系數(shù) B較大。若各工序加工時間如表 1所示,則各機器上的加工序列為;制造跨度 f(π＊)=(13.5,15,17.3), Vω(f(π))=14.8,ω =0.7。當 T0=20;B=0.90時 ,達到最優(yōu)解的平均迭代次數(shù)為 52.2。

SA-ACO算法在解決上述規(guī)模較小的問題時,能得到最優(yōu)解。針對對于較大規(guī)模的問題,本文選擇 JSP的部分基準問題算例 9,將其中的加工時間 t由確定值調(diào)整為三角模糊數(shù)(δ＊ t,t,φ＊ t),令δ=0.9,φ=1.15。然后將結(jié)果與傳統(tǒng) ACO方法 10進行對比,為對比方便,表中數(shù)據(jù)均為三角模糊數(shù)的中間數(shù)。實驗中采用和傳統(tǒng) ACO方法相同的參數(shù)體系:q0= 0.8,m0=100,Im=200,運行結(jié)果的對比數(shù)據(jù)見表 2。表中數(shù)據(jù)說明,在解決大規(guī)模的 JSS問題時,隨著機器數(shù)和作業(yè)數(shù)的增加,SA-ACO在路徑的均衡搜索能力上的優(yōu)勢更為明顯,與最優(yōu)解的偏差更小。

表2 SA-SCO與傳統(tǒng)ACO實驗結(jié)果的比較

五、結(jié) 論

本文對具有模糊加工時間的 JSS問題進行了研究,用三角模糊數(shù)來表征時間參數(shù),并給出了相應(yīng)的目標函數(shù)。在對JSS問題求解方面,本文在 ACO算法的基礎(chǔ)上,結(jié)合 SA跳離局部解空間的特性,給出的 SA-ACO算法有效地克服了 ACO局部最優(yōu)的缺陷,改善了 ACO的收斂性能。實驗表明,相對于傳統(tǒng) ACO,SA-ACO在處理 JSS問題時有明顯的優(yōu)勢。對離散型制造企業(yè)來說,有效的車間作業(yè)計劃是其實現(xiàn)先進制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。該算法有助于構(gòu)造更加高效、魯棒的車間作業(yè)計劃,并可適用于現(xiàn)實的模糊生產(chǎn)環(huán)境,以提高企業(yè)生產(chǎn)運作中的智能決策水平,從而提高企業(yè)競爭能力。

[1]Garey E L,Johnson D S,Sethi R.The complexity if flowshop and job-shop scheduling[J].Mathematical Operation Research,1976,1:117-129.

[2]Blazewicz J,Presch E,SternaM B.Disjunctive graph machine representation of the jobshop scheduling problem [J]. European Journal ofOperational Research,2000,127 (2) :317-331.

[3]Colorni A,Dorigo M,Maniezzo V,et al.Ant system for job shop scheduling[J].Belgian Journal ofOperations Research,1994,34:39–53.

[4]Blum C,SampelsM.An ant colony optimization algorithm for shop scheduling problems[J].Journal ofMathematical Modelling and Algorithms,2004,3:285–308.

[5]Heinonen J,Pettersson F.Hybrid ant colony optimization and visibility studies applied for job shop scheduling problem [J].AppliedMathematics and Computation.In Press.A-vailable,2006,10:18.

[6]Kuo-Ling Huang,Ching-JongLiao.Ant colony optimization combined with taboo search for the job shop scheduling problem[J].Computers&Operations Research.In Press Available,2006,8:22.

[7]Ish iiH,Tada M,Asuda M T.Two scheduling problems with fuzzy due dates[J].Fuzzy Sets and System's,1992, 46(3):339-347.

[8]Feng-Tse Lin.Constructiong a job-shop schedulingmodel based on imprecise data[C].the IEEE international conference on fuzzy system,2003.

[9]JSS.Benchmark Problem [EB/OL].[2004-04-20] ftp://mascmga.Ms.ic.ac.uk/pub/jobshop1 (2). txt.

[10]Boryczka U.Ant Colony System for JSS[J].Lecture Notes in Computer Science,2004,33(5):296-305.

[責(zé)任編輯:余志虎 ]

The Research of Enterprise Job-shop Scheduling Problem Based on Hybrid Ant Colony Optim ization

LU Bing-yuan1,CHENG Ba-yi2
(1.School of Econom ics and M anagem ent,Nanjing Institute of Technology,Nanjing211167,China;2.School of M anagem ent,University of Science and Technology of China,Hefei230026,China)

This paper studies the job-shop scheduling problem which has fuzzy operation time and which aims at min imized makespan.For this problem,it introduces triangle fuzzy number to denote time parameters,on which the aim function is constructed.After that,a hybrid ant colony optimization is proposed to get perfect scheduling scheme,which can prevent premature opt imization by inserting the global opt imization ability of SA into ACO.Moreover,some examples are described to approve its effectiveness.

job-shop scheduling;ant colony optimization;simulated annealing;combinatorial optimization

F273

A

1007—5097(2010)11—0147—03

10.3969/j.issn.1007-5097.2010.11.035

2009—09—04

江蘇省教育廳高校哲學(xué)社會科學(xué)基金項目 (09SJD630036);國家自然科學(xué)基金項目 (70671096)

盧冰原 (1977—),男,安徽阜陽人,副教授,博士,研究方向:商務(wù)智能;

程八一 (1981—),男,安徽安慶人,博士研究生,研究方向:商務(wù)智能。