1吴晔李霄玉姚骏1
上海正帆科技股份有限公司,上海大学机电工程与自动化学院上海200072
摘要:置换流水车间调度问题(flow-shopschedulingproblem)是生产调度问题的一个子问题，是NP-hard组合优化离散问题之一，具有很强的实际研究意义。在现代的生产制造过程中，单一的目标优化已经满足不了日益发展的工业需求，所以对多目标流水车间调度问题的研究显得尤为重要，已在实际生产中得到广泛应用。本文在多目标进化算法粒子群算法PSO的基础上设计了一种多目标进化算法离散多目标粒子群优化算法MDPSO以求解该问题,用MATLAB编程实现该算法并对几个标准多目标flowshop算例进行仿真测试。实验结果表明，提出的算法比已有的NSGA_II算法具有更好的优化性能。
关键词：多目标flowshop问题；MDPSO算法；NSGA-II；
ImprovedMDPSOmethodforMulti-objectiveflow-shopschedulingproblem
WuYe,LiXiaoyu,YaoJun
(Shanghaizhengfantechnologyco.Ltd,SchoolofMechatronicsandAutomation,ShanghaiUniversity,Shanghai,China)
Abstract
Multi-objectiveflow-shopschedulingproblemisasubproblemofproductionschedulingproblem.ItisoneofthediscreteproblemsofNP-hardoptimizationandhasstrongtheoreticalandactualpurpose.Inthemodernproductionandmanufacturingprocess,single-objectiveoptimizationcan’tmeetthegrowingindustrialdemand,sotheresearchontheschedulingproblemofmulti-objectiveflow-shopisparticularlyimportant.ThispaperdesignsaMulti-objectiveevolutionaryalgorithmbasedonthePSOtosolvethisproblem.ItwasimplementedbyMATLABandsimulationonakindofbenchmarkfunctions.TheexperimentalresultsshowthattheproposedalgorithmhasabetteroptimizationperformancethantheNSGA–II.
Keywords:Multi-objectiveflow-shopschedulingproblem;MDPSO;NSGA-II
1引言
在现实生活中，许多问题都需要寻找一个最优决策或者是最佳解决方案，这类问题被统称为优化问题,仅有一个目标函数的最优化问题称为单目标优化问题，目标函数超过一个的最优化问题称为多目标优化问题（Multi-objectiveOptimizationProblems，MOP）[1]。目前，多目标问题的优化研究已经引起越来越多的关注，对于一个多目标优化问题而言，由于目标之间会有一定的冲突和制约，即一个优化目标的性能提高通常会导致另外至少一个优化目标的性能退化，所以一个解对某一个目标函数来说是最优的，但是对于其他目标函数来说却不一定是最优的。因此，多目标优化问题的解不再是一个或多个孤立点，而是一个解集的形式。这个解集被称作Pareto解的最优解集合[2]。
置换流水车间调度问题(permutationflowshopschedulingproblem，PFSSP)是生产调度问题的一个子问题，是NP-hard组合优化离散问题之一[3],多目标置换流水车间调度问题涉及合理利用时间和资源，在满足各种约束条件的前提下，使预定的所有生产目标达到最优，更是在实际生活中得到广泛应用。
多目标置换流水车间调度问题的Pareto解可以认为是单向链表的形式，它的解注重的是单个元素在整个排列中的位置。所以，本文提出了一种MDPSO算法来解决多目标flow-shop问题，论文将MDPSO算法与传统的NSGA-II在标准的多目标flow-shop问题上进行性能对比，实验结果验证了算法的有效性。
我们的目标就是要找到最优工件排序，使得最大完成时间makespan最小和总流程时间TFT最小。
基于工件次序的编码方式是解决此类排程问题常被采用的方式。每一个工件在序列中的位置表示工件在一台机器上的加工次序。在MDPSO算法中，采用整数编码，每一个编码代表一个工件，每一个个体由1到n之间所有整数的排列组合构成，每一个整数在序列中出现的位置即为该工件加工的次序。例如4个工件在3台机器上加工，那么{3，1，4，2}可以表示一个个体。对应的在机器上的加工顺序如图(4.1)的甘特图所示。
图2-1甘特图表示多目标flowshop的解
3MDPSO算法解决多目标flowshop问题
3.1MDPSO算法
在传统的粒子群算法中，粒子的位置速度都是采用连续实数的形式来表示的。这种连续参数形式的表示限制了粒子在离散优化组合问题领域中的应用发展。所以本文对经典PSO进行了改进，采用离散的基于工序的编码方法[4]。其全局最优解以及局部最优解的更新方式分别如下：
(1)全局最优解的更新
将迭代过程中产生的全局最优值与交叉操作生产的适应值进行比较，取优胜者为全局最优值。同时为了保存父代中的最优解和维持种群的多样性，应按照一定的比例进行交叉操作。借鉴遗传算法中的交叉算子，产生新的个体。具体的过程可以分为选择和交叉两个操作过程。选择操作的基本过程是：将当前种群中的所有个体加入集合中，并将其按照擂台赛法则产生非劣解集，同时计算非劣解集中的个体平均拥挤距离。选取平均拥挤距离最大的两个个体作为交叉个体。若有多个，则随机选取。这样可以使得种群向最优解靠近，维持了非劣解的均匀分布性。
(2)局部最优解的更新策略
粒子根据邻域的变化动态的选取邻域中的最优值与个体最优值进行比较，若邻域最优值优于个体最优值，则个体最优值替换为邻域最优值，否则，个体最优值保持不变。
3.2多目标优化算法评价指标
为了全面客观的评价算法解的优劣，通常用收敛性、一般距离、最大分布、非劣解比率、纯度、超立方体体积、覆盖率等指标来验证算法的性能。由于对于收敛性、一般距离、最大分布指标的计算需要理论Pareto前沿，而本章节的多目标置换流水车间调度问题的理论Pareto未知，所以本文采用以下几个常用的指标进行量化评价。
(1)非劣解比率
(2)纯度指标
纯度指标（Purity）[6]表示不同比较算法获得非支配解在它们总的非支配解中所占的比例，且越大说明算法性能越强。
(3)超立方体体积指标
超立方体体积指标（HV）[7]表示由Pareto解集中个体与参考点在目标空间中所围的超立方的体积，超立方体体积值越大，算法的性能越好。
4多目标置换流水车间调度问题仿真结果
本节将DNSGAII和MDPSO算法分别优化解决多目标车间流水问题的标准算例，其中测试所用算例是从Taillard[8]标准算例库选取的2个基准问题。分别是最小规模的Ta1和Ta91，求解结果如下：
综合以上分析,可以看出对于多目标flowshop问题来说,MDPSO算法的优化性能是优于传统的NSGA-II的。
5结论
从以上数据实验结果中不难看出,MDPSO算法的pareto解分布比较稠密,形成了一个明显的Pareto前沿，且前沿解集明显比传统的NSGA-II的Pareto前沿解集好，既保证解集的均匀分布又具有更好的求解精度。本文提出的解决多目标置换流水车间调度问题的方法可以进一步应用于实际工业生产中，从而提高生产效率并转化为实际生产力，所以下一步将研究如何将本文算法应用于其他更复杂，更高维，更真实的多目标优化问题，以进一步验证其在此类问题上的有效性。
参考文献:
[1]公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究[J].软件学报,2009,(02):271-289.
[2]AmruthaBuddana,TomaszJ.Kozubowski.DiscreteParetoDistributions[J].EconomicQualityControl,2015,29(2).
[3]ChangPC.AParetoblock-basedestimationanddistributionalgorithmformulti-objectivepermutationflowshopschedulingproblem[J].InternationalJournalofProductionResearch,2015,53(3):793-834.
[4]符强,汪鹏君,童楠,王铭波,张会红.基于MODPSO算法的FPRM电路多约束极性优化方法[J].电子与信息学报,2017,39(03):717-723.
[5]YenG.G.,HeZ.N.,Performancemetricensembleformulti-objectiveevolutionaryalgorithms[J].EvolutionaryComputation,IEEETransactionson,Vol.18,No.1,2014,pp.131-144.
[6]DejemeppeC.,SchausP.,DevilleY.,Derivative-FreeOptimization:LiftingSingleObjectivetoMulti-ObjectiveAlgorithm[M].IntegrationofAIandORTechniquesinConstraintProgramming,SpringerInternationalPublishing,2015,pp.124-140.
[7]JiangS.,OngY.S.,ZhangJ.,etal.Consistenciesandcontradictionsofperformancemetricsinmulti-objectiveoptimization[J].Cybernetics,IEEETransactionson,Vol.44,No.122014,pp.2391-2404.
[8]http://mistic.heig-vd.ch/taillard.