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

盧冰原,程八一

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

●實務·方法

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

盧冰原1,程八一2

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

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

車間作業計劃;蟻群算法;模擬退火算法;組合優化

一、引 言

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

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

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

二、企業車間作業計劃問題模型

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

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

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

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

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

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

三、SA-ACO混合算法

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

(一 )初始化

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

(二)信息素更新

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

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

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

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

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

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

(三)搜索終止規則

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

四、案例分析

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

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

表2 SA-SCO與傳統ACO實驗結果的比較

五、結 論

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

[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.

[責任編輯:余志虎 ]

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

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

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

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