改进的协同粒子群算法求解流水车间调度问题

秦志伟

摘 要：针对协同粒子群算法容易早熟和停滞的问题，提出了一种基于精英综合学习的协同粒子群（ECLCPSO）算法。该算法在协同粒子群算法的基础上，采用精英库种群和普通种群并行协同进化架构。精英库种群由高适应度个体构成，进行自我综合学习，普通种群中个体向精英库种群进行精英学习。为了避免算法陷入局部最优，引入了扰动机制。将该算法应用于Flow shop调度问题上，和另外三种优化算法进行比较，仿真结果证明改进的算法收敛速度快且精度高，优化性能较好。

关键词：协同；粒子群；精英学习；流水车间调度

1 引言

当今的制造技术正由自动化、数字化、网络化向智能化方向发展，智能制造（Intelligent Manufacturing，IM）被工业界和学术界普遍认为代表了制造业的发展方向，随之带来的智能调度问题成为研究的热点。特别是工业4.0的提出，使得智能调度在智能制造中的智能工厂和智能物流两方面扮演着核心大脑的角色，是智能制造的基础。而流水车间调度问题（Flow Shop Scheduling Problem，FSSP），作为许多实际流水线上的简化模型，它已被是一个典型的NP-hard问题1[1]，因此其研究具有重要的理论意义和工程意义。

虽然协同粒子群算法可以有效地改善传统算法效率低、鲁棒性差的问题，但容易陷入局部极值。由此，本文以确定型无限中间存储方式的流水车间作为研究对象，并以整个流水车间工件的加工时间Makespan为目标函数，在将精英策略和综合学习策略有效地结合一起，并引入扰动机制，来改进协同粒子群算法，提高协同粒子群算法的收敛速度和精度。

2 数学描述

本文以流水车间工件加工时间 Makespan为目标函数。Makespan可以描述为从第一个加工工件开始加工到最后一个工件完工所经历的时间，问题具体描述如下：

一个n x m的确定型流水车间调度问题就是n个工件在n台机器上流水加工的过程，假设工件按机器1～m的顺序依次加工，令tij表示工件i在机器j上的加工时间，Cij表示工件i在机器j上的加工完成时间，Cmax表示所有工件加工完成时间，即Makespan。任给一个调度方案，即工件的加工排序，按照工件加工的次序，任意工件ik在机器j上的完成时间可以分为以下3种情况：[2]

，

上述模型即是FSSP优化的一个目标，可以看出，流水车间调度问题就是寻找一种可行的调度方案，使得加工周期最小，也就是说，求解最小的makespan。

3 精英综合学习的协同粒子群算法流程

Step 1 初始化。确定m和n的数量，m是加工机器的数量，n是工件的数量，设定算法的协同种群个数、初始的子群粒子位置及速率，将粒子的个体最优位置设置为粒子的当前位置，随机选择一个粒子作为种群最优位置。

Step 2 按照适应度大小对每个子群粒子的适应值进行升序排序。

Step 3 根据Pareto 的精英理论中的 80 /20 法则选择每个子群的20%个体组建精英库种群。

Step 4 对于精英库种群，每个个体随机地向精英库种群中的其他两个个体学习，取适应度好的就更新当前个体。

Step 5 对于普通种群，每个个体都可以通过随机地向精英库种群中的某个个体学习，若适应度得到改善就更新当前个体。

Step 6 判断 t-tn是否大于扰动因子n。若是，则重置粒子速率；否则继续。

Step 7 重复 step 2～step 7，确定各粒子应选择的 pbest值。

Step 8 更新迭代次数，若还在迭代范围内，则转到步骤step 2；否则，停止更新。

Step 9 输出整个粒子群（包括精英库种群）的全局最优适应度，算法运行结束。

4 仿真结果及分析

本文采用的编码是实数编码转换为自然数编码的策略。将一个随机的粒子按照权重分量升序排列得到对应的新粒子序列，而新粒子序列所对应于原粒子的位置就可以组合成一个新的自然数序列。

取划分因子为5，惯性权重ω=0.4，学习因子c1=c2=2，自主学习概率Pc=0.3，扰动因子n=150，种群规模popsize=150。分别将每种算法运行10次。

图1中可以看出，对于确定型流水车间调度问题，无论在搜索最优值上还是收敛速度上，GA、PSO、CPSO的结果都没有ECLCPSO好，这说明 ECLCPSO求解Flow shop问题的有效性。

5 结论

本文研究了Flow Shop调度问题，以工件的加工时间Makespan为目标函数。针对协同粒子群优化算法（CPSO） 容易早熟和停滞的问题的缺陷，本文提出一种精英综合学习的协同粒子群算法（ECLCPSO）。该算法在 CPSO 算法的基础上，将精英策略和综合学习策略有效地结合一起，组成了新的学习机制，并引入了扰动机制，将其通过与GA、PSO、CPSO进行仿真比较分析，仿真结果表明改进的算法收敛速度快且精度高，优化性能好，验证了其解决Flow shop问题的有效性。

参考文献

[1]王凌.车间调度及其遗传算法[M].清华大学出版社，2003（05）：109-110

[2]张顺，徐震浩，顾幸生.用改進的协同免疫算法求解FlowShop调度问题[J].东南大学学报（自然科学版），2012，42（s1）：157-162.