改进粒子群算法在柔性作业车间调度中的应用

杨文理 李长云

（1、湖南工业大学 计算机学院，湖南 株洲412007 2、智能信息感知及处理技术湖南省重点实验室，湖南 株洲412007）

近年来，在“中国制造2025”政策的支持下，制造业正迅速朝着信息化的方向发展，车间排产的复杂性、不确定性、多目标性、多约束性导致车间管理仍存在诸多问题，引发很多专家学者对其进行研究。

为了解决柔性车间调度中存在的诸多问题，国内外专家学者提出了一系列改进优化算法。如彭建刚[1]对多目标柔性作业车间调度算法进行了总结，主要采取加权聚合法和Pareto 优化方法对该问题进行求解，但是存在很难得到最有权重值、种群收敛性能等问题。孙丽珍[2]等人提出一种改进的遗传算法，提出了MCGI 的解码方案，但是没有考虑复合动态调度问题。李传鹏[3]等人讨论了柔性作业车间调度现存问题及未来的发展趋势，提出目前工作对工件生产批量不同的问题研究较少等问题。王艳[4]等人提出一种改进的多目标差分进化算法进行求解，在寻优能力和综合决策方面表现较优。其中文献[5]提出了一种对粒子位置状态更新的改进粒子群优化算法获得最优工序排序，但是结果受计算经验限制，性能有待进一步提高。

综上所述，借鉴研究学者们的经验，设计了一种混合轮盘赌选择算子的粒子群算法。通过算例分析，验证了使用该方法改进的粒子群算法的有效性。

1 柔性作业车间调度模型

1.1 问题描述

在实际生产过程中，柔性作业车间调度问题可以描述为：有n 个工单在m 台机器上进行生产排程，每个工单对应唯一的生产工艺路线，每条工艺路线包含不完全相同的工序，各工艺路线对应的工序之间具有严格的先后顺序，每个工序可以选择多台机器进行生产，但是每道工序只能在对应的机器上加工一次，相同工序在不同机器上加工时间不同。

一般的车间调度需要满足以下约束条件：（1）所有工单在生产开始前优先级相同，即不考虑其他因素的情况下，所有工单都有机会在开始时刻进行加工。（2）特定机器上生产某个工单对应工序的生产时间是不变的。（3）若当前生产工序没用完成时，当前机器不能暂停进行其他任务生产。

1.2 模型构建

本文以最大完工时间最小化为优化目标，结合上述约束条件和数学符号，将柔性作业车间调度数学模型描述如下：

目标函数:

式（1）表示求所有订单的生产时间之和的最小值，即本文的优化目标；式（2）表示一个工单有且仅有一条加工工艺路线与其匹配；式（3）表示所有订单的初始优先级都相同；式（4）表示上一个订单的开始加工时间小于下一个订单的开始时间，即同一时刻，同一机器在完成当前生产任务前，不能加工其他生产任务。

2 改进的粒子群算法求解FJSP

2.1 粒子群算法

粒子群算法[6]是美国心理学家Kennedy 和电气工程师Eberhart 在1995 年提出来的，该算法可以由两个向量表示，它们分别是位置向量和速度向量。粒子所处的位置表示当前问题的可行解，速度则表示粒子在空间中的搜索方向。粒子在求解空间中不断飞行，更新粒子优化位置，最终寻到全局最优解。可以用下面两个公式表示：

其中，i 表示第i 个粒子；j 表示粒子的第j 维；vij(t)表示粒子i在t 时刻的第j 维飞行速度向量；xij(t)表示粒子i 在t 时刻的第j维的位置分量；pbestij(t)表示粒子种群在t 时刻最佳位置gbestij(t)表示粒子i 在t 时刻第j 维度的分量；c1,c2为学习因子，通常在[0,1]之间随机取值。

2.2 基于轮盘赌的粒子群算法

为了解决算法早熟收敛问题，我们引入轮盘赌选择算子对粒子群算法进行改进，具体步骤如下：

步骤5：重复步骤4，得到足够多的新个体，构建一个新种群。

3 实验结果与分析

本文选择10*6 的算例对两种算法进行实验，截取其中一个工单的数据如表1 所示。

表1 工单的工序和生产时间表

表1 反映了一个工单对应的工艺路线中包含5 道工序，这5 道工序可以在6 台机器上进行加工，每道相同工序在不同机器上的加工时间不完全相同。在该问题中，每个订单对应的工艺路线包含了5 个工序，这些工序可以在全部或部分机器上进行加工，在不同机器上的加工时间不完全相同。

文章设置改进粒子群算法的种群规模为50，最大迭代次数为500，进行实验，根据实验结果可知，改进粒子群算法计算的最小完工时间为28，传统方法为33，由此可知，改进的粒子群算法在全局寻优和种群适应度最小值变化上表现更好。实验结果如图1、图2 所示。

4 结论

文章提出一种改进粒子群算法求解柔性作业车间调度问题，该方法引入了轮盘赌策略对粒子初始化进行改进。实验表明，改进算法的收敛速度更快、全局寻优能力更强，验证了本文改进粒子群算法对求解柔性作业车间调度问题的有效性。

图1 改进算法的全局最优解的变化情况和种群适应度最小值的变化情况

图2 传统算法的全局最优解的变化情况和种群适应度最小值的变化情况