改進(jìn)的細(xì)菌覓食算法求解多目標(biāo)FJSP問(wèn)題

金 花 寧 濤 劉 芳

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

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

筆者在分析FJSP的特點(diǎn)并總結(jié)已有文獻(xiàn)方法優(yōu)勢(shì)和不足的基礎(chǔ)上，提出利用模擬細(xì)菌覓食行為的改進(jìn)細(xì)菌覓食算法(Improved Bacteria Foraging Optimization Algorithm,IBFOA)來(lái)求解FJSP[7]。

1.1 問(wèn)題描述

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

1.2 目標(biāo)函數(shù)

生產(chǎn)企業(yè)實(shí)現(xiàn)效益的首要目標(biāo)是及時(shí)、高效地完成生產(chǎn)任務(wù)，因此FJSP首要的調(diào)度目標(biāo)是最小化最大完工時(shí)間和最小化總成本。筆者設(shè)計(jì)了最小化工件的最大完工時(shí)間和最小化總成本目標(biāo)模型，并建立目標(biāo)函數(shù)，其中最小化最大完工時(shí)間模型如下：

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

(1)

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

最小化總成本模型如下：

(2)

Pijm=μijm+νijm

(3)

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

1.3 約束條件

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

(4)

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

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

2 改進(jìn)的細(xì)菌覓食算法

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

a. 初始化操作。對(duì)細(xì)菌個(gè)體的位置Po、種群規(guī)模SP、趨化次數(shù)Nc、繁殖次數(shù)Nr和驅(qū)散次數(shù)Nd進(jìn)行確定。

c. 復(fù)制操作。復(fù)制操作中引入繁殖閾和死亡閾兩個(gè)概念。繁殖閾指如果細(xì)菌個(gè)體在游動(dòng)過(guò)程中因?yàn)橐恢蔽諣I(yíng)養(yǎng)而發(fā)展到可繁殖的程度則達(dá)到繁殖閾；死亡閾指若細(xì)菌個(gè)體在游動(dòng)過(guò)程中因?yàn)闆](méi)有吸收到足夠的營(yíng)養(yǎng)難以繼續(xù)存活而被淘汰則達(dá)到死亡閾。計(jì)算細(xì)菌個(gè)體吸收的營(yíng)養(yǎng)物質(zhì)，分裂復(fù)制達(dá)到繁殖閾的優(yōu)秀個(gè)體，淘汰低于死亡閾的劣質(zhì)個(gè)體，如果細(xì)菌復(fù)制達(dá)到規(guī)定次數(shù)則轉(zhuǎn)到驅(qū)散操作，否則轉(zhuǎn)到趨化操作。

d. 驅(qū)散操作。如果菌落達(dá)到規(guī)定的驅(qū)散次數(shù)，則算法結(jié)束；否則，菌落將被驅(qū)散到任意方向，并轉(zhuǎn)到步驟b重新進(jìn)行趨化和復(fù)制操作。

3 數(shù)據(jù)分析與驗(yàn)證

3.1 算法性能實(shí)驗(yàn)與分析

為了驗(yàn)證所提出算法的有效性，筆者對(duì)包含10個(gè)算例的Brandimarte測(cè)試集進(jìn)行測(cè)試[12]。針對(duì)10個(gè)算例分別運(yùn)行IBFOA和其他算法的結(jié)果對(duì)比見(jiàn)表1，Tx表示最大完工時(shí)間，Cx表示加工成本；HVNSA表示基于變鄰域的遺傳禁忌搜索算法[13]；MADSA表示Seyed H A R等提出的兩類(lèi)多目標(biāo)資源受限項(xiàng)目調(diào)度和多Agent分布式車(chē)間動(dòng)態(tài)調(diào)度方法[14]。

表1 Brandimarte算例結(jié)果對(duì)比

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

3.2 實(shí)例驗(yàn)證

以某化工設(shè)備加工車(chē)間的實(shí)際生產(chǎn)為例，進(jìn)一步驗(yàn)證IBFOA解決多目標(biāo)FJSP的性能。設(shè)備包括6個(gè)作業(yè)單位、8個(gè)裝配工件和20道工序，作業(yè)單位包含1臺(tái)機(jī)器設(shè)備，交貨期單位為分鐘。訂單包括助力軸30件，要求30件的熱處理同批進(jìn)行，交貨期為35 000min。設(shè)置迭代次數(shù)為200次，分別使用CPA[15]、MADSA和IBFOA對(duì)問(wèn)題進(jìn)行求解的調(diào)度結(jié)果見(jiàn)表2?？梢钥闯觯總€(gè)算法在設(shè)定的迭代周期內(nèi)都可以得到少于交貨期的解，其中IBFOA的最大完工時(shí)間為22 387min，相對(duì)于CPA，生產(chǎn)成本節(jié)約了5%。不同算法調(diào)度結(jié)果的比較如圖1所示。

表2 不同算法的調(diào)度結(jié)果

圖1 不同算法調(diào)度結(jié)果比較

4 結(jié)束語(yǔ)

筆者根據(jù)約束條件不同，建立了多目標(biāo)FJSP的數(shù)學(xué)模型，在基于調(diào)整趨化步長(zhǎng)的基礎(chǔ)上，提出了包括趨化、復(fù)制和驅(qū)散操作的改進(jìn)細(xì)菌覓食算法。并以Brandimarte算例和某設(shè)備加工車(chē)間工件工序調(diào)度為例，對(duì)IBFOA、CPA和MADSA進(jìn)行比較，結(jié)果表明：IBFOA獲得了最小化最大完工時(shí)間和最小化總成本的目標(biāo)，這也驗(yàn)證了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ī)制小生境技術(shù)改進(jìn)禁忌搜索算法[J].化工自動(dòng)化及儀表,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] 劉曉冰,焦璇,寧濤,等.基于雙鏈量子遺傳算法的柔性作業(yè)車(chē)間調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng),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] 張靜,王萬(wàn)良,徐新黎,等.混合粒子群算法求解多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].控制理論與應(yīng)用,2012,29(6):715～722.

[9] 施進(jìn)發(fā),焦合軍,陳濤.交貨期懲罰下柔性車(chē)間調(diào)度多目標(biāo)Pareto優(yōu)化研究[J].機(jī)械工程學(xué)報(bào),2012,48(12):184～192.

[10] 劉芹.差分進(jìn)化細(xì)菌覓食算法求解公交車(chē)調(diào)度問(wèn)題[J].交通運(yùn)輸系統(tǒng)工程與信息,2012,12(2):156～161.

[11] 崔靜靜,孫延明,車(chē)蘭秀.改進(jìn)細(xì)菌覓食算法求解車(chē)間作業(yè)調(diào)度問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究,2011,28(9):3324～3326.

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

[13] 張利平.作業(yè)車(chē)間預(yù)反應(yīng)式動(dòng)態(tài)調(diào)度理論與方法研究[D].武漢:華中科技大學(xué),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] 劉愛(ài)軍,楊育,邢青松,等.多目標(biāo)模糊柔性車(chē)間調(diào)度中的多種群遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(9):1954～1961.