一种求解多目标柔性作业车间调度的改进粒子群算法白俊杰王宁生唐敦兵（南京航空航天大学CMS工程研究中心江苏南京210016）摘要：针对具有高纬搜索空间的多目标柔性作业车间调度问题，提出了一种基于偏好的多目标粒子群优化算法（PMOPSO）。算法引入了决策者的偏好信息，用以指导算法的搜索过程，使算法在决策者感兴趣的区域进行搜索，不但缩小了算法的搜索空间，提高了算法的效率，而且一次运算只求得偏好区域内若干个折中解，避免了决策者要在众多非劣解中做出困难的选择。在算法中，采用了新的偏好信息给定方法，即采用目标间重要关系、目标数值或目标权重大致取值范围来表示偏好信息。采用该方法，不但便于决策者给定偏好信息，而且还可以根据决策者的需求，对搜索区域的范围进行适当的调整。针对偏好信息的特点，提出了一种模拟人类社会组织“投票选举”的偏好信息处理方法，该方法直观简便并易于实现。最后，通过实例仿真，对算法性能进行比较分析和评价，结果表明了算法的有效性和可行性。关键词：柔性作业车间调度；粒子群优化算法；多目标优化；偏好信息中图分类号：TH16；TP278文献标识码：AImprovedPSOAlgorithmfortheMulti-ObjectiveOptimizationFlexibleJobShopSchedulingProblemsBaiJun-jieWangNing-shengTangDun-bing（CMSResearchcentre,NanjingUniv.OfAeronauticsandAstronautics,Nanjing210016,Jiangsu,China）Abstract:Tosolvethemulti-objectiveflexiblejobshopschedulingproblemwithlargedimensionalsearchingspace,apreferencebasedmulti-objectiveparticleswarmoptimizationalgorithm(PMOPSO)wasproposed.Thepreferenceinformationofdecisionsmakerisincorporatedintothealgorithmtoleadthesearchingdirection.Sothat,notonlythesearchingspaceiscompressedandtheefficiencyofthealgorithmisimproved,butalsojustafewtrade-offsolutionslocatedinpreferredareaareobtainedinasinglerun,andthehardworkofchoosingasatisfyingsolutionfromnumerousnon-inferiorsolutionsiseliminated.Inthealgorithm,anewexpressionmethodofpreferenceinformationbasedonimportancerelationshipamongobjectivesandthevaluerangeofobjectivesorobjectiveweightswasproposed.Withthismethod,notonlythepreferenceofdecisionsmakercanbeeasilyspecified,butalsotherangeofsearchingareacanbeadjustedproperlyaccordingtotherequirementsofdecisionsmaker.Inviewofthecharacteristicsofpreferenceinformation,anewpreferenceinformationhandlingmethod,whichsimulatesthe“vote”ofhumansociety,wasproposed.Themethodisintuitive,simpleandeasytouse.Finally,theperformanceofthealgorithmwasevaluatedthroughsimulations,andtheresultsdemonstratethefeasibilityandefficiencyofproposedalgorithm.Keywords:flexiblejobshopscheduling;particleswarmoptimizationalgorithm;multi-objectiveoptimization;preferenceinformation0.引言近年来，多目标柔性作业车间调度问题（Multi-objectiveFlexibleJob-shopSchedulingProblem,MFJSP）日益受到了学者们的关注，一些学者对该问题进行了深入的研究。以往的研究通常采用分步的求解策略，即首先采用多目标优化算法搜索到一组均匀分布在整个Pareto曲面的最优解，常用求解算法包括改进的混合遗传算法[1、2]、改进的多目标粒子群算法[3]、存档进化粒子群优化算法[4]等；然后再根据决策者的偏好进行多目标决策，从众多非劣解中选出满意的调度方案。这样的求解策略对于目标较少的多目标调度问题往往是有效的，但却很难解决高维多目标优化调度问题。随着调度目标的增加，算法的搜索空间和Pareto曲面的面积会迅速增大，所包含的非劣解的数量迅速增多。若要使算法朝着各个目标的方向同时搜索，并使搜索结果均匀分布在整个Pareto曲面上，则算法搜索效率会迅速降低，造成所求解的质量偏低，可能无法得到决策者满意解。而且得到的非劣解数量也偏多，造成决策者很难从中选出满意方案。并且，在实际生产中，由于个人的偏好和调度问题自身的需求，决策者...