求解柔性作業(yè)車間調(diào)度問題的細(xì)菌算法對比及改進(jìn)

吳秀麗， 張志強(qiáng)

(北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083)

0 引言

生產(chǎn)調(diào)度對于提高制造企業(yè)運(yùn)作效率、降低成本具有舉足輕重的作用，該問題也是典型的優(yōu)化難題，吸引了眾多學(xué)者開展研究.近年來，Brukcer等[1]提出了柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem, FJSP).FJSP包含兩個(gè)子問題：路由問題和調(diào)度問題，分別表示工序的機(jī)器分配問題和調(diào)度問題.FJSP將機(jī)器柔性引入傳統(tǒng)job-shop調(diào)度模型，更接近于實(shí)際生產(chǎn)調(diào)度環(huán)境，增加了調(diào)度靈活性，但問題復(fù)雜度也相應(yīng)增加，傳統(tǒng)數(shù)學(xué)方法難以在有限時(shí)間內(nèi)求解，因此眾多學(xué)者采用智能優(yōu)化算法研究該問題[2-3].

細(xì)菌算法作為一個(gè)較為新穎的算法，受到了學(xué)者的廣泛關(guān)注.細(xì)菌算法都是基于細(xì)菌的生物特性來實(shí)現(xiàn)的:其一是基于細(xì)菌覓食過程;其二是基于細(xì)菌進(jìn)化過程.前者由于對細(xì)菌覓食過程的拆解和側(cè)重，衍生出一系列其它算法，如細(xì)菌趨化算法、細(xì)菌群體趨化算法、細(xì)菌群游算法和細(xì)菌覓食算法等；后者發(fā)展出細(xì)菌進(jìn)化算法.

細(xì)菌趨化算法最初由Bremermann等[4]提出，后經(jīng)Müller等[5-6]進(jìn)一步地研究與綜合，提出了細(xì)菌趨化(bacterial chemotaxis, BC)算法.該算法是優(yōu)化領(lǐng)域的一種新的仿生學(xué)進(jìn)化算法，其利用細(xì)菌對環(huán)境中引誘劑的應(yīng)激反應(yīng)行為來進(jìn)行函數(shù)優(yōu)化.國內(nèi)最早研究BC算法的是李威武等[7]，他提出細(xì)菌群體趨藥性算法(bacterial colony chemotaxis, BCC).細(xì)菌覓食優(yōu)化算法(bacterial foraging optimization algorithm, BFO)最初由Passino[8]2002年提出，借鑒了大腸桿菌在覓食過程中的趨化、群聚、繁殖和消除-擴(kuò)散等運(yùn)動特性，設(shè)計(jì)了優(yōu)化算法.在此基礎(chǔ)上，Tang等[9]提出細(xì)菌群游算法(bacterial swarming algorithm, BSA)，Chu等[10]提出快速細(xì)菌群游算法(fast bacterial swarming algorithm, FBSA).Nawa等[11]提出了細(xì)菌進(jìn)化算法(bacterial evolutionary algorithm, BEA).

筆者設(shè)計(jì)了多種算法結(jié)構(gòu)并進(jìn)行對比實(shí)驗(yàn)，以確定算法的不同特性對問題的影響，并將其中性能最佳的細(xì)菌覓食算法作為主要研究對象，在其基礎(chǔ)上進(jìn)行改進(jìn)和集成，以得到一個(gè)尋優(yōu)能力更強(qiáng)的改進(jìn)細(xì)菌覓食算法(IBFO).

1 柔性作業(yè)車間調(diào)度問題建模

1.1 問題描述

FJSP問題可以這樣描述：n個(gè)工件在m臺機(jī)器上加工，每個(gè)工件有多道工序，工序順序是預(yù)先確定的，每道工序可由多臺機(jī)器加工，不同機(jī)器對同一工序的加工時(shí)間并不相同.調(diào)度過程中主要解決兩個(gè)子問題：一是機(jī)器分配問題;二是工件排序問題.調(diào)度目標(biāo)是通過機(jī)器分配和工序排序而優(yōu)化某個(gè)(些)目標(biāo)，如完工時(shí)間為優(yōu)化目標(biāo).

此外，加工過程還要滿足約束條件：①所有機(jī)器在t=0時(shí)刻都可用；②所有工件在t=0時(shí)刻都可被加工；③所有工件的工藝計(jì)劃都是固定不變的；④工序在可用機(jī)器上的加工時(shí)間是確定的；⑤每個(gè)工件在固定時(shí)刻只能在一臺機(jī)器上加工，且一旦開始加工不能中斷；⑥加工是非搶占式的.

1.2 模型建立

建模所用變量如下：

n——工件總數(shù)；

m——機(jī)器總數(shù)；

ni——工件i的工序總數(shù)；

i,h——工件號索引，i,h=1, 2,…,n；

j,g——工序號索引，j,g=1, 2,…,ni；

k——機(jī)器號索引，k=1, 2,…,m；

Oij——工件i的第j道工序；

Oijk——工序Oij選擇在機(jī)器k上加工；

pijk——工序Oij選擇在機(jī)器k上加工所耗費(fèi)的時(shí)間；

Sij——工序Oij的可用機(jī)器集合，Sij?{1,2,…，m}；

Cij——工序Oij的完工時(shí)間；

Cmax——調(diào)度方案的最大完工時(shí)間Makespan；

Xijk——決策變量，若Xijk=1表示工序Oij選擇在機(jī)器k上加工Oijk，否則Xijk=0；

Yhgij——決策變量，若Yhgij=-1表示工序Ohg為Oij相鄰的前一道工序；Yhgij=1表示工序Ohg為Oij相鄰的后一道工序；Yhgij=0表示Ohg和Oij為不相鄰的兩道工序.

通常情況下，高效快速地完成生產(chǎn)任務(wù)是絕大多數(shù)生產(chǎn)企業(yè)追求的第一目標(biāo)，因此設(shè)定優(yōu)化目標(biāo)函數(shù)是最大完工時(shí)間，即

minCmax=min(max(Cij)).

(1)

s.t.

Cij-Ci(j-1)≥pijkXijk,j=2,3,…,ni；

(2)

(3)

∑Xijk=1,k∈Sij,?i,j；

(4)

Xijk∈{0,1}；

(5)

Yhgij∈{-1,0,1}.

(6)

其中，式(1)是目標(biāo)函數(shù)；式(2)是工藝約束；式(3)是機(jī)器約束；式(4)限定一道工序只能在一臺機(jī)器上獨(dú)立完成；式(5)和式(6)限定決策變量的取值范圍.

2 細(xì)菌系列算法性能比較

為了求解FJSP，必須建立該問題模型與算法的映射關(guān)系，采用基于工序的編碼方式[12]來實(shí)現(xiàn)，并依據(jù)活動化調(diào)度方式生成具體的調(diào)度方案.

為了對比細(xì)菌系列算法與其他進(jìn)化算法的性能，對FJSP的標(biāo)準(zhǔn)問題Kacem[13]的5個(gè)標(biāo)準(zhǔn)算例和Brandimarte[3]的10個(gè)標(biāo)準(zhǔn)算例進(jìn)行實(shí)驗(yàn)，并與最新的研究成果進(jìn)行對比分析.平均離差率為一個(gè)衡量算法尋優(yōu)能力的指標(biāo):

(7)

式中：M為平均離差率；n為試驗(yàn)算例數(shù)目；i為試驗(yàn)號；Fi為試驗(yàn)i的試驗(yàn)最優(yōu)值；Fio為試驗(yàn)i的目前最優(yōu)值.

這些算法具有不同的參數(shù)，筆者在保證各算法具有可比性的前提下綜合考慮各個(gè)參數(shù)的經(jīng)驗(yàn)值[4-11]，得到細(xì)菌系列算法的參數(shù)見表1.

表1 細(xì)菌算法的參數(shù)

計(jì)算對比如表2和表3所示.可以看出，對于Kacem算例，各算法達(dá)到最優(yōu)值的成功率均為100%；對于Brandimarte算例，BC、BEA和BSA成功率為40%，BCC為50%，BFO為60%.并且對于Brandimarte算例，各個(gè)算法的離差率均較低，說明各算法性能都較好；BFO的平均離差率最低，說明其性能最好，其次依次為BCC、BSA、BEA、BC.考慮成功率和平均離差率的結(jié)果，5種算法的性能排序?yàn)锽C

表2 Kacem算例計(jì)算結(jié)果

表3 Brandimarte算例計(jì)算結(jié)果

3 細(xì)菌覓食算法改進(jìn)設(shè)計(jì)

由對比實(shí)驗(yàn)可知，細(xì)菌覓食算法性能最優(yōu)，因此在細(xì)菌覓食算法的基礎(chǔ)上，試驗(yàn)多種優(yōu)化算子，以求得到性能更優(yōu)的算法.細(xì)菌覓食算法三大操作中，趨向性操作對算法影響的顯著性最高，其次是驅(qū)散操作，而復(fù)制操作最低.因此，筆者著重進(jìn)行了趨向性操作算子和驅(qū)散操作算子的優(yōu)化試驗(yàn)，通過改變其操作算子的操作方式，試驗(yàn)不同算子的尋優(yōu)能力.

為保證試驗(yàn)的可靠性，遵循單一變量的試驗(yàn)原理，在每改變一個(gè)算子操作方式后均進(jìn)行單獨(dú)試驗(yàn)，其他試驗(yàn)條件不變.試驗(yàn)過程中涉及主要參數(shù)設(shè)置如表4所示.

3.1 驅(qū)散操作改進(jìn)

(1)隨機(jī)驅(qū)散.細(xì)菌覓食算法原始的驅(qū)散方式是以一定概率隨機(jī)產(chǎn)生個(gè)體.

(2)基于工件驅(qū)散.借鑒基于工件的編碼方式，以工件進(jìn)行編碼，解碼過程中優(yōu)先排完一個(gè)工件所有工序才進(jìn)入下一個(gè)工件的排序.

表4 試驗(yàn)參數(shù)設(shè)置

(3)基于最長工件驅(qū)散.優(yōu)先加工總加工時(shí)間最長的工件.由于FJSP存在機(jī)器選擇的問題，無法確切知道每道工序在哪臺機(jī)器上加工以及加工時(shí)間是多少.因此，采用其可用機(jī)器的加工時(shí)間求均值的方式來衡量該工件的平均加工時(shí)間，通過比較每個(gè)工件每道工序平均加工時(shí)間的和，可以找到加工時(shí)間最長的工件，優(yōu)先安排其所有工序.

(4)基于最短工件驅(qū)散.與基于最長工件的驅(qū)散方式原理相同，僅將最長工件換成最短工件.

對4種不同的驅(qū)散方式進(jìn)行試驗(yàn)，試驗(yàn)結(jié)果見表5.由表5可知，基于工件驅(qū)散方式表現(xiàn)最優(yōu).

表5 驅(qū)散試驗(yàn)結(jié)果

3.2 趨向性操作改進(jìn)

BFO的趨向性操作包括群體自身尋優(yōu)和基于最優(yōu)個(gè)體的群體尋優(yōu)兩個(gè)過程，兩個(gè)過程分別體現(xiàn)了細(xì)菌的趨化特性和群聚特性.

3.2.1 最優(yōu)個(gè)體自身尋優(yōu)

個(gè)體表現(xiàn)優(yōu)秀是因?yàn)槠鋵Ω鱾€(gè)工件的排列順序更加合理，而每個(gè)工件的第一道工序又起到?jīng)Q定性作用.因此，最優(yōu)個(gè)體自身尋優(yōu)方式為保留不同工件的第一道工序的相對位置信息，其他工序隨機(jī)重排.

3.2.2 個(gè)體自身尋優(yōu)

①交換變異：隨機(jī)產(chǎn)生兩個(gè)位置，交換位置信息.②移碼變異：隨機(jī)產(chǎn)生一個(gè)位置和一個(gè)距離s，將該位置信息向右移動距離s;如果超過最后一個(gè)位置則轉(zhuǎn)到第一個(gè)位置繼續(xù).③反轉(zhuǎn)變異：隨機(jī)產(chǎn)生兩個(gè)位置，將兩個(gè)位置之間的信息逆序排列.④插入變異：隨機(jī)產(chǎn)生兩個(gè)位置，將第一個(gè)位置的信息插入到第二個(gè)位置之后.⑤位移變異：隨機(jī)產(chǎn)生3個(gè)位置，將前兩個(gè)位置之間的信息插入到第3個(gè)位置之后.

3.2.3 基于最優(yōu)個(gè)體尋優(yōu)

(1)次序交叉：隨機(jī)產(chǎn)生兩個(gè)交叉位置，將最優(yōu)個(gè)體交叉點(diǎn)之間的信息片段復(fù)制給普通個(gè)體a，并剔除普通個(gè)體的交叉點(diǎn)之外與最優(yōu)個(gè)體交叉點(diǎn)之間沖突的信息，得到b；復(fù)制普通個(gè)體交叉點(diǎn)之間的位置信息，得到c；將c中的位置信息從第二交叉位置開始依次填入b中的空缺位置得到最終個(gè)體e.

(2)基于位置的交叉：隨機(jī)產(chǎn)生多個(gè)位置點(diǎn)，將最優(yōu)個(gè)體位置點(diǎn)的信息復(fù)制給普通個(gè)體a，得到b；依次剔除普通個(gè)體a中與最優(yōu)個(gè)體位置點(diǎn)的信息沖突的部分，得到c；將c中的位置信息依次填入b個(gè)體中的空缺位置得到最終個(gè)體e.

(3)基于順序的交叉：隨機(jī)產(chǎn)生一個(gè)二進(jìn)制表，將最優(yōu)個(gè)體與二進(jìn)制表中為1的對應(yīng)位置的位置信息復(fù)制給普通個(gè)體a，得到b；依次剔除普通個(gè)體a中與最優(yōu)個(gè)體位置點(diǎn)的信息沖突的部分，得到c；將c中的位置信息依次填入b中的空缺位置得到最終個(gè)體e.

(4)線性次序交叉：隨機(jī)產(chǎn)生兩個(gè)交叉位置，將最優(yōu)個(gè)體交叉點(diǎn)之間的信息片段復(fù)制給普通個(gè)體a，得到b；依次剔除普通個(gè)體a中與最優(yōu)個(gè)體信息片段沖突的位置部分，得到c；將c中的位置信息依次填入b中的空缺位置得到最終個(gè)體e.

(5)局部調(diào)度交換交叉：在最優(yōu)個(gè)體和普通個(gè)體a中分別隨機(jī)產(chǎn)生兩個(gè)交叉位置(交叉位置間長度可不同)，將最優(yōu)個(gè)體交叉點(diǎn)之間的信息片段填充到普通個(gè)體交叉點(diǎn)之間，保留普通個(gè)體交叉點(diǎn)外位置信息，得到b；在交叉點(diǎn)外，依次剔除(或增補(bǔ))b中與交叉位置信息片段沖突(多或者少位置信息)的位置部分得到c；整理即得到最終個(gè)體e.

(6)優(yōu)先級保存交叉：產(chǎn)生一個(gè)由0和1組成的隨機(jī)序列,0對應(yīng)的位置取最優(yōu)染色體的信息，1對應(yīng)的位置取普通個(gè)體a的信息，每個(gè)位置信息選取的時(shí)候保證取到信息不與之前信息沖突；最后得到最終個(gè)體為b.

(7)優(yōu)先操作交叉：隨機(jī)選擇一個(gè)優(yōu)先操作集合，將最優(yōu)個(gè)體的優(yōu)先操作集合的位置信息復(fù)制給普通個(gè)體a，得到b；剔除普通個(gè)體中該優(yōu)先操作集合，將剩余位置信息依次填入b空缺位置，得到最終個(gè)體c.

3.2.4 改進(jìn)設(shè)計(jì)數(shù)值實(shí)驗(yàn).

(1)是否增加最優(yōu)個(gè)體自身尋優(yōu)試驗(yàn).對增加最優(yōu)個(gè)體尋優(yōu)過程的BFO進(jìn)行10組試驗(yàn)，平均值為148.9,沒有增加該過程的試驗(yàn)值為149.5.經(jīng)過比較可見，增加最優(yōu)個(gè)體自身尋優(yōu)過程，有利于增加算法的尋優(yōu)能力.

(2)個(gè)體自身尋優(yōu)試驗(yàn).對細(xì)菌覓食算法的個(gè)體自身尋優(yōu)過程進(jìn)行10組試驗(yàn)，由表6中第2列可知，個(gè)體自身尋優(yōu)過程中采用反轉(zhuǎn)變異，有利于增加算法的尋優(yōu)能力.

表6 10組群體自身尋優(yōu)試驗(yàn)試驗(yàn)均值Tab.6 Results for 10 tests of the population optimization

(3)最優(yōu)個(gè)體自身尋優(yōu)試驗(yàn).對BFO的最優(yōu)個(gè)體自身尋優(yōu)過程進(jìn)行10組試驗(yàn)，由表6中第3列可知，最優(yōu)個(gè)體自身尋優(yōu)過程中采用交換變異有利于增加算法的尋優(yōu)能力.

(4)基于最優(yōu)個(gè)體的群體尋優(yōu)試驗(yàn).對BFO基于最優(yōu)個(gè)體的群體尋優(yōu)試驗(yàn)過程進(jìn)行10組試驗(yàn)，由表7可知,基于最優(yōu)個(gè)體的群體尋優(yōu)過程中，PBX、LOX及POX有利于增加算法尋優(yōu)能力.

表7 基于最優(yōu)個(gè)體的群體尋優(yōu)試驗(yàn)

綜合考慮趨向性操作改進(jìn)的試驗(yàn)結(jié)果，可以得出結(jié)論：增加最優(yōu)個(gè)體的尋優(yōu)過程，有利于算法尋優(yōu)；在尋優(yōu)初期，適宜進(jìn)行反轉(zhuǎn)變異；待群體染色體達(dá)到一定的優(yōu)秀程度，適宜進(jìn)行交換變異；對于交叉操作，適宜進(jìn)行PBX、LOX和POX.

3.3 算法最佳配置及參數(shù)

根據(jù)以上試驗(yàn)數(shù)據(jù)和BFO的參數(shù)配置，確定IBFO的配置：①基于工件驅(qū)散方式，②增加最優(yōu)個(gè)體自身尋優(yōu)，③普通個(gè)體自身尋優(yōu)方式為反轉(zhuǎn)變異，④最優(yōu)個(gè)體自身尋優(yōu)方式為交換變異，⑤基于最優(yōu)個(gè)體的尋優(yōu)方式為基于位置的交叉，⑥種群規(guī)模為50，趨向性操作次數(shù)Nc為50，復(fù)制操作次數(shù)Nre為5，驅(qū)散(遷徙)操作次數(shù)Ned為20，驅(qū)散(遷徙)概率Ped為0.7.

3.4 數(shù)值實(shí)驗(yàn)

為了對比IBFO與其他進(jìn)化算法的性能，應(yīng)用IBFO對Kacem[13]算例和Brandimarte[3]系列進(jìn)行實(shí)驗(yàn)，結(jié)果見表8和9，可以看出IBFO以90%的成功率找到最優(yōu)解，且平均離差率最低，證明IBFO算法的優(yōu)越性能.因此，6種算法排名為BC

表8 Kacem算例計(jì)算結(jié)果

表9 Brandimarte算例計(jì)算結(jié)果Tab.9 Results for Brandimarte Benchmarks

4 結(jié)論

針對FJSP，建立了優(yōu)化模型，提出了BC、BEA、BSA、BCC和BFO,并進(jìn)行了數(shù)值實(shí)驗(yàn)和分析.結(jié)果表明，5種算法穩(wěn)定性、改進(jìn)空間和尋優(yōu)能力存在一定差異.其中，BFO表現(xiàn)最為優(yōu)異，因此對其進(jìn)行了改進(jìn)，針對其關(guān)鍵操作設(shè)計(jì)了多種優(yōu)化算子，最終得到優(yōu)化能力最強(qiáng)的算法結(jié)構(gòu)和算子組合.數(shù)值實(shí)驗(yàn)表明，改進(jìn)的細(xì)菌覓食算法的尋優(yōu)能力及穩(wěn)定性大幅提升，體現(xiàn)出非常好的全局開發(fā)能力和局部搜索能力，能高效求解FJSP.

參考文獻(xiàn)：

[1] BRUCKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375.

[2] 王書鋒,肖小城,馮冬青.求解Job-shop問題的改進(jìn)混合離散粒子群優(yōu)化算法[J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版), 2010,31(4)：44-47.

[3] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of operations research, 1993, 41(3): 157-183.

[4] BREMERMANN H. Chemotaxis and optimization[J]. Journal of the franklin institute, 1974, 297(5): 397-404.

[5] MüLLER S, AIRAGHI S, MARCHETTO J, et al. Optimization algorithms based on a model of bacterial chemotaxis[C]∥ Proceedings of the 6th International Conference Simulation of Adaptive Behavior: From Animals to Animats. Paris, France: Springer, 2000: 375-384.

[6] MüLLER S D, MARCHETTO J, AIRAGHI S, et al. Optimization based on bacterial chemotaxis[J]. IEEE transactions on evolutionary computation, 2002, 6(1): 16-29.

[7] LI W, WANG H, ZOU Z, et al. Function optimization method based on bacterial colony chemotaxis[J]. Journal of circuits and systems, 2005, 10(1): 58-63.

[8] PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control[J]. Control systems IEEE, 2002, 22(3): 52-67.

[9] TANG W J, WU Q H, SAUNDERS J R. A bacterial swarming algorithm for global optimization[C]∥ 2007 IEEE Congress on Evolutionary Computation (CEC 2007). Singapore: IEEE, 2007: 1207-1212.

[10] CHU Y, MI H, LIAO H, et al. A fast bacterial swarming algorithm for high-dimensional function optimization[C]∥ 2008 IEEE Congress on Evolutionary Computation (CEC 2008). Hong Kong, China: IEEE, 2008: 3135-3140.

[11] NAWA N E, FURUHASHI T. Fuzzy system parameters discovery by bacterial evolutionary algorithm [J]. IEEE transactions on fuzzy systems, 1999, 7(5): 608-616.

[12] 吳秀麗, 孫樹棟, 余建軍, 等. 多目標(biāo)柔性作業(yè)車間調(diào)度優(yōu)化研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2006, 12(5): 731-736.

[13] KACEM I, HAMMADI S, BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems [J]. IEEE transactions on systems, man and cybernetics part C:application & reviews, 2002, 32:408-19.

[14] LI J Q, PAN Q K, GAO K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International journal of advanced manufacturing technology, 2012, 55:1159-1169.