张建军 彭亚丽 张 利 刘小平

合肥工业大学，合肥，230009

0 引言

铜卷加工制造兼有离散型制造和流程型制造的特点，属于典型的混合型生产方式[1]，其生产过程的非线性、随机性、不确定性，导致该类问题的生产约束条件更为多样，其生产调度问题具有更大的复杂性，求解更加困难。而调度问题本身往往需要综合考虑生产成本、资源能耗和产品周期等多个因素，而且各因素之间往往会存在冲突，属于多目标优化问题（multi－objective optimization problem，MOP）[2]，混合型制造业也是典型的MOP。MOP往往不存在使各目标都为全局最优的解，而是存在一个在多个目标间折衷的均衡解的集合，即Pareto最优解集，求解多目标问题的关键就是找到数量足够多且分布均匀的Pareto最优解[3]。

自从Kennedy等[4]在1995年提出粒子群优化（particle swarm optimization，PSO）算法以来，PSO算法就以其概念简单、容易实现和需要调整的参数较少等优点吸引了大批学者进行研究，逐步渗透到各个应用领域[5－7]。而将PSO算法应用到MOP需要解决三个问题：如何产生非支配解并构成Pareto解集；采用何种策略更新全局极值和个体极值；如何保持Pareto前沿上优化解的多样性。目前，在铜卷加工等混合型生产调度中应用PSO算法的研究相对较少，但由于混合型生产在现代制造生产中具有典型的代表意义，并且属于多目标优化问题，以及PSO算法自身的优势和容易与其他算法进行融合的特点，使得研究PSO算法在混合型多目标生产调度中的应用有着深刻的意义与广阔的前景。

1 多目标铜卷加工生产调度模型

1.1 铜卷加工生产方式描述

相对于传统的离散型或连续型生产方式而言，铜卷加工的生产方式有自己的特点：生产过程更为复杂、多种生产方式并存、多品种小批量生产等。以某铜卷生产企业的黄铜卷加工为例，产品的生产从投料到最终生产出成品需要经过若干个连续生产加工的过程（每个生产过程为一个单元）：熔炼炉→罩式炉退火1→粗扎机1→罩式炉退火2→粗扎机2→中间退火（罩式炉）→脱脂机→精扎机→气垫炉→罩式炉退火3→脱脂机→拉弯机。企业的生产是按订单驱动的，并且每件在制品在任一连续生产过程结束时都要进入缓冲区暂存。

1.2 铜卷加工生产调度问题模型

在生产计划调度中，由于企业接到的订单种类和产品类别都不唯一，各产品的交货期也会有差别，因此在调度之初需对订单进行分解，并将分解后的订单进行合并来安排生产，以便将同种类型以及交货期接近的产品作为一类产品进行加工。根据该铜卷加工企业的生产调度问题，建立企业生产调度问题模型如图1所示。企业从X个客户接收到一些订单，将订单基于交货期和产品种类进行分解和合并，产生要加工的产品系列a、b、c、d、f，每个产品都要经历 M 个生产单元，每个单元对应一台生产设备，则生产调度问题就是将这些产品在M个生产设备上的加工时间和顺序进行优化。

图1 铜卷加工生产调度问题模型

对于问题模型必须有一定的约束条件才能使调度算法有合理的解空间。为方便建立模型，我们对该铜卷加工企业的生产进行如下的约定：①产品的加工工艺路线是确定的；②企业的一批订单共涉及N种产品（序号为1，2，…，N），第j种产品的交货期为Tj（天）；③产品经历M个连续生产单元，第j种产品在第i个生产单元上所用的时间为tij，开始加工时间为tsij，结束的时间为teij，产品最后实际完成加工时间为TeMi，后一个加工单元必须在前一个加工单元完成后方可开始加工工件；④任一连续生产单元在任一时刻只能加工一种产品；⑤在零时刻，任何一种产品均有可能被加工。

考虑到铜卷企业生产实际的需求，本文选择交货期满意程度和完成时间两项指标[8]建立多目标优化函数。交货期满意度指标用产品最大拖期Td度量，第j种产品的拖期表示为Tdj；完成时间用产品最大完成时间Tf度量。因此，铜卷加工多目标调度优化模型为

其中，式（1）表示调度问题的目标函数；式（2）表示最大完成时间为所有工件在最后一台设备上完成时间的最大值；式（3）表示最大拖期取所有产品拖期的最大值，其中当所有产品均提前完成时，最大拖期为0；式（4）表示每个产品的拖期等于实际完工时间与交货期之差；式（5）表示加工时间等于结束加工时间减去开始加工时间；式（6）表示某种产品在某个连续生产单元上的结束加工时间大于开始加工时间。

2 求解M OP的自适应改进PSO算法

2.1 多目标优化问题描述

一般地，一个多目标优化问题就是要求所有目标函数在满足约束条件下越小越好，一个含有n个决策变量、m个目标变量的多目标优化问题可表述为[9]

其中，x为n维的决策矢量，x＝（x1，x2，…，xn）∈X⊂Rn；X为n维的决策空间；y为m维的目标矢量，y＝（y1，y2，…，yn）∈Y ⊂Rm；Y 为m 维的目标空间。

2.2 外部种群的更新

非支配排序遗传算法（non－dominated sorting genetic algorithm，NSGA－Ⅱ）[10]是目前公认高效的多目标优化算法，NSGA－Ⅱ中非支配排序思想已成为目前M OPSO（PSO for multi－objective problem）构成Pareto最优解的主流方法[11]。利用外部种群保留种群进化过程中产生的非支配解是目前比较高效的精英策略。

本文借鉴文献[12]中的基于拥挤距离排序的方法更新外部种群，其操作过程如图2所示。设内部种群为Ps，进化到第t代时内部种群粒子数为St；外部种群为Pt，外部种群粒子数为Sp，设置外部种群最大粒子数为Sm（Sp≤Sm）。内部种群Ps进化后，将产生的非支配个体（Np为非支配个体的个数）复制到外部种群，形成种群P′t。

图2 外部种群更新策略

（1）删除P′t中的重复个体（目标值相同的个体即为重复个体，随机删除一个而保留另一个）；标记并删除P′t中的非支配个体，此时记P′t中包含的非劣个体数为m2（m2≤Sm＋Np）；

（2）计算P′t中拥挤距离Di并降序排列，记为种群P″t；

（3）判断m2与Sm的数值关系，若m2≤Sm，如图2中情况①所示，则将P″t记为新外部种群Pt＋1，此时Pt＋1的后Sm－m2个个体为空；否则，如图2中情况②所示，调用外部种群的缩减过程，仅保留P″t中的前Sm个个体，删除后m2－Sm个最密集个体，形成缩减的外部种群Pt＋1，由此来保持外部种群的个体数在最大值Sm之内，避免了随着进化运算的进行，非支配个体数无限增多而降低算法效率；同时，外部种群缩减时删除最密集的多余个体而保留大量分散个体，保证了Pareto前沿的均匀分布。

其中对于非支配个体拥挤距离的计算，本文根据非支配个体与其周围的两个空间点的欧几里得距离来计算：

式中，fi，j（x）表示第i个个体的第j个目标函数值；i－1、i＋1为外部种群基于各目标函数排序后个体i附近的两个个体。

另外设置各目标函数排序后的第一个个体和最后一个个体的拥挤距离D1和DSp均为无穷大。

2.3 最优值更新策略

M OPSO希望获得分布均匀的Pareto前沿，因此不同于求解单目标问题时只选取目标函数值最大或者最小的点，而是要选择处于Pareto前沿中分散区域的点，从而引导原始粒子群向分散区域进化。图2所示的外部种群Pt更新完成后，全局最优值Pg的更新策略分为如下两种情况：

（1）若Pt中只包含极少数边界个体，即所有个体的拥挤距离均为无穷大，则随机选择一个作为全局最优位置Pg；

（2）若Pt中包括拥挤距离不为无穷大的个体，则使用轮盘法选择，即以较大概率选择拥挤距离较大的个体为Pg，计算公式为

式中，PB（xi）为粒子xi被选中的概率；Di为xi的个体拥挤距离。

个体拥挤距离含有无穷大会造成轮盘法选择失效，因此计算概率时定义边界个体的拥挤距离为除去这些个体后其余个体拥挤距离的中位数。

通过比较个体历史最优值与当前粒子的支配关系来确定是否更新个体最优值。若当前粒子支配该粒子的个体历史最优值，则用当前粒子替换历史最优值；若当前粒子与历史最优值互不支配，则随机选择二者之一作为新的个体最优；否则，保持历史最优值不变。

2.4 种群多样性保持策略

2.4.1 粒子编码与计算

借鉴遗传算法的矩阵编码方法对粒子进行编码，编码矩阵如下：

矩阵A是所有工件对应所有生产单元的完全编码，其每一列对应一个生产单元，每一行对应一个工件。矩阵元素aij是区间（0，1）内的一个实数，其大小决定了每个工件在第j个生产单元上的加工顺序。

解码时，对矩阵A的第j（j＝1，2，…，M）列的元素a1j，a2j，…，aNj进行大小比较，按照数值从小到大的顺序进行排列，排列结果即为这N个工件在第j个生产单元上的加工顺序。显然，从第二个生产单元开始，还得考虑工件在前面一个生产单元的结束时间，将结束时间和排序结果相结合来决定该工件在该生产单元上的加工顺序。具体说来，若该工件在前一个生产单元的加工没有结束，则考虑编码矩阵排序结果中排在其后的工件是否已结束前一个生产单元的加工，若已结束，则安排该工件进行加工。

2.4.2 基于动态自适应惯性权重进行进化计算

根据上述编码，计算时不再单独考虑粒子在各维空间的信息，而是将编码矩阵A整体作为搜索空间中的一个粒子，直接更新粒子的速度和位置的整体信息。

PSO算法的基本思想是随机初始化一群没有体积没有质量的粒子，将每个粒子视为优化问题的一个可行解，粒子的好坏由一个事先设定的适应度函数来确定。每个粒子将在可行解空间运动，并由一个速度变量决定其运动方向和距离。假设一个由M个粒子组成的群体在D维搜索空间以一定的速度飞行，其中粒子i的位置的第d维分别为搜索空间的下限和上限；速度的第d维分量分别为最小和最大速度；个体最优位置为，全局最优位置为P（t）g。则粒子在t＋1时刻的位置和速度通过下式更新获得[5]：

式中，ω 为惯性权重；r1、r2为均匀分布在（0，1）之间的随机数；c1、c2为学习因子，通常取值为2；Pid为第i个粒子第d维的个体最优值；Pgd为所有粒子第d维的全局最优值。

惯性权重ω的大小决定了粒子对当前速度继承的多少，较大的ω有利于全局寻优，较小的ω则有利于局部寻优，而根据进化代数进行惯性权重的自适应调整策略有利于加强保持种群多样性的能力，因此本文采取了动态自适应惯性权重调整策略：

其中，r3为均匀分布在（0，1）之间的随机数。本文根据前人经验取ω0＝0.9，ω1＝0.35。

2.4.3 基于非支配解的内部种群规模自适应调整策略

如果进化多目标优化算法采用小规模种群，那么对于一些复杂的多目标优化问题将很难收敛到理想Parato前沿面，而且很难获得均匀分布的Pareto最优解。因此，如何根据问题的复杂度自适应地调整种群的规模是需要进一步研究的问题[13]。根据非支配解在当前种群中所占的比例来自适应地调整种群规模是解决该问题的一个可行方向[9]。本文采取下式来更新内部种群大小：

式中，Ss、Se分别为最小、最大内部种群规模；Pp为非支配解在当前内部种群中所占比例。

由式（14）可知，种群规模是逐渐增大的，因此本文采取随机单点交叉策略产生新的个体补充到原始种群以形成新的内部种群。具体操作如下：记录内部种群进化结束时非支配解的个数Np，从原始种群中随机选取Np个个体，从外部种群中随机选取Np个个体，然后采用单点交叉方式产生新的个体复制到内部种群，同时将粒子的当前位置设置为个体最优值，由此形成新的内部种群进入下一代的进化，从而有效地保持了种群的多样性。

2.5 基于自适应的改进PSO算法流程

基于以上分析，本文提出的求解M OP的改进PSO算法流程如图3所示。

针对图3，对该方法的操作步骤描述如下：①初始化内部种群Ps的粒子数为最小规模Ss，迭代次数t＝0（初始化时未开始迭代），随机初始化粒子速度vi和位置xi，并将粒子当前位置作为该粒子的个体最优值。②判断St中每个粒子是否是非支配解，若是，则将其放入外部种群，记录外部种群粒子数Sp，转 ③；否则，转 ⑥。③ 删除外部种群中的重复个体以及被支配个体，保留非劣个体。④计算外部种群Pt中各粒子的拥挤距离Di，并将所有粒子基于Di降序排列。⑤判断Sp是否大于Sm，若是，则删除Pt中后Sp－Sm个个体，转 ⑥；否则，直接转 ⑥。⑥ 更新全局极值Pg。判断内部种群规模St是否超出规模上限Se，若是，直接转 ⑦；否则，单点交叉产生新的粒子，并放入内部种群，并记录个体极值，转⑦。⑦t←t＋1。进化计算内部种群中个体速度和位置，根据进化计算结果更新个体极值。⑧判断是否达到最大迭代次数tmax，若是，则输出外部种群中的Pareto解集，结束；否则，转②。

图3 算法流程

3 性能验证与实例仿真

3.1 测试函数和指标及性能分析

将本优化方法应用于经典的多目标优化函数ZDT1：

本文采用了如下2个评价非支配解集优劣的量化标准[14]进行算法的性能分析：

其中外部种群的粒子个数Sp是优化方法所得的非支配解的个数；DSi为第i个解到Pareto最优解在目标空间上的最短距离；di是第i个解到其他解在目标空间上的距离为di的平均值。

仿真环境：计算机处理器为英特尔Celeron（赛扬）2.66GHz，内存768MB，Windows XP操作系统，采用MATLAB7.0编写算法程序。

参数设置如下：NSGA－Ⅱ、SPEA2（强度Pareto进化算法）[15]的交叉概率为0.8，变异概率为1／L（L为染色体编码长度），SPEA2的外部集设为200；NSPSO（基于非支配解的PSO算法）[16]内部和外部种群大小均为200。本文算法的内部种群初始规模为200，最大规模为400，外部种群最大规模为200，迭代次数为1000，设置参数c1＝2，c2＝2，ω0＝0.9，ω1＝0.35。 表1所示为10次独立运行的数据统计结果。

表1 各算法的收敛性和分布性比较

表1的实验结果[17]表明，本文所提算法在收敛性和分布性方面与其他三种算法相比具有较大优势，满足了求解多目标优化的要求。

3.2 应用实例

将本文算法应用于某铜卷加工企业，通过仿真结果验证算法的有效性。

选取该企业的5个加工单元对企业接到的一批订单进行生产调度优化。各产品在各生产单元上的加工时间和交货期如表2所示。

表2 产品在各生产单元上的加工时间表 h

鉴于最大完成时间的方差相对最大拖后时间要小，因此令目标f1为最大完成时间的5倍，目标f2为最大拖后时间的2倍[18]。

算法参数设置：内部种群初始规模Ss＝20，最大规模Se＝40，外部种群最大规模Sm＝20，迭代次数tmax＝100，设置参数c1＝2，c2＝2，ω0＝0.9，ω1＝0.35，外部种群粒子数初始化Sp＝0。

根据以上建立的数学模型与设计的算法，利用MATLAB7.0编程进行调度问题的求解，最终得到外部种群Pareto解集的分布如图4所示。由图4可以看出，算法得到了完整的Pareto解集，并且图中Pareto最优解的目标向量比较均匀地分布在最优界面附近，说明基于拥挤距离排序的策略对外部种群保持的必要性。仿真结果表明，该改进的PSO算法用较小的迭代次数就可以得到较好的Pareto解，保持了算法的快速收敛性，体现了该调度方法的合理和有效性。

图4 Pareto解集分布图

4 结语

本文根据铜卷加工生产调度问题的特点，采用改进的粒子群优化算法求解该调度问题。首先采用外部种群保留进化过程中产生的Pareto最优解，同时在外部种群中基于拥挤距离概率更新全局极值，最后基于非支配解的概率使用单点交叉方式产生新的粒子来自适应调整内部种群的大小，同时采用动态自适应调整的惯性权重来更新粒子速度和位置。仿真实例验证了该算法能较好地保持种群的多样性，使算法能够快速收敛到Pareto最优解集。如何将该算法进行调整用于更多约束和评价的混合型生产调度模型，需要进一步研究。

[1]张旭升，戴青云.一种基于改进蚁群算法的混合型调度算法[J].中国制造业信息化，2010，39（13）：8-17.

[2]Deb K.Multi－objective Optimization Using Evolutionary Algorithms[M].New York：John Wiley ＆Sons，2001.

[3]贾兆红，陈华平，唐俊，等.面向多目标的自适应动态概率粒子群优化算法[J].系统仿真学报，2008，20（18）：4959-4963.

[4]Kennedy J，Eberhart R.Particle Swarm Optimization[C]／／IEEE Int.Conf.on Neural Networks.Piscataway，1995：1942-1948.

[5]李丽，牛奔.粒子群优化算法[M].北京：冶金工业出版社，2009.

[6]周辉仁，唐万生，魏颖辉.基于微粒群算法的柔性流水车间调度优化[J].中国机械工程，2010，21（9）：1053-1057.

[7]鲁建厦，蒋玲玲，李修琳.基于混合粒子群算法求解装配线第二类平衡问题[J].中国机械工程，2010，21（4）：420-424.

[8]武广州.混合型生产方式车间调度建模及应用[D].武汉：武汉理工大学，2007.

[9]公茂果，焦李成，杨咚咚，等.进化多目标优化算法研究[J].软件学报，2009，20（2）：271-289.

[10]Laumanns M，Thiele L，Deb K，et al.Combining Convergence and Diversity in Evolutionary Multiobjective Optimization[J].Evolutionary Computation，2002，10（3）：263-282.

[11]陈民铀，张聪誉，罗辞勇.自适应进化多目标粒子群优化算法[J].控制与决策，2009，24（12）：1851-1864.

[12]李中凯，谭建荣，冯毅雄，等.基于拥挤距离排序的多目标粒子群优化算法及其应用[J].计算机集成制造系统，2008，14（7）：1329-1336.

[13]Tan K C，Lee T H，Khor E F.Evolutionary Algorithms with Dynamic Population Size and Local Exploration for Multi－objective Optimization[J].IEEE Trans.on Evolutionary computation，2001，5（6）：565-588.

[14]蒋程涛，邵世煌.基于适配粒子群的多目标优化方法[J].计算机工程，2007，33（21）：175-178.

[15]Zitzler E，Thiele L.Multiobjective Evolutionary Algorithm：a Comparative Case Study and the Strength Pareto Approach[J].IEEE Transactions on Evolutionary Compution，1999，3（4）：252-271.

[16]Benabid R，Boudour M，Abido M.Optimal Location and Setting of SVC and TCSC Devices Using Non－dominated Sorting Particle Swarm Optimization[J].Electric Power Systems Research，2009，12（79）：1668-1677.

[17]陈绍新.多目标优化的粒子群算法及其应用研究[D].大连：大连理工大学，2007.

[18]王凌.车间调度及其遗传算法[M].北京：清华大学出版社，2003.