基于MAZAK 柔性制造线的粒子群与免疫算法研究❋

张 利，孟祥凯，刘文生

（武汉轻工大学 机械工程学院，湖北 武汉 430023）

1 车间调度优化问题的描述

车间调度优化问题可描述为：有n个工件在m台机器上加工，在已有的工序要求下，在工件的加工顺序及时间给定的条件下，将n个工件在机器上排序，使得生产周期与加工时间最短、最优［1］。

由于日本MAZAK柔性制造生产线在现代制造业中得到了较广泛的应用，因此本文将智能算法中的克隆免疫遗传算法和粒子群算法运用在生产调度中，以提高生产效率，且可得到比较直观的仿真结果［2］。

2 免疫遗传算法的优化过程

免疫算法所求解的问题即抗原，首先提取抗原中的特征信息——疫苗；然后对疫苗处理将其转变为求解问题方案；再将这个方案转变成免疫算子来具体操作，抗原所提取的疫苗有多个，可将其进行组合后再注射。在提取疫苗的过程中，通过接种疫苗来提高适应度，而免疫选择则是为了防止种群退化。

2.1 免疫遗传算法接种疫苗［3］

设种群c＝（m1，…，），则对c种群接种的疫苗就是按比例λ（0＜λ≤1）得到的qλ＝λq个个体的变异，qλ为总的种群数量，疫苗是特定的特征信息。

2.2 免疫遗传算法免疫选择

图1 免疫遗传算法基本流程

3 粒子群算法的优化过程

粒子群算法（Particle Swarm Optimization，PSO）是由美国的Kennedy博士和Eberhar博士于1995年提出的一种基于群智能的进化算法。在粒子群的优化算法当中，粒子在一个n维的空间上搜索时，每个粒子的位置是一个所要解答的问题的解，它持续地调整自己所处的位置来进行解的优化。本文中，第d维第i个粒子所处的位置用Xid来表示，用Pid表示粒子群中粒子搜索到的解，用Pgd表示所有的粒子所经历的最好位置［5］，用表示粒子群的速度。因此，第d维的第i个粒子在某一时刻的速度为：

其中：ω为权重；η1，η2为粒子当中两个解的参数值；rand（）为随机生成的函数值。因此，由式（1）可以得到粒子群下一代的位置为：

重新构造下一位置X′id的粒子速度V′id，其中粒子移动的算式为：

其中：α与β为随机数，α，β∈［0，1］。交换序列（Xid→Pid）以概率α保留，基本的工序操作为α（Xid→Pid）；同样地，交换序列（Xid→Pgd）以概率β保留，基本操作由β（Xid→Pgd）表示［6］。从式（2）、式（3）当中可以看出，它们是PSO算法求解的主要算子，并且在式子当中，α的值对局部最优移动的影响很大，当其增大时，粒子位置Pid也开始向最优解移动；同样，β的值对局部的影响也很大，当其越大，对粒子位置Pgd的影响就越大。图2为粒子群算法的调度过程。

4 实验仿真与结果分析

本文采用经典的10/10/G/Cmax的Job shop调度问题，通过仿真得到求解结果，并确定是否是最优的结果。

图2 粒子群算法的调度过程

4.1 免疫遗传算法仿真分析

克隆免疫遗传算法继承了遗传算法的高度并行迭代模式［7］，采用原始克隆免疫算法的基本参数数据如下：初始抗体数为60，替换抗体为350，克隆选择概率0.8，克隆细胞数80，迭代次数70。

在MATLAB 2013a下得到的免疫遗传算法的调度仿真加工曲线为图3～图5所示。

图3 免疫遗传算法最优完成时间变化曲线

图4 免疫遗传算法亲和度曲线

图5 免疫遗传算法加工时间曲线

图3为免疫遗传算法最优完成时间变化曲线，可以看到，在迭代过程中随着迭代次数增加响应时间持续下降，最后恒定。图4为免疫遗传算法亲和度曲线，亲和度的变化不是恒定的，而是上下波动的。图5为免疫遗传算法加工时间曲线，它呈现与迭代次数有关的上下波动，其中迭代次数在20～40之间是最好的。

对10个工件、10台机器进行作业调度，每个工件分别在10台机器上各加工一次，由免疫遗传算法得到的调度甘特图见图6。

图6 免疫遗传算法调度甘特图

4.2 粒子群算法仿真分析

通过对10个工件、10台机器进行作业调度，每个工件分别在10台机器上各加工一次，每个工件的加工路线与每道工序对应的加工时间T与机器Js矩阵如下：

由粒子群算法得到的调度甘特图如图7所示。对比图6与图7可以看出，两图的调度顺序完全不同，其中粒子群算法最优完成时间为1 128s，而免疫算法的调度最优完成时间为1 306s，远远地大于粒子群调度算法的最优调度时间。由此可以看出在柔性生产调度中粒子群算法优于免疫遗传算法。

图7 粒子群算法调度甘特图

5 结束语

本文以日本MAZAK柔性生产线为基础，通过对两种算法的仿真比较分析，可以得到较为优秀的调度值。从两种算法的对比中可以看到，粒子群算法要优于免疫遗传算法调度，得到解的时间也相对较短。在今后的作业调度中，智能化调度将会得到更加广泛的应用。

［1］于颖，李永生，朴孝春.粒子群算法在工程优化设计中的应用［J］.机械工程学报，2008，44（12）：226－231.

［2］宋晓宇，曹阳，孟秋宏.求解Job Shop调度问题的粒子群算法研究［J］.系统工程与电子技术，2008，30（12）：2398－2401.

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

［4］Rui Zhang，Shiji Song，Cheng Wu.A two－stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem ［J］. Knowledge－Based Systems，2012，27：393－406.

［5］李小华，熊禾根.基于粒子群算法的车间作业调度问题［J］.信息技术，2009（7）：19－21.

［6］何利，刘永贤，谢华龙.基于粒子群算法的车间调度与优化［J］.东北大学学报（自然科学版），2008，29（4）：555－568.

［7］Sha D Y，Lin Hsing－Hung.A multi objective PSO for job－shop scheduling problems［J］.Expert Systems with Applications，2009（6）：1065－1070.