基于批量流水線調度問題的混合離散果蠅優(yōu)化算法

潘玉霞+賈保先

摘要：提出了一種混合離散果蠅優(yōu)化算法，求解以最大完工時間為目標的批量流水線調度問題。與傳統(tǒng)的果蠅算法不同，首先，該算法采用基于工序的編碼方式，使得算法適合解決調度問題；其次，混合了貪婪迭代進化機制進行群體間相互協(xié)作的學習，以此平衡算法的全局開發(fā)能力和局部搜索能力。仿真試驗表明了所提果蠅算法的有效性和高效性。

關鍵詞： 果蠅優(yōu)化算法；批量流水線調度問題；貪婪迭代

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）30-0146-03

Hybrid Discrete Fruit Fly Optimization Algorithm for Lot-streaming Flow Shop Scheduling Problem

PAN Yu-xia1， JIA Bao-xian2

（1.Department of Basic Computer Education， Sanya University ，Sanya 572000，China；2.School of Computer Science，Liaocheng University， Liaocheng 252059，China ）

Abstract： This paper presents a Hybrid Discrete Fruit Fly Optimization Algorithm （HDFOA） for solving the Lot-streaming flow shop scheduling problem（LFSP） with makespan criteria.Unlike the traditional FOA， the proposed algorithm applies the job-permutation-based representation ，make sure it is suitable for scheduling problem. Second， Iterative Greedy is made for the whole group， so that the who group keeps in good balance between global exploration and local exploitation. Finally， to improve the efficiency of the scheduling algorithm . Computational results show that the FOA presented in this paper is very effective and efficient for the LFSP.

Key words： fruit fly optimization algorithm； lot-streaming flow shop scheduling problem； iterative greedy

1 概述

批量流水線調度問題（Lot-streaming Flowshop Scheduling Problem ，LFSP） 廣泛應用于冶金、塑料、化工等工業(yè)生產(chǎn)中，具有重要的理論研究背景和實際應用價值。隨著市場競爭的日益激烈和客戶需求的多樣化，多品種中小批量生產(chǎn)模式占據(jù)了主導地位。因此對批量流水線調度問題的研究已成為學術界和工程界的關注焦點。

果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）是近幾年剛興起的一類全局進化優(yōu)化算法，于2011年由臺灣博士潘文超提出的。該算法源于對果蠅覓食行為的模擬，已經(jīng)在求解數(shù)學函數(shù)極值[3]，自動化倉庫揀選作業(yè)調度問題[4]等方面得到成功的應用。由于FOA提出時間不長，理論研究尚不成熟，就已經(jīng)在求解連續(xù)和離散問題方面顯示了特有的優(yōu)勢。因此FOA算法的相關研究迫切需要開展。

2 批量流水線調度模型

為了減小機床的等待時間，將每個工件按等量分配的原則劃分成若干個小批量。各個工件的小批量加工完成后就能被傳送到下一臺機床上加工，所有小批量的加工順序都相同。假設工件按機床1到[m]的順序加工，給定一個工序[π=δ1，δ2，…，δn]，工件[j]被劃分成[sj]個小批量，[ltij]是工件[j]的小批量在機床[i]上的加工時間， [ctijk]為工件[j]的第[k]個小批量在機床[i]上的完成時間，[cj]為工件[j]的完成時間，則LFSP的數(shù)學模型為：

1）[ct1，δ1，1=lt1，δ1]

第一個工件的第一個小批量在第一臺機床上的完成時間；

2）[cti，δ1，1=cti-1，δ1，1+lti，δ1]，[i=2，...，n]

第一個工件的第一個小批量在第[i]臺機床上的完成時間；

3） [ct1，δ1，k=ct1，δ1，k-1+lt1，δ1] ，[k=2，...，sδj]

第一個工件的第[k]個小批量在第一臺機床上的完成時間；

4） [ct1，δj，1=ct1，δj-1，sδj-1+lt1，δj]，[j=2，...，n]

第[j]個工件的第一個小批量在第一臺機床上的完成時間；

5） [ct1，δj，k=ct1，δj，k-1+lt1，δj]，[j=2，...，n][k=2，...，sδj]

第[j]個工件的第[k]個小批量在第一臺機床上的完成時間；

6） [cti，δj，k=maxcti-1，δj，k，cti，δj-1，sδj-1+lti，δj]，[k=1]

第[j]個工件的第一個小批量在第[i]臺機床上的完成時間；

7） [cti，δj，k=maxcti-1，δj，k，cti，δj，k-1+lti，δj]，[k=2，...，sδj]

第[j]個工件的第[k]個小批量在在第[i]臺機床上的完成時間；

調度的目標就是求最小化最大完工時間，即：

[minf（π）=cn=ctm，δn，sδn]

3 混合離散果蠅算法

果蠅優(yōu)化算法的基本原理是初始化種群的中心位置，利用敏銳的嗅覺進行搜索，即根據(jù)中心位置隨機產(chǎn)生多個鄰域解。計算各可行解的味道濃度，即評價值，然后利用視覺從中選擇較好的解，更新替換中心位置，然后進行迭代尋優(yōu)，以更好的進靠近食物源。

FOA在整個迭代尋優(yōu)過程中，所有個體都聚集到本次迭代的最優(yōu)個體附近，只向當前最優(yōu)果蠅個體學習，極易使算法陷入局部最優(yōu)。要克服早熟的問題，必須提供一種機制可以跳出局部最優(yōu)，在其他解空間中繼續(xù)搜索[5]。此外，在連續(xù)空間中產(chǎn)生新個體的方法不適合解決調度。故運用FOA算法的主體流程，對其優(yōu)化過程進行離散化是算法成功應用于LFSP的關鍵。基于以上分析，提出了混合離散果蠅算法（Hybrid Discrete Fruit Fly Optimization Algorithm ，HDFOA）。

3.1算法編碼

對具有連續(xù)特性的算法進行離散化，首先要解決的關鍵問題是個體如何編碼，即果蠅個體的表示方法。種群中的每個個體對應問題中的一個解，故采用基于工序的置換編碼，因為基于工序的置換編碼承載與問題相關的必要信息，已經(jīng)廣泛應用于此類文章中[6]。

以5工件調度問題為例，在（-1，1）之間產(chǎn)生5個隨機數(shù)（-0.4，0.6，0.3，0.5，-0.1，0.0），利用最大位置值規(guī)則得到一個置換解（2，4，3，6，5，1）。

3.2種群初始化

FOA算法基本思想是在種群的初始位置基礎上，向食物源飛近，因此，好的初始解有利于提高算法的收斂速度和解的質量。一個好的初始解應該以較大的概率覆蓋解空間，并包含部分質量高的個體以指導算法搜索方向。為了保證種群中初始解的多樣性和高質量，初始解在解空間中隨機產(chǎn)生。初始化方法如下：

[x={-0.6，-0.5，0.1，0.2，-0.1，0.3}]，利用最大位置法將和聲解轉化成工序[π={6，4，3，5，2，1}]。

a） 嗅覺和視覺搜索

影響FOA算法性能的核心是如何生成嗅覺階段的鄰域個體[6]。本文結合迭代貪婪（Iterative Greedy，IG）進化過程，對種群中的果蠅個體進行優(yōu)化，迭代貪婪啟發(fā)式算法步驟如下：

步驟1：分解當前個體

1） 從當前個體中隨機取出[d]個工件，標記為[πR]，其中[d]為工件數(shù)范圍內隨機產(chǎn)生的整數(shù)。

2） 剩余的n-d個工件組成果蠅個體的一部分，標記給[πD]

步驟2：利用NEH方法的最后一步組成新的果蠅個體

1） 設置參數(shù)[i=1]

2） [πR]中的第[i]個工件被重新插入到[πD]的[n-d+i]個可能的位置，選出目標值最好的解作為當前解。

3） [i=i+1]，[i

利用視覺功能確定新解是否優(yōu)于當前解，若是，則更新當前解。

4 HDFOA算法流程

基于以上分析，混合離散果蠅優(yōu)化算法步驟如下

步驟1：初始化參數(shù)，種群個體數(shù)，迭代代數(shù)

步驟2：初始化果蠅個體。

步驟3：利用IG進化過程產(chǎn)生新果蠅個體

步驟4：更新種群。利用視覺選擇決定是否更新解。如果新果蠅個體比較好，則替換之，否則不變。

5 仿真實驗

通過與文獻[7]提出的DPSO算法進行比較，測試本文提出的算法的性能。采用與文獻[7]相同的參數(shù)設置和指標。利用C++編程語言，在處理器為Intel（R）Core（TM） i3 2GHZ、內存為2.00G的PC機上進行程序測試。為了公平比較，各算法采用相同的終止條件，每個實例獨立運行30次。

兩種算法比較結果如表1所示

由表1知：

1） HDFOA的平均MRPI為0.02，遠遠小于DPSO的0.33，說明了HDFOA具有較好的求解質量。

2） HDFOA的平均時間為1.03，遠遠小于DPSO的6.58，說明了HDFOA具有較快的收斂速度。

3） 13個不同規(guī)模的問題來看，隨著問題規(guī)模的增加，HDFOA的優(yōu)越性越來越明顯。

總之，與DPSO相比，HDFOA具有較優(yōu)越的性能。

6 總結

結合LFSP的特點，設計了工序編碼的混合離散果蠅調度算法。為了克服果蠅算法容易陷入局部最優(yōu)的缺陷，在框架中引入基于IG的進化方案。仿真結果表明所得算法具有較高的優(yōu)化性能。

參考文獻：

[1] 周亞勤，李蓓智，楊建國.基于遺傳算法的批量Flow-shop調度問題研究，機械制造[J].2004，42（482）：57-59.

[2] Tseng C T，Liao C J.A discrete particle swarm optimization for lot-streaming flowshop scheduling problem[J].European Journal of Operational Research，2007，8（30）.

[3] 潘文超.果蠅最佳化演算法[M].臺北： 滄海書局，2011： 10-12.

[4] 劉志雄，王雅芬，張煜.多種群果蠅優(yōu)化算法求解自動化倉庫揀選作業(yè)調度問題[J].武漢理工大學學報，2014，36（3）.

[5] 韓俊英，劉成忠，王聯(lián)國.動態(tài)雙子群協(xié)同進化果蠅優(yōu)化算法[J].模式識別與人工智能，2013（11）：1057-1067.

[6] 鄭曉龍，王凌，王圣堯.求解置換流水線調度問題的混合離散果蠅算法[J].控制理論與應用， 2014， 31（2）： 159 -164.

[7] 潘玉霞，潘全科，桑紅燕，武磊.解決批量流水線調度問題的離散微粒群算法[J].聊城大學學報， 22（3）.