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

畢孝儒，張黎黎，賀拴，賀艷果（四川外國語大學(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)域，它不僅需要確定工序的加工順序，還要給每個(gè)工序分配機(jī)器，是更為復(fù)雜的NP-hard問題［1］。調(diào)度問題的復(fù)雜性，使得采用一般的數(shù)學(xué)規(guī)劃方法很難求解因而許多學(xué)者運(yùn)用遺傳算法（Genetic Algorithm，GA）、粒子群算法（Particle Swarm Optimization，PSO）等智能優(yōu)化算法［2-4］求解單目標(biāo)NWFJSP問題，并取得了較好的效果。然而在實(shí)際生產(chǎn)中不僅要考慮工件最大完工時(shí)間、總拖延時(shí)間等調(diào)度性能指標(biāo)，同時(shí)還要考慮生產(chǎn)成本等費(fèi)用指標(biāo)，即對(duì)多目標(biāo)函數(shù)同時(shí)優(yōu)化。因此求解多目標(biāo)的無等待柔性車間調(diào)度問題更符合實(shí)際需求。

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

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

1　問題描述

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

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

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

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

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

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

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

（1）最大完工時(shí)間

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

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

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

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

（3）總拖延時(shí)間為：

式中，i=1，2，…，M，Ei表示工件i的最大完工時(shí)間，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)勢(shì)。在優(yōu)化時(shí)先將每個(gè)目標(biāo)作為單目標(biāo)分別求得最優(yōu)解，并用這些最優(yōu)解構(gòu)成參考序列，即多目標(biāo)優(yōu)化的理想解。然后將Pareto解的目標(biāo)函數(shù)值序列作為比較序列，利用灰關(guān)聯(lián)度計(jì)算這兩個(gè)序列的接近程度以分析每個(gè)Pareto解與理想解的近似程度，即利用灰關(guān)聯(lián)度評(píng)判Pareto解的優(yōu)劣。上述評(píng)判方法并未考慮個(gè)目標(biāo)因素之間的信息，因而該分析方法的精度不高。本文將熵理論與灰色關(guān)聯(lián)度分析結(jié)合，提出了灰互信息適應(yīng)度值分配策略，其具體步驟如下：

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

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

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

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

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

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

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

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

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

3.1基本人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1編碼設(shè)計(jì)

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

4.2交叉

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

（1）IPOX交叉

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

（2）MPX交叉

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

圖1　IPOX交叉操作

圖2　MPX交叉操作

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

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

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

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

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

圖3　甘特圖示例

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

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

圖4　基于工序編碼的變異

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

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

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

5　仿真實(shí)驗(yàn)與分析

遺傳蜂群優(yōu)化算法在MATLAB 7.0上實(shí)現(xiàn)，實(shí)驗(yàn)采用文獻(xiàn)［6］提供的實(shí)例數(shù)據(jù)進(jìn)行測(cè)試。仿真硬件環(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）本文算法在三個(gè)目標(biāo)函數(shù)函數(shù)上的平均值。三個(gè)優(yōu)化目標(biāo)的部分Pareto解集如表1所示，決策者可以根據(jù)企業(yè)實(shí)際，運(yùn)用式（7）對(duì)Pareto解集各個(gè)解進(jìn)行評(píng)價(jià)，并從中選出最優(yōu)妥協(xié)解。圖6是第16號(hào)解調(diào)度甘特圖。

表1　部分Pareto解集

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

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

圖6　第16號(hào)解的甘特圖

6　結(jié)語

本文將最大完工時(shí)間、生產(chǎn)成本、總拖延時(shí)間作為為調(diào)度的目標(biāo)函數(shù)建立了NWMFJSP的多目標(biāo)調(diào)度模型，提出了灰互信息適應(yīng)度值分配策略，給出了求解NWMFJSP問題的GABC算法。實(shí)驗(yàn)結(jié)果表明，提出的模型和算法對(duì)無等待多目標(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)工程理論與實(shí)踐，2014，34（3）：802-809.

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

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

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

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

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

賀艷果（1983-），助教，研究方向?yàn)榻逃龑W(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)建以最大完工時(shí)間、生產(chǎn)成本、總拖延時(shí)間為目標(biāo)函數(shù)的多目標(biāo)調(diào)度模型，結(jié)合灰色關(guān)聯(lián)分析和熵理論，提出灰互信息適應(yīng)度值分配策略，以評(píng)價(jià)Pareto解的優(yōu)劣。在此基礎(chǔ)上，運(yùn)用遺傳蜂群優(yōu)化算法求解，該算法給出以關(guān)鍵路徑為導(dǎo)向的變異操作，并將該變異操作和遺傳算子中的IPOX和MPX交叉操作嵌入到人工蜂群算法中，以增強(qiáng)其全局尋優(yōu)能力，提升搜索后期收斂速度。一個(gè)車間調(diào)度實(shí)驗(yàn)驗(yàn)證調(diào)度模型和算法的有效性和適應(yīng)性。

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

四川外國語大學(xué)重慶南方翻譯學(xué)院科研項(xiàng)目（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.