改进的混合粒子群算法求解作业车间调度问题

卫尧

摘要：为解决作业车间调度问题，在标准粒子群算法中加入随机惯性权重策略，使其具有灵活调节全局搜索和局部搜索的能力，同时在进化过程中引入遗传算法中的交叉、变异操作来增强种群的多样性，另外在粒子群算法进化停滞时加入模拟退火算法，利用模拟退火算法可以及时跳出局部最优的能力，保证得到全局最优解。最后通过使用作业车间调度问题的经典算例进行实验仿真测试，实验结果证明了新算法可以有效地解决作业车间调度问题。

关键词：粒子群算法；随机惯性权重；模拟退火算法；作业车间调度

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2018）12-0200-03

1引言

作业车间调度问题（Job-shop Scheduling Problem，JSP）是实际生产车间调度过程中的一种简化问题，属于最困难的组合优化问题之一，生产调度[1]对于制造业企业来说是非常重要的一步，可以说调度方法的好坏以及结果的优劣直接影响着企业的生存和发展，所以对于寻找车间调度问题的最优解，国内外学者们一直在不断地探索。目前解决JSP问题比较常用的方法有遗传算法[2]、禁忌搜索算法[3]、粒子群算法等智能优化算法。这些智能优化算法[4]不仅可以弥补传统算法的不足，同时也为解决JSP问题提供了新的思路。黄霞等[5]针对JSP提出了使用入侵式杂草优化算法来进行求解并取得了不错的效果。周鑫等[6]提出一种结合遗传算法和模拟退火算法优点的混合算法用来解决JSP问题。张梅等[7]将改进的教学算法用于解决JSP问题。张文鹏等[8]结合变领域搜索策略改进蝙蝠算法，并通过JSP问题的经典算例进行试验仿真证明了算法的有效性。

粒子群算法（Particle Swarm Optimization，PSO）是一种通过模拟鸟类聚集飞行，在运动中不断改变自身的位置和速度，最终达到最优状态的进化搜索计算方法。粒子群算法[9]通用性强、容易实现还有收敛速度快的优点使其成为近年来求解车间调度问题的热点，仲于江等[10]将小生境技术应用于粒子群算法中用来解决FJSP问题；Shi等[11]对粒子群算法速度更新公式进行了改进，加入了惯性权重因子，使其随着进化代数线性递减，从而提高了算法的性能；谭跃等[12]提出将遗传算法中交叉操作和多混沌策略加入PSO中来提高PSO算法的搜索能力。潘全科等[13]将变邻域搜索与PSO算法混合成一种调度算法，顾文斌等[14]将生物体的自我调节机制引入到PSO算法中也取得很好的效果，张飞等[15]将混沌机制加入粒子群算法中来解决JSP问题。

本文通过分析PSO算法的优化过程，根据它存在的一些缺陷和不足，提出了一种改进的混合粒子群算法（Improved Hybrid Particle Swarm Optimization，IHPSO）。在粒子群算法基础上加入随机惯性权重策略，同时PSO算法进化前期引入遗传算法（Genetic Algorithm，GA）中交叉和变异操作来增强种群多样性，并在进化后期为避免种群陷入局部最优解，加入了拥有强大局部搜索能力的模拟退火算法，来保证种群可以取得最终的全局最优解。

2 作业车间调度问题的描述

2.1问题描述

作业车间调度问题描述如下：有n个工件在m 台机器上进行加工，每个工件包含 m 道工序，其中工件的各道工序所需要的机器和加工时间都是已知的，另外加工过程中还要满足以下几个约束条件：

（1）不同工件的工序没有加工顺序要求，但是同一工件的工序必须按照预先规定好的加工顺序进行加工；

（2）一道工序开始在机器上进行加工，中途就不能被打断，直到此道工序加工完成；

（3）一个工件在同一台机器上只进行一次加工；

（4）同一时间一台机器上只能加工一个工件；

（5）所有待加工工件没有优先级之分，都有可能在初始时间开始加工。

本文性能指标即适应度函数定为总工期最短，也就是最小化最大完工时间。

2.2建立数学模型

解决作业车间调度问题的实质就是在满足上述约束条件的情况下，得到一个可行的加工工序并且使所要求的目标函数达到最优。实现最大完工时间最小化是这一类车间调度问题中比较常见的目标函数。这有助于提高生产车间的工作效率，降低企业的生产成本，因此将这一指标作为目标函数进行改进具有一定的现实意义。

本文选取的作业车间调度问题的目标函数是最小化最大完工时间，即

3 算法描述

3.1编码与解码

在JSP中如果有n个工件，每个工件有m道工序时，则JSP的一个可行解就可以表示成一个长度为n×m的整数串。本文采用一种将粒子的实数位置通过计算转化成一个工序加工序列的编码方式，这种编码方式可以将主要用于求解连续型问题的PSO算法应用到离散型的JSP问题中，而且实际操作简单、便于理解、容易实现。下面以3个工件和3台机器的JSP问题为例来对粒子的编码和解码过程进行说明。

首先在取值范围内随机生成一組3×3的数组，例如数组A=[0.1，0.3，0.6，1.5，0.2，1，0.8，0.5，2.1]，然后对数组A中的数字按照大小进行排列，同时将排列结果按照原数组各个数字的顺序写入一个新的数组B中，得到结果为B=[1，3，5，8，2，7，6，4，9]，将B数组中的每一个数字都除以工序数m，并向上取整后可到一组新的数组C=[1，1，2，3，1，3，2，2，3]。很显然得到这个数组C就是JSP问题的一个可行解，其中第一个1表示工件1的第一个工序，第二个1表示工件1的第二个工序，依次类推，最后一个位置的3表示工件3的第三个工序，这样每一个随机产生的数组就能转化成工件的一个加工顺序，用于进行问题的求解。

3.2粒子群算法

在PSO算法中，为了使粒子的全局搜索能力和局部搜索能力保持一定的均衡，加入一种随机惯性权重策略，粒子速度和位置的更新公式如下：

3.3模拟退火算法

模拟退火算法（Simulated annealing，SA）可以利用概率突跳特性让所求问题的可行解在解空间中随机寻找目标函数的全局最优解。

模拟退火算法的步骤如下：

（1）初始化各项控制参数。

（2）根据初始解，找到新解，计算两个解对应适应值的变化量[df=fx1-fx2]，若[df<0]，则接受[x2]为新的当前解，令[x1=x2]，否则计算新解[x2]的接受概率[exp-df/T]，其中T为当前温度，若[exp-df/T>rand]（rand（）表示产生一个0到1之间的随机数），也接受[x2]作为新的当前解，令[x1=x2]，否则保留当前解[x1]。

（3）利用降温速率a对当前温度T进行降温迭代，降温公式为[Ti=a×Ti-1]。

（4）判断当前进化温度是否小于设置结束温度，若是，则结束算法搜索过程，输出最优解，否则重复步骤（2）和（3）。

3.4改进的混合粒子群算法（IHPSO）

IHPSO算法的具体步骤如下：

步骤1.设置混合算法中的各项参数，如粒子种群规模M、最大进化代数Tmax、当前进化代数t以及模拟退火算法中的相关参数。

步骤2.初始化粒子种群，使用本文提出的编码方式进行编码和解码操作，然后计算各个粒子的适应度值。

步骤3.找出粒子的pbest以及整个粒子种群的gbest。

步骤4.利用公式（4）、（5）更新粒子的速度和位置，同时在粒子种群中按照一定概率随机选出两个粒子进行两点交叉和两点互换变异操作。

步骤5.在进化过程中判断种群是否陷入局部最优，若种群进化陷入停滞阶段，判断种群的进化停滞代数是否大于初始设定值N，若是转步骤6，否则转入步骤7。

步骤6.使用SA算法对当前种群进行优化搜索，如果可以得到更优结果则更新粒子的pbest和gbest。

步骤7.判断是否达到种群最大进化代数或者得到全局最优解，若是则输出粒子最优解对应的加工工序，加工结束，否则转步骤3。

4 仿真实验与分析

为了检验IHPSO算法对求解JSP问题是否有效，本文采用JSP中的经典算例FT06、FT10作为仿真实例进行实验测试。同时用IHPSO算法、PSO算法以及GA这三种算法对实验算例进行求解，并将结果进行对比分析。

在对算例进行仿真实验测试的过程中，针对不同的算例设置不同的参数，例如在测试FT06算例时，种群规模设置为100，最大进化代数设置为200，学习因子c1和c2都设为2，因为该实验算例规模较小，计算复杂度低，所以停滞代数N设置为3，但是如果在计算FT10算例时，由于该实验算例规模较大，计算复杂度较高，所以停滞代数N相应增大设置为5，各个算法分别进行10次独立仿真运算，最后统计各算法的实验结果。

使用IHPSO算法求解FT06算例取得最优解55的甘特图如图1所示。

改进的混合粒子群算法、标准粒子群算法以及遗传算法求解FT06算例、FT10算例的收敛速度对比图如下图2、3所示。

观察图2和图3可以发现IHPSO算法很快地求出FT06算例的最优解55以及FT10算例的最优解930，而其他两个算法，只有GA算法找到了FT06问题的最优解55，剩下的则没有找到最优解。而且通过对比图2和图3中的收敛速度，可以很明显地看出IHPSO算法的收敛速度远远快于PSO算法和GA的收敛速度，并且IHPSO算法可以很快就得到最优解，而其他两个算法有时会得不到最优解，这是因为PSO在进化初期易陷入局部最优值导致取不到最优解，而IHPSO算法因为在PSO算法后期引入了SA，所以在粒子种群进化后期陷入局部最优时可以很快地跳出，并顺利找到全局最优解。另外比较两张收敛速度对比图还可以发现，相对于GA和PSO算法，IHPSO算法可以更快找到最优解的这个优势在求解大规模的JSP问题时会更加明显。

5 结论

本文在求解JSP问题时针对PSO算法存在的后期收敛速度慢、容易陷入局部最优解的问题，首先在PSO算法中加入随机惯性权重，同时引入GA中的交叉和变异操作，最后在种群进化后期结合SA算法，来提高混合算法的全局寻优能力，最后通过对JSP问题的经典算例进行仿真实验，并将仿真实验结果和GA、PSO算法的仿真实验结果进行对比分析，证明了改进的混合粒子群算法的有效性和可行性。

参考文献：

[1] Rodammer F A and White KP.A recent survey of production scheduling[J]. IEEE Trans. SMC， 1988， 18（6）： 841-851

[2] CORCE F D，TADEI R，VOLTA G.A genetic algorithm for the Job Shop problem[J].Computers and Operations Research，1995，22（1）：15-24.

[3] NOWICKI E，SMUTNICKI C.A fast taboo search algorithm for the Job Shop scheduling[J].Management Science，1996，42（6）：797-813.

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

[5] 黄霞，叶春明，包晓晓.作业车间调度問题的杂草优化算法求解[J].计算机应用与软件，2016（06）：231-234.

[6] 周鑫，马跃，胡毅.求解车间作业调度问题的混合遗传模拟退火算法[J].小型微型计算机系统，2015（02）：370-374.

[7] 张梅，吴凯华，胡跃明.基于改进教学算法的车间作业调度问题[J].控制与决策，2017（02）：349-09.

[8] 张文鹏，王兴.改进型蝙蝠算法在作业车间调度问题中的应用[J].计算机工程与应用，2017（53）：137-140.

[9] Ratnaweera A， HalgamugeS K， Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration [J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 240-255.

[10] 仲于江，杨海成，莫蓉，等.基于小生境粒子群算法的柔性作业车间调度优化方法[J].计算机集成制造系统，2015（12）：3231-3238.

[11] Shi Y， Eberhart R C. A modified particle swarm optimizer[A]. Proc. of the IEEE International Conference on Evolutionary Computation. [C]. Anchorage， AK， 1998： 69-73.

[12] 谭跃，谭冠政，邓曙光.基于遗传交叉和多混沌策略改进的粒子群优化算法[J].计算机应用研究，2016（12）：3643-3647.

[13] 潘全科，王文宏，朱剑英，等.基于粒子群优化和变邻域搜索的混合调度算法[J].计算机集成制造系统.2007（02）：323-326.

[14] 顾文斌，张薇薇，苑明海.基于改进型粒子群的作业车间调度问题研究[J].机械设计与制造工程.2017（01）：11-15.

[15] 张飞，耿红琴.基于混沌粒子群算法的车间作业调度优化[J].山东大学学报（工学版），2013（03）：19-22+37