張曉霞 呂云虹

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

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

張曉霞 呂云虹

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

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

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

0 引 言

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

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

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

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

1 MNPFSP問(wèn)題的描述

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

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

(1)

(2)

(3)

(4)

Cmax(π)=Cm,[n]

(6)

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

2 分布估計(jì)算法

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

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

(2) 計(jì)算個(gè)體的適應(yīng)值，選擇群體中的優(yōu)勢(shì)群體。

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

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

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

3 改進(jìn)的分布估計(jì)算法求解MNPFSP

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

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

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

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

(1) 計(jì)算工件i在各個(gè)機(jī)器上的總的加工時(shí)間；

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

(3) 取位于順序的前兩個(gè)工件，使部分最大流程時(shí)間達(dá)到極?。?/p>

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

3.2 計(jì)算適應(yīng)值選擇優(yōu)勢(shì)群體

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

3.3 建立概率模型

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

(7)

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

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

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

(8)

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

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

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

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

3.5 更新概率模型

(9)

4 鄰域搜索策略

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

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

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

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

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

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

針對(duì)MNPFSP的特性將每個(gè)測(cè)試實(shí)例分為7種問(wèn)題進(jìn)行測(cè)試：

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

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

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

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

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

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

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

七種情況的的測(cè)試結(jié)果如表1和表2所示。

表1 前三種情況的測(cè)試結(jié)果

表2 后四種情況的測(cè)試結(jié)果

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

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

表3 四種算法的對(duì)比結(jié)果

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

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

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

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

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

圖2 TEDA算法的收斂曲線

6 結(jié) 語(yǔ)

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

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

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

[3] 張麗萍.改進(jìn)的蟻群算法求解置換流水車間調(diào)度問(wèn)題[J].微型機(jī)與應(yīng)用,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] 張鳳超.改進(jìn)的分布估計(jì)算法求解混合流水車間調(diào)度問(wèn)題研究[J].軟件導(dǎo)刊,2014,13(8):23-26.

[7] 周樹(shù)德，孫增圻.分布估計(jì)算法綜述[J].自動(dòng)化學(xué)報(bào),2007，33(2)：113-124.

[8] 吳紅，王維平，王磊，等.分布估計(jì)算法在巡航導(dǎo)彈航跡規(guī)劃中的應(yīng)用[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問(wèn)題的啟發(fā)式算法[J].系統(tǒng)工程理論與實(shí)踐,2000,20(9)：41-47.

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

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

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

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

[15] 王亞敏，冀俊忠，潘全科.基于離散蛙跳算法的零空閑流水線調(diào)度問(wèn)題的求解[J].北京工業(yè)大學(xué)學(xué)報(bào)，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。遼寧省教育廳科學(xué)研究項(xiàng)目(L2015265)。張曉霞，教授，主研領(lǐng)域：智能優(yōu)化算法，組合優(yōu)化問(wèn)題。呂云虹，碩士生。

TP3

A

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