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

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

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

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

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

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

四川外國語大學重慶南方翻譯學院科研項目（No.ky2014004）

0　引言

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

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

1　問題描述與模型

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

2　改進人工蜂群算法

2.1標準人工蜂群算法

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

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

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

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

2.2改進人工蜂群算法

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

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

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

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

（2）采蜜蜂自適應全局搜索方程

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

3　改進人工蜂群算法用于求解NWFFSP

3.1種群編碼和解碼

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

表1　可行解編碼示例

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

3.2算法描述

輸入：待調(diào)度的工件、工序和可用設備集合；采蜜蜂轉(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）重復步驟（2），如果count=limit且fit（Vgbesti）值未發(fā)生變化，則依據(jù)式（7）尋找新蜜源，count=0；如果n=NC，輸出調(diào)度最優(yōu)解。

4　實驗與分析

為檢驗算法有效性，在標準算例集XWdata中選取8×8（8工件8機器）、10×10（10工件10機器）、15×10（15工件10機器）的不同規(guī)模問題仿真實驗。利用本文提出的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)度問題，本文提出了改進的人工蜂群算法，在求解過程中引入混沌算子初始化種群；并采用自適應全局最優(yōu)蜜源搜索策略以平衡人工蜂群算法的“探索與開發(fā)”能力，通過不同實例測試證明，本文提出的算法能夠有效求解無等待柔性流水車間調(diào)度問題。

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

表2　三種算法實驗對比結(jié)果

[1]李建祥，唐立新等.帶運輸和設置時間的無等待并行流水車間調(diào)度問題研究[J].系統(tǒng)工程理論與實踐，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)工程理論與實踐，2014，34（3）:802～809

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

畢孝儒（1975-），碩士，網(wǎng)絡工程師，研究方向為計算機網(wǎng)絡安全與集成

楊柳（1982-），講師，研究方向為數(shù)據(jù)挖掘

張黎黎（1982-），講師，研究方向為軟件理論與技術(shù)

賀拴（1982-），助教，研究方向為數(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