隨機工時下的多目標柔性作業(yè)車間魯棒調度問題

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

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

?

隨機工時下的多目標柔性作業(yè)車間魯棒調度問題

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

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

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

關鍵詞：隨機工時；柔性作業(yè)車間；多目標；魯棒對等模型

0引言

柔性作業(yè)車間調度問題(flexiblejob-shopschedulingproblem，FJSP)對經典作業(yè)車間調度問題(job-shopschedulingproblem，JSP)進行了擴展，近年來引起了眾多學者的關注。目前，對確定條件下調度問題的研究很多，對不確定條件下的調度問題的研究較少，對不確定條件下多目標調度問題的研究更少，本文主要研究加工時間不確定條件下的多目標FJSP。

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

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

1隨機工時下的多目標FJSP模型

1.1多目標FJSP數學模型

隨機工時下的多目標柔性作業(yè)車間調度問題模型：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

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

1.2魯棒對等模型

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

(8)

(9)

式中，φ為足夠小的正實數。為研究方便，將式(8)、式(9)簡寫成通用表達形式：

Ax+By≤P

(10)

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

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

考慮到不確定變量圍繞理論值波動，故可用理論值部分和隨機波動部分來表示不確定變量A、B和P[9]：

(11)

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

(12)

對應的逆函數為F-1(ξ)，其分位點λ關于κ的表達式為λ=F-1(1-κ)。

(13)

綜上所述，含有不確定加工時間的FJSP模型可轉換成加工時間波動部分服從標準正態(tài)分布的魯棒對等模型。

2算法設計

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

2.1多目標變異操作

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

(14)

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

(15)

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

2.2局部搜索策略

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

圖1　局部搜索流程圖

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

圖2　鄰域結構S1

圖3　鄰域結構S2、S3、S4

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

3實驗數據及分析

3.1算法參數分析

表1　4×5 FJSP加工時間表

圖4　不確定參數對加工時間的影響

圖5　不確定參數對機器總負荷的影響

圖6　不確定參數對關鍵機器負荷的影響

在各種不確定情形中，完工時間、關鍵機器負荷及機器總負荷均值的變化曲線如圖4～圖6所示。分析圖4～圖6中曲線可知，魯棒對等問題的最優(yōu)解都大于確定條件下的最優(yōu)解，這是因為魯棒方案吸收了加工時間的擾動量。同時，隨著不確定水平的增大，3個目標函數的值平穩(wěn)增長，說明加工時間中存在的不確定因素對3個目標函數值的影響很大；隨著約束條件不可行限度κ的增大，目標函數值逐漸減小，即工時擾動對調度目標的影響減小，說明了約束條件允許違背程度與性能損失之間存在著一定的折中。此外，當加工時間波動程度ε較小且約束條件的允許違背程度κ較大時，魯棒對等問題與原確定型問題的最優(yōu)解較接近，吸收不確定擾動所需冗余較小，調度方案的性能損失最小。ε=0.15時，魯棒對等問題的目標函數值比原確定問題的大很多，說明其需要很大的冗余來吸收隨機波動才能確?？尚行裕瑢е抡{度方案的性能損失大。參考文獻[9-10]及本文的算法實例，確定本文2個不確定參數ε=0.1，κ=0.15。

3.2算法性能分析

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

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

表4　Kacem案例結果比較　s

表5　Brandimarte案例結果比較

4結語

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

參考文獻：

[1]于曉義,孫樹棟,王彥革.面向隨機加工時間的車間作業(yè)調度[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]徐震浩, 顧幸生. 不確定條件下具有零等待的流水車間免疫調度算法[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]唐秋華, 何明, 何曉霞,等. 隨機工時下柔性加工車間的魯棒優(yōu)化調度方法[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]汪雙喜, 張超勇, 劉瓊,等. 不同再調度周期下的柔性作業(yè)車間動態(tài)調度[J]. 計算機集成制造系統(tǒng), 2014, 20(10): 2470-2478.

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

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

[14]王凌.智能優(yōu)化算法及其應用[M].北京：清華大學出版社，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]劉煒琪,劉瓊，張超勇，等. 基于混合粒子群算法求解多目標混流裝配線排序[J].計算機集成制造系統(tǒng), 2011, 17(12): 2590-2598.

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

(編輯張洋)

收稿日期：2015-06-02

基金項目：國家自然科學基金資助項目(51275190)；中央高校基本科研業(yè)務費資助項目(2014TS038)；湖北省自然科學基金資助項目(2013CFB025)

中圖分類號：TP18

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

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

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