基于混合粒子群优化算法的置换流水车间调度问题研究

刘 敏 张超勇 张国军 孙 艺

华中科技大学数字制造装备与技术国家重点实验室，武汉，430074

0 引言

置换流水车间调度问题（permutation flow shop scheduling problem，PFSSP）是目前研究最广泛的一类典型调度问题，具有很重要的工程应用价值。然而，绝大多数PFSSP（工件数n≥3）是NP－hard问题，不存在多项式精确求解算法，因此，对该问题的研究不仅具有重要的实际意义，而且具有重要的理论意义。

国内外学者在过去几十年里做了大量研究，提出了许多解决置换流水车间调度问题的方法。这些方法大致可分为三类：精确算法、启发式算法和元启发式算法。由于NP－hard问题的复杂性，精确算法只适用于小规模问题的求解。启发式算法能够快速构造解，但是通常解的质量较差。元启发式算法能在较短时间内获得较高质量的解，因此在求解置换流水车间调度问题中获得广泛应用。

粒子群优化（particle swarm optimization，PSO）算法是受鸟群捕食启发产生的元启发式算法，也是一种基于群体的优化算法，最早由Kennedy等[1]于1995年提出。PSO算法是通过种群内粒子之间的合作与竞争而产生的群体智能优化算法。与遗传算法（genetic algorithm，GA）相比，PSO算法保留了基于种群的全局搜索策略，搜索模型简单，收敛速度快，鲁棒性高，但是，PSO算法主要用于无约束连续函数的优化。

目前，PSO算法在解决连续函数优化方面取得了成功，但在如何应用于离散组合优化问题方面尚处于探索阶段，其解决离散组合优化问题主要有以下两条途径，一是采用基于随机键的最小位置值（smallest position value，SPV）规则将标准PSO算法应用于组合优化问题中，二是采用向量编码方式的离散粒子群算法解决离散组合优化问题。Tasgetiren等[2]基于SPV规则提出了一种混合PSO算法，并将其用于求解最小化加权总拖后时间的单机流水车间调度问题，以及最小化最大完工时间和总流经时间的PFSSP问题[3－4]。Rameshkumar等[5]采用向量编码的方式提出了离散PSO算法，定义了粒子群算法的离散操作，并将其用于求解最小化最大完工时间的PFSSP问题。Lian等[6]直接将GA的交叉和变异操作作为PSO算法中粒子速度和位置的更新操作，提出了一种基于PSO的进化算法，并将其应用于求解最小化最大完工时间的PFSSP问题。

本文结合PSO算法和变邻域搜索算法各自的优点，设计了一种混合PSO算法（hybrid particle swarm optimization algorithm，HPSO）。该混合算法采用基于升序排列规则（ranked－order－value，ROV）的连续PSO算法对解空间进行全局搜索，应用基于关键路径的变邻域搜索算法对全局优化的粒子进行局部搜索，并使算法在分散搜索和集中搜索之间达到合理的平衡。通过对Taillard[7]和 Watson等[8]提出的基准测试集进行仿真实验，证实了算法的有效性。

1 HPSO算法求解置换流水车间调度问题

1.1 基于PSO算法的置换流水车间调度研究

基本粒子群算法采用速度－位置模型进行搜索。算法初始化为一群随机粒子，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：第一个是粒子本身所找到的最好解，叫做个体极值点（用pbest表示其位置），全局PSO中的另一个极值点是整个种群目前找到的最好解，称为全局极值点（用gbest表示其位置），而局部PSO不用整个种群而是用其中一部分作为粒子的邻居，所有邻居中的最好解就是局部极值点（用lbest表示其位置）。在找到这两个最好解后，粒子根据下式来更新自己的速度和位置：

粒子i的信息可以用n维向量表示，位置表示为Xi＝（xi1，xi2，…，xin），速度表示为vi＝ （vi1，vi2，…，vin），其他向量类似。 其中，ω（t）＝ω（t－1）β是惯性系数；β为线性递减因子，其主要作用是产生扰动，以防止算法的早熟收敛；c1和c2为学习因子，分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长，通常设c1＝c2＝2；r1和r2是[0，1]之间均匀产生的随机数。

1.1.1 解的表示和ROV规则

对于PFSSP问题，最常用的编码方式就是直接采用基于工件的排序。由于连续PSO算法中微粒的位置为连续值矢量，为了得到微粒位置矢量到工件排序的映射关系，基于随机键编码，王凌[9]提出了ROV规则，将粒子的连续位置矢量Xi＝（xi1，xi2，…，xin）转换为离散的加工排序π，即机器上各工件的加工 顺序，π ＝ ｛σ1，σ2，…，σn｝。

ROV规则具体描述如下：对于一个微粒的位置矢量，首先将值最小的分量位置赋予ROV值为1，其次将值第二小的分量位置赋予ROV值为2，依此类推，直到将所有的分量位置都赋予一个唯一的ROV值，从而基于ROV值构造出一个工件排序。

1.1.2 种群初始化

初始种群一方面应该具有一定的分布性，能够以较大的概率覆盖整个解空间，另一方面为了提高种群的搜索效率，避免盲目搜索，初始种群中也应该包括部分质量较高的解。因此，本文的初始解采用以下两种方式产生，一是用构造性启发式方法产生，二是在一连续区间内随机产生。在构造性启发式方法中，本文采用NEH启发式算法，它是由Nawaz、Enscore和 Ham共同提出，是当前解决PFSSP性能最好的启发式算法。该算法步骤如下：①按工件在机器上的总加工时间递减的顺序排列n个工件；②取前两个工件调度，使部分总完工时间达到最小；③把第k（k＝3，4，…，n）个工件插入到k个可能的位置，求得最小的部分总完工时间。

NEH启发式算法产生的解是工件序列，在此，按如下方式将其转换为一定区间内的位置矢量：

式中，xNEH，j为粒子在第j维的位置值；sNEH，j为通过NEH算法得到的解的第j维工件序号；xmax，j、xmin，j分别为连续空间上粒子位置矢量的上界值和下界值；r3为[0，1]间均匀产生的随机数。

xij、vij随机产生的方式为

其中，xij在连续区间[xmin，xmax]变化，vij在连续区间[vmin，vmax]变化。

1.2 基于变邻域搜索的置换流水车间调度研究

Mladenovic等[10]在1997年提出了一种变邻域搜索算法，在很多问题的求解中得到了很好的应用。不过，变邻域搜索的效率取决于邻域结构的选择。Zobolas等[11]将遗传算法与变邻域搜索算法结合来求解置换流水车间调度问题，Bassem等[12]将分布评估算法与变邻域搜索算法结合来求解转换流水车间调度问题。然而，他们对所有工件均采取插入移动和交换移动两种邻域操作方式，没有考虑问题的具体邻域知识。本文采用基于关键路径的两种邻域结构，基于变邻域搜索求解置换流水车间调度问题，有效地提高了算法集中搜索能力。

1.2.1 关键路径

针对问题知识设计的局部搜索是邻域搜索元启发式算法的关键组成部分。对于车间调度问题，例如流水车间调度问题（flow shop scheduling problem，FSSP），可行调度的关键块中工序的局部移动是该类问题最有效的更新算子之一。

路径和关键路径可以由一个有向栅格图来分析，G（π）＝（N，E）是表示排列π的一个栅格图，其中N 是所有节点的集合，Ni，j∈ N，i∈ ｛1，2，…，m｝，j∈ ｛1，2，…，n｝，Nij在N中具有权重pi，π（j），而 E 则是所有箭头指向的有向边的集合，它不具有权重。图1所示为G（π）的有向栅格图，π＝｛2，7，5，3，6，1，4｝为工件数n＝7、机器数m＝5的置换流水车间调度问题的一个排列，粗箭头所示的为该排列的关键路径。

图1 有向栅格图G（π）

由图1所示的有向栅格图可以得到排列的关键路径，同时找到关键路径上的关键块Bk，在这里共有3个关键块，分别为：B1＝｛2，7，5｝、B2＝｛5，3，6｝和B3＝｛6，1，4｝。关键块所对应的机器分别为m1＝2、m2＝3、m3＝5。

1.2.2 基于关键路径的变邻域搜索

Nowicki等[13]、Grabowski等[14]分别在1996年和2004年利用关键路径和块的概念，针对置换流水车间调度问题提出了一种有效的邻域结构，并将其成功地运用在了禁忌搜索（tabu search，TS）算法中，取得了较好的结果。本文将这两种邻域结构运用在了变邻域搜索算法中。

在Grabowski等[14]提出的邻域结构（简称为邻域结构Gw）中，执行插入移动时，将被移动的工件插入到相邻关键块边界之后，其具体的移动操作如图2所示（在图2中标记为黑色的工件为关键块边界，椭圆包含的区域是需要考虑插入的位置，下同）。

图2 邻域结构Gw的移动操作

在Nowicki等[13]提出的邻域结构（简称为邻域结构Ns）中，执行插入移动时，当要被移动的工件在关键块内时，他们仅考虑了相邻关键块中的插入位置，如图3a所示，如果要被移动的工件在关键块边界上，除了考虑相邻关键块内的位置外，其临近的位置也要考虑在内，如图3b所示。

图3 邻域结构Ns的移动操作

由此，笔者设计了包含两种基于关键路径的不同邻域结构的变邻域搜索算法，将邻域结构Gw作为第一邻域结构，邻域结构Ns作为第二邻域结构。算法流程如图4所示，其中Nk（s）表示解s的第k种邻域，具体的算法流程如下：

（1）初始化。选择邻域结构集Nk，初始化内外循环步长inloop，并给出邻域搜索初始解s0，外循环次数i＝0。

（2）随机产生s0的第一种邻域结构s，s∈N1（s0），内循环次数l＝0，并循环步骤（3）～ 步骤（8），直到达到外循环步长outloop。

（3）循环步骤（4）～ 步骤（7），直到达到内循环步长。

（4）设置k＝1。

（5）循环步骤（6）～ 步骤（7），直到k＝kmax。

（6）产生s的第k种邻域结构s1，s1∈Nk（s）。

图4 基于关键路径的变邻域搜索流程

（7）若序列s1优于s，则用s1替代s并设置k＝1，否则，将k值加1。

（8）若序列s优于s0，则用s替代s0。（9）输出局部搜索最优序列s0。

1.3 混合粒子群优化算法流程

本文结合了问题本身的邻域知识结构，把PSO算法和变邻域搜索算法有机结合，设计了一种混合粒子群优化算法，使分散搜索和集中搜索达到有机平衡，混合粒子群优化算法的流程如图5所示。具体的算法流程如下。

图5 混合粒子群算法具体流程

（1）初始化算法参数——惯性系数w、认知系数c1和社会系数c2等。

（2）初始化粒子种群。①利用NEH算法生成种群的10%个工件加工序列，评价其调度目标，并根据式（3）将加工序列转换为一个粒子的位置矢量；②随机产生余下种群的90%个粒子的位置矢量，根据ROV规则得出各粒子对应的工件加工序列，并根据加工序列评价各粒子的调度目标；③随机初始化种群中所有粒子的速度矢量；④令各粒子的局部最优为当前位置，并根据比较的各粒子的调度目标确定其中最好的粒子的位置，并将其作为全局最优。

（3）循环步骤（4）～步骤（6）直到满足停止条件，这里定义的停止条件是种群代数达到给定的最大迭代次数。

（4）对所有粒子执行下列操作：①更新所有粒子的速度和位置；②根据ROV规则，确定各粒子位置矢量所对应的工件加工序列，并评价各粒子调度目标；③更新各粒子的个体极值。

（5）更新全体极值。

（6）对全体极值执行变邻域搜索算法：①找出全局极值的关键路径，设计邻域结构；②执行基于关键路径的变邻域搜索算法；③更新全局极值。

（7）输出全体极值。

2 实例仿真与结果分析

为了验证提出的混合粒子群优化算法，本文测试数据采用Taillard[7]在1993年提出的120个基准测试问题，以及Watson等[8]在2002年提出的随机型基准测试问题，应用提出的算法求解这些基准实例，并与其他文献算法进行比较，以验证算法的有效性。

本文算法编程采用Visual C＋＋6.0，计算机CPU为Intel Celeron M520，主频为1.6GHz，物理内存为512MB，操作系统为Windows XP。实验参数设置如下：c1＝c2＝2.0，惯性系数w初始值设为0.9，β＝0.975，β最小不能小于0.4，粒子的最小位置值xmin＝0，粒子的最大位置值xmax＝4.0，粒子的最小速度值vmin＝14.0，粒子的最大速度值vmax＝4.0，最大迭代次数设为400，种群规模设为40，每个实例独立连续运行10次。Taillard基准测试集包含120个流水线调度问题实例，通过网站 http：／／mistic.heig－vd.ch／taillard／中的FSP实例可以获得这些实例的数据和当前最好解。本文选取每种规模系列问题中的第一个和第五个问题进行计算，并运用提出的混合粒子群优化算法（HPSO）与 Nearchou[15]提出的多算子遗传算法、Lian等[16]提出的一种新的粒子群算法（NPSO）和Zhang等[17]提出的混合轮换两阶段粒子群算法（ATPPSO）进行比较，结果如表1所示。表1中也列出了本文算法获得的最优解（best solution，BS）、最差解（worst solution，WS）、多次运行获得的解的平均值（average solution，AS）和最优相对偏差（best relative error，BRE）。由表1可知，本文算法求解Taillard系列问题能够取得很好的效果，相比其他几种算法本文算法能够更好地收敛于最优解。

2002年，Watson等[8]针对置换流水车间调度问题给出了一类新的基准问题测试集，该测试集共有14 000个问题，分为随机型问题和构造型问题，其中随机型问题有800个，分别为20×20rand问题，50×20rand问题，100×20rand问题，200×20rand问题，20×20rand－narrow问题，50×20rand－narrow问题，100×20randnarrow问题和200×20rand－narrow问题8种，每种有100个同等规模的问题，其中的rand问题的数值从1～99间随机产生，rand－narrow问题的数值从45～55间随机产生，这些测试集的数据和Watson等给出的最优解都能在网站http：／／www.cs.colostate.edu／sched／generator／中 查到。通过本算法对其中的800个随机型问题进行了测试，将其中的部分问题结果列于表2中。从表2可以看到，90%的被测试问题都能达到先前给出的问题的最好解，并改进了其中8个问题的最好解结果，这一结果充分表现了本文算法具有良好的收敛性。

表1 不同调度算法Taillard基准问题测试结果

表2 算法求解Watson基准问题测试结果

3 结束语

本文针对置换流水车间调度问题提出了一种结合粒子群优化算法和变邻域搜索算法的混合优化算法。在混合算法中，采用NEH算法和随机方式产生初始解，采用基于ROV规则连续PSO算法进行有效的全局搜索；应用基于关键路径的变邻域搜索算法进行局部搜索，使分散搜索和集中搜索达到有效的平衡，提高了算法的搜索能力。运用混合算法求解了Taillard基准问题和 Watson基准问题，并将测试结果与其他算法比较，证实了该算法的有效性。

在今后的工作中，可从以下两个方面进行改进研究：一方面，用局部搜索能力更强的禁忌搜索算法代替变邻域搜索算法；另一方面，对邻域结构采用评估策略，从而进一步提高算法的搜索效率。

[1]Kennedy J，Eberhart R C.Particle Swarm Optimization[C]／／Proceedings of International Conference on Neural Net－works.Piscataway：IEEE Press，1995：1942-1948.

[2]Tasgetiren M F，Sevkli M，Liang Y C，et al.Particle Swarm Optimization Algorithm Forpermutation Flowshop Sequencing Problem[J].Lecture Notes in Computer Science，2004，3172：382-389.

[3]Tasgetiren M F，Liang Y C，Sevkli M，et al.Particle Swarm Optimization and Differential Evolution for the Singlemachine Total Weighted Tardiness Problem[J].Int.J.Prod.Res.，2006，44：4737-4754.

[4]Tasgetiren M F，Liang Y C，Sevkli M，et al.A Particle Swarm Optimization Algorithm for Makespanand Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem[J].European Journal of Operational Research，2007，177：1930-1947.

[5]Rameshkumar K，Suresh R K，Mohanasundaram K M.Discrete Particle Swarm Optimization（DPSO）Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[J].Advances in Natural Computation，2005，3612：572-581.

[6]Lian Z G，Gu X S，Jiao B.A Similar Particle Swarm Optimization Algorithm Forpermutation Flowshop Scheduling to Minimize Makespan[J].Appl.Math.Comput.，2006，175：773-785.

[7]Taillard E.Benchmarks for Basic Scheduling Problems[J].European Journal of Operational Research，1993，64：278-285.

[8]Watson J P，Barbulescu L，Whitley L D，et al.Contrasting Structured and Random Permutation Flowshop Scheduling Problems：Search Space Topology and Algorithm Performance[J].ORSA Journal of Computing，2002，14（2）：98-123.

[9]王凌.微粒群优化与调度算法[M].北京：清华大学出版社，2008.

[10]Mladenovic N，Hansen P.Variable Neighborhood Search[J].Computers and Operations Research，1997，24：1097-1100.

[11]Zobolas G I，Tarantilis C D，Ioannou G.Minimizing Makespan in Permutation Flow Shop Schedulingproblems Using a Hybrid Metaheuristicalgorithm[J].Computers ＆ Operations Research，2009，36：1249-1267.

[12]Bassem J，Mansour E，Patrick S.An Estimation of Distribution Algorithm Forminimizing the Total Flowtime in Permutation Flowshop Scheduling Problems[J].Computers ＆ Operations Research，2009，36：2638-2646.

[13]Nowicki E，Smutnicki C.A Fast Tabu Search Algorithm for Thepermutation Flowshop Problem[J].European Journal of Operational Research，1996，91：160-175.

[14]Grabowski J，Wodecki M.A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion[J].Computers and Operations Research，2004，31（11）：1891-1909.

[15]Nearchou.The Effect of Various Operators on the Genetic Search Forlarge Scheduling Problems[J].International Journal of Production Economy，2004，88：191-203.

[16]Lian Z G，Gu X S，Jiao B，et al.A Novel Particle Swarm Optimization Algorithm Forpermutation Flow－shop Scheduling to Minimize Makespan[J].Chaos Solitons and Fractals，2008，35（5）：851-861.

[17]Zhang C S，Ning J X，Ouyang D T，et al.A Hybrid Alternate Two Phases Particle Swarm Optimization Algorithmfor Flow Shop Scheduling Problem[J].Computers ＆Industrial Engineering，2010，58：1-11.