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

面向無等待多目標(biāo)柔性車間調(diào)度問題的遺傳蜂群優(yōu)化算法

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

0　引言

當(dāng)前，無等待柔性車間調(diào)度問題 （No-Waiting Flexible Flow Job-Shop Scheduling Problem，NWFJSP）廣泛存在于塑料塑造、鋼鐵鑄造、化工制造等領(lǐng)域，它不僅需要確定工序的加工順序，還要給每個工序分配機(jī)器，是更為復(fù)雜的NP-hard問題［1］。調(diào)度問題的復(fù)雜性，使得采用一般的數(shù)學(xué)規(guī)劃方法很難求解因而許多學(xué)者運用遺傳算法（Genetic Algorithm，GA）、粒子群算法（Particle Swarm Optimization，PSO）等智能優(yōu)化算法［2-4］求解單目標(biāo)NWFJSP問題，并取得了較好的效果。然而在實際生產(chǎn)中不僅要考慮工件最大完工時間、總拖延時間等調(diào)度性能指標(biāo)，同時還要考慮生產(chǎn)成本等費用指標(biāo)，即對多目標(biāo)函數(shù)同時優(yōu)化。因此求解多目標(biāo)的無等待柔性車間調(diào)度問題更符合實際需求。

人工蜂群算法 （Artificial Bee Colony，ABC）是由Karaboga于2005年提出的一種群集智能優(yōu)化算法。由于ABC算法具有收斂速度快、控制參數(shù)少，魯棒性強(qiáng)等優(yōu)點，一些學(xué)者［5］用其求解柔性車間調(diào)度問題。但該算法存在搜索后期容易陷入局部最優(yōu)，且搜索速度慢的不足。

針對以上不足，本文給出了以關(guān)鍵路徑為導(dǎo)向的變異操作，并將該變異操作和遺傳算子中的IPOX和MPX交叉操作嵌入到人工蜂群算法中，以增強(qiáng)其全局尋優(yōu)能力，提升搜索后期收斂速度，在設(shè)計了多目標(biāo)優(yōu)化模型和適應(yīng)度值分配策略的基礎(chǔ)上，將其用于無等待多目標(biāo)柔性車間調(diào)度問題求解。

1　問題描述

無等待柔性車間調(diào)度問題可以描述為：設(shè)有m臺機(jī)器和n個工件，pi表示工件i包含的工序數(shù)，Oijk表示工件工件i的第j道工序在機(jī)器k上加工，Sijk表示工序開始加工時間，Tijk表示工序的加工時間，每個工件包含一道或多道工序并且每道工序可以在多臺性能不同的機(jī)器上加工，每道工序的加工時間、成本等因機(jī)器性能的不同而變化。調(diào)度目標(biāo)是對所有工序在不同機(jī)器上的加工順序進(jìn)行排列，使總目標(biāo)達(dá)到最優(yōu)。同時加工過程還要滿足以下假設(shè)和約束條件：

（1）在t=0時刻所有工件都可以被加工；

（2）所有工件的工序的先后順序是固定不變的；

（3）同一時刻、同一臺機(jī)器只能加工一道工序；

（4）同一工件工序之間有先后約束，上一工序r。

完成后才能開始下一工序r+1，即Si（r+1）k-Sirk-Tirk≧0。

本文針對無等待柔性車間調(diào)度的需求，給出了以下優(yōu)化目標(biāo)：縮短最大完工時間以增加生產(chǎn)效率、減少總拖延時間以提高客戶滿意度、減低成本以滿足企業(yè)可持續(xù)發(fā)展，其需要優(yōu)化的目標(biāo)函數(shù)如下：

（1）最大完工時間

式中，Ti表示工件在機(jī)器i上的加工時間。

（2）生產(chǎn)成本

式中，Cijk表示工件i第j道工序在機(jī)器k上加工成本。

xijk決策變量，當(dāng)工件Ji的第j道工序在機(jī)器k上加工時，xijk=1，否則為0。

（3）總拖延時間為：

式中，i=1，2，…，M，Ei表示工件i的最大完工時間，Di表示工件i的交貨期。

2　灰互信息關(guān)聯(lián)度適應(yīng)度值分配策略

在多目標(biāo)優(yōu)化問題中，灰色關(guān)聯(lián)度分析根據(jù)各目標(biāo)的函數(shù)值組成數(shù)列的幾何形狀與參考序列接近程度來分析問題發(fā)展的態(tài)勢。在優(yōu)化時先將每個目標(biāo)作為單目標(biāo)分別求得最優(yōu)解，并用這些最優(yōu)解構(gòu)成參考序列，即多目標(biāo)優(yōu)化的理想解。然后將Pareto解的目標(biāo)函數(shù)值序列作為比較序列，利用灰關(guān)聯(lián)度計算這兩個序列的接近程度以分析每個Pareto解與理想解的近似程度，即利用灰關(guān)聯(lián)度評判Pareto解的優(yōu)劣。上述評判方法并未考慮個目標(biāo)因素之間的信息，因而該分析方法的精度不高。本文將熵理論與灰色關(guān)聯(lián)度分析結(jié)合，提出了灰互信息適應(yīng)度值分配策略，其具體步驟如下：

（1）對于N個Pareto解，計算各目標(biāo)函數(shù)值為：

上式中，T為目標(biāo)個數(shù)，fT（0）是第T個子目標(biāo)作為單目標(biāo)函數(shù)求出最優(yōu)解的目標(biāo)函數(shù)值，fi是每個子目標(biāo)最優(yōu)解組合而成的序列；

（2）依據(jù)式（5）對各Pareto解的目標(biāo)函數(shù)值進(jìn)行歸一化處理；

其中，k=1，2，…，T，j=1，2，…，N。

3）依據(jù)式（6）計算各目標(biāo)函數(shù)值之間的互信息量；

其中，P（fk'（i），fk'（j））為fk'（i），fk'（j）的聯(lián)合熵。

（4）依據(jù)式（7）計算Pareto解灰互信息關(guān)聯(lián)度；

其中，ρ∈（0，1）為分辨系數(shù)，一般取值為0.5。

3　遺傳蜂群優(yōu)化算法

3.1基本人工蜂群算法

在求解優(yōu)化問題時，ABC算法將食物源位置抽象成優(yōu)化問題的一個可行解，人工蜂尋找食物源的過程就是搜尋最優(yōu)解的過程。人工蜂群主要包括雇傭蜂、觀察蜂和偵查蜂三種個體。雇傭蜂數(shù)目和食物源數(shù)目相等，雇傭蜂和觀察蜂各占蜂群總數(shù)的一半，食物源的含密量（收益度）對應(yīng)優(yōu)化問題的適應(yīng)度函數(shù)。假設(shè)初始種群含有SN個解，每個解xi（i=1，2，…，SN）是一個d維向量。雇傭蜂首先尋找食物源，并根據(jù)式（9）進(jìn)行食物源位置更新，

其中，k∈｛1，2，…，SN｝，j∈｛1，2，…，d｝，且k≠i。

雇傭蜂在進(jìn)行位置更新后，若新食物源含密量高于舊食物源含密量時，用新位置代替原位置，否則仍保持對舊食物源的開采。

當(dāng)雇傭蜂完成搜索后，觀察蜂根據(jù)雇傭蜂傳達(dá)的食物源信息，依照含密量以輪盤賭方式選擇食物源：

其中，Pi是第i個解的選擇概率，fiti是第i個解的適應(yīng)度值，fi是被優(yōu)化問題的目標(biāo)函數(shù)。在ABC算法中，如果某個解連續(xù)經(jīng)過“l(fā)imit”次循環(huán)后沒有得到改善，則表明該解陷入局部最優(yōu)，則此時與該解對應(yīng)的雇傭蜂轉(zhuǎn)變?yōu)閭刹榉洌ㄟ^式（12）隨機(jī)產(chǎn)生一個新解代替原解。

3.2遺傳蜂群優(yōu)化算法

作為模擬蜜蜂行為的一種新穎的群智能優(yōu)化算法，人工蜂群算法具有簡單、靈活、魯棒性強(qiáng)、尋優(yōu)時間短的優(yōu)點，但其也存在全局搜索能力差，容易陷入局部最優(yōu)的問題。遺傳算法是一類模擬生物界自然選擇遺傳機(jī)制過程來解決負(fù)責(zé)問題的隨機(jī)搜索算法，迭代計算過程從一組解（群體）出發(fā)，采用類似自然選擇和游行繁殖的方式，通過交叉和變異操作，生成具有更好性能指標(biāo)的下一代解的群體。遺傳算法雖然有尋優(yōu)時間長，搜索效率低的不足，但其具有較強(qiáng)的全局搜索能力。因而本文將遺傳算子中的交叉和變異嵌入到人工蜂群算法中，提出了一種遺傳蜂群智能優(yōu)化算法。該算法描述如下：

輸入：蜜蜂數(shù)量、變異概率、交叉概率；

輸出：最優(yōu)解及相應(yīng)參數(shù)；

（1）依據(jù)式（12）隨機(jī)生成對應(yīng)蜜蜂數(shù)量的解（蜜源），利用式（7）求解適應(yīng)度值；

（2）引領(lǐng)蜂在當(dāng)前位置鄰域內(nèi)產(chǎn)生新位置，利用式（10）評價選擇概率，在引領(lǐng)蜂搜索到的新位置和原位置中通過貪婪選擇算子選取一個具有更高適應(yīng)度的位置，保留給下一代種群；

（3）各跟隨蜂按照式（10）選擇跟隨一個引領(lǐng)蜂，并在其鄰域內(nèi)進(jìn)行新位置的搜索；

（4）當(dāng)某只蜜蜂再起位置周圍搜索次數(shù)達(dá)到某一閾值limit，仍沒找到更優(yōu)位置時，變?yōu)閭刹榉洌⒁罁?jù)式（12）隨機(jī)初始化其蜜源位置；

（5）按照交叉概率選擇群體中的兩個個體進(jìn)行交叉操作 ，如果產(chǎn)生的新解優(yōu)于父代，則替換父代，同時對最差個體按照變異率進(jìn)行變異操作，變異后，若更好則替換最差個體；

（6）計算每個食物源適應(yīng)度值及相應(yīng)參數(shù)值；

（7）重復(fù)步驟（1）～（6），直到達(dá)到最大迭代次數(shù)。

4　求解NWMFJSP的遺傳蜂群優(yōu)化算法設(shè)計

4.1編碼設(shè)計

針對無等待柔性車間調(diào)度不僅需要確定工序的加工順序，還要給工序分配機(jī)器特點，本文采用一種擴(kuò)展的基于工序編碼，該編碼由兩部分組成：前半段是基于工序的編碼，它是用來確定工序的加工順序；后半部分是基于機(jī)器的編碼，該編碼中的機(jī)器按照每個工件工序的順序進(jìn)行排列，它用來給每個工序分配合適的機(jī)器。結(jié)合這兩部分編碼，就可以得到無等待柔性作業(yè)車間調(diào)度問題一個可行解。

4.2交叉

交叉操作是將種群中個體的某些基因隨機(jī)交接，以產(chǎn)生新的基因組合。交叉的目的是將優(yōu)良的基因進(jìn)行組合以使子代較好地繼承優(yōu)良的父代基因。本文采用兩種交叉操作［6］，第一種是改進(jìn)工件優(yōu)先順序交叉（Improved Precedence Preserving Order-based Crossover，IPOX）用于染色體中加工工序的交叉；第二種是多點交叉操作（Multi-point Preservative Crossover，MPX）用于染色體工序分配的機(jī)器交叉。

（1）IPOX交叉

IPOX交叉是對每個個體中的工件順序進(jìn)行交叉，其具體操作過程是：所有的工件被隨機(jī)分成兩個集合J1，J2后，首先將父代染色體P1中包含在J1的工件復(fù)制到子代染色體C1，將父代染色體P2中包含在J2的工件復(fù)制到子代染色體C2，保留它們的位置不變，然后將父代染色體P1中包含在J1的工件復(fù)制到子代染色體C2，將父代染色體P2中包含在J2的工件復(fù)制到子代染色體C1，保留它們的順序不變。圖1給出了一個IPOX交叉示例，其中，J1=｛2，4｝，J2=｛1，3｝。

（2）MPX交叉

MPX交叉操作僅對染色體中工序分配的機(jī)器進(jìn)行交叉。設(shè)父代染色體MP1和MP2，交叉產(chǎn)生的子代染色體分別是MC1和MC2，MPX交叉操作過程為：首先隨機(jī)產(chǎn)生一個0、1組成的與染色體長度相等的序列集合R，其次將MP2和MP1中與R中的“1”的位置對應(yīng)的工序選出，復(fù)制到MC1和MC2，最后將MP1和MP2中剩下的機(jī)器保留到MC1和MC2。

圖1　IPOX交叉操作

圖2　MPX交叉操作

圖2給出了一個MPX交叉示例，其中，1、2、3、4、5分別表示機(jī)器編號。

4.3以關(guān)鍵路徑為導(dǎo)向的變異

引入變異算子是為了改善人工蜂群算法的局部搜索能力，有助于維持進(jìn)化群體的多樣性，防止過早陷入局部最優(yōu)?？紤]到無等待柔性車間調(diào)度具體問題，本文在變異中引入了關(guān)鍵路徑的思想。

無等待柔性作業(yè)車間的可行調(diào)度可以通過有向圖表示。在有向圖從源點到匯點的路徑中，長度最長的路徑稱為關(guān)鍵路徑，且關(guān)鍵路徑的長度等于無等待柔性作業(yè)車間的可行調(diào)度的最大完工時間。在關(guān)鍵路徑上的所有工序都稱為關(guān)鍵工序。任何一個關(guān)鍵工序一旦延遲，該調(diào)度的最大完工時間就必然會被推遲。圖3為一無等待柔性車間調(diào)度示例的甘特圖，其中，陰影工序為關(guān)鍵工序。

在變異過程中，只有當(dāng)關(guān)鍵路徑發(fā)生改變時，最大完工時間才會改變，才可能得到比父代更優(yōu)的子代，因而本為給出了基于關(guān)鍵路徑的變異操作。當(dāng)對染色體的工序編碼和機(jī)器分配編碼進(jìn)行變異時，分別通過改變關(guān)鍵路徑上工序的順序和修改關(guān)鍵工序所處的機(jī)器來達(dá)到改變關(guān)鍵路徑的目的。

圖3　甘特圖示例

（1）基于工序編碼的變異

對工序編碼的變異，將變異位置的選擇由整個染色體壓縮到關(guān)鍵路徑上。其操作過程為：從父代中隨機(jī)選擇一個關(guān)鍵工序，并且在滿足工件內(nèi)部順序約束的前提下，將這個工序前插到其緊鄰的前一個關(guān)鍵工序之前的某個位置，同時將對應(yīng)的機(jī)器分配編碼同步前移。圖3對應(yīng)的關(guān)鍵路徑為｛O21，O11，O12，O13，O33｝，若選中關(guān)鍵工序O13，則其前插位置應(yīng)在另一個關(guān)鍵工序O12之前，如圖4所示。

圖4　基于工序編碼的變異

（2）基于機(jī)器編碼的變異

機(jī)器編碼部分變異過程為：從加工成本最高的機(jī)器上選擇一個關(guān)鍵工序，將它重新分配到加工成本最低的機(jī)器上。該變異過程不僅實現(xiàn)了對關(guān)鍵工序的修改，還實現(xiàn)了加工成本的降低。若圖3中M2加工成本最高，M1的加工成本最小，則機(jī)器編碼部分變異后結(jié)果如圖5所示。

圖5　基于機(jī)器編碼的變異

5　仿真實驗與分析

遺傳蜂群優(yōu)化算法在MATLAB 7.0上實現(xiàn)，實驗采用文獻(xiàn)［6］提供的實例數(shù)據(jù)進(jìn)行測試。仿真硬件環(huán)境為Intel Core i5 CPU、2.2GHz主頻、2GB內(nèi)存；軟件環(huán)境為Windows7操作系統(tǒng)。多目標(biāo)混合人工蜂群算法參數(shù)設(shè)置為：種群規(guī)SN=50，采蜜蜂轉(zhuǎn)成偵查蜂的limit= 6，最大迭代次數(shù)150。表2給出了遺傳算法（GA）、人工蜂群算法（ABC）本文算法在三個目標(biāo)函數(shù)函數(shù)上的平均值。三個優(yōu)化目標(biāo)的部分Pareto解集如表1所示，決策者可以根據(jù)企業(yè)實際，運用式（7）對Pareto解集各個解進(jìn)行評價，并從中選出最優(yōu)妥協(xié)解。圖6是第16號解調(diào)度甘特圖。

表1　部分Pareto解集

由表2中實驗結(jié)果可知，本文提出的算法在求解無等待多目標(biāo)柔性車間調(diào)度優(yōu)化問題時在最大完工時間、生產(chǎn)成本、總拖延時間三個分目標(biāo)上均具有一定優(yōu)勢。

表2　三種算法優(yōu)化結(jié)果比較

圖6　第16號解的甘特圖

6　結(jié)語

本文將最大完工時間、生產(chǎn)成本、總拖延時間作為為調(diào)度的目標(biāo)函數(shù)建立了NWMFJSP的多目標(biāo)調(diào)度模型，提出了灰互信息適應(yīng)度值分配策略，給出了求解NWMFJSP問題的GABC算法。實驗結(jié)果表明，提出的模型和算法對無等待多目標(biāo)柔性車間調(diào)度問題是可行的。

［1］GAREY E L，JOHNSON D S，SETHI R.The complexity of flowshop and job-shop scheduling［J］.Mathematics of Operations Research，1976，1：117-129.

［2］Zhu Xia，Li Xiao-ping，Wang Qian.Total-idle-time increment based hybrid GA for no-wait flowshop with makespan minimization ［J］.Journal of Computer Research and Development，2011，48（3）：455-463.

［3］Zhou Hui-ren，Tang Wan-sheng，Wei Yinghui.PSO-based optimization of flexible flow-shop scheduling［J］.China Mechanical Engineering，2010，21（9）：1053-1056.

［4］基于混合粒子群-NEH算法求解無等待柔性流水車間調(diào)度問題［J］.系統(tǒng)工程理論與實踐，2014，34（3）：802-809.

［5］混合蜂群算法求解柔性作業(yè)車間調(diào)度問題［J］.計算機(jī)集成制造系統(tǒng)，2011，17（7）.

［6］張超勇，董星，王曉娟等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度［J］.機(jī)械工程學(xué)報.2010，46（11）：156-164.

畢孝儒（1975-），碩士，網(wǎng)絡(luò)工程師，研究方向為計算機(jī)網(wǎng)絡(luò)安全與集成、智能優(yōu)化

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

賀拴（1982-），助教，研究方向為數(shù)據(jù)挖掘

賀艷果（1983-），助教，研究方向為教育學(xué)

NWFJSP；Multi-Objective Optimization GABC

Genetic Artificial Bee Colony Algorithm Faced with Multi-objective and No-wait Flexible Flow Job-shop Scheduling Problem

BI Xiao-ru，ZHANG Li-li，HE Shuan，HE Yan-guo
（School of Management，Chongqing South Translation College of University of SISU，Chongqing 401120）

1007-1423（2015）23-0011-06

10.3969/j.issn.1007-1423.2015.23.002

2015-06-04

2015-08-10

為了解決無等待柔性車間調(diào)度的多目標(biāo)優(yōu)化問題，構(gòu)建以最大完工時間、生產(chǎn)成本、總拖延時間為目標(biāo)函數(shù)的多目標(biāo)調(diào)度模型，結(jié)合灰色關(guān)聯(lián)分析和熵理論，提出灰互信息適應(yīng)度值分配策略，以評價Pareto解的優(yōu)劣。在此基礎(chǔ)上，運用遺傳蜂群優(yōu)化算法求解，該算法給出以關(guān)鍵路徑為導(dǎo)向的變異操作，并將該變異操作和遺傳算子中的IPOX和MPX交叉操作嵌入到人工蜂群算法中，以增強(qiáng)其全局尋優(yōu)能力，提升搜索后期收斂速度。一個車間調(diào)度實驗驗證調(diào)度模型和算法的有效性和適應(yīng)性。

無等待柔性車間調(diào)度；多目標(biāo)優(yōu)化；遺傳蜂群優(yōu)化

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

To solve no-wait and multi-objective flexible flow shop scheduling problem（NWMFJSP），proposes an optimization model，which takes finished time of maximum，machine cost and total delayed time as the objectives.Then presents the distribution strategy of the grey mutual information relational adaptive value combined with the grey correlation and information entropy to evaluate feasible solution.Based on it，applies genetic artificial bee colony algorithm（GABC）to solve the problem，the algorithm，which presents the mutation based on key path，embeds artificial bee colony with the nutation，IPOX and MPX crossover to enhance ability to search optimal solution globally and raise convergence rate in late search.The validity and adaptability of the scheduling structure and algorithm are proved by a case of job-shop scheduling.