面向無等待多目標柔性車間調度問題的遺傳蜂群優化算法

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

面向無等待多目標柔性車間調度問題的遺傳蜂群優化算法

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

0　引言

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

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

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

1　問題描述

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

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

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

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

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

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

本文針對無等待柔性車間調度的需求，給出了以下優化目標：縮短最大完工時間以增加生產效率、減少總拖延時間以提高客戶滿意度、減低成本以滿足企業可持續發展，其需要優化的目標函數如下：

（1）最大完工時間

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

（2）生產成本

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

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

（3）總拖延時間為：

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

2　灰互信息關聯度適應度值分配策略

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

（1）對于N個Pareto解，計算各目標函數值為：

上式中，T為目標個數，fT（0）是第T個子目標作為單目標函數求出最優解的目標函數值，fi是每個子目標最優解組合而成的序列；

（2）依據式（5）對各Pareto解的目標函數值進行歸一化處理；

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

3）依據式（6）計算各目標函數值之間的互信息量；

其中，P（fk'（i），fk'（j））為fk'（i），fk'（j）的聯合熵。

（4）依據式（7）計算Pareto解灰互信息關聯度；

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

3　遺傳蜂群優化算法

3.1基本人工蜂群算法

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

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

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

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

其中，Pi是第i個解的選擇概率，fiti是第i個解的適應度值，fi是被優化問題的目標函數。在ABC算法中，如果某個解連續經過“limit”次循環后沒有得到改善，則表明該解陷入局部最優，則此時與該解對應的雇傭蜂轉變為偵查蜂，通過式（12）隨機產生一個新解代替原解。

3.2遺傳蜂群優化算法

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

輸入：蜜蜂數量、變異概率、交叉概率；

輸出：最優解及相應參數；

（1）依據式（12）隨機生成對應蜜蜂數量的解（蜜源），利用式（7）求解適應度值；

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

（3）各跟隨蜂按照式（10）選擇跟隨一個引領蜂，并在其鄰域內進行新位置的搜索；

（4）當某只蜜蜂再起位置周圍搜索次數達到某一閾值limit，仍沒找到更優位置時，變為偵查蜂，并依據式（12）隨機初始化其蜜源位置；

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

（6）計算每個食物源適應度值及相應參數值；

（7）重復步驟（1）～（6），直到達到最大迭代次數。

4　求解NWMFJSP的遺傳蜂群優化算法設計

4.1編碼設計

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

4.2交叉

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

（1）IPOX交叉

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

（2）MPX交叉

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

圖1　IPOX交叉操作

圖2　MPX交叉操作

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

4.3以關鍵路徑為導向的變異

引入變異算子是為了改善人工蜂群算法的局部搜索能力，有助于維持進化群體的多樣性，防止過早陷入局部最優。考慮到無等待柔性車間調度具體問題，本文在變異中引入了關鍵路徑的思想。

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

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

圖3　甘特圖示例

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

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

圖4　基于工序編碼的變異

（2）基于機器編碼的變異

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

圖5　基于機器編碼的變異

5　仿真實驗與分析

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

表1　部分Pareto解集

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

表2　三種算法優化結果比較

圖6　第16號解的甘特圖

6　結語

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

［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算法求解無等待柔性流水車間調度問題［J］.系統工程理論與實踐，2014，34（3）：802-809.

［5］混合蜂群算法求解柔性作業車間調度問題［J］.計算機集成制造系統，2011，17（7）.

［6］張超勇，董星，王曉娟等.基于改進非支配排序遺傳算法的多目標柔性作業車間調度［J］.機械工程學報.2010，46（11）：156-164.

畢孝儒（1975-），碩士，網絡工程師，研究方向為計算機網絡安全與集成、智能優化

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

賀拴（1982-），助教，研究方向為數據挖掘

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

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

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

無等待柔性車間調度；多目標優化；遺傳蜂群優化

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