改進的細菌覓食算法求解多目標FJSP問題

金 花 寧 濤 劉 芳

(大連交通大學軟件學院,遼寧 大連 116045)

多目標FJSP包括機器分配和工序排序兩個子問題。吳俊和方錦明提出基于禁忌算法利用分步策略求解FJSP的兩個子問題[2]。Chaudhry I A在考慮機器負荷平衡性的前提下，提出了一種選擇累加工時較短機器的機器選擇法，雖然這種方法提高了初始種群的質量，但增加了機器選擇的復雜性[3]。劉曉冰等提出了包括機器選擇鏈和工序順序鏈的雙鏈量子編碼方法，但該方法對機器選擇對工序順序的影響考慮較少[4]。Deng G L和Gu X S提出了一種混合的離散差分進化算法求解非空閑置換流水車間調度問題，該算法用一種基于網絡表示的加速方法對工件加工序列的鄰域進行評價[5]。Mokhtari H等為了優化最大完工時間和總成本雙目標，采用混合了可變鄰域搜索和坐標方位搜索的DE算法，但他們對影響算法效率的因素分析不充分[6]。

筆者在分析FJSP的特點并總結已有文獻方法優勢和不足的基礎上，提出利用模擬細菌覓食行為的改進細菌覓食算法(Improved Bacteria Foraging Optimization Algorithm,IBFOA)來求解FJSP[7]。

1.1 問題描述

FJSP的描述如下：車間有N個待加工工件并配有M臺機器，每個工件i(i∈{1,2,…,N})包含ni(ni≥1)道工序，工序要按照指定的加工路線進行；Rij表示工件i的第j(j∈{1,2,…,ni})道工序，Mij(Mij?{1,2,…,M})表示可以加工工件i的第j道工序的機器集合，每道工序Rij可以在M臺機器中有處理能力的任意一臺機器m(m∈{1,2,…,Mij})上加工，機器m可以加工不同工件的多道工序[8,9]。問題包括機器選擇和工序排序兩個子問題。

1.2 目標函數

生產企業實現效益的首要目標是及時、高效地完成生產任務，因此FJSP首要的調度目標是最小化最大完工時間和最小化總成本。筆者設計了最小化工件的最大完工時間和最小化總成本目標模型，并建立目標函數，其中最小化最大完工時間模型如下：

f1=min(F)=min[max(Sijmtijm)]

(1)

其中，F為機器的完工時間，是衡量機器工作負荷的重要指標；tijm表示工序Rij在機器m上的加工時間；Sijm表示工件i的第j道工序在機器m上的加工狀況(1表示加工，0表示未加工)。

最小化總成本模型如下：

(2)

Pijm=μijm+νijm

(3)

其中，P表示工件i的加工總成本；pi表示工件i的原材料成本；Pijm表示工序Rij在機器m上的加工成本；μijm表示工序Rij在機器m上的加工人工成本；νijm表示工序Rij在機器m上的加工機器成本。

1.3 約束條件

生產要求同一工件的工序間應有先后約束，即工件i的第j道工序必須在第(j-1)道工序完成后才可以開始，即：

(4)

其中，Sijm=Si(j-1)m=1；bijm表示工序Rij在機器m上的開始加工時間；bi(j-1)m表示工件i的第(j-1)道工序Ri(j-1)在機器m上的開始加工時間。

同一臺機器在同一時刻只能加工一道工序，即對工序Rij在時刻t(t>0)時,若?Sijm=1，則Sxym=1必不成立(當i=x時j≠y)。

2 改進的細菌覓食算法

基本的細菌覓食優化算法(Bacteria Foraging Optimization Algorithm,BFOA)[10]是一種基于全局隨機搜索的算法，其主要操作包括趨化、復制和驅散；而趨化操作是BFOA的核心，其包括翻轉和游動。但一般BFOA中應用的是定步長策略對問題進行求解，這限制了算法的收斂[11]。因此筆者提出了基于擁擠距離的自適應變步長調整策略IBFOA。改進算法的步驟描述如下：

a. 初始化操作。對細菌個體的位置Po、種群規模SP、趨化次數Nc、繁殖次數Nr和驅散次數Nd進行確定。

c. 復制操作。復制操作中引入繁殖閾和死亡閾兩個概念。繁殖閾指如果細菌個體在游動過程中因為一直吸收營養而發展到可繁殖的程度則達到繁殖閾；死亡閾指若細菌個體在游動過程中因為沒有吸收到足夠的營養難以繼續存活而被淘汰則達到死亡閾。計算細菌個體吸收的營養物質，分裂復制達到繁殖閾的優秀個體，淘汰低于死亡閾的劣質個體，如果細菌復制達到規定次數則轉到驅散操作，否則轉到趨化操作。

d. 驅散操作。如果菌落達到規定的驅散次數，則算法結束；否則，菌落將被驅散到任意方向，并轉到步驟b重新進行趨化和復制操作。

3 數據分析與驗證

3.1 算法性能實驗與分析

為了驗證所提出算法的有效性，筆者對包含10個算例的Brandimarte測試集進行測試[12]。針對10個算例分別運行IBFOA和其他算法的結果對比見表1，Tx表示最大完工時間，Cx表示加工成本；HVNSA表示基于變鄰域的遺傳禁忌搜索算法[13]；MADSA表示Seyed H A R等提出的兩類多目標資源受限項目調度和多Agent分布式車間動態調度方法[14]。

表1 Brandimarte算例結果對比

由對比結果可知，使用IBFOA，對Tx有5次獲得最優解；除了Mk04算例外，其余9個算例用筆者提出的算法求得的解都優于或等同于其他兩個算法求得的解；除Mk04外，IBFOA計算的Cx值均不大于其他算法的值。因此，用IBFOA求解問題優于其他兩種算法。

3.2 實例驗證

以某化工設備加工車間的實際生產為例，進一步驗證IBFOA解決多目標FJSP的性能。設備包括6個作業單位、8個裝配工件和20道工序，作業單位包含1臺機器設備，交貨期單位為分鐘。訂單包括助力軸30件，要求30件的熱處理同批進行，交貨期為35 000min。設置迭代次數為200次，分別使用CPA[15]、MADSA和IBFOA對問題進行求解的調度結果見表2。可以看出，每個算法在設定的迭代周期內都可以得到少于交貨期的解，其中IBFOA的最大完工時間為22 387min，相對于CPA，生產成本節約了5%。不同算法調度結果的比較如圖1所示。

表2 不同算法的調度結果

圖1 不同算法調度結果比較

4 結束語

筆者根據約束條件不同，建立了多目標FJSP的數學模型，在基于調整趨化步長的基礎上，提出了包括趨化、復制和驅散操作的改進細菌覓食算法。并以Brandimarte算例和某設備加工車間工件工序調度為例，對IBFOA、CPA和MADSA進行比較，結果表明：IBFOA獲得了最小化最大完工時間和最小化總成本的目標，這也驗證了IBFOA解決FJSP的有效性。

[1] Bagheri A,Zandieh M,Mahdavi I,et al.An Artificial Immune Algorithm for the Flexible Job-shop Scheduling Problem[J].Future Generation Computer Systems,2010,26(4):533～541.

[2] 吳俊,方錦明.采用排擠機制小生境技術改進禁忌搜索算法[J].化工自動化及儀表,2010,37(8):34～36.

[3] Chaudhry I A.Job Shop Scheduling Problem with Alternative Machines Using Genetic Algorithms[J].Journal of Central South University,2012,(19):1322～1333.

[4] 劉曉冰,焦璇,寧濤,等.基于雙鏈量子遺傳算法的柔性作業車間調度[J].計算機集成制造系統,2014,20(9):1～11.

[5] Deng G L,Gu X S.A Hybrid Discrete Differential Evolution Algorithm for the No-idle Permutation Flow Shop Scheduling Problem with Makespan Criterion[J].Computers & Operations Research,2012,39(9):2152～2160.

[6] Mokhtari H,Abadi I N K,Cheraghalikhani A.A Multi-objective Flow Shop Scheduling with Resource-dependent Processing Times:Trade-off between Makespan and Cost of Resources[J].International Journal of Production Research,2011,49(19):5851～5875.

[7] Shiv P,Deo P V.A Hybrid GABFO Scheduling for Optimal Makespan in Computational Grid[J].International Journal of Applied Evolutionary Computation,2014,5(3):57～83.

[8] 張靜,王萬良,徐新黎,等.混合粒子群算法求解多目標柔性作業車間調度問題[J].控制理論與應用,2012,29(6):715～722.

[9] 施進發,焦合軍,陳濤.交貨期懲罰下柔性車間調度多目標Pareto優化研究[J].機械工程學報,2012,48(12):184～192.

[10] 劉芹.差分進化細菌覓食算法求解公交車調度問題[J].交通運輸系統工程與信息,2012,12(2):156～161.

[11] 崔靜靜,孫延明,車蘭秀.改進細菌覓食算法求解車間作業調度問題[J].計算機應用研究,2011,28(9):3324～3326.

[12] Brandimarte P.Decision Making under Risk[M].New York:John Wiley & Sons Inc,2011.

[13] 張利平.作業車間預反應式動態調度理論與方法研究[D].武漢:華中科技大學,2013.

[14] Seyed H A R,Zandieh M,Yazdani M.Developing Two Multi-objective Evolutionary Algorithms for the Multi-objective Flexible Job Shop Scheduling Problem[J].The International Journal of Advanced Manufacturing Technology,2013,64(5-8):915～932.

[15] 劉愛軍,楊育,邢青松,等.多目標模糊柔性車間調度中的多種群遺傳算法[J].計算機集成制造系統,2011,17(9):1954～1961.