一种求解多目标柔性作业车间调度的改进粒子群算法

一种求解多目标柔性作业车间调度的改进粒子群算法

白俊杰 王宁生 唐敦兵

（南京航空航天大学 CMS工程研究中心 江苏 南京 210016）

摘要：针对具有高纬搜索空间的多目标柔性作业车间调度问题，提出了一种基于偏好的多目标粒子群优化算法（PMOPSO）。算法引入了决策者的偏好信息，用以指导算法的搜索过程，使算法在决策者感兴趣的区域进行搜索，不但缩小了算法的搜索空间，提高了算法的效率，而且一次运算只求得偏好区域内若干个折中解，避免了决策者要在众多非劣解中做出困难的选择。在算法中，采用了新的偏好信息给定方法，即采用目标间重要关系、目标数值或目标权重大致取值范围来表示偏好信息。采用该方法，不但便于决策者给定偏好信息，而且还可以根据决策者的需求，对搜索区域的范围进行适当的调整。针对偏好信息的特点，提出了一种模拟人类社会组织“投票选举”的偏好信息处理方法，该方法直观简便并易于实现。最后，通过实例仿真，对算法性能进行比较分析和评价，结果表明了算法的有效性和可行性。 关键词：柔性作业车间调度；粒子群优化算法；多目标优化；偏好信息 中图分类号：TH16；TP278 文献标识码：A

Improved PSO Algorithm for the Multi-Objective Optimization Flexible Job

Shop Scheduling Problems

Bai Jun-jie Wang Ning-sheng Tang Dun-bing

（CMS Research centre, Nanjing Univ. Of Aeronautics and Astronautics, Nanjing 210016, Jiangsu,

China）

Abstract: To solve the multi-objective flexible job shop scheduling problem with large dimensional searching space, a preference based multi-objective particle swarm optimization algorithm (PMOPSO) was proposed. The preference information of decisions maker is incorporated into the algorithm to lead the searching direction. So that, not only the searching space is compressed and the efficiency of the algorithm is improved, but also just a few trade-off solutions located in preferred area are obtained in a single run, and the hard work of choosing a satisfying solution from numerous non-inferior solutions is eliminated. In the algorithm, a new expression method of preference information based on importance relationship among objectives and the value range of objectives or objective weights was proposed. With this method, not only the preference of decisions maker can be easily specified, but also the range of searching area can be adjusted properly according to the requirements of decisions maker. In view of the characteristics of preference information, a new preference information handling method, which simulates the “vote” of human society, was proposed. The method is intuitive, simple and easy to use. Finally, the performance of the algorithm was evaluated through simulations, and the results demonstrate the feasibility and efficiency of proposed algorithm.

Key words: flexible job shop scheduling; particle swarm optimization algorithm; multi-objective optimization; preference information

化算法搜索到一组均匀分布在整个Pareto曲面的

最优解，常用求解算法包括改进的混合遗传算法0.引言

[1、2]

近年来，多目标柔性作业车间调度问题、改进的多目标粒子群算法[3]、存档进化粒子（Multi-objective Flexible Job-shop Scheduling 群优化算法[4]等；然后再根据决策者的偏好进行Problem, MFJSP）日益受到了学者们的关注，一多目标决策，从众多非劣解中选出满意的调度方些学者对该问题进行了深入的研究。以往的研究案。这样的求解策略对于目标较少的多目标调度通常采用分步的求解策略，即首先采用多目标优问题往往是有效的，但却很难解决高维多目标优

收稿日期:2009-10-19

基金项目：教育部霍英东教育基金青年教师基金项目(111056). 新世纪优秀人才支持计划资助项目(NCET-08).

化调度问题。随着调度目标的增加，算法的搜索空间和Pareto曲面的面积会迅速增大，所包含的非劣解的数量迅速增多。若要使算法朝着各个目标的方向同时搜索，并使搜索结果均匀分布在整个Pareto曲面上，则算法搜索效率会迅速降低，造成所求解的质量偏低，可能无法得到决策者满意解。而且得到的非劣解数量也偏多，造成决策者很难从中选出满意方案。并且，在实际生产中，由于个人的偏好和调度问题自身的需求，决策者通常只对某一区域的Pareto折中解感兴趣。因此，本文提出了一种适用于求解高维多目标柔性作业车间调度的改进的多目标粒子群算法。该算法采用偏好信息指导算法的搜索过程，使得算法在一次运行结束时只求得偏好区域内的若干个折中解，这不但可以大大提高算法的求解效率，减少计算资源的消耗，提高解的质量，同时也便于决策者从较少的候选方案中做出最终的决策。

目前，有关多目标优化算法的研究焦点主要集中于如何通过选取适当的适应值分配策略和排挤算子保持种群的多样性，使得算法最终搜索到一组均匀分布在整个Pareto曲面上的解。而在偏好信息的处理方面，却很少受到学者们的关注。目前，仅有少数学者对多目标优化的偏好处理问

题进行了研究。Fonseca[5]和商秀芹[6、

7]分别采用单个目标向量来表示决策者的偏好信息，并将目标向量引入到算法的群体排序过程中，缩小了解的搜索范围，该方法简单易行，但事先需消耗较多的计算资源确定每个目标的变化范围，以便决策者为算法提供精确的合理的目标向量值。余进[8]

将偏好信息表示为多个目标向量，将每个目标向量作为一个参考点，一次运算可得到多个特定区域的多个解，该方法是偏好信息单目标向量处理方法的扩展，方法比较新颖。但是，和单目标向量处理方法相同，为了确定各目标的变化范围并选取适当的目标向量值，同样需要事先消耗较多的计算资源。Cvetkvoic[9]和Jin[10]分别将决策者的偏好信息表示为模糊偏好矩阵的形式，并进一步转化为定量的目标权重值，建立了基于权重值的偏好优于关系，该方法在权重值的确定及优于关系的重新定义中，有多个待定参数，而这些参数的取值对解集的构成有着较大的影响。而且，事先很难准确估计各目标的取值范围，因此决策者很难一次给出合理的精确各目标权重值及其它参数值，为了得到问题的满意解，往往需要选取

不同参数进行多次求解。Branke[11]采用一种线性最大最小协调模型方法将偏好信息引入群体排序过程中，该方法允许用户指定每对目标可以接受的最大“均衡量”，即一个目标获得一个单位程度改进的同时，允许另一目标出现最大的劣化程度。该方法在两个目标情况下可以获得较好的结果，但在目标较多时，要确定合理的每对目标间的优胜关系则比较困难。而且，随着目标数量的增加，采用该模型构造和使用优于关系的过程也越来越

复杂。崔逊学[12、

13]采用ELECTRE协调模型将偏好信息引入到算法的搜索过程中，并采用该协调模型构造了一种称为“级别不劣于”的关系来替代“Pareto支配关系”，对进化群体进行排序。该方法思想新颖，但该协调模型所用的参数偏多，而且各参数的取值对解集的构成有显著的影响，为了得到满意解往往需要选取不同的参数，进行反复试验，并且构造和使用该“级别不劣于”关系的过程也很复杂。

对以往的研究成果进行归纳总结，可发现，偏好信息处理方法大致可分为目标权重、目标向量和多目标决策协调模型等3类方法。采用目标权重和目标向量的偏好信息处理方法，虽然构造和使用新的优于关系的过程比较简单，但是为了给出合理的精确的目标权重值和目标向量值，往往需要事先进行多次求解试验。而且，采用精确的目标权重值和目标向量值来引导算法搜索方向，往往造成算法搜索区域过于狭小。因此，不但使算法易于收敛到局部极值，形成早熟现象；而且，搜索区域过于狭小很可能漏掉一些更让决策者满意的折中解。采用多目标决策协调模型的方法，虽然可能省略计算目标权重和目标向量的工作，但是采用该方法构造新的优于关系过程中所用参数偏多，而且最终解集构成对各参数比较敏感，往往需要选取不同参数进行反复试验才能得到满意解，而且随着目标数量的增多，构造和使用新的优于关系的过程也越来越复杂。针对以往研究的不足，本文提出了一种基于偏好的多目标粒子群算法（preference based multi-objective particle swarm optimization algorithm, PMOPSO）。该算法不再采用精确的目标权重或目标向量的偏好信息给定方法，而是采用目标间重要关系、各目标权重值的大致范围、或各目标大致取值范围形式表示。这样，既便于决策者给定偏好信息，避免了因给出精确的目标权重值和目标向量而作

2

大量的预先计算工作；同时，决策者还可以根据自身的需求，对算法搜索区域的范围进行适当调整，在提高算法搜索效率的同时，避免了因搜索区域过于狭小而造成满意折中解的遗漏。结合“Pareto支配”和偏好信息定义了一种新的“偏好优于关系”，在按“偏好优于关系”对群体进行排序过程中提出了一种新的偏好信息处理方法，该方法模拟人类社会组织由低级向高级进化过程中“投票选举”的过程，采用种群投票表决选取偏好解集的方式，引导算法朝着偏好区域搜索，加快算法的求解速度，并使结果集中在决策者偏好区域内，便于最终决策。该方法直观、简单易行，并且不需要设置过多的参数。最后采用高维多目标柔性作业车间调度问题验证了算法的性能，仿真结果表明了算法的有效性和可行性。

1. 多目标柔性作业车间调度

1.1问题描述

多目标柔性作业车间调度问题的可描述为：一个加工系统有m台机器，要加工n种工件。每个工件包含一道或多道工序，工件的工序顺序是预先确定的；每道工序可以在多台不同的机床上加工，工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器、确定每台机器上各工件工序的最佳加工顺序及开工时间，使系统的某些性能指标达到最优（如生产周期最小、交货期满意度最高、生产成本最小等）。此外，在加工过程中还需满足如下约束条件：⑴同一时刻同一台机器只能加工一个零件。⑵每个工件在某一时刻只能在一台机器上加工，不能中途中断每一个操作。⑶同一工件的工序之间有先后约束，不同工件的工序之间没有先后约束。⑷不同工件具有相同的优先级。

1.2数学模型

在以往研究中，生产周期、机床利用率等基于性能的指标受到了学者们的普遍关注，而一些基于代价的指标（如交货期满意度、生产成本等）却很少受到关注。然而这类指标对企业的管理决策又是至关重要的。因此，本文从生产实际出发，分别从生产周期、交货期满意度、生产成本及机床利用率等多个方面建立优化目标。生产周期用工件的最大完成时间f1（h）度量；交货期满意度用拖期惩罚f2（元）度量；由于作业车间调度

问题未涉及到工件的原材料选择等环节，因此生产成本采用由工艺路线不同而造成的加工成本f3（元）

度量；机床利用率用机床最大负荷f4（h）和机床总负荷f5（h）度量。建立多目标整数规划模型如下：

Nf1?maxTn?1n ⑴

Nf2???nETn ⑵

n?1ETn?max(0,Tn?DTn) ⑶

MNOnf3??vpm??tonmxonm?m?1n?1o?1MO ⑷

Nn?spm(MCT???tonmxonm)m?1n?1o?1MNOnf4?max ⑸

m?1??tonmxonm n?1o?1MNOnf5????tonmxonm ⑹

m?1n?1o?1式中：

n—待加工工件种类 m—机床数量

on—第n类工件工序数量 Tn—第n类工件的完工时间 ETn—第n类工件的延误时间 ?n—第n类工件的拖期惩罚系数 DTn—第n类工件的交货期

tomn—单件第n类工件第o道工序在机床m上加工所需时间

xonm—决策变量，xonm?1时第n类工件第o道工序在机床m上加工，xonm?0时，表示未选中

vpm—单位工作时间机床m所需费用 spm—单位闲置时间机床m所需费用 MCT—调度方案决定的最大完成时间

2. PMOPSO算法

目前，多目标优化算法通常采用“Pareto支配”准则对群体进行排序。然而，“Pareto支配”是一种较强的排序关系，对于目标数量较多的高维多目标优化问题，它将使群体产生大量的非劣

3

解，难以从中进行选择操作，并可能导致算法出现停滞现象。因此，在本文提出的PMOPSO算法中，将决策者的偏好信息与“Pareto支配”相结合，定义了一种较弱的“偏好优于关系”，用于对群体进行排序并生成偏好解集。以往的算法通常采用精确的目标向量值、目标权重值、多目标决策协调模型来表示偏好信息。采用精确数值表示的偏好信息引导算法搜索方向，会造成算法搜索区域过于狭小。因此，不但使算法易于收敛到局部极值，形成早熟现象；而且，搜索区域过于狭小很可能漏掉一些更让决策者满意的折中解。同时，由于在问题求解以前很难准确估计各目标取值范围，因此往往造成表示偏好信息的数值取值不够合理，使得算法的搜索区域偏离了决策者真正感兴趣的区域，从而无法求得满意的解。为了得到满意的结果，往往需要取不同的偏好信息数值进行多次试验。与以往的算法不同，本文不再采用精确的数值来表示偏好信息，而是采用目标间重要关系、各目标权重值的大致范围、或各目标大致取值范围形式表示。这样，不但便于决策者给定偏好信息，而且还可以根据问题本身或个人的需要来调整搜索区域的大小。由于偏好信息不再采用精确数值的表示方法，因此以往的用于精确数值偏好信息处理方法就很难对本文引入的偏好信息进行处理。因此，本文提出一种模拟人类社会组织投票选举产生“领导集体”的偏好信息处理方法，通过群体对Pareto非劣解进行投票表决，从而产生偏好解集，并将偏好解集作为群体的“领导集体”对群体搜索过程进行引导，使群体朝着决策者感兴趣的区域进行搜索，提高算法的搜索效率，并使求解结果集中在偏好区域内，便于最终决策。该方法不但直观、简单易行，而且不需设置过多参数。

2.1基本定义

本文将偏好信息引入“Pareto准则”，提出了一种较弱的“偏好优于关系”用于对种群排序产生偏好解集，分别对“偏好优于关系”和“偏好解集”定义如下：

定义1：偏好优于关系 为了不失一般性，以一个n个决策变量参数、k个目标函数和m个约束条件的最小化多目标问题为例。设决策向量a、b?Xf（Xf为可行解集）是n维的可行解，其对应的k维的目标函数

分别为

f(a)?(fa1fa2....fak)和

f(b)?(fb1fb2...fbk)。引入偏好函数g(x)，g(x)表示在偏好信息环境下一个解优于其它非

劣解的可信度。则a偏好优于b需满足以下充分条件：①a Pareto优于b ②a Pareto 无差别于b，并且a 的偏好函数值大于b的偏好函数值。以上两个条件可表达如下：

(fai?fbi?fam?fbm)?{(fal?fbl?fam?fbm)? g(a)?g(b)}?i?1...n，?lm?1...n

定义2：偏好解集

应用决策者的偏好信息在非劣解集中选取的解为偏好解，由偏好解组成的集合称为偏好解集。

2.2偏好信息的处理

人类社会是由各种各样的组织构成的，各组织中普遍存在领导机构，通过不断将更优秀个体补充到领导机构，对领导成员进行优胜劣汰，并由领导机构对组织进行领导，组织可以由小变大、由弱变强，像一个生物有机体一样不断的发展变化。领导机构通常不是单个个体，而是由多个优秀个体组成的一个小群体，从这个角度分析，社会组织的发展过程与多目标优化算法的搜索过程极其相似。因此，我们可以模拟社会组织的发展过程进一步完善多目标优化算法的搜索过程。

目前，投票选举已经成为最常用的领导机构产生方法，该方法简单易行、便于操作，因此被全世界众多组织所采用。在选举过程中，通常要考察被选举人的多方面条件，比如才能、品德、学历、年龄、身体健康状况等。如果假设组织中所有成员都具有被选举权，并采用“Pareto准则”对被选举人进行评判和比较，将优胜者补充到领导机构，由于考察条件过多，则会产生众多的优胜者，甚至所有成员都是优胜者，从而造成无法产生领导群体，组织机构混乱，组织无法正常运转。因此，通常人们在对被选举者评判过程中采用一些为人们普遍认可的隐含的准则，例如可按照“品德和才能作为重要考察条件，年龄在一定范围内，学历和身体健康状况为参考条件”进行

4

评判。本质上说，这样的准则体现了选举人的偏好，是一种选举人普遍认可的隐含的偏好信息。并且，这样的偏好信息通常是以特性间重要关系或特性值大致取值范围形式表述的，也与本文提出的偏好信息表示方法极其相似。为了保证选举的公正和有效，避免个人的偏见，普遍采用群体投票表决的方式。在投票过程中，存在众多选举人，每个选举人评判准则都和隐含的偏好信息相一致，同时又保持个体差异，这样被选举者得票数量越多，则他优于其他被选举者的可信度就越高。因此，投票选举过程其实就是采用偏好信息构造“偏好优于关系”对群体进行排序的过程。因此，本文模拟人类社会组织“投票选举”产生领导集体的方式来处理偏好信息，其过程如下：

1） 种群的初始化及偏好信息的预处理

与以往采用精确数值对偏好信息进行表示不同，本文采用以下3种形式对偏好信息进行表示，分别为：⑴各目标间重要关系；⑵各目标权重值大致取值范围；⑶各目标值大致取值范围；或以上3种形式的综合表示方式。这样，不但便于决策者给定偏好信息，而且还可以通过调整数值取值范围控制算法搜索区域的大小。在适当提高算法的效率的同时，又不会造成算法搜索区域过于狭小。

对于采用各目标取值范围表示的偏好信息，可以在非劣解评价函数中引入偏好信息进行处理。而对于采用各目标重要关系或各目标权重值大致范围表示的偏好信息，为了保证通过选举产生的偏好解集更加有效，需要对偏好信息进行预处理。以一个最小化4目标问题为例，采用综合的方式给出偏好信息为“目标1、2重要目标，目标3、4为参考目标，目标1比目标2更重要，而且目标1的权重取值在0.4 至0.6之间，目标3的取值最好小于100”。则在粒子种群的初始化过程中，除了随机生成各粒子初始编码外，同时对每个粒子随机生成对应各目标的权重系数，使各权重系数与决策者偏好信息相一致，并且其和为1。随机生成任意粒子i的各指标权重系数wi1、

wi2、wi3、wi4，使得wi1?wi2?wi3?wi4?1，

并且wi1?wi?2wi、wi1?wi2?wi4、

0.6?wi1?0.4。采用上述方法，可以在与偏好

信息相一致的情况下，保证各粒子对偏好解存在不同的衡量标准，保证了粒子间的差异性。通过群体投票，保证偏好解集的有效性，避免了因采用单个目标权重值造成评价的偏见。

2） 经初选，生成候选解集

为了保存计算过程中的候选解，需设置一个外部存档。在每一代计算过程中，首先将上一代选举产生的偏好解集复制到外部存档中。计算过程中，对各粒子进行解码并计算各目标值，按Pareto支配关系，将各粒子与外部存档中的解两两比较。若该粒子与各解相比均不Pareto受控，则将该粒子信息保存到外部存档中，即该粒子取得了“候选资格”，成为一个候选解。若该粒子Pareto优于外部存档中某个候选解，则取消该解的“候选资格”，即从外部存档中删除该候选解。通过上述步骤，即可得到一个包含多个候选解的候选解集。

3） 投票选举

为了保证偏好解的多样性，我们在偏好信息预处理过程中，同样保持了各目标权重系数的多样性。这就造成不同的粒子具有不同的偏好解选取标准，即在同一个候选解集中，不同的粒子选取偏好解也可能不同。为了在上述情况下，从候选解集中选取出令决策者满意的偏好解集，我们采用一种模拟人类社会组织“投票选举”的处理方法。“投票选举”是人类社会组织产生领导机构普遍采用的方法。在选举过程中，虽然每个投票者对候选人的评判标准不完全相同，但通过投票的方式总能产生令人满意的领导机构，该方法简单而有效，因此已成为一种最普遍的领导机构产生方法。同时，也为本文的问题提供了一种简单有效的处理方法，具体过程如下：

在投票过程中，每个粒子都拥有相同的投票机会，本文规定每个粒子只能将选票投给一个自己认为最优的候选解，而且必须投给一个候选解。在粒子投票时，必须计算粒子对各候选解的偏好程度，本文采用投影寻踪的方法来计算粒子对候选解的偏好程度。如粒子i对候选解j偏好程度可

记为

4Fij??wio(maxfo?fjo)/maxfo?minfo；

o?1其中fjo为候选解j的第o个指标值；当第o个目

5

标存在决策者预设的取值范围时，maxfo为第o个指标的预设最大取值；否则，为外部存档中所有解的第o个指标最大值；minfo为外部存档中所有候选解第o个指标值最小值。当全部粒子投票完毕时，统计各候选解所得票数。候选解的得票数越多，则它在偏好信息域下，优于其它候选解的可信度也就越高。因此，我们将各候选解所得票数作为他们的偏好函数值，并按照偏好函数值的大小对候选解排序，偏好函数值越大的候选解的优先级就越高，偏好函数值越小的优先级就越低。

4）生成偏好解集

按照候选解的优先级，由高到低选择一定数量（按全局存档可存储偏好解数量确定）的候选解，作为偏好解集。将它们存入全局存档，他们将作为算法的本次迭代计算全局最优位置，起到领导机构的作用，引导整个种群进化。

5）由偏好解集引导种群进化

为了使算法朝着决策者感兴趣的方向搜索，必须将偏好解集作为全局最优位置，从而引导算法的搜索过程。为了在保证算法收敛情况下，同时避免算法早熟，本文采用一种最优位置混合选取策略。首先判断粒子前代是否产生过偏好解，若产生过，则在全局存档信息中进行查找，若未被替代则选择该偏好解为全局最优位置；若粒子未产生过偏好解或已被替代则选择收到该粒子投票的偏好解为全局最优解。采用上述混合选取策略，既可保证偏好解的特征按照优先级的高低以不同几率的遗传给下一代，引导算法朝着决策者感兴趣方向搜索，保证算法收敛，同时又可避免算法早熟。

2.3编码与解码

与文献[1、2]相同，本文采用基于工序的编码方法。由于存在工艺路线柔性，同一道工序可由不同机床完成，因此解码时必须为每道工序分派适当的机床。拖期惩罚通常是作业车间调度首先要考虑的指标，因此本文采用的分派规则为优先选择最早完工时间的机床。即对于一道工序，计算该工序所有可加工机床的完工时间，并选取完工时间最早的机床。

2.4粒子速度和位置

为求解本文的问题，对文献[14]中的粒子速

度和位置表达式进行改进如下：

vion(t?1)?rand(c1)(randiont?xiont)?rand(c2)(piont?xiont)? ⑺

rand(c3)(arc(?i)ont?xiont)xion(t?1)?xiont?vion(t?1) ⑻

其中，xiont为第t代时粒子i中第工件n的第o道工序在编码中位置。piont为第t代时工件n的第o道工序所在粒子i局部最优解编码的位置，局部最优解可从粒子的局部存档中选取。

arc(?i)ont表示第t代时工件n的第o道工序所在

全局最优解编码中的位置，全局最优解可按2.2节的规则从全局存档中选取。randiont为第t代时粒子i中第工件n的第o道工序所在编码中一个随机位置。rand(c1)、rand(c2)和rand(c3)为0、1整数，分别受c1、c2和c3影响而随机产生。

2.5 PMOPSO算法流程 算法具体步骤如下：

⑴初始化控制参数：种群规模大小P，最大迭代代数gen，候选解集存档规模大小，偏好解集存档规模大小，算法控制参数c1、c2和c3，偏好信息（按2.2节的3种形式或3种形式的综合方式给定）

⑵gen?0，随机产生P个粒子编码，并对偏好信息进行预处理，按照偏好信息随机产生各粒子的目标权重值

⑶对各粒子进行解码，并计算各子目标值 ⑷将上一代的偏好解拷贝到候选解存档中，并采用Pareto准则与各粒子进行比对，生成候选解集

⑸计算各粒子对各候选解的偏好程度，各粒子对自己认为最优的候选解进行投票

⑹统计各候选解得票数量，并按得票数量由高到低对候选解排序

⑺按优先级由高到低选取一定数量（按全局存档规模确定）的候选解复制到全局存档中

⑻依2.2节规则选取全局最优位置，并计算粒子速度，更新粒子位置

⑼gen?gen?1，如果达到规定循环代数，则停止计算；否则，转至第⑶步

6

⑽输出偏好解集存档中得票数不为0的偏好解，为算法最终搜索结果

3.仿真试验

算法运行环境为Pentium 3、CPU主频850MHz、256MB内存、Windows XP操作系统，并采用java语言编写。为验证本文算法的性能，本文分别采用3组仿真试验验证了算法的性能：⑴对文献[15]的3个标准测试用例（8×8、10×10、15×10）进行求解，并与一些典型算法求解结果进行对比，初步验证算法的性能；⑵对文献[1、2]中的6目标的6×6×10（6个工件6台机床，每个工件有10道工序）的高纬多目标优化调度问题进行求解，并与原文进行比对，进一步验证算法求解高纬多目标调度问题的性能。⑶将文献[16]中10个典型测试用例改进为5目标优化调度问题，将本文算法所求结果与典型多目标优化算法所求结果进行比对，进一步验证本文算法的性能。

3.1仿真试验1 为了验证PMOPSO算法的性能，我们对文献[15]中的3个标准测试用例（8×8、10×10、15×10）进行求解，并把结果与一些典型的优化算法求解结果进行对比，如表1所示。由于篇幅限制，仅将15×10问题所求两个结果采用甘特图形式表示，如图1和图2所示（方框中数字表示工件和工序）。进行比较的优化算法包括：混合粒子群算法（Particle Swarm Optimization and Simulated Annealing Algorithm, PSO+SA）[15]、结合禁忌搜索的混合粒子群算法（Particle Swarm Optimization with Tabu Search, PSO+TS）[16]、改进的遗传算法（Improved Genetic Algorithm, IGA）[17]

。PMOPSO算法的主要参数：种群数取100，最大循环代数取200，常数c1、c2、c3分别取0.2、0.4、0.5，偏好信息为“各目标按重要程度由高到低依次为：生产周期、机床最大负荷、机床总负荷”。表1中各符号所代表的目标分别为：A—生产周期，B—机床最大负荷，C—机床总负荷。

表1.求解结果比较

算法

问题（A/B/C） 8×8 10×10 15×10

PSO+TS 14/12/77 7/6/43 11/11/93 PSO+SA 15/12/75 7/6/44 12/11/91 IGA 14/12/77 7/6/43 12/11/91

14/12/77 7/5/43 12/11/91

PMOPSO 15/12/75 7/6/42 11/11/92

16/11/77 8/5/42

图1. 15×10问题调度甘特图（A=11,B=11,C=92）

图2. 15×10问题调度甘特图（A=12,B=11,C=91）

观察表1、图1、图2，可知：PMOPSO算法所

求结果的各项目标均达到或接近几种典型算法所求结果最优值，且没有未出现受控解。并且某些求解结果还略优于对比算法的所求结果。可见，所求结果是比较令人满意的。而且，PMOPSO算法是多目标优化算法，一次求解可得到多个调度方案，可以为决策者提供了多样性的选择。因此，通过该仿真试验，我们就初步验证了该算法求解多目标柔性作业车间调度问题的可行性和有效性。

3.2仿真试验2 文献[1、2]从实际生产中提取了一个6目标柔性作业车间调度问题，作者吴秀丽采用了分步策略进行求解，首先采用一种混合遗传算法对问题进行求解（种群数取100，最大循环次数取3000），得到了一个包含20个非劣解的均匀分布在整个Pareto曲面的解集，然后采用层次分析模糊综合评判从20个非劣解中选出一个最终解决方案。为了验证PMOPSO算法求解高纬多目标优化调度问题的性能，对该6目标高纬多目标优化调度问题进行求解，并与文献[1、2]结果进行对比。采用PMOPSO算法对问题求解，算法的主要参数：种群数取100，最大循环代数取2000，常数c1、c2、c3分别取0.2、0.4、0.5，偏好信息为“生产周期、生产成本和最大提前/拖后时间为非常重要目标，机床最大负荷和机床总负荷为重要目标，在制品库存成本为次要目标”。算法运算过程中，

7

所用各目标表达式及问题的原始数据均与文献[1、2]相同，可参阅文献[1、2]相关表达式及表格。PMOPSO算法结果包括6个偏好解的解集，如表2所示。将文献[1、2]中包含20个非劣解的Pareto解集与表2对比，发现其中存在11个的受控解，将剩余的9个非受控解列表，如表3所示。将表3与表2进行对比，如表4所示。表2、表3、表4中各符号所代表的目标分别为：A—生产周期（h），B—生产成本（元），C—最大提前/拖后（h），D—机床总负荷（h），E—机床最大负荷（h），F—在制品库存成本（元）。

表2. PMOPSO求解结果

序号 指标 A B C D E F 1

301 7873 11 275 1538 125 2 310 8185 16 276 1567 92 3 299 7831 9 279 1548 139 4 306 7757 11 286 1529 133 5 302 7746 12 286 1525 145 6

306

7639

17 280 1512

201

表3.文献[1、2]的非受控解

序号 指标 A B C D E F 1 335 8172 72 270 1714 153 2 300 8067 10 270 1752 185 3 331 8994 86 318 1714 59 4 328 8772 93 292 1694 69 5 305 8005 51 284 1698 118 6 306 8533 43 295 1692 102 7 298 8050 11 296 1738 171 8 299 8185 44 267 1725 146 9

299

8280

16 280

1739

110

表4.表2、表3结果对比

表3 表2 受控目标数量 非受控目标项 差值

1 1 5 D 5 2 3 5 D 9 3 2 5 F 33 4 2 5 F 23 5 1 5 F 7 6 2 5 A 4 7 3 5 A 1 8 3 5 D 12 9 3 5 F 29

图3.调度甘特图

观察表2、表3可知：PMOPSO算法所求结果包括6个偏好解，将这6个偏好解与文献[1、2]中包括20个解的Pareto解集进行对比，发现20个解中有11个解为受控解，而6个偏好解中未发现受控解。表4列出了表3中的解与表2中适当解的比较结果，观察该表可知：表3的9个非受控解，与表2相比虽然未受控，但是它们均在5个目标劣于表2中的解，只是在单个目标上略微优于表2中对应解。说明，这9个非受控解主要集中于Pareto曲面上某个目标的极值点附近，而不在决策者的偏好区域，并不是令人满意的折中解。与文献[1、2]的算法相比，PMOPSO算法不但搜索效率更高，所得结果更加令人满意，而且算法得到解的数量较少，避免了决策者要在众多非劣解中选取满意解。文献[1、2]采用层次分析模糊综合评判的方法从20个非劣解选择表3中第5个解作为最优调度方案，我们可将表2中第1个解作为最终调度方案，调度甘特图如图3所示（方框数字表示工件和工序）。该方案在生产周期、生产成本、最大提前/拖后时间、机床最大负荷、机床总负荷等五个调度指标上均明显优于表5的第5个解，只是在制品库存费用为125（元），比文献[1、2]的调度方案多7（元）。不难看出，本文的方案更加令人满意。

3.3仿真试验3 为了进一步验证PMOPSO算法的性能，我们对典型的MK01-MK10的10个测试用例进行改进，将它们改为5目标柔性作业车间调度问题。其中，工件的交货期及拖期惩罚系数如表5所示，机床的工作及空闲费率如表6所示（工艺路线等数据请参阅相关文献）。采用PMOPSO算法求解，并与两种典型的多目标优化算法（MOGA及NSGA算法）所求结果进行比对。3种算法的种群数均取100，最大循环代数均取2000；PMOPSO算法常数c1、c2、c3分别取0.2、0.4、0.5，偏好信息为“拖期惩罚、生产成本和生产周期为重要目标，并且其重要程度依次为拖期惩罚、生产成本、生产周期；机床最大负荷、机床总负荷为次要目标”。对3种算法结果进行比较，如表7所示。为了说明不同算法结果的质量，我们以MK10问题为例，将不同算法求解的结果分别列表表示，表8表示PMOPSO算法的偏好解，表9表示NSGA算法结果中的非受控解，表10表示MOGA算法结果中的非受控解。表8、表9、表10中各符号所代表的目标分别为：A—拖期惩罚（元），B—生产成本（元），

8

C—生产周期（h），D—机床最大负荷（h），E—机床总负荷（h）。

表5.交货期及拖期惩罚系数 序号

1 2 3 4 5 6 7 8

DT 20 24 30 40 48 60 80 88

9 10 100 130 1 2 19 20 450 500 3 3

表6. 机床的工作及空闲费率 序号 VP SP 序号 VP SP 1 2 1 9 11 1 2 4 1 10 10 1 3 8 1 11 9 1 4 6 1 12 3 1 5 7 1 13 5 1 6 5 1 14 8 1 7 8 2 15 4 1 8 5 1 16

a 序号 DT

1 2 1 1 1 1 2 1

11 12 13 14 15 16 17 18

170 160 160 190 210 230 320 420

a

1 1 2 1 1 1 2 1

表7.结果的比较

问题 MK01 MK02 MK03 MK04 MK05 MK06 MK07 MK08 MK09 MK10 规模 10×6 10×6 15×8 15×8 15×4 10×15 20×5 20×10 20×10 20×15 非劣解 20 20 20 20 20 20 20 20 20 20 MOGA NSGA PMOPSO

受控解 时间(S) 非劣解 受控解 时间(S) 偏好解 受控解 时间(S) 3 212 20 4 220 3 0 234 11 410 20 13 398 5 0 432 12 1042 20 13 1022 5 0 1078 10 723 20 12 754 5 0 785 5 842 20 4 834 4 0 876 6 832 20 7 841 5 0 884 4 854 20 3 843 4 0 874 9 1147 20 8 1132 3 0 1187 10 1354 20 11 1342 5 0 1395 12 1541 20 13 1537 4 0 1596 表8.PMOPSO求解MK10问题的解集 序号 1 2 3 4

A 2389 2309 2259 2477

指标 B C 15134 241 15215 235 15541 242 15210 248 指标 B C 15702 263 15962 272 15745 263 15566 259 15886 264 15684 257 15368 253 指标 B C 15425 260 15526 259 15579 259 15572 272 15580 260 15322 260 15488 258 15381 260

D 222 223 222 234

E 2110 2117 2152 2097

表9.NSGA求解MK10问题的非受控解 序号 1 2 3 4 5 6 7

A 2875 2782 2602 2609 2654 2525 2571

D 221 220 219 229 220 235 230

E 2121 2115 2155 2107 2121 2095 2087

的结果中也包含一定数量的非受控解（如表9、10所示），但是与PMOPSO算法的偏好解集相比，这些非受控解均在4项指标上明显劣于PMOPSO算法的结果，而只是在某个指标上略微优于PMOPSO算法的结果（受篇幅限制，不再采用表4的形式列表表示）。不难看出，与MOGA算法和NSGA算法相比，PMOPSO算法不但搜索效率更高，而且得到的结果也更令人满意。同时，PMOPSO算法的偏好解集包含解的数量较少，更便于决策者做出最终的决策。

4.结论

针对高纬多目标柔性作业车间调度问题，提出了一种基于偏好的多目标粒子群算法（PMOPSO）。通过偏好信息引导算法的搜索过程，使算法朝着决策者感兴趣的区域搜索，缩小了算法的搜索空间，提高了算法的效率。而且，使最终结果集中在决策者感兴趣的区域，减少了非劣解的数量，避免了决策者要在众多非劣解中做出困难的选择。在算法中，不再采用精确数值表示偏好信息，而是提出了一种采用目标间重要关系、目标权重大致取值范围和各目标大致取值范围偏好信息表示方法，采用该方法，不但便于决策者给定偏好信息，而且还可根据决策者或问题本身的需要，对搜索区域的范围进行适当调整。针对偏好信息的特点，提出了一种模仿人类社会组织“投票选举”产生领导机构的偏好信息处理

表10.MOGA求解MK10问题的非受控解 序号 1 2 3 4 5 6 7 8

A 2752 2695 2762 2895 2667 2638 2750 2753

D 229 227 220 242 242 227 251 243

E 2081 2083 2113 2080 2076 2103 2090 2079

表7列出了3种算法在取相同种群数量、相同最大循环代数情况下对10个典型问题的求解结果。观察该表不难看出，与PMOPSO算法相比，MOGA算法和NSGA算法的解集中均出现了受控解，而PMOPSO算法的偏好解集中却未出现受控解。观察表8、9、10可知，虽然MOGA算法和NSGA算法

9

方法，该方法不但直观、而且简单易行。最后，通过仿真实例验证了算法的可行性和有效性。

参考文献：

[1]吴秀丽,孙树栋,余建军,等.多目标柔性作业车间调度优化研究[J].计算机集成制造系统, 2006,12(5):731-736.

[2]吴秀丽,孙树栋,余建军,等.多目标柔性作业车间调度决策精选机制研究[J].中国机械工程,2007,18(2):161-165.

[3]鞠全勇,朱剑英.多目标批量生产柔性作业车间优化调度[J].机械工程学报,2007,43(8):148-154.

[4]Deming Lei. A Pareto archive particle swarm optimization for multi-objective job shop scheduling [J]. Computers and Industrial Engineering, 2008, 54(4): 960-971.

[5]Fonseca Carlos M, Fleming Peter J. Multiobjective genetic algorithms made easy: Selection, sharing and mating restriction [C]// Proceedings of the 1st IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. Sheffield, England, 1995:45-52. [6]商秀芹,卢建刚,孙优贤,等.一种基于偏好的多目标遗传算法在动态模型参数辨识中的应用[J].化工学报,2008,59(7):1620-1624.

[7]Shang Xiuqin, Lu Jiangang, Sun Youxian. A preference-based non-dominated sorting genetic algorithm on dynamic economic dispatch [C]// Proceedings of the World Congress on Intelligent Control and Automation. Chongqing, China, 2008: 2794-2797.

[8]余进,何正友,钱清泉.基于偏好信息的多目标微粒群优化算法研究[J].控制与决策,2009,24(1):66-70+75. [9]Cvetkovic Dragan, Parmee Ian C. Preferences and their application in evolutionary multiobjective optimization [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 42-57.

[10]Jin Y, Sendhoff B. Incorporation of Fuzzy Preferences into Evolutionary Multi-objective Optimization [C]// Proceedings of the 4th Asia Pacific Conference on Simulated Evolution and Learning. Singapore, 2002: 26-30.

[11]Branke J, Kauler T, Schmeck H. Guidance in evolutionary multi-objective optimization [J]. Advances in Engineering Software, 2001, 32(6):

499-507.

[12]崔逊学,李淼,方廷健.多目标协调进化算法研究[J].计算机学报,2001,24(9):979-984.

[13]Cui Xun-Xue, Lin Chuang. Preference-based multi-objective concordance genetic algorithm [J]. Ruan Jian Xue Bao, 2005, 16(5): 761-770.

[14]Eberhart R, Kennedy J. A new optimizer using particle swarm theory [C]// Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya, Japan, 1995: 39-43.

[15]Xia Weijun, Wu Zhiming. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems [J]. Computers and Industrial Engineering, 2005, 48(2): 409-425.

[16]Guohui Zhang, Xinyu Shao, Peigen Li, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem [J]. Computers and Industrial Engineering, 2009, 56(4): 1309-1318.

[17]袁坤, 朱剑英. 一种求解多目标柔性Job Shop调度的改进遗传算法[J]. 中国机械工程, 2007, 18(2): 156-160.

10

本文来源：https://www.bwwdw.com/article/ruff.html