張曉霞 呂云虹

(遼寧科技大學軟件學院 遼寧 鞍山 114051)

一種求解混合零空閑置換流水車間調(diào)度禁忌分布估計算法

張曉霞 呂云虹

(遼寧科技大學軟件學院 遼寧 鞍山 114051)

結合混合零空閑置換流水車間調(diào)度問題MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性，運用基于概率模型的分布估計算法解決該問題。算法將啟發(fā)式算法融入分布估計算法中提高了初始解的質(zhì)量。為了避免算法陷入局部最優(yōu)，將禁忌算法融入分布估計算法中，提出一種禁忌分布估計算法求解混合零空閑置換流水車間問題。為了提高種群的多樣性，加入了三種鄰域搜索。實例測試結果顯示，該算法求解混合零空閑置換流水車間問題具有很好的優(yōu)勢。

混合零空閑置換流水車間調(diào)度問題算法 分布估計算法 啟發(fā)式算法 禁忌算法

0 引 言

置換流水車間調(diào)度問題屬于經(jīng)典的調(diào)度問題，它是在流水車間調(diào)度問題約束的基礎上，進一步增加所有工件在任一臺機器上的加工順序均相同的約束后形成的生產(chǎn)調(diào)度問題[1]。零空閑置換流水車間調(diào)度問題NPFSP(No-idle permutation flowshop scheduling problem)是在置換流水車間調(diào)度問題的前提下，設置一臺機器一旦開始加工就不能中斷，直到加工完所有的工件。當前關于NPFSP的研究，在實際生產(chǎn)過程中，NPFSP是很少存在的，更多的是混合零空閑調(diào)度問題，因此研究混合零空閑置換流水車間調(diào)度問題MNPFSP具有十分重要的意義。

MNPFSP是典型NP難題。對于問題規(guī)模較小的MNPFSP，可以采用精確算法來求得問題的解，例如啟發(fā)式算法等。但在解決實際問題的情況下，MNPFSP問題規(guī)模相對較大，問題相對復雜，此時不適合用精確算法求解該問題。智能優(yōu)化算法作為一種經(jīng)常求解NP問題的方法，人們對于求解大規(guī)模生產(chǎn)調(diào)度問題更多地采用智能優(yōu)化算法。當前用于解決生產(chǎn)調(diào)度問題的算法有遺傳算法[2]、蟻群算法[3]、分布估計算法[4]和人工蜂群算法[5]等。

分布估計算法EDA(Estimation of distribution algorithm)興起成為最近幾年里研究的熱點問題，它的思想來源于遺產(chǎn)算法。在遺產(chǎn)算法的基礎上，EDA采用概率分布模型來替換遺傳算法中的交叉和變異等操作，并根據(jù)概率模型的信息，運用各種策略對種群進行采樣，產(chǎn)生新種群，通過反復地進化得到最終結果。概率分布模型很好地克服了遺傳算法構造模塊破壞的問題。這種算法具有很強的自適應能力和自學習能力，不依賴問題的具體領域[6]。根據(jù)概率模型的復雜度，分布估計算法大致分為三類：變量無關、雙變量相關和多變量相關[7]。

EDA引起在各個領域的專家學者廣泛的研究，并取得了不錯的進展。例如巡航導彈航跡規(guī)劃中的應用[8]、旅行商問題的應用、圖像處理和過程控制等。本文將分布估計算法應用于求解混合零空閑置換流水車間調(diào)度問題，結合問題的特點，將啟發(fā)式算法與禁忌算法融入到算法中，來提高算法的搜索效率。為了防止算法陷入局部最優(yōu)的狀況，在算法中加入局部搜索策略。通過實例驗證了本文的混合分布估計算法在求解該問題上有很大的優(yōu)勢。

1 MNPFSP問題的描述

混合零空閑置換流水車間調(diào)度問題就是NPFSP與PFSP調(diào)度的混合，主要是指在加工過程中，存在某些機器一旦開始加工就不能停止，直到加工結束，而其余的機器在加工過程中是可以停止的。

MNPFSP的數(shù)學描述如下：Π(π1，π2，…，πk，…，πn)是工件加工的一個調(diào)度。其中下標表示在加工序列中的位置。用l表示工件在加工序列的位置，Ci,[l]表示l位置上的工件在機器i上的加工完成時間，用Si,[l]表示l位置上的工件在機器i上開始加工時間。用Pi,j表示工件j在機器i上加工所消耗時間。用ai表示位置1的工件要在開始加工時延遲加工時間，為了便于描述，公式中把推延時間放在后面出現(xiàn)延遲的地方，最終結果是相同的。將NPFSP的機器集合記為M1，空閑的記為M。這里將最大完成時間makespan設為調(diào)度指標。其公式為[9]：

(1)

(2)

(3)

(4)

Cmax(π)=Cm,[n]

(6)

式(1)計算了位置1的工件在第一個機器的起始與終止時間。式(2)是計算位置1的工件在各個機器上的起始與終止時間。式(3)是計算不同位置的工件在機器1上的起始與終止時間。式(4)是計算不同位置上的工件在機器2上的起始與終止時間。式(5)是計算不同位置的工件在剩余機器上的起止時間。式(6)是調(diào)度的目標函數(shù)。

2 分布估計算法

分布估計算法這一概念最初是在1996年被提出，近年來國際上進化計算領域的各大學術會議(如ACM SIGEVO、IEEE CEC等)都將分布估計算法作為重要專題予以討論[7]，并成功解決了一些實際的問題。分布估計算法運用概率模型來替換遺傳算法中的交叉、變異操作，根據(jù)概率模型產(chǎn)生新一代的種群?；静襟E如下：

(1) 產(chǎn)生初始化種群。

(2) 計算個體的適應值，選擇群體中的優(yōu)勢群體。

(3) 根據(jù)優(yōu)勢群體的信息，建立概率模型，來產(chǎn)生下一代。

(4) 根據(jù)優(yōu)勢群體的概率模型，采用一定的策略來產(chǎn)生新個體并進行更新操作。

(5) 重復以上步驟，如果滿足終止條件，則算法停止；否則，轉(zhuǎn)步驟(2)繼續(xù)執(zhí)行。

3 改進的分布估計算法求解MNPFSP

為了提高算法的收斂速度，在初始化種群的過程中，引入了NEH啟發(fā)式算法，提高初始種群的質(zhì)量。為了提高算法的局部搜索能力，將2-opt、逆序、交換等操作融入到算法中。同時算法將禁忌搜索算法加入到分布估計算法中，提高算法的全局搜索能力。實驗表明這些操作對算法的效率和性能具有很大的提升，能夠有效地取得算法較好的解。

3.1 產(chǎn)生初始種群

對于混合零空閑置換流水車間調(diào)度問題，直接使用十進制數(shù)來編碼。用自然數(shù)來表示工件的加工順序，即每個自然數(shù)代表一個工件。隨機產(chǎn)生T條加工順序作為初始種群。為了保證種群的多樣化和提高收斂速度，這里運用NEH啟發(fā)式算法對初始種群進行優(yōu)化，使其產(chǎn)生一個局部最優(yōu)解，將其放入到初始種群中。

NEH啟發(fā)式算法是1983年Nawaz、Enscore和Ham共同提出來的[10]。該算法是求解加工時間周期性能最好的。其具體的操作：

(1) 計算工件i在各個機器上的總的加工時間；

(2) 根據(jù)工件總的加工時間，非遞增的順序排列N個工件；

(3) 取位于順序的前兩個工件，使部分最大流程時間達到極??；

(4) 令k=3到N，把第k個工件插入到k個可能的位置，求得子調(diào)度最優(yōu)。為了提高種群的質(zhì)量，剩下的隨機產(chǎn)生。

3.2 計算適應值選擇優(yōu)勢群體

按照各個工件i在機器上的排列作為加工順序，所有工件加工完成所使用的時間作為適應度值。時間越長，適應度值越小，反之亦然。按照適應度值將工件進行排序。從適應值較高的種群中選擇m個個體作為優(yōu)勢群體。

3.3 建立概率模型

在分布估計算法中，概率模型的構造方式多種多樣。本文采用位置概率和連接概率相結合的方式來建立概率模型，即建立兩個概率模型。根據(jù)種群中的優(yōu)勢群體兩兩連接出現(xiàn)的工件頻率來建立一個頻率矩陣。

(7)

式中，ei,j表示在工件i后面的連接工件是j的頻率，如果δ(xl)的值為1，表示加工順序l中工件i和工件j兩兩相鄰出現(xiàn)，否則為0。

類似建立一個頻率矩陣來記錄優(yōu)勢種群的位置概率模型。統(tǒng)計計算在各個加工機器上工件出現(xiàn)的頻率，即在序列Π(π1，π2，…，πk，…，πn)中πk表示排在k位置上的工件號。

在構建概率矩陣時，采用了文獻[11]的概率矩陣優(yōu)化方法，將PBIL[7]算法的Heb規(guī)則運用到概率矩陣構造中，即：

(8)

式中，λ∈(0,1)，λ越大，對下一代的影響也就越大，反之越小。

3.4 禁忌算法產(chǎn)生新種群

為了產(chǎn)生新一代種群，防止算法早熟，本文將禁忌算法融入到EDA算法中，提出了一種禁忌思想的改進分布估計算法。禁忌算法對搜索過的區(qū)域進行封鎖避免迂回搜索，同時赦免禁忌區(qū)域中一些優(yōu)良狀態(tài)，進而保證搜索的多樣性，防止陷入局部最優(yōu)[12]。利用禁忌算法的特點，首先初始化了長度為K的禁忌列表，然后將要進化的優(yōu)勢群體賦值給禁忌列表。當最優(yōu)解在KT代內(nèi)不再進化時，更新禁忌列表。將該局部最優(yōu)解個體作為禁忌對象，從而禁止產(chǎn)生相同適應度值的新一代個體。反復抽樣，產(chǎn)生新一代群體。

算法利用輪盤賭法根據(jù)位置概率的分布產(chǎn)生新個體的第一個工件，為了保持種群的多樣性，其余的部分則隨機產(chǎn)生第一個工件。剩下的工件利用輪盤賭法根據(jù)禁忌算法中的禁忌列表產(chǎn)生。判斷種群進化的收斂性，若達到收斂則算法結束，否則更新概率模型，選擇新的優(yōu)勢群體繼續(xù)進化。

3.5 更新概率模型

(9)

4 鄰域搜索策略

為了算法避免陷入局部最優(yōu)，增強算法的局部搜索效率。在算法中加入了2-opt操作、逆序操作[13]和交換操作[13]。

2-opt鄰域搜索算法是一種簡單的啟發(fā)式鄰域搜索算法[12]。其基本思想是：對一條有向路徑，選擇兩條不相鄰邊，如(x1，x2)和(x3，x4)；將這兩條邊斷開，以某種方式連接成新有向路徑，如有向路徑的邊變成(x1，x3)和(x2，x4)；使新的路徑長度滿足約束并小于原來的路徑長度，如C(x1，x2)+C(x3，x4)>C(x1，x3)+C(x2，x4)，新的路徑作為當前路徑。由于2-opt操作是從第一個工件開始搜索遍歷的，而生產(chǎn)調(diào)度的問題跟它有所不同，第一個工件和最后一個工件不參與2-opt操作，所以將2-opt操作用于每一代的優(yōu)勢群體。

逆序操作在工件排列的順序中隨機選定兩個位置x和y，將選定的兩個位置中間的工件順序逆序排列。即工件順序為(2，5，3，4，1，6，7)，選定的點為x=2，y=6，則工件的排列順序為(2，6，1，4，3，5，7)。

為了提高種群的多樣性，在算法中還添加了交換操作。交換操作與逆序操作不同，即在工件序列中隨機選定兩個位置x和y，但是對這兩個選定的位置進行交換。即設工件序列(2，5，3，4，1，6，7)，選定的點為x=2，y=6，則工件的排列順序為(2，6，3，4，1，5，7)。

5 仿真實驗

由于研究MNPFSP方面的問題非常少，目前沒有經(jīng)典的測試實例，本文運用測試NPFSP問題的實例來測試MNPFSP問題，并將NPFSP問題的最優(yōu)解作為MNPFSP問題的最優(yōu)解。采用了Taillard提出的120個經(jīng)典Benchmark問題進行測試，為了證明數(shù)據(jù)的有效性，每個問題測試5次。該算法的仿真環(huán)境為：處理器為2.27 GHz,內(nèi)存為2 GB，32位操作系統(tǒng)，系統(tǒng)為Windows 7，編譯環(huán)境為Visual Studio 2010。本文在求得最優(yōu)解或運行到最大代數(shù)時，程序結束運行。本文算法的設置參數(shù)為：種群規(guī)模Scale=100，學習效率AF=0.5，優(yōu)勢群體的規(guī)模為T=30，禁忌表長度L=10，最大運行代數(shù)5000，最小限定值為0.00001×α/n，最大限定值為0.0001×α/n。

針對MNPFSP的特性將每個測試實例分為7種問題進行測試：

(1) 前50%的機器是NIPFSP，后50%的機器是PFSP：FRTST50。

(2) 后50%機器是NIPFSP，前50%的機器是PFSP：SECOND50。

(3) 空閑與零空閑機器交替出現(xiàn)：ALTERNATE。

(4) 有25%的機器是NIPFSP的并且是隨機指定的：RANDOM25。

(5) 有50%的機器是NIPFSP的并且是隨機指定的：RANDOM50。

(6) 有75%的機器是NIPFSP的并且是隨機指定的：RANDOM75。

(7) 全部是零空閑機器：ALL。

七種情況的的測試結果如表1和表2所示。

表1 前三種情況的測試結果

表2 后四種情況的測試結果

表中PRD表示平均相對百分比偏差，即算法的最優(yōu)解的平均相差百分比。SD表示平均標準差，即所求解的平均偏離程度，體現(xiàn)算法的穩(wěn)定性[2]。從表1和表2中可以看出，任意混合零空閑置換流水車間調(diào)度的PRD都小于全部是零空閑置換流水車間的調(diào)度，并且隨著種群規(guī)模的不斷增加，MNPFSP問題中的PRD明顯優(yōu)于NPFSP問題。雖然MNPFST測試實例中的SD不小于NPFST調(diào)度，但是基本接近于零空閑調(diào)度。所以混合零空閑置換流水車間問題運用本文算法解決具有良好的優(yōu)越性和全局搜索能力。

因為MNPFSP問題是相對復雜的車間調(diào)度問題，目前關于混合零空閑置換流水車間問題的研究非常少，在Benchmark問題中MNPFSP問題的最優(yōu)解目前尚未求得。為了更好地驗證本文算法對解決流水車間問題的優(yōu)良性，將禁忌分布估計算法(TEDA)的第七組測試數(shù)據(jù)，即解決零空閑置換流水車間問題，與遺傳算法(GA)[14]、離散粒子群算法(DPSO)[14]和離散蛙跳算法(DSFLA)[15]，進行解決NPFSP問題的比較。文中的參數(shù)數(shù)據(jù)來自相應文獻，四種算法的對比結果如表3所示。

表3 四種算法的對比結果

表3中測試實例數(shù)據(jù)中，本文算法除了20×20和100×10中PRD的數(shù)據(jù)稍大于其他算法，剩下的PRD數(shù)據(jù)都小于其他算法，并且TEDA的PRD平均值優(yōu)于其他算法，因此可以驗證TEDA具有更好尋優(yōu)搜索能力和全局搜索能力。TEDA算法的平均標準差都小于其他算法，表明該算法具有很好的穩(wěn)定性。

為了更好地體現(xiàn)算法的性能，將TEDA算法與DPSO算法進行算法最優(yōu)解平均標準差的折線圖比較，如圖1所示。

圖1 TEDA算法與DPSO算法的SD比較折線圖

根據(jù)表3中SD的數(shù)據(jù)，畫出TEDA算法與DPSO算法的最優(yōu)解平均標準差折線圖，橫坐標表示問題N×M，其中點1就代表規(guī)模20×5，縱坐標表示SD。從圖1中可以看出，除了在規(guī)模50×5、100×5和100×20，即點4、點7和點9的位置，TEDA算法的SD小于DPSO算法，而且TEDA算法SD的平均值明顯低于DPSO算法。這表明TEDA算法在解決混合零空閑置換流水車間問題時表現(xiàn)出很好的穩(wěn)定性。

為了更好地說明算法的收斂性，圖2給出了TEDA算法求解中規(guī)模50×5問題的收斂曲線圖。由圖可見，TEDA具有較快的收斂性。

圖2 TEDA算法的收斂曲線

6 結 語

本文根據(jù)分布估計算法與禁忌算法各自的特點，提出了一種融合了禁忌算法的混合分布估計算法求解MNPFSP問題。算法將禁忌算法與分布估計算法融合在一起，通過引入禁忌列表來控制種群的進化方向，有效避免了算法陷入局部最優(yōu)的陷阱。為了提高算法的收斂速度，引入三種局部搜索策略；同時引入了NEH算法，提高了初始種群的質(zhì)量。通過仿真測試表明，本文提出的混合分布估計算法在求解MNPFSP問題時具有一定的優(yōu)越性。但是MNPFSP問題是一個非常新穎的問題，目前關于此類問題的研究十分少，本文中用于測試的實例的最優(yōu)解目前尚未求得，因此本文算法用于求解MNPFSP的優(yōu)越性還需進一步的研究。

[1] 劉長平，葉春明.求解置換流水車間調(diào)度問題的布谷鳥算法[J].上海理工大學學報，2013,35(1)：17-20.

[2] 郭海東.遺傳算法及其在生產(chǎn)調(diào)度中的應用研究[D].浙江：浙江工業(yè)大學,2004.

[3] 張麗萍.改進的蟻群算法求解置換流水車間調(diào)度問題[J].微型機與應用,2014,33(12):66-68，72.

[4] Quan Ke Pan,Rubén Ruiz.An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J].OMEGA,The International Journal of Management Science，2012，40(2):166-180.

[5] M Fatih Tasgetirena,Quan Ke Pan,P N Suganthan,et al.A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion[J].Applied Mathematical Modelling,2013,37(10/11):6758-6779.

[6] 張鳳超.改進的分布估計算法求解混合流水車間調(diào)度問題研究[J].軟件導刊,2014,13(8):23-26.

[7] 周樹德，孫增圻.分布估計算法綜述[J].自動化學報,2007，33(2)：113-124.

[8] 吳紅，王維平，王磊，等.分布估計算法在巡航導彈航跡規(guī)劃中的應用[J].電光與控制,2010,17(7):6-10.

[9] Quan Ke Pan,Rubén Ruiz.An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem[J].OMEGA,The International Journal of Management Science,2014,44: 41-50.

[10] 韋有雙，楊湘龍，馮允成.一種新的求解Flow Shop問題的啟發(fā)式算法[J].系統(tǒng)工程理論與實踐,2000,20(9)：41-47.

[11] 何小娟，曾建潮.基于優(yōu)良模式連接的分布估計算法求解TSP問題[J].模式識別與人工智能,2011，24(2):185-193.

[12] 汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法[M].北京：高等教育出版社,2007.

[13] 劉長平，葉春明.求解零空閑置換流水車間調(diào)度問題的離散螢火蟲算法[J].系統(tǒng)管理學報,2014,23(5)：723-727.

[14] 潘全科，王凌，趙保華.解決零空閑流水線調(diào)度問題的離散粒子群算法[J].控制與決策，2008,23(2):191-194.

[15] 王亞敏，冀俊忠，潘全科.基于離散蛙跳算法的零空閑流水線調(diào)度問題的求解[J].北京工業(yè)大學學報，2010,36(1):124-130.

A TABU ESTIMATION OF DISTRIBUTION ALGORITHM TO SOLVE THE MIXED NO-IDLE PERMUTATION FLOWSHOP SCHEDULING PROBLEM

Zhang Xiaoxia Lü Yunhong

(SchoolofSoftware,UniversityofScienceandTechnologyLiaoning,Anshan114051,Liaoning,China)

According to the characteristics of the mixed no-idle permutation flowshop scheduling problem,an estimation of distribution algorithm based on probability model is used to solve this problem.What’s more,the heuristic algorithm is designed into the estimation of distribution algorithm in order to improve the quality of the initial solution.In order to avoid the algorithm into local optimum,the tabu algorithm is designed into the estimation of distribution algorithm.The tabu estimation of distribution algorithm is proposed to solve the mixed no-idle permutation flowshop scheduling problem with three added kinds of local searches in order to improve the diversity of population.Experimental result shows that the algorithm has advantages to solve this problem.

Mixed no-idle permutation flowshop scheduling problem Estimation of distribution algorithm Heuristic algorithm Tabu algorithm

2015-09-03。遼寧省教育廳科學研究項目(L2015265)。張曉霞，教授，主研領域：智能優(yōu)化算法，組合優(yōu)化問題。呂云虹，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.01.049