朱福珍，朱凌

(揚州職業(yè)大學(xué)，江蘇揚州225009)

作業(yè)調(diào)度主要研究如何合理配置加工過程的各種資源，減少零件的加工準備，從而提高設(shè)備利用率與生產(chǎn)效率，降低生產(chǎn)成本。蟻群算法是人類在長期觀察蟻群覓食活動中總結(jié)出來的仿生優(yōu)化算法?；炝餮b配線是指在一定時間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。它是車間作業(yè)調(diào)度的具體應(yīng)用之一。現(xiàn)以混流裝配線為例，討論蟻群算法在混流裝配線作業(yè)調(diào)度上的應(yīng)用。

1 蟻群算法簡介

本文以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號的汽車消耗零部件的種類大致相同，那么原問題可以簡化為單級流裝配線調(diào)度問題。由此，該問題可描述為[1]式中，i表示車型數(shù)的標號;n表示需要裝配的車型數(shù);m表示裝配線上需要的零部件種類總數(shù);p表示生產(chǎn)調(diào)度中子裝配的標號;αp表示零部件p的理想使用速率;j表示車型調(diào)度結(jié)果(即排序位置)的標號;D表示在一個生產(chǎn)循環(huán)中需要組裝的各種車型的總和;di表示在一個生產(chǎn)循環(huán)中車型i的數(shù)量;bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量;βj－1，p表示在組裝線調(diào)度中前j－1臺車消耗零部件p的數(shù)量和βj－1，p+xjiβip，且β0，p=0。

2 算法的具體應(yīng)用

這里采用如圖1所示的搜索空間定義，列表示排序階段(用j表示)，行表示每個階段可供選擇的車型(用i表示)，圓圈的大小表示選擇概率的大小，蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。這里假設(shè)有3種車型A、B、C排序，每個生產(chǎn)循環(huán)需要A型車3輛、B型車2輛、C型車1輛，則每個循環(huán)共需生產(chǎn)6輛車(D=6)。列表示6個排序階段，行表示有3種車型可以選擇。圖1(a)是搜索的初始狀態(tài)，圓圈由局部搜索值和信息素綜合而成;圖1(b)經(jīng)過若干次迭代之后，搜索空間變化，此時最可能的可行解[2]是B－A－C－A－B－A。

圖1 簡單混流裝配線排序的搜索空間舉例

利用這種表示方法可以降低問題描述的維數(shù)，其問題規(guī)模為O(n，m)，其中n是車型數(shù)，m是排序長度。

2.1 局部搜索(ηij)的計算

計算公式如下

局部搜索ηij采用的是貪婪法。[3]目標追隨法的思路是，每一步均從當(dāng)前可選擇策略中選取，使目標函數(shù)值增加最少的策略，即在確定第n+1臺車輛車型時，如果有多種車型可供選擇，則從中選擇一種車型，使第n+1臺車輛組裝時各零部件使用速率最為均勻。若每步只考慮當(dāng)前的狀態(tài)，而不考慮全局狀態(tài)，這樣得到的結(jié)果常常為局部最優(yōu)解。但是蟻群算法為每個可選擇的車型i計算ηij，最后再結(jié)合信息素的作用對車型做出選擇。

2.2 狀態(tài)轉(zhuǎn)移概率

狀態(tài)轉(zhuǎn)移概率公式如下

2.3 信息素更新規(guī)則

式中，LB表示目標函數(shù)的下限值;Z表示當(dāng)前目標函數(shù)的平均值;Zcutr表示當(dāng)前的目標函數(shù)值。[4]這種動態(tài)標記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟，見圖2。

圖2 線性動態(tài)標注

3 算例分析

算例數(shù)據(jù)來源于揚州亞星客車股份有限公司的生產(chǎn)數(shù)據(jù)，該公司主要生產(chǎn)各種車型的客車，數(shù)據(jù)見表1。

對參數(shù)設(shè)置經(jīng)過多種組合實驗，得到蟻群算法最優(yōu)組合參數(shù)為ρ=0.9，α=0.2，Q=20000，Ncmax=400，n=5目標函數(shù)值為2859.8。排序結(jié)果為C－A－D－E－B－A－D－E－A－C－A－B－E－D－A－C。

表1 各車型的物料單和需求的子裝配數(shù)

用蟻群算法進行反復(fù)實驗，并同時與目標追隨法、遺傳算法和模擬退火算法相比較，結(jié)果見表2。

表2 蟻群算法與其他啟發(fā)式算法的對比

由表2可見，蟻群算法的求解性能優(yōu)于其他啟發(fā)式算法。

4 結(jié)論

本文采用局部搜索、狀態(tài)轉(zhuǎn)移概率、信息素更新規(guī)則分析了蟻群算法在揚州亞星股份有限公司生產(chǎn)的某種車型混流裝配線調(diào)度上的具體應(yīng)用，結(jié)果證明跟其它算法相比，它有較優(yōu)的加工路徑。

［1］GAO Q L，LUO X，YANG S Z．Stigmergic cooperation mechanism for shop floor control system［J］．International Journal of Advanced Manufacturing Technology，2009，25(7):743－753．

［2］王常青，操云甫，戴國忠．用雙向收斂蟻群算法解作業(yè)車間調(diào)度問題［J］．計算機集成制造系統(tǒng)，2009，7(10):820－824．

［3］劉海龍，鄭春，黃小源．Job shop的多機多目標調(diào)度［J］．系統(tǒng)工程理論方法應(yīng)用，2007，5(2):68－72．

［4］周國華．生產(chǎn)作業(yè)調(diào)度的軟計算方法研究［J］．系統(tǒng)仿真學(xué)報，2008，8(2):24－35．