改進(jìn)人工蜂群算法求解無等待柔性流水車間調(diào)度問題

畢孝儒，楊　柳，張黎黎，賀　拴（四川外國語大學(xué)重慶南方翻譯學(xué)院管理學(xué)院，重慶401120）

改進(jìn)人工蜂群算法求解無等待柔性流水車間調(diào)度問題

畢孝儒，楊柳，張黎黎，賀拴
（四川外國語大學(xué)重慶南方翻譯學(xué)院管理學(xué)院，重慶401120）

為了解決無等待柔性流水車間調(diào)度問題，提出一種改進(jìn)人工蜂群算法。在算法初始階段采用混沌算子初始化種群以增強(qiáng)其多樣性；在蜜源搜索階段運(yùn)用自適應(yīng)全局最優(yōu)蜜源搜索策略以平衡人工蜂群算法的“探索與開發(fā)”能力，避免算法在搜索后期易于陷入局部最優(yōu)。將改進(jìn)算法用于求解無等待柔性流水車間調(diào)度問題，仿真實(shí)驗(yàn)驗(yàn)證改進(jìn)算法的有效性和優(yōu)越性。

人工蜂群算法；無等待柔性車間調(diào)度；混沌算子；搜索能力

四川外國語大學(xué)重慶南方翻譯學(xué)院科研項(xiàng)目（No.ky2014004）

0　引言

柔性流水車間調(diào)度（Flexible Flow Shop Scheduling Problem，F(xiàn)FSP）是傳統(tǒng)流水車間調(diào)度問題的擴(kuò)展，是復(fù)雜的組合優(yōu)化問題。其最大特點(diǎn)是允許加工的工序存在并行機(jī)器。在FFSP中，若工件開始加工后不允許等待，直到該工件加工完畢為止，則稱為無等待柔性流水車間調(diào)度問題（No-wait FFSP，NWFFSP）。在求解該類問題方法上，群體智能優(yōu)化算法是當(dāng)前的研究熱點(diǎn)，其以種群的個體代表問題的可行解，根據(jù)個體適應(yīng)度值，通過群體搜索尋最優(yōu)解。如文獻(xiàn)[1]采用遺傳算法求解無等待柔性流水車間調(diào)度問題，文獻(xiàn)[2]將遺傳算法運(yùn)用于具有時間窗的無等待柔性流水車間調(diào)度問題求解中，文獻(xiàn)[3]針對工件加工無等待特點(diǎn)，設(shè)計(jì)了分階段實(shí)現(xiàn)的無等待算法，并采用粒子群算法對無等待柔性流水車間調(diào)度問題進(jìn)行了求解，文獻(xiàn)[4]提出了一種混合粒子群-NEH算法以求解無等待柔性流水車間調(diào)度問題。

本文針對人工蜂群算法存在易陷入局部最優(yōu)、算法后期熟練速度較慢和搜索精度不高問題，提出一種改進(jìn)人工蜂群算法，并將其用于解決無等待柔性流水車間調(diào)度問題，與其他算法比較，改進(jìn)算法提高了最優(yōu)解的精度和收斂速度。

1　問題描述與模型

NWFFSP可以描述為n個工件{J0，J1，…，Jn-1}連續(xù)在r道工序以相同的順序加工，所有工件的工藝路線相同，r道工序中至少有一道工序存在多臺并行機(jī)器，工件開始加工后不允許等待直至完成加工。設(shè)m為加工機(jī)器總數(shù)，第k道工序的并行機(jī)器數(shù)為qk（k=0，1，…，r-1），0＜qk＜m；Tik為工件Ji（j=0，1，…，n-1）在工序k上的運(yùn)行時間；Sik為工件Ji在工序k上的開始加工時間；Cik為工件Ji在工序k上的完工時間；問題最大化完工時間為Cmax。

2　改進(jìn)人工蜂群算法

2.1標(biāo)準(zhǔn)人工蜂群算法

在ABC算法中，人工蜂群按照分工可分為3種，即采蜜蜂、跟隨蜂和偵查蜂，其中采蜜蜂和跟隨蜂各占蜂群總數(shù)的一半，并且每一個蜜源僅有一個采蜜蜂工作。算法初始化時首先按式隨機(jī)生成NF個初始解xm=（xm1，xm2，…，xmd），并計(jì)算每個蜜源位置的花粉量或者適應(yīng)度值，同時記錄全局最優(yōu)值。其中，xmi為蜜源位置，m=1，2，…，SN，i∈d；Li和Ui分別是蜂群搜索的下界和上界。適應(yīng)度值計(jì)算公式為：

其中f（xm）為蜜源xm目標(biāo)函數(shù)值。之后按照以下步驟搜索最優(yōu)解：（1）采蜜蜂對蜜源進(jìn)行搜索并記憶蜜源的花蜜量，即問題解的質(zhì)量（適應(yīng)度）；（2）跟隨蜂根據(jù)從采蜜蜂處獲得的蜜源信息通過判斷收益率來選擇一個蜜源，而后對記憶的位置進(jìn)行更新；（3）當(dāng)蜜源因蜂蜜開采完而被放棄時，產(chǎn)生偵察蜂并搜索新的蜜源來替代舊蜜源。在算法中，為了根據(jù)蜜源位置xm產(chǎn)生一個新的候選位置vm，采用式

進(jìn)行更新。根據(jù)蜜源的蜂蜜量，跟隨蜂選擇某個蜜源的概率為：

若經(jīng)過“l(fā)imit”次后，蜜源位置沒有更新，則放棄該位置，而該位置采蜜蜂轉(zhuǎn)換為偵查蜂并按照式（1）產(chǎn)生新蜜源。

2.2改進(jìn)人工蜂群算法

（1）混沌算子初始化蜂群

混沌是自然界中廣泛存在的一種非線性現(xiàn)象，利用混沌序列的遍歷性、隨機(jī)性和規(guī)律性特點(diǎn)進(jìn)行種群初始化以增強(qiáng)ABC算法的種群多樣性。本文采用廣泛應(yīng)用的Logistic映射表達(dá)式：

其中，T是預(yù)設(shè)的最大混沌迭代次數(shù)，rt為區(qū)間[0，1]上均勻分布的隨機(jī)數(shù)且r0不包含{0，0.25，0.5，0.75，1}，u是混沌控制參數(shù)，當(dāng)u=4時，系統(tǒng)將處于完全混沌狀態(tài)。利用式產(chǎn)生一組混沌變量rt，并運(yùn)用混沌序列依次將NF個d維食物源向量Fi按照式：

映射到混沌區(qū)間[Li，Ui]內(nèi)，最后計(jì)算出每個食物源對應(yīng)的適應(yīng)度值。

（2）采蜜蜂自適應(yīng)全局搜索方程

對于一個群體智能優(yōu)化算法而言，如何權(quán)衡算法的“探索與開發(fā)”能力決定了算法的優(yōu)化性能。開發(fā)能力是指在某個特定區(qū)域內(nèi)搜索并能夠提煉出較好解的能力，而探索能力是指算法探究搜索空間的不同區(qū)域以便確定一個較好解的能力。ABC算法的蜜源搜索方程因其選擇的隨機(jī)性而具有較強(qiáng)的探索能力。但同時可以發(fā)現(xiàn)，ABC算法的開發(fā)能力較差，因而存在收斂速度慢、搜索精度差的問題。針對這一問題，本文結(jié)合文獻(xiàn)[5]在研究粒子群算法時所提出的自適應(yīng)思想，提出了自適應(yīng)蜜源搜索方程：

3　改進(jìn)人工蜂群算法用于求解NWFFSP

3.1種群編碼和解碼

根據(jù)柔性車間調(diào)度問題的特點(diǎn)，不僅要確定所有工序的加工順序，而且還要為每道工序選擇一臺合適的機(jī)器，因而本文采用基于工序和機(jī)器的兩段編碼方法。該編碼由兩部分組成：前半段是基于工序的編碼，編碼長度與工序數(shù)一致，表示蜜蜂對所有工序的遍歷，每個碼位記錄該工序所屬的工件號i，則工件Ji出現(xiàn)迄今為止出現(xiàn)的次數(shù)j代表了工序Oij。后半段是基于機(jī)器的編碼，該段按照工序順序，在每個碼位記錄加工該工序的設(shè)備在可選設(shè)備集M中的順序編號（并非機(jī)器號）。

表1　可行解編碼示例

表1為一個可行解編碼，其中，E編碼段中的E6=3表示工件J3的第二道工序O32，G編碼段中的G7=1表示工序O32在第二臺設(shè)備M3上加工。在解碼階段，由工序編碼段E可得各個工件的加工序號，由機(jī)器編碼段G可知每個工序的加工設(shè)備編號，在按照時間約束將工序安排在適當(dāng)時間，生成調(diào)度方案。

3.2算法描述

輸入：待調(diào)度的工件、工序和可用設(shè)備集合；采蜜蜂轉(zhuǎn)成偵查蜂的循環(huán)最大次數(shù)limit；

輸出：調(diào)度最優(yōu)解；

（1）初始化參數(shù)種群數(shù)目NF，算法循環(huán)最大次數(shù)NC，n=0，count=0，使用混沌算子公式（6）初始化食物源P={x1，x2，…，xNF}；

（3）重復(fù)步驟（2），如果count=limit且fit（Vgbesti）值未發(fā)生變化，則依據(jù)式（7）尋找新蜜源，count=0；如果n=NC，輸出調(diào)度最優(yōu)解。

4　實(shí)驗(yàn)與分析

為檢驗(yàn)算法有效性，在標(biāo)準(zhǔn)算例集XWdata中選取8×8（8工件8機(jī)器）、10×10（10工件10機(jī)器）、15×10（15工件10機(jī)器）的不同規(guī)模問題仿真實(shí)驗(yàn)。利用本文提出的IABC算法對8×8問題迭代15次得到問題最優(yōu)值14，對10×10問題迭代17次得到問題最優(yōu)值7，其最優(yōu)解的甘特圖如圖1所示。

由表2可知，與其他幾種典型算法，本文提出的IABC算法在迭代次數(shù)和最小完工時間方面均有一定的優(yōu)勢。

5　結(jié)語

為了解決無等待柔性流水車間調(diào)度問題，本文提出了改進(jìn)的人工蜂群算法，在求解過程中引入混沌算子初始化種群；并采用自適應(yīng)全局最優(yōu)蜜源搜索策略以平衡人工蜂群算法的“探索與開發(fā)”能力，通過不同實(shí)例測試證明，本文提出的算法能夠有效求解無等待柔性流水車間調(diào)度問題。

圖1　　10×10（10工件10機(jī)器）問題最優(yōu)解甘特圖

表2　三種算法實(shí)驗(yàn)對比結(jié)果

[1]李建祥，唐立新等.帶運(yùn)輸和設(shè)置時間的無等待并行流水車間調(diào)度問題研究[J].系統(tǒng)工程理論與實(shí)踐，2006，26（1）:18～25

[2]Jolai F，Sheikh S，Rabbani M，et al.A Genetic Algorithm for Solving No-Wait Flexible Flow Lines with Due Window and Job Rejection[J].International Journal of Advanced Manufacturing Technology，2009，42（5-6）:523～532

[3]Song Jiwei，Tang Jiafu.No-Wait Hybrid Flow Shop Scheduling Method Based on Discrete Particle Swarm Optimization[J].Journal of System Simulation，2010，22（10）:2257～2261

[4]張其亮，陳永生.基于混合粒子群-NEH算法求解無等待流水車間調(diào)度問題[J].系統(tǒng)工程理論與實(shí)踐，2014，34（3）:802～809

[5]吳建輝，章兢，李仁發(fā)等.多子種群微粒群免疫算法及其在函數(shù)優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，2012，49（9）:1883～1898

畢孝儒（1975-），碩士，網(wǎng)絡(luò)工程師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全與集成

楊柳（1982-），講師，研究方向?yàn)閿?shù)據(jù)挖掘

張黎黎（1982-），講師，研究方向?yàn)檐浖碚撆c技術(shù)

賀拴（1982-），助教，研究方向?yàn)閿?shù)據(jù)挖掘

Artificial Bee Colony Algorithm;NWFFSP;Chaotic Mechanism;Searching Ability

Improved Artificial Bee Colony Algorithm for Solving No-wait Flexible Flow Shop Scheduling Problem

BI Xiao-ru，YANG liu，ZHANG Li-li，HE shuan
（School of Management，College of Chongqing South Translation，University of SISU，Chongqing 401120）

To solve NWFFSP,proposes an improved artificial bee colony algorithm.Adopts chaotic mechanism to initialize each individual of the swarm for it's diversity;in the phase of search for nectar source,applies self-adaptive global searching strategy to balance ability of the algorithm for exploring and development for avoiding local optimization of end phase of search.Uses improved artificial bee colony algorithm for solving NWFFSP and proves the validity and superiority of the algorithm by simulation experiment.

1007-1423（2015）14-0014-04

10.3969/j.issn.1007-1423.2015.14.004

2015-03-17

2015-04-27