随机工时下的多目标柔性作业车间鲁棒调度问题

朱传军　邱　文　朱孟周　陈　光　张超勇

1.湖北工业大学，武汉，430068　　2.江苏省电力公司电力科学研究院，南京，2111033.华中科技大学数字制造装备与技术国家重点实验室，武汉，430074



随机工时下的多目标柔性作业车间鲁棒调度问题

朱传军1邱文1朱孟周2陈光2张超勇3

1.湖北工业大学，武汉，4300682.江苏省电力公司电力科学研究院，南京，2111033.华中科技大学数字制造装备与技术国家重点实验室，武汉，430074

摘要：针对工时不确定条件下的多目标柔性作业车间调度问题，采用2个不确定参数描述随机工时的波动程度和约束条件允许违背程度，将不确定条件下的柔性作业车间调度问题模型转换成确定条件下的鲁棒对等问题模型。在算法设计中采用全局非支配解集保存每代进化过程中产生的非支配解，并选择全局非支配解集中的个体参与变异操作。在交叉和变异操作之后，设计了一种基于变邻域结构的局部搜索策略。最后，运用该算法求解经典基准算例，验证了其有效性。

关键词：随机工时；柔性作业车间；多目标；鲁棒对等模型

0引言

柔性作业车间调度问题(flexiblejob-shopschedulingproblem，FJSP)对经典作业车间调度问题(job-shopschedulingproblem，JSP)进行了扩展，近年来引起了众多学者的关注。目前，对确定条件下调度问题的研究很多，对不确定条件下的调度问题的研究较少，对不确定条件下多目标调度问题的研究更少，本文主要研究加工时间不确定条件下的多目标FJSP。

目前，工时不确定因素通常有随机数[1-3]、模糊数[4-5]和区间数[6-7]三类描述方法。随机数和模糊数方法都依赖于事先获得的大量样本数据，受车间实际生产中数据采集手段、统计方法和工作量等实际因素的影响，工序加工时间的大量样本数的获得较为困难。区间数方法无需考虑区间内的具体取值或分布规律，适用性和可操作性较好。该方法虽能得出具有一定可行性的调度方案，但是调度方案本身的鲁棒性不强，对加工过程中随机扰动的抗干扰能力较差。为进一步提高调度方案的鲁棒性，Janak等[8]针对化工生产过程中出现的工时不确定、产品需求不确定及市场价格不确定等不确定因素提出了一种新的鲁棒优化方法。唐秋华等[9]在文献[5]的基础上引入2个不确定参数描述随机工时的波动程度和约束条件允许违背程度，成功将鲁棒优化方法应用到单目标FJSP中。

笔者依据实际生产情况，针对工时不确定条件下的多目标FJSP，建立随机工时下的多目标柔性作业车间鲁棒对等问题模型，以最小化最大完工时间，机器总负荷和关键机器负荷为优化目标，设计了一种基于Pareto优化的改进多目标差分算法(P-IDE)求解该问题。

1随机工时下的多目标FJSP模型

1.1多目标FJSP数学模型

随机工时下的多目标柔性作业车间调度问题模型：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

式(2)表示机器分配约束条件，即每道工序需且仅需分给一台机器加工；式(3)表示各工件的前道工序完工后才能安排其后续工序；式(4)表示每道工序一旦开始，加工就不能中断；式(5)表示同一机器上只有在前道工序完工后，才能安排后续工序加工；式(6)、式(7)表示各工序完工时间与各机器事件点之间的一一对应关系。

1.2鲁棒对等模型

为将鲁棒优化技术用于上述含有不确定参数的约束条件，应将上述模型中的等式约束消除，本文采用文献[7]提出的方法，松弛式(4)中的等式约束并改写式(5)，得到适合采用鲁棒优化技术的不等式约束：

(8)

(9)

式中，φ为足够小的正实数。为研究方便，将式(8)、式(9)简写成通用表达形式：

Ax+By≤P

(10)

式中，x为连续变量；y为0-1变量；A、B为系数矩阵；P为列向量。

此处的参数不确定泛指在A、B和P中都可能存在不确定。

考虑到不确定变量围绕理论值波动，故可用理论值部分和随机波动部分来表示不确定变量A、B和P[9]：

(11)

为实现调度方案与约束条件允许违背程度之间的一种折中，用折中参数κ来描述约束条件的允许违背程度，则1-κ表示不等式成立的概率，此时得出的解被称为约束条件违背程度为κ时的鲁棒解[9]。假设随机变量ξa、ξb、ξp服从标准正态分布，即ξ∈N(0，1)，其概率分布函数为

(12)

对应的逆函数为F-1(ξ)，其分位点λ关于κ的表达式为λ=F-1(1-κ)。

(13)

综上所述，含有不确定加工时间的FJSP模型可转换成加工时间波动部分服从标准正态分布的鲁棒对等模型。

2算法设计

针对多目标FJSP，本文提出基于Pareto优化的改进差分算法，提出了新的变异操作和变邻域局部搜索策略。

2.1多目标变异操作

本文改进Xue等[11]提出的多目标差分变异操作，采用基于Pareto的优化方法，在每代进化过程中将得到当前种群的非支配解集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所占比重越大。经测试发现，改进后的变异操作充分利用到全局的非支配解集D，提高了解的质量[12]。

2.2局部搜索策略

对群体中的个体进行交叉和变异操作能有效提高算法的寻优能力，但是算法在进化过程中易提前收敛。局部搜索算法可以有效地改善解的质量，避免算法收敛到局部最优。每个子代以一定的概率进行局部搜索。变邻域局部搜索算法具体步骤如图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

测试发现，融入了以上4种邻域结构的局部搜索策略增强了局部搜索算法的性能，有效地避免了搜索结果陷入局部最优解[13]。

3实验数据及分析

3.1算法参数分析

表1　4×5 FJSP加工时间表

图4　不确定参数对加工时间的影响

图5　不确定参数对机器总负荷的影响

图6　不确定参数对关键机器负荷的影响

在各种不确定情形中，完工时间、关键机器负荷及机器总负荷均值的变化曲线如图4～图6所示。分析图4～图6中曲线可知，鲁棒对等问题的最优解都大于确定条件下的最优解，这是因为鲁棒方案吸收了加工时间的扰动量。同时，随着不确定水平的增大，3个目标函数的值平稳增长，说明加工时间中存在的不确定因素对3个目标函数值的影响很大；随着约束条件不可行限度κ的增大，目标函数值逐渐减小，即工时扰动对调度目标的影响减小，说明了约束条件允许违背程度与性能损失之间存在着一定的折中。此外，当加工时间波动程度ε较小且约束条件的允许违背程度κ较大时，鲁棒对等问题与原确定型问题的最优解较接近，吸收不确定扰动所需冗余较小，调度方案的性能损失最小。ε=0.15时，鲁棒对等问题的目标函数值比原确定问题的大很多，说明其需要很大的冗余来吸收随机波动才能确保可行性，导致调度方案的性能损失大。参考文献[9-10]及本文的算法实例，确定本文2个不确定参数ε=0.1，κ=0.15。

3.2算法性能分析

本文从算法的求解质量和解的数量来验证其有效性。以最大完工时间、机器总负荷和最大机器负荷为调度目标，利用所提出的基于Pareto优化的改进差分(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所示的统计结果。表4、表5中，f1、f2、f3为目标函数；C1、C2分别表示使用P-IDE算法求解确定型问题和ε=0.1、κ=0.15时的鲁棒对等问题所得解，t1、t2分别为用P-IDE算法求解确定型问题和ε=0.1、κ=0.15的鲁棒对等问题时连续运行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算法求解柔性作业车间调度问题时在解的质量上有较大提高，且非支配解的数量明显比SM算法多。

表4　Kacem案例结果比较　s

表5　Brandimarte案例结果比较

4结语

针对具有随机加工时间的多目标柔性作业车间调度问题，本文建立了加工时间服从标准正态分布的鲁棒对等问题模型，设计了基于Pareto优化的改进差分进化(P-IDE)算法。在该算法中，采用了基于全局非支配解的多目标变异操作，同时，为平衡算法的局部搜索能力和全局搜索能力，提出了融入4种邻域结构的变邻域局部搜索策略。最后，用P-IDE算法测试6组Brandimarte标杆案例和3组Kacem案例。测试结果表明：(1)P-IDE算法在求解相同规模确定型问题时，比其他算法具有更高的效率；(2)在求解鲁棒对等问题时，对于每个基准案例，当加工时间存在不确定扰动时，P-IDE算法的运行时间比确定条件下的运行时间略长，说明算法能快速有效地处理不确定扰动；(3)随着问题规模的增大，P-IDE算法在求解确定型问题和鲁棒对等问题时仍能得出质量较好且数量较多的非支配解，说明所提出算法对大规模问题同样具有较好的处理能力。当随机工时的波动程度ε和约束条件允许违背程度κ不确定时，所提鲁棒优化调度方法可在一定的运行时间内，以较低的性能损失获得最优解。

参考文献：

[1]于晓义,孙树栋,王彦革.面向随机加工时间的车间作业调度[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]. 计算机集成制造系统, 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]. 计算机集成制造系统, 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]汪双喜, 张超勇, 刘琼,等. 不同再调度周期下的柔性作业车间动态调度[J]. 计算机集成制造系统, 2014, 20(10): 2470-2478.

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

[13]张利平.作业车间预反应式动态调度理论与方法研究：[D]. 武汉：华中科技大学，2013.

[14]王凌.智能优化算法及其应用[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].计算机集成制造系统, 2011, 17(12): 2590-2598.

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

(编辑张洋)

收稿日期：2015-06-02

基金项目：国家自然科学基金资助项目(51275190)；中央高校基本科研业务费资助项目(2014TS038)；湖北省自然科学基金资助项目(2013CFB025)

中图分类号：TP18

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

作者简介：朱传军，男，1971年生。湖北工业大学机械工程学院副教授。主要研究方向为制造信息、智能调度算法、决策分析等。邱文(通信作者)，女，1989年生。湖北工业大学械工程学院硕士研究生。朱孟周，男，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