蘇志雄，伊俊敏

(廈門理工學(xué)院管理學(xué)院， 福建 廈門 361024)

求解置換流水車間調(diào)度問題的Memetic算法

蘇志雄，伊俊敏

(廈門理工學(xué)院管理學(xué)院， 福建 廈門 361024)

針對(duì)以最小化最大完工時(shí)間為目標(biāo)的置換流水車間調(diào)度問題，建立了0-1型混合整數(shù)線性規(guī)劃模型。在對(duì)模型進(jìn)行Benders分解的基礎(chǔ)上，提出了問題的求解策略，進(jìn)而設(shè)計(jì)了一種Memetic調(diào)度算法，并探討了基于組合規(guī)則的種群初始化方法和混合遺傳操作。為了提高算法的搜索效率，采用了更加高效的適應(yīng)度值計(jì)算方法以及兩種鄰域搜索方法。最后，基于Benchmark算例的仿真實(shí)驗(yàn)結(jié)果表明了該算法的有效性，可以找到26個(gè)算例中的17個(gè)最優(yōu)解(65.38%)，且其平均相對(duì)誤差的均值僅為0.88%。

生產(chǎn)調(diào)度；置換流水車間；Memetic算法；鄰域搜索

由于此類調(diào)度問題的NP難特性[1]，精確算法只能求解很小規(guī)模的算例，而啟發(fā)式算法[2-5]可以在很短的時(shí)間內(nèi)獲得調(diào)度解，但是其求解質(zhì)量和通用性較差。因此，近期的研究重點(diǎn)更多地集中在元啟發(fā)式算法[6-11]。遺傳算法作為一種常用的元啟發(fā)式算法，具有魯棒性、通用性、隱含并行性等特點(diǎn)，在求解PFSP上取得了較好的效果。然而，傳統(tǒng)的遺傳算法存在進(jìn)化停滯和計(jì)算時(shí)間長(zhǎng)等問題，故本文在問題分析和已有算法研究的基礎(chǔ)上，提出了一種將遺傳算法與鄰域搜索相結(jié)合的Memetic算法(memeticalgorithm,MA)，其關(guān)鍵在于種群初始化策略、遺傳操作、鄰域搜索算法的設(shè)計(jì)。最后，通過基于benchmark算例的對(duì)比實(shí)驗(yàn)對(duì)其有效性進(jìn)行了驗(yàn)證。

一、 PFSP的數(shù)學(xué)模型

1.符號(hào)說明

為了敘述方便，引入下列符號(hào)：i為機(jī)器編號(hào)，i∈{1,…,m}；j為工件編號(hào)，j∈{1,…,n}；k為排列中的位置編號(hào)，k∈{1,…,n}；π為所有工件的一個(gè)排列，即工件加工順序方案，π={π1,π2,…,πn}；pij為工件j在機(jī)器i上的加工時(shí)間；Pik為工件πk在機(jī)器i上的加工時(shí)間；xjk為1，如果工件j位于排列π中的第k個(gè)位置，否則為0；Cik為工件πk在機(jī)器i上的完工時(shí)間；Cmax為最大完工時(shí)間，即makespan。

2.模型的建立

基于上述符號(hào)說明，本文建立如下所示的0-1型混合整數(shù)線性規(guī)劃模型(以下稱為[P]模型)：

minCmax，

(1)

s.t.Cmax=Cmn，

(2)

Cik≥Ci,k-1+Pik,?i,k，

(3)

Cik≥Ci-1,k+Pik,?i,k，

(4)

(5)

(6)

(7)

xjk∈{0,1},?j,k，

(8)

Cik≥0,?i,k;Ci0=0，?i;C0k=0，?k。

(9)

上述模型中：式(1)表示目標(biāo)函數(shù)為最小化最大完工時(shí)間；約束(2)表示最后一個(gè)工件在最后一個(gè)機(jī)器上的完工時(shí)間為Cmax；約束集(3)表示資源約束，即在同一機(jī)器上前一工件加工完，下一工件才能開始加工；約束集(4)表示同一工件前一道工序完成后下一道工序才能開始；約束集(5)表示pij與Pik之間的關(guān)系，Pik取決于排序變量xjk；約束集(6)表示排列中的每一位置有且僅有一個(gè)工件；約束集(7)表示每一個(gè)工件有且僅有一個(gè)位置；約束集(8)～(9)表示變量的取值范圍。

二、 模型的求解思路

根據(jù)Benders分解[12]，將模型[P]的所有變量分成二元變量、連續(xù)變量?jī)刹糠?固定二元變量x，令v(x)=min{(1)|(2)-(5),9}，則模型[P]可以表示為以下等價(jià)形式(以下稱為[P1]模型)：

minv(x)，

s.t.(6)-(8)。

[P1]稱為原問題[P]的投影問題，二元變量x稱為投影變量。若給定[P1]的一個(gè)可行解，則工件加工順序方案π被唯一確定，進(jìn)而可以確定工件π(k)在機(jī)器i上的加工時(shí)間Pik；此時(shí)，可以通過求解下述線性規(guī)劃模型來計(jì)算v(x)(以下稱為[P2]模型)：

minCmax，

s.t.(2)-(5),(9)。

由上述模型分解可以看出：[P1]的每個(gè)可行解都對(duì)應(yīng)著一個(gè)工件加工順序方案；給定[P1]的一個(gè)可行解，通過求解子問題[P2]可以確定最優(yōu)完工時(shí)間進(jìn)而得到完整的調(diào)度解(原問題[P]的可行解)。此外，由于[P1]的可行解易于表示為染色體，可以通過Memetic算法在外層搜索遍歷二元變量空間來優(yōu)化工件加工順序；在內(nèi)層通過求解[P2]來確定滿足約束條件的最優(yōu)連續(xù)解，并以f=1/Cmax作為染色體的適應(yīng)度函數(shù)。

三、 模型的求解方法

Memetic算法是一種模擬人類文化進(jìn)化的群體智能優(yōu)化算法，是基于種群的全局搜索與基于個(gè)體的啟發(fā)式局部搜索的結(jié)合，它是元啟發(fā)式算法研究領(lǐng)域中的一個(gè)熱點(diǎn)，相應(yīng)的偽代碼見文獻(xiàn)[13]。

1.染色體編碼

編碼是Memetic算法的首要問題，本文采用排列編碼，即取所有工件編號(hào)的排列作為解的表示，比如6個(gè)待加工工件的一個(gè)加工序列{3，5，6，4，1，2}就是其相應(yīng)的編碼。

2.適應(yīng)度值計(jì)算

在算法的迭代過程中，需要對(duì)所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，即通過求解[P2]來確定相應(yīng)的適應(yīng)度值。因此，需要去求解大量的線性規(guī)劃模型，假如采用單純形法之類的常規(guī)方法進(jìn)行求解，則算法的進(jìn)化運(yùn)算過程進(jìn)展相對(duì)緩慢。對(duì)于給定的染色體，亦即確定了一個(gè)工件加工順序方案，PFSP可以用一個(gè)有向柵格圖G=(N,E)來表示，其關(guān)鍵路徑的長(zhǎng)度就是[P2]的最優(yōu)目標(biāo)函數(shù)值，進(jìn)而通過遞推公式得到的完工時(shí)間[14]是模型[P2]的一個(gè)最優(yōu)解。本文采用此種方法來計(jì)算總完工時(shí)間進(jìn)而確定染色體的適應(yīng)度值。

3.初始種群

初始種群的好壞，會(huì)對(duì)算法的搜索路徑和收斂速度產(chǎn)生影響。為了保證初始種群具有較高的質(zhì)量和多樣性，本文采用4種方法來進(jìn)行初始化。首先，由CDS[2]生成m-1個(gè)染色體：將m臺(tái)機(jī)器分組，產(chǎn)生m-1個(gè)兩臺(tái)機(jī)器的PFSP集合，進(jìn)而利用Johnson算法獲得相應(yīng)的工件加工順序方案。其余的染色體20%按照隨機(jī)規(guī)則產(chǎn)生，20%根據(jù)GRASP(貪婪水平α=0.15)構(gòu)造得到，60%通過基于NEH的GRASP[6-7](貪婪水平α=0.85)生成。

4.交叉變異算子

PFSP的遺傳調(diào)度算法針對(duì)排列編碼設(shè)計(jì)了許多成功的交叉算子，如順序交叉(ordercrossover,OX)、部分匹配交叉(partialmappedcrossover,PMX)、相似塊兩點(diǎn)順序交叉(similarblock2-pointordercrossover,SB2OX)，其中OX側(cè)重保持工件間的相對(duì)順序，PMX在保持絕對(duì)位置的同時(shí)也保證了一定的相對(duì)順序，而SB2OX在OX的基礎(chǔ)上還直接將相似塊遺傳給后代。

考慮到PMX[8]和SB2OX[9]在求解PFSP的成功經(jīng)驗(yàn)，本文提出了一種混合交叉算子，它將PMX和SB2OX結(jié)合起來，對(duì)應(yīng)的選擇概率分別為0.40、0.60。此外，本文的變異算子也采用混合算子，它將平移(shift)算子、交換(swap)算子、逆轉(zhuǎn)(inverse)算子結(jié)合起來，對(duì)應(yīng)的選擇概率分別為0.25、0.25、0.50。

5.鄰域搜索

針對(duì)PFSP的特點(diǎn)，本文采用2種鄰域搜索算法：相鄰交換鄰域搜索[4]、改進(jìn)NEH鄰域搜索。經(jīng)典的NEH算法[3]依次插入了初始排序中的n個(gè)工件，而本文的改進(jìn)NEH鄰域搜索保留前一半作為當(dāng)前排序，只是插入最后的[n/2]個(gè)工件。每一代種群中的個(gè)體均有機(jī)會(huì)進(jìn)行鄰域搜索：交叉?zhèn)€體以相同的概率來進(jìn)行選擇，而變異個(gè)體有0.20的概率進(jìn)行改進(jìn)NEH鄰域搜索。

四、仿真實(shí)驗(yàn)

為了驗(yàn)證Memetic算法求解PFSP的性能，以O(shè)R-Libray中的26個(gè)benchmark算例作為測(cè)試數(shù)據(jù)：Carlier提出的8個(gè)算例(Car1～Car8)，后18個(gè)是由Reeves提出的Rec01～Rec35。為了評(píng)價(jià)算法的性能，本文采用文獻(xiàn)[11]給出的下界C*，在此基礎(chǔ)上可以求得以下指標(biāo)：相對(duì)誤差(relativeerror,RD)，其公式為RE=(Cmax-C*)/C*×100%；最佳相對(duì)誤差(bestrelativeerror,BRE)；平均相對(duì)誤差(averagerelativeerror,ARE)；最差相對(duì)誤差(worstrelativeerror,WRE)。

1.實(shí)驗(yàn)環(huán)境

本文算法采用Matlab2014a編程實(shí)現(xiàn)，運(yùn)行環(huán)境為Win8.1、i3-4130(3.40G)/4G的一體機(jī)。算法的參數(shù)設(shè)置如下：種群大小為80，保留2個(gè)適應(yīng)度最好的子輩，交叉概率為0.70，選擇操作采用隨機(jī)遍歷抽樣算法，最大運(yùn)行代數(shù)為2mn，最大運(yùn)行時(shí)間為600s。如果在允許的時(shí)間范圍內(nèi)沒有達(dá)到下界，則將算法終止時(shí)所找到的“最好解”作為最終調(diào)度解。

2.實(shí)驗(yàn)結(jié)果及分析

針對(duì)上述26個(gè)算例，采用本文提出的MA在相同的條件下獨(dú)立運(yùn)行20次，并與NEH[3]、混合遺傳算法(hybridgeneticalgorithm,HGA)[10]、限優(yōu)遺傳算法(optimumlimitedgeneticalgorithm,OLGA)[11]進(jìn)行比較，具體如表1所示。從表1中可以看出：

表1 4種算法的計(jì)算結(jié)果比較

(1)MA具有很好的求解質(zhì)量，對(duì)于20×10及以下規(guī)模的算例均可以找到最優(yōu)解，尤其對(duì)8個(gè)Car算例都可以100%求出最優(yōu)解，而對(duì)于較大規(guī)模的算例也能夠獲得較好的近優(yōu)解，對(duì)于這26個(gè)算例，MA、HGA、OLGA分別找到了17、16、16個(gè)最優(yōu)解，對(duì)應(yīng)的最優(yōu)比率分別為65.38%、61.54%、61.54%;(2)MA具有較好的穩(wěn)定性，對(duì)較大規(guī)模算例也能保持ARE很小，其平均ARE最小，另外，MA避免陷入局部最優(yōu)點(diǎn)的能力較好，其平均WRE最小；(3)總體來說，MA遠(yuǎn)遠(yuǎn)優(yōu)于NEH、HGA，MA與OLGA各具優(yōu)勢(shì)，MA的平均ARE、平均WRE略勝0.04%、0.03%，而平均BRE略低0.07%。

五、結(jié)語

本文針對(duì)置換流水車間調(diào)度問題中的最小化最大完工時(shí)間問題展開研究，主要取得了以下成果：(1)將相鄰交換鄰域搜索、改進(jìn)NEH鄰域搜索與遺傳算法結(jié)合起來，提出了一種Memetic算法；(2)在算法設(shè)計(jì)中，充分利用已有的啟發(fā)式信息，提出了一種基于組合規(guī)則的混合策略來提高初始種群的質(zhì)量；此外，考慮到已有算子的優(yōu)點(diǎn)，提出了一種混合交叉、變異算子；(3)基于benchmark算例的實(shí)驗(yàn)結(jié)果，通過與NEH、HGA、OLGA進(jìn)行比較，驗(yàn)證了該算法在求解質(zhì)量上的優(yōu)越性。

但是，隨著問題規(guī)模的增大，鄰域搜索的計(jì)算量大大增加，進(jìn)而影響到求解質(zhì)量。下一步研究中，可通過問題規(guī)模來確定相應(yīng)的參數(shù)，在全局搜索與局部搜索之間進(jìn)行均衡。

[1]GAREYMR,JOHNSONDS,SENTHIR.Thecomplexityofflowshopandjobshopscheduling[J].MathematicsofOperationsResearch,1976,1(2):117-129.

[2]CAMPBELLHG,DUDEKRA,SMITHML.Aheuristicalgorithmforthenjob,mmachine sequencing problem[J].Management Science,1970,16(10):630-637.

[3]NAWAZM,ENSCOREE,HAMI.Aheuristicalgorithmforthem-machine,n-job flow shop sequencing problem[J].Omega,1983,11(1):91-95.

[4]DANNENBRINGDG.Anevaluationofflowshopsequencingheuristics[J].ManagementScience,1977,23(11):1 174-1 182.

[5]王正元,岑凱輝,譚躍進(jìn).求解同順序加工調(diào)度問題的一種啟發(fā)式方法[J].計(jì)算機(jī)集成制造系統(tǒng),2004,10(9):1 124-1 128.

[6]劉延鳳,劉三陽.改進(jìn)微粒群優(yōu)化求解置換流水車間調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(10):1 968-1 972,1 985.

[7]顧文斌,唐敦兵,鄭堃,等.基于激素調(diào)節(jié)機(jī)制改進(jìn)型自適應(yīng)粒子群算法在置換流水車間調(diào)度中的應(yīng)用研究[J].機(jī)械工程學(xué)報(bào),2012,48(14):177-182.

[8]CHENCL,VEMPATIVS,ALJABERN.Anapplicationofgeneticalgorithmsforflowshopproblems[J].EuropeanJournalofOperationalResearch,1995,80(2):389-396.

[9]RUIZR,MAROTOC,ALCARAZJ.Twonewrobustgeneticalgorithmsfortheflowshopschedulingproblem[J].Omega,2006,34(5):461- 476.

[10]WANGL,ZHENGDZ.Aneffectivehybridheuristicforflowshopscheduling[J].InternationalJournalofAdvancedManufacturingTechnology,2003,21(1):38- 44.

[11]李小繽,白焰,耿林霄.求解置換流水車間調(diào)度問題的改進(jìn)遺傳算法[J].計(jì)算機(jī)應(yīng)用,2013,33(12):3 576-3 579.

[12]BENDERSJF．Partitioningproceduresforsolvingmixed-variablesprogrammingproblems[J].NumerischeMathematik,1962,4(3):238- 252.

[13]劉漫丹.文化基因算法(MemeticAlgorithm)研究進(jìn)展[J].自動(dòng)化技術(shù)與應(yīng)用,2007,26(11):1- 4.

[14]PINEDOM.Schedulingtheory,algorithms,andsystem[M].2nded.NewJersey:PrenticeHall,2002:130-131.

(責(zé)任編輯 雨 松)

Memetic Algorithm for Permutation Flow Shop Scheduling Problems

SU Zhi-xiong,YI Jun-min

(School of Management,Xiamen University of Technology,Xiamen 361024,China)

A 0-1 mixed-integer linear programming model was established for the permutation flow shop scheduling with makespan criterion.Based on Benders’ decomposition,a problem solving strategy was proposed,and a Memetic algorithm designed.In designing the algorithm,a combinatorial population initialization method and a hybrid genetic operation were discussed.Further,a more efficient fitness value computation and two neighborhood search algorithms were adopted to improve searching efficiency.The final results of benchmark simulation verify the effectiveness of the proposed algorithm,which solves 17 of the 26 instances (65.38%) with the mean value of average relative error standing at only 0.88%.

production scheduling;permutation flow shop;Memetic algorithm;neighborhood search

2015-10-13

2015-11-13

國(guó)家自然科學(xué)基金項(xiàng)目(71371162)；福建省自然科學(xué)基金項(xiàng)目(2014J01271)；廈門理工學(xué)院高層次人才項(xiàng)目(YSK10009R)

蘇志雄(1980-)，男，講師，博士，研究方向?yàn)樯a(chǎn)計(jì)劃與調(diào)度、運(yùn)輸調(diào)度。E-mail:z.su@163.com

F273；TP278

A

1673-4432(2015)06-0025-05