基于基因片段分解的粒子群算法求解置换Flowshop问题

郝平波，魏英姿，冯艺君

（沈阳理工大学 信息科学与工程学院，辽宁 沈阳 110159）

流水线调度问题（flow-shop scheduling problem，FSP）是许多实际流水线生产调度问题的简化模型，约有25%的生产制造、组装线盒信息服务设施可简化为FSP模型。FSP是一类典型的NP问题[1]，也是目前研究最广泛的一类调度问题，因此其研究具有重要的理论意义和工程价值。

粒子群算法 （particle swarm optimization，PSO）[2]是由Kennedv和Eberhart于1995年对鸟群觅食行为研究提出来的。PSO和遗传算法类似，是一种基于迭代的优化算法。算法初始化为一群随机粒子（随机解）。然后粒子们追随当前的最优粒子在解空间中探索，通过迭代找到最优解。在每一次迭代中，粒子通过跟踪个体极值（本身所找到的最优解）和全局极值（整个种群目前找到的最优解）来更新自己。与其他进化算法相比，PSO保留了基于种群的全局搜索策略，其特有的记忆可以动态地跟踪当前的搜索情况来调整下一步的搜索策略，是一种更高效的并行搜索算法，而且具有扩展性，容易与其他算法结合。适用于处理连续优化问题及多点搜索，已成功应用于函数优化、多目标优化、动态优化等领域中。因此，PSO一经提出，立刻引起了演化计算等领域学者们的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。

1 Flowshop调度问题描述和数学模型

Flowshop调度问题的简化数学模型是安排n个工件在m台机器上加工顺序的问题，每个零件在各机器上加工的顺序相同，同时约定每个工件在每台机器上只加工一次。每台机器一次在某一时刻只能加工一个工件，各工件在各机器上所需的加工时间和准备时间已知，要求得到某调度方案使得某项指标最优。进一步，约定每台机器加工的各工件的顺序相同，则称其为置换FlowShop调度问题。

置换FlowShop调度问题的数学模型如下：令tij为工件i在机器j上的加工时间，θkij为机器k上加工完工件i后马上加工工件j所需的准备时间 （无特殊说明，=0），Ti为工件 i的加工完毕时间，不是一般性，假设各工件按机器1到m的顺序进行加工，令 π=（σ1，σ2，…，σn）为所有工件的一个排序，则以最大完成时间为指标，即Makespan指标：

2 粒子群算法

在d维搜索空间中第i个粒子的位置和速度分别表示为Xi=[xi,1，xi，2，…，xi，d]和 Vi=[vi，1，vi，2，…，vi，d]。 通过评价各粒子的目标函数。 确定 t时刻每个粒子所经过的最佳位置（pbest）Pi=[pi，1，pi，2，… ，pi，d]以及群体的最佳位置（gbest）Pg，按如下公式更新各粒子的速度和位置：

其中，ω为惯性因子，c1和c2为正的加速度常数，r1和r2为0到1之间的随机数。通过设置粒子的速度区间[vmin，vmax]和位置区间[xmin，xmin]，可以对粒子的移动做适当的限制。

粒子群算法流程：

Step1:随机初始化种群中每个粒子的位置和速度。

Step2:评价每个粒子，将当前各粒子的位置和目标值存放在各粒子的pbest中，将所有pbest中目标值最优的个体的位置和目标值存放在gbest中。

Step3:按式（1）和式（2）更新各粒子的速度和位置。

Step4:评价种群中的所有粒子，更新pbest和gbest。

Step5:若满足终止条件，则输出gbest及其目标值，否则返回Step3。

3 粒子群优化算法求解Flowshop调度问题

3.1 解的描述

采用n维粒子群优化算法求解n个工件的置换流水车间调度问题。 粒子的位置 Xi=[xi，1，xi，2，…，xi，n]蕴含了工件排列顺序。本文采用ROV规则[3]提取工件的加工顺序。表1给出了将维数为6的粒子位置转换为6个工件顺序的实例。

表1 粒子的位置及其对应的ROV值Tab.1 Particle position and its corresponding value ROV

首先，赋予值最小xi，1的分量位置ROV值1，接下来赋予xi，6对应的分量位置 ROV 值 2， 然后分别赋予 xi，3，xi，5，xi，2和 xi，4分量位置ROV值3，4，5和6，从而得到工件的加工次序，即π=（1，5，3，6，4，2）。

3.2 粒子群算法的初始化及其基因片段[4]的分解

在粒子群算法中，粒子的位置和速度的初始值通过在区间[0，1]上的均匀分布随机产生。个体最优解的初始值为个体的初始解。适应值F（x）初始值都设为0。初始种群的生成，本文提出了一种贪婪的生成方法。

例如：粒子的位置 Xi=[xi，1，xi，2，…，xi，n]，种群大小为popsize，将其分成 m 个基因片 段[xi，1，xi，2，… ，xi，n1]，[xi，n1+1 ，xi，n1+2 ，…，x i，n2]，…，[xi，nm-2+1 ，xi，nm-2-2 ，…，xi，nm-1]， [xi，nm-1+1 ，xi，nm-1+2 ，…，xi，n]i∈[1，popsize]，适应值为 F（x）。 本文初始种群的生成：

经适应值的计算，找到基因片段 1 的最优排序[xk，1，kk，2，…，xk，n1],k∈[1，popsize])。 接着生成

种群对基因片段2进行最优调度，直到对基因片段m调度完毕。将得到一组最优排序。

例如：粒子的位置 Xi=[xi，1，xi，2，…，xi，d]中 d=25，将其平均分成5个基因片段，即每个基因片段5个工件。每个基因片段有5！种排序，则整个片段有5×5！种排序。这远远比整个片段25！种排序少得多。从而提升了解的收敛和程序的运行速度。如果基因片段中工件不够，则以0补齐。

3.3 综合学习与基因片段间的合作

3.3.1 综合学习策略

找局部最优值较大的粒子，随机的与其他粒子的局部最优值比较，选取适应值较小的一个替换该粒子的局部最优值。

3.3.2 基因片段间的合作

找出每个粒子所经过的最佳位置pbest以及群体发现的最佳位置gbest。利用式（1）和式（2）更新粒子的速度和位置。根据目标函数更新基因片段中各粒子的最优适应值、最优位置和基因片段全局最优适应值。

3.4 种群局部搜索

将每次迭代后得到的基因片段最优解的最佳值作为初始解，做交换局部搜索[5]。 具体地说，假设[xk，1，xk，2，…，xk，n1]，

k∈[1，popsize]为得到的基因片段最优解，如果 i≠k，将[xk，1，xk，2，…，xk，n1]与[xi，1，xi，2，…，xi，n1]交换。

3.5 算法流程

Step1:确定Pso的控制参数。包括种群规模，最大迭代代数，惯性因子等。

Step2:初始种群的生成，并将其分成个基因片段。

Step3:计算每个粒子的目标函数，如果粒子的当前解优于个体最优解，更新个体最优解，利用个体最优解更新全局最优解。

Step4:根据4.3和4.4更新所有粒子的速度和位置。

Step5:计算每个粒子的目标函数。

Step6:对于每一个粒子，如果当前解优于个体最优解，则更新个体最优解，利用个体最优解更新全局最优解。

Step7:如果停止条件满足，则输出全局最优解；否则，转Step4。

4 仿真结果

为测试算法的性能，本文通过对Rec系列基准测试。本文用MATLAB7.1编程。硬件环境的处理器主频为2.53 GHz，内存为0.99 G，操作系统为Windows XP。参数设置为：c1=c2=2，惯性因子ω=0.4，粒子最小位置值xmin=0，粒子最大位置值xmax=1。粒子最小速度值vmin=0，粒子最大速度值vmax=1。对于Rec系列的IPSO（本文算法）算法，粒子种群规模为50，迭代次数为100。PSO算法，Rec01到Rec23种群规模为50，迭代次数为100，Rec25到Rec41种群规模为50，迭代次数为500。每个算例独立运行50次。

设A表示本实验取得的最优值，B表示平均值，C表示最差值，C*表示已知最优值。则最佳相对误差：BRE=（A-C*）/C*×100%、 平均相对差:ARE=（B-C*）/C*×100%、 最差相对误差:WRE=（C-C*）/C*×100%[6]分别表示 50 次运行得到的最佳值、平均值以及最差值与C*的相对误差。表2记录了本文仿真的实验数据。

从表2可见，IPSO算法明显好于PSO算法。在20个子问题中，IPSO在每个子问题上都取得了优于PSO算法的解，在5个子问题上取得了最优解。从运行过程来看，IPSO算法取得解得时间要远小于PSO算法。

从图1中可以看出，随着迭代次数的增加，PSO陷入了局部最优，而IPSO在PSO陷入局部最优之前就通过扩大搜索范围找到了比PSO更好的解。

图2为在Rec 07上的甘特图，从图2中可以看出，工件被合理地分配在各机器上进行加工。

从实验结果我们可以发现采用基因片段分解的粒子群算法[7]在求解置换流水调度问题上求解性能良好，所求解均好于PSO算法的结果，为求解置换流水线调度问题提供了一种新的途径。

表2 本文算法求解Rec系列若干问题仿真结果Tab.2 This algorithm Rec Series simulation results of a number of issues

图1 在Rec 07上的运行情况Fig.1 The operation of Rec 07

图2 在Rec 07上的甘特图Fig.2 The gantt chart of Rec 07

5 结束语

本文提出了基因片段分解的粒子群算法求解置换流水车间调度问题，采用了基因片段分解的方法，初始个体最优解基于贪婪方法得到，算法中结合粒子群算法的全局搜索能力和交换粒子位置的局部搜索能力将解决连续优化问题的标准粒子群优化算法成功应用于Flowshop调度问题中，为解决生产调度问题提供了一个高速有效的寻优算法。通过对不同维数的基准问题进行计算机仿真，仿真结果表明了本文提出算法的有效性与可行性。

[1]Garey M R，Johnson D S，Sethi R.The complexity of flowshop and job-shop scheduling[J].Mathematics of Operations Research，1976，1（1）:117-l29.

[2]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks.Piscataway，N.J.，USA:IEEE Press，1995:1942-1948.

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

[4]梁艳春，冯大鹏，周春光.遗传算法求解旅行商问题时的基因片段保序[J].系统工程理论与实践，2000，20（4）:7-12.LIANG Yan-chun，FENG Da-peng，ZHOU Chun-guang.Order preserving of gene section for solving traveling salesman probeloms using genetic algorithms[J].System Engineering-Theory&practice， 2000，20（4）:7-12.

[5]任红燕，张文国.一种新的求解置换Flowshop问题的粒子群算法[J].计算机系统应用，2008，17（5）:3-4.REN Hong-yan，ZHANG Wen-guo.A novel particle swarm optimization algorithm for permutation flowshop problem[J].Computer System Applications，2008，17（5）:3-4.

[6]周鹏.求解置换流水车间调度问题的混合蚁群算法[J].计算机工程与应用，2009，45（17）:191-193.ZHOU Peng.Hybdd ant colony algorithm for permutation flow shop scheduling problem [J].Computer Engineering and Applications，2009，45（17）:191-193.

[7]叶红权,郭益辉.粒子群算法在电力系统低频振荡辩识中的应用[J].陕西电力,2009,37（3）：35-38.YE Hong-quan,GUO Yi-hui.Application of Particle Swarm Optimization in the Identification of Low-frequency Oscillation in Power System [J].Shaanxi Electric Power，2009,37（3）：35-38.