朱傳軍　邱　文　朱孟周　陳　光　張超勇

1.湖北工業(yè)大學(xué)，武漢，430068　　2.江蘇省電力公司電力科學(xué)研究院，南京，2111033.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

?

隨機(jī)工時(shí)下的多目標(biāo)柔性作業(yè)車(chē)間魯棒調(diào)度問(wèn)題

朱傳軍1邱文1朱孟周2陳光2張超勇3

1.湖北工業(yè)大學(xué)，武漢，4300682.江蘇省電力公司電力科學(xué)研究院，南京，2111033.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

摘要：針對(duì)工時(shí)不確定條件下的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題，采用2個(gè)不確定參數(shù)描述隨機(jī)工時(shí)的波動(dòng)程度和約束條件允許違背程度，將不確定條件下的柔性作業(yè)車(chē)間調(diào)度問(wèn)題模型轉(zhuǎn)換成確定條件下的魯棒對(duì)等問(wèn)題模型。在算法設(shè)計(jì)中采用全局非支配解集保存每代進(jìn)化過(guò)程中產(chǎn)生的非支配解，并選擇全局非支配解集中的個(gè)體參與變異操作。在交叉和變異操作之后，設(shè)計(jì)了一種基于變鄰域結(jié)構(gòu)的局部搜索策略。最后，運(yùn)用該算法求解經(jīng)典基準(zhǔn)算例，驗(yàn)證了其有效性。

關(guān)鍵詞：隨機(jī)工時(shí)；柔性作業(yè)車(chē)間；多目標(biāo)；魯棒對(duì)等模型

0引言

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(flexiblejob-shopschedulingproblem，F(xiàn)JSP)對(duì)經(jīng)典作業(yè)車(chē)間調(diào)度問(wèn)題(job-shopschedulingproblem，JSP)進(jìn)行了擴(kuò)展，近年來(lái)引起了眾多學(xué)者的關(guān)注。目前，對(duì)確定條件下調(diào)度問(wèn)題的研究很多，對(duì)不確定條件下的調(diào)度問(wèn)題的研究較少，對(duì)不確定條件下多目標(biāo)調(diào)度問(wèn)題的研究更少，本文主要研究加工時(shí)間不確定條件下的多目標(biāo)FJSP。

目前，工時(shí)不確定因素通常有隨機(jī)數(shù)[1-3]、模糊數(shù)[4-5]和區(qū)間數(shù)[6-7]三類描述方法。隨機(jī)數(shù)和模糊數(shù)方法都依賴于事先獲得的大量樣本數(shù)據(jù)，受車(chē)間實(shí)際生產(chǎn)中數(shù)據(jù)采集手段、統(tǒng)計(jì)方法和工作量等實(shí)際因素的影響，工序加工時(shí)間的大量樣本數(shù)的獲得較為困難。區(qū)間數(shù)方法無(wú)需考慮區(qū)間內(nèi)的具體取值或分布規(guī)律，適用性和可操作性較好。該方法雖能得出具有一定可行性的調(diào)度方案，但是調(diào)度方案本身的魯棒性不強(qiáng)，對(duì)加工過(guò)程中隨機(jī)擾動(dòng)的抗干擾能力較差。為進(jìn)一步提高調(diào)度方案的魯棒性，Janak等[8]針對(duì)化工生產(chǎn)過(guò)程中出現(xiàn)的工時(shí)不確定、產(chǎn)品需求不確定及市場(chǎng)價(jià)格不確定等不確定因素提出了一種新的魯棒優(yōu)化方法。唐秋華等[9]在文獻(xiàn)[5]的基礎(chǔ)上引入2個(gè)不確定參數(shù)描述隨機(jī)工時(shí)的波動(dòng)程度和約束條件允許違背程度，成功將魯棒優(yōu)化方法應(yīng)用到單目標(biāo)FJSP中。

筆者依據(jù)實(shí)際生產(chǎn)情況，針對(duì)工時(shí)不確定條件下的多目標(biāo)FJSP，建立隨機(jī)工時(shí)下的多目標(biāo)柔性作業(yè)車(chē)間魯棒對(duì)等問(wèn)題模型，以最小化最大完工時(shí)間，機(jī)器總負(fù)荷和關(guān)鍵機(jī)器負(fù)荷為優(yōu)化目標(biāo)，設(shè)計(jì)了一種基于Pareto優(yōu)化的改進(jìn)多目標(biāo)差分算法(P-IDE)求解該問(wèn)題。

1隨機(jī)工時(shí)下的多目標(biāo)FJSP模型

1.1多目標(biāo)FJSP數(shù)學(xué)模型

隨機(jī)工時(shí)下的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題模型：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

式(2)表示機(jī)器分配約束條件，即每道工序需且僅需分給一臺(tái)機(jī)器加工；式(3)表示各工件的前道工序完工后才能安排其后續(xù)工序；式(4)表示每道工序一旦開(kāi)始，加工就不能中斷；式(5)表示同一機(jī)器上只有在前道工序完工后，才能安排后續(xù)工序加工；式(6)、式(7)表示各工序完工時(shí)間與各機(jī)器事件點(diǎn)之間的一一對(duì)應(yīng)關(guān)系。

1.2魯棒對(duì)等模型

為將魯棒優(yōu)化技術(shù)用于上述含有不確定參數(shù)的約束條件，應(yīng)將上述模型中的等式約束消除，本文采用文獻(xiàn)[7]提出的方法，松弛式(4)中的等式約束并改寫(xiě)式(5)，得到適合采用魯棒優(yōu)化技術(shù)的不等式約束：

(8)

(9)

式中，φ為足夠小的正實(shí)數(shù)。為研究方便，將式(8)、式(9)簡(jiǎn)寫(xiě)成通用表達(dá)形式：

Ax+By≤P

(10)

式中，x為連續(xù)變量；y為0-1變量；A、B為系數(shù)矩陣；P為列向量。

此處的參數(shù)不確定泛指在A、B和P中都可能存在不確定。

考慮到不確定變量圍繞理論值波動(dòng)，故可用理論值部分和隨機(jī)波動(dòng)部分來(lái)表示不確定變量A、B和P[9]：

(11)

為實(shí)現(xiàn)調(diào)度方案與約束條件允許違背程度之間的一種折中，用折中參數(shù)κ來(lái)描述約束條件的允許違背程度，則1-κ表示不等式成立的概率，此時(shí)得出的解被稱為約束條件違背程度為κ時(shí)的魯棒解[9]。假設(shè)隨機(jī)變量ξa、ξb、ξp服從標(biāo)準(zhǔn)正態(tài)分布，即ξ∈N(0，1)，其概率分布函數(shù)為

(12)

對(duì)應(yīng)的逆函數(shù)為F-1(ξ)，其分位點(diǎn)λ關(guān)于κ的表達(dá)式為λ=F-1(1-κ)。

(13)

綜上所述，含有不確定加工時(shí)間的FJSP模型可轉(zhuǎn)換成加工時(shí)間波動(dòng)部分服從標(biāo)準(zhǔn)正態(tài)分布的魯棒對(duì)等模型。

2算法設(shè)計(jì)

針對(duì)多目標(biāo)FJSP，本文提出基于Pareto優(yōu)化的改進(jìn)差分算法，提出了新的變異操作和變鄰域局部搜索策略。

2.1多目標(biāo)變異操作

本文改進(jìn)Xue等[11]提出的多目標(biāo)差分變異操作，采用基于Pareto的優(yōu)化方法，在每代進(jìn)化過(guò)程中將得到當(dāng)前種群的非支配解集Dg(g=1，2，…，gmax，其中，g、gmax分別為種群的當(dāng)前代數(shù)和最大進(jìn)化代數(shù))和一個(gè)進(jìn)化到當(dāng)前代的全局非支配解集D(用來(lái)保存進(jìn)化到當(dāng)前代數(shù)為止的每個(gè)全局非支配解xbest)。由于當(dāng)前種群的非支配解集Dg中的個(gè)體往往能被全局非支配解集D中的個(gè)體支配[12]，因此在進(jìn)行多目標(biāo)變異操作時(shí)，首先從當(dāng)前群體中隨機(jī)選擇3個(gè)不同的向量xig、xri,1、xri,2，然后判斷向量xig是否為全局非支配解集D中的非支配解，若是，則按式(14)進(jìn)行變異操作。

(14)

反之，則從全局非支配解集D中隨機(jī)選擇一個(gè)向量xbest參與變異操作：

(15)

其中，Vig為變異后的向量；參數(shù)F為縮放因子；λ(0≥λ≥1)為貪婪因子，λ越接近1，xbest所占比重越大，λ越接近0，xig所占比重越大。經(jīng)測(cè)試發(fā)現(xiàn)，改進(jìn)后的變異操作充分利用到全局的非支配解集D，提高了解的質(zhì)量[12]。

2.2局部搜索策略

對(duì)群體中的個(gè)體進(jìn)行交叉和變異操作能有效提高算法的尋優(yōu)能力，但是算法在進(jìn)化過(guò)程中易提前收斂。局部搜索算法可以有效地改善解的質(zhì)量，避免算法收斂到局部最優(yōu)。每個(gè)子代以一定的概率進(jìn)行局部搜索。變鄰域局部搜索算法具體步驟如圖1所示，圖中，Pl為算法的局部搜索概率。

圖1　局部搜索流程圖

鄰域結(jié)構(gòu)設(shè)計(jì)是局部搜索算法的關(guān)鍵部分。本文采用4種類型的鄰域結(jié)構(gòu)(這4種鄰域結(jié)構(gòu)在很多文獻(xiàn)中被證明是有效的[13-14])，分別記為S1、S2、S3和S4。本文中，染色體編碼由機(jī)器碼和工序碼兩部分組成，根據(jù)染色體編碼方式，鄰域結(jié)構(gòu)S1僅對(duì)機(jī)器選擇部分進(jìn)行鄰域更新。隨機(jī)選擇一個(gè)機(jī)器染色體上的基因，則該位置對(duì)應(yīng)工序的可選擇機(jī)器都是此基因位的鄰域，如圖2所示。鄰域結(jié)構(gòu)S1僅對(duì)機(jī)器選擇部分進(jìn)行鄰域更新。隨機(jī)選擇機(jī)器碼中的一個(gè)基因，則該位置對(duì)應(yīng)工序的可選機(jī)器都是此基因位的鄰域，如圖2所示。鄰域結(jié)構(gòu)S2、S3、S4均對(duì)工序染色體部分進(jìn)行鄰域更新，這3種鄰域結(jié)構(gòu)分別是交換、反向和插入，圖3為鄰域結(jié)構(gòu)S2、S3和S4的示意圖。

圖2　鄰域結(jié)構(gòu)S1

圖3　鄰域結(jié)構(gòu)S2、S3、S4

測(cè)試發(fā)現(xiàn)，融入了以上4種鄰域結(jié)構(gòu)的局部搜索策略增強(qiáng)了局部搜索算法的性能，有效地避免了搜索結(jié)果陷入局部最優(yōu)解[13]。

3實(shí)驗(yàn)數(shù)據(jù)及分析

3.1算法參數(shù)分析

表1　4×5 FJSP加工時(shí)間表

圖4　不確定參數(shù)對(duì)加工時(shí)間的影響

圖5　不確定參數(shù)對(duì)機(jī)器總負(fù)荷的影響

圖6　不確定參數(shù)對(duì)關(guān)鍵機(jī)器負(fù)荷的影響

在各種不確定情形中，完工時(shí)間、關(guān)鍵機(jī)器負(fù)荷及機(jī)器總負(fù)荷均值的變化曲線如圖4～圖6所示。分析圖4～圖6中曲線可知，魯棒對(duì)等問(wèn)題的最優(yōu)解都大于確定條件下的最優(yōu)解，這是因?yàn)轸敯舴桨肝樟思庸r(shí)間的擾動(dòng)量。同時(shí)，隨著不確定水平的增大，3個(gè)目標(biāo)函數(shù)的值平穩(wěn)增長(zhǎng)，說(shuō)明加工時(shí)間中存在的不確定因素對(duì)3個(gè)目標(biāo)函數(shù)值的影響很大；隨著約束條件不可行限度κ的增大，目標(biāo)函數(shù)值逐漸減小，即工時(shí)擾動(dòng)對(duì)調(diào)度目標(biāo)的影響減小，說(shuō)明了約束條件允許違背程度與性能損失之間存在著一定的折中。此外，當(dāng)加工時(shí)間波動(dòng)程度ε較小且約束條件的允許違背程度κ較大時(shí)，魯棒對(duì)等問(wèn)題與原確定型問(wèn)題的最優(yōu)解較接近，吸收不確定擾動(dòng)所需冗余較小，調(diào)度方案的性能損失最小。ε=0.15時(shí)，魯棒對(duì)等問(wèn)題的目標(biāo)函數(shù)值比原確定問(wèn)題的大很多，說(shuō)明其需要很大的冗余來(lái)吸收隨機(jī)波動(dòng)才能確保可行性，導(dǎo)致調(diào)度方案的性能損失大。參考文獻(xiàn)[9-10]及本文的算法實(shí)例，確定本文2個(gè)不確定參數(shù)ε=0.1，κ=0.15。

3.2算法性能分析

本文從算法的求解質(zhì)量和解的數(shù)量來(lái)驗(yàn)證其有效性。以最大完工時(shí)間、機(jī)器總負(fù)荷和最大機(jī)器負(fù)荷為調(diào)度目標(biāo)，利用所提出的基于Pareto優(yōu)化的改進(jìn)差分(P-IDE)算法，求解各種標(biāo)桿案例(3個(gè)Kacem案例和6個(gè)Brandimarte案例)在ε=0.1、κ=0.15的魯棒對(duì)等問(wèn)題。同時(shí)，將本文算法與幾種多目標(biāo)算法(PSO+SA[15]、HPSO[16]、P-DABC[17]、MOPSO-LS[18]、SM[19-20])進(jìn)行比較，得到表4、表5所示的統(tǒng)計(jì)結(jié)果。表4、表5中，f1、f2、f3為目標(biāo)函數(shù)；C1、C2分別表示使用P-IDE算法求解確定型問(wèn)題和ε=0.1、κ=0.15時(shí)的魯棒對(duì)等問(wèn)題所得解，t1、t2分別為用P-IDE算法求解確定型問(wèn)題和ε=0.1、κ=0.15的魯棒對(duì)等問(wèn)題時(shí)連續(xù)運(yùn)行10次得到的平均運(yùn)行時(shí)間。

分析表4中數(shù)據(jù)可知，對(duì)于3個(gè)Kacem案例，P-IDE獲得的非支配解等于或者小于其他4種算法得到的非支配解， P-IDE算法計(jì)算8×8問(wèn)題時(shí)得到目標(biāo)函數(shù)值分別為f1=14 s，f2=77 s，f3=12 s；10×10問(wèn)題時(shí)得到目標(biāo)函數(shù)值f1=7 s，f2=42 s，f3=6 s；15×10問(wèn)題時(shí)得到目標(biāo)函數(shù)值f1=11 s，f2=91 s，f3=11 s。分析表5中數(shù)據(jù)可知，對(duì)于6個(gè)Brandimarte案例，與SM算法比較，P-IDE算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題時(shí)在解的質(zhì)量上有較大提高，且非支配解的數(shù)量明顯比SM算法多。

表4　Kacem案例結(jié)果比較　s

表5　Brandimarte案例結(jié)果比較

4結(jié)語(yǔ)

針對(duì)具有隨機(jī)加工時(shí)間的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題，本文建立了加工時(shí)間服從標(biāo)準(zhǔn)正態(tài)分布的魯棒對(duì)等問(wèn)題模型，設(shè)計(jì)了基于Pareto優(yōu)化的改進(jìn)差分進(jìn)化(P-IDE)算法。在該算法中，采用了基于全局非支配解的多目標(biāo)變異操作，同時(shí)，為平衡算法的局部搜索能力和全局搜索能力，提出了融入4種鄰域結(jié)構(gòu)的變鄰域局部搜索策略。最后，用P-IDE算法測(cè)試6組Brandimarte標(biāo)桿案例和3組Kacem案例。測(cè)試結(jié)果表明：(1)P-IDE算法在求解相同規(guī)模確定型問(wèn)題時(shí)，比其他算法具有更高的效率；(2)在求解魯棒對(duì)等問(wèn)題時(shí)，對(duì)于每個(gè)基準(zhǔn)案例，當(dāng)加工時(shí)間存在不確定擾動(dòng)時(shí)，P-IDE算法的運(yùn)行時(shí)間比確定條件下的運(yùn)行時(shí)間略長(zhǎng)，說(shuō)明算法能快速有效地處理不確定擾動(dòng)；(3)隨著問(wèn)題規(guī)模的增大，P-IDE算法在求解確定型問(wèn)題和魯棒對(duì)等問(wèn)題時(shí)仍能得出質(zhì)量較好且數(shù)量較多的非支配解，說(shuō)明所提出算法對(duì)大規(guī)模問(wèn)題同樣具有較好的處理能力。當(dāng)隨機(jī)工時(shí)的波動(dòng)程度ε和約束條件允許違背程度κ不確定時(shí)，所提魯棒優(yōu)化調(diào)度方法可在一定的運(yùn)行時(shí)間內(nèi)，以較低的性能損失獲得最優(yōu)解。

參考文獻(xiàn)：

[1]于曉義,孫樹(shù)棟,王彥革.面向隨機(jī)加工時(shí)間的車(chē)間作業(yè)調(diào)度[J].中國(guó)機(jī)械工程,2008,19(19):2319-2324.

YuXiaoyi,SunShudong,WangYange.ResearcheonStochasticProcessingTimeOrientedJob-shopScheduling[J].ChinaMechanicalEngineering, 2008, 19(19): 2319-2324

[2]HonkompSJ,MockusL,ReklaitisGV.RobustSchedulingwithProcessingTimeUncertainty[J].Computers&ChemicalEngineering, 1997, 21(10):S1055-S1060.

[3]BonfillA,EspuaA,PuigjanerL.ProactiveApproachtoAddresstheUncertaintyinShort-termScheduling[J].Computers&ChemicalEngineering, 2008, 32(8): 1689-1706.

[4]徐震浩, 顧幸生. 不確定條件下具有零等待的流水車(chē)間免疫調(diào)度算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2004, 10(10):1247-1251.

XuZhenghao,GuXingsheng.ImmuneSchedulingAlgorithmforFlowShopunderUncertaintywithZeroWait[J].ComputerIntergratedManufacturingSystems, 2004,10(10):1247-1252.

[5]HeC,QiuD,GuoH.SolvingFuzzyJobShopSchedulingProblemBasedonIntervalNumberTheory[J].LectureNotesinElectricalEngineering, 2013, 211:393-401.

[6]LeiD.Population-basedNeighborhoodSearchforJobShopSchedulingwithIntervalProcessingTime[J].Computers&IndustrialEngineering, 2011, 61(4): 1200-1208.

[7]LeiD.IntervalJobShopSchedulingProblems[J].InternationalJournalofAdvancedManufacturingTechnology, 2012, 60(1/4):291-302.

[8]JanakSL,LinX,FloudasCA.ANewRobustOptimizationApproachforSchedulingunderUncertainty:II.UncertaintywithKnownProbabilityDistribution[J].Computers&ChemicalEngineering, 2007, 31(3):171-195.

[9]唐秋華, 何明, 何曉霞,等. 隨機(jī)工時(shí)下柔性加工車(chē)間的魯棒優(yōu)化調(diào)度方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2015, 21(4):1002-1012.

TangQiuhua,HeMing,HeXiaoxia,etal.RobustOptimizationSchedulingofFlexibleJobShopsunderStochasticProcessingTimes[J].ComputerIntegratedManufacturingSystems,2015,21(4):1002-1012.

[10]LinX,JanakSL,FloudasCA.ANewRobustOptimizationApproachforSchedulingunderUncertainty:I.BoundedUncertainty[J].Computers&ChemicalEngineering, 2004, 28(6/7):1069-1085.

[11]XueF,SandesonAC,GravesRJ.Pareto-basedMulti-objectiveDifferentialEvolution[C]//Proceedingsofthe2003CongressonEvolutionaryComputation.WashingtonDC, 2003:862-869.

[12]汪雙喜, 張超勇, 劉瓊,等. 不同再調(diào)度周期下的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2014, 20(10): 2470-2478.

WangShuangxi,ZhangChaoyong,LiuQiong,etal.FlexibleJobShopDynamicSchedulingunderDifferentReschedulePeriods[J].ComputerIntegratedManufacturingSystems,2015,21(4):1002-1012.

[13]張利平.作業(yè)車(chē)間預(yù)反應(yīng)式動(dòng)態(tài)調(diào)度理論與方法研究：[D]. 武漢：華中科技大學(xué)，2013.

[14]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001.

[15]XiaWJ,WuZM.AnEffectiveHybridOptimizationApproachforMulti-objectiveFlexibleJobShopSchedulingProblems[J].Computers&IndustrialEngineering, 2005,48(2): 409-425.

[16]MurataT,IshibuchiH,GenM.Multi-objectiveFuzzySchedulingwiththeOWAOperatorfor

HandlingDifferentSchedulingCriteriaandDifferentJobImportance[C]//IEEEInternationalFuzzySystemsConferenceProceedings.Seoul, 1999:773-778.

[17]LiJQ,PanQK,GaoKZ.Pareto-basedDiscreteArtificialBeeColonyAlgorithmforMulti-objectiveFlexibleJob-shopSchedulingProblems[J].InternationalJournalofAdvancedManufacturingTechnology,2011,55: 1159-1169.

[18]MoslehiG,MahnamM.AParetoApproachtoMulti-objectiveFlexibleJob-shopSchedulingProblemUsingParticleSwarmOptimizationandLocalSearch[J].InternationalJournalofProductionEconomics, 2011,129(1): 14-22.

[19]SakawaM,KubotaR.FuzzyProgrammingforMulti-objectiveJobShopSchedulingwithFuzzyProcessingTimeandFuzzydueDateThroughGeneticAlgorithm[J].EuropeanJournalofOperationalResearch, 2000,120(2):393-407.

[20]劉煒琪,劉瓊，張超勇，等. 基于混合粒子群算法求解多目標(biāo)混流裝配線排序[J].計(jì)算機(jī)集成制造系統(tǒng), 2011, 17(12): 2590-2598.

LiuWeiqi,LiuQiong,ZhangChaoyong,etal.HybridParticleSwarmOptimizationforMulty-objectiveSequencingProbleminMixedModelAssemblyLines[J].ComputerIntegratedManufacturingSystems, 2011, 17(12): 2590-2598.

(編輯張洋)

收稿日期：2015-06-02

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(51275190)；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(2014TS038)；湖北省自然科學(xué)基金資助項(xiàng)目(2013CFB025)

中圖分類號(hào)：TP18

DOI：10.3969/j.issn.1004-132X.2016.12.019

作者簡(jiǎn)介：朱傳軍，男，1971年生。湖北工業(yè)大學(xué)機(jī)械工程學(xué)院副教授。主要研究方向?yàn)橹圃煨畔?、智能調(diào)度算法、決策分析等。邱文(通信作者)，女，1989年生。湖北工業(yè)大學(xué)械工程學(xué)院碩士研究生。朱孟周，男，1982年生。江蘇省電力公司電力科學(xué)研究院工程師、博士。陳光，男，1986年生。江蘇省電力公司電力科學(xué)研究院工程師。張超勇，男，1972年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院副教授。

Multi-objectiveFlexibleJobShopsRobustSchedulingProblemunderStochasticProcessingTimes

ZhuChuanjun1QiuWen1ZhuMengzhou2ChenGuang2ZhangChaoyong3

1.HubeiUniversityofTechnology,Wuhan，430068 2.ElectricPowerResearchInstituteofJiangsuElectricPowerCompany,Nanjing, 211103 3.StateKeyLaboratoryofDigitalManufacturingEquipment&Technology，HuazhongUniversityofScienceandTechnology,Wuhan，430074

Abstract:Multi-objective flexible job shop schedule problem with uncertain processing time was studied. Two uncertain parameters were adopted to describe the degree of disturbance volatility and allowable constraints violence respectively. A robust optimization approach to translate multi-objective flexible job shop scheduling problem into deterministic robust counterpart problem was proposed. A set of global non-dominated solution was adopted to preserve the best solutions in every generation, and the solution which in the set was selected to participate in the mutation operation. After crossover and mutation, a local search strategy was proposed based on neighborhood structure. Several benchmark problems were handled by the algorithm, the results indicate that it is effective for such problem.

Key words:rand process time; flexible job shop; multi-objective; robust counterpart model