改进粒子群算法求解置换流水车间调度问题

张源 王加冕

摘  要： 针对置换流水车间调度问题，本文以最小化最大完工时间为优化目标建立仿真模型，并设计一种改进粒子群算法（IPOS）进行求解。为克服标准粒子群算法寻优结果稳定性差的缺点，首先，该算法结合NEH算法生成初始种群;其次，在迭代进化中引入自适应权重系数和学习因子;最后，在粒子的个体极值搜索中引入模拟退火算法的Metropolis准则。将改进前后的粒子群算法分别进行仿真优化实验，实验结果验证了该算法的优越性和有效性。

关键词： 置换流水车间;粒子群算法;NEH算法;Metropolis准则;最小化完工时间

中图分类号： TP391.9    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.06.023

本文著录格式：张源，王加冕. 改进粒子群算法求解置换流水车间调度问题[J]. 软件，2020，41（06）108111+131

【Abstract】： Aiming to the permutation flow shop scheduling problem， a simulation model was established with the goal of minimizing the maximum completion time， and an improved particle swarm optimization （IPOS） algorithm was designed to solve the problem. In order to overcome the poor stability of the optimization results of the standard particle swarm optimization algorithm， firstly， the algorithm combines with NEH algorithm to generate the initial population. Secondly， adaptive weight coefficient and learning factor are introduced into iterative evolution. Finally， the Metropolis criterion of simulated annealing algorithm is introduced into the individual extremum search of particles. The particle swarm optimization （pso） algorithm is simulated and optimized before and after the improvement. The experimental results verify the superiority and effectiveness of the algorithm.

【Key words】： Permutation flow shop; Particle swarm optimization algorithm; NEH algorithm; Metropolis criterion; Makespan

0  引言

车间生产调度问题[1]是指在一定的时间内将生产资源与生产任务及设备进行合理的分配，其目的是对某些特定的性能指标进行优化。置换流水车间调度问题[2]（permutation flow shop scheduling problem，PFSP）是實际生产调度问题的简化形式，并且已被证明是一类经典的NP难题[3]。所以对置换流水车间调度问题的研究有利于企业提高其生产效率和核心竞争力，具有重要的应用价值和意义。

目前针对置换流水车间调度问题的求解算法主要包括遍历式算法[4]、构造型算法[5]、智能优化算  法[6]。其中智能优化算法由于其原理简单的特点，在求解置换流水车间调度问题的研究中得到了普及。粒子群算法（particle swarm optimization，POS）是由Kennedy和Eberhart在1995年共同提出的一种元启发式智能优化算法[7]。最初主要用于模拟社会行为，作为鸟群或鱼群中有机个体运动的表现形式，后经改进使得该算法同样适用于求解生产线调度问题，但是粒子群算法在流水车间调度问题的应用中仍存在收敛精度低、稳定性差等缺点。

因此，针对上述问题，本文以置换流水车间调度问题为研究对象建立仿真模型，并提出一种改进粒子群算法（improved particle swarm optimization，IPOS） 对置换流水车间调度问题进行求解，优化目标为最小化最大完工时间[8]（makespan）。最终通过仿真优化实验的结果对比分析，验证了IPOS算法的有效性。

1  问题描述

置换流水车间调度问题可以描述为[9]：由M台加工设备和I个待加工工件组成，并且待加工工件要在所有设备上进行加工。每台设备的工件加工顺序和工件在各设备上的加工顺序都相同，置换流水车间存在的约束为[9]：相邻设备间存在无限暂存缓冲区;每台设备在同一时间只能加工一个工件;各工件同一时刻只能在一台设备上加工;工件在加工过程中不能中断。已知各工件在所有设备上的加工时间。为方便描述问题，定义参数如表1所示。

2.6  改进粒子群算法步骤及流程图

本文将NEH算法、自适应权重系数及学习因子、Metropolis准则引入到标准粒子群算法的各环节中进行改进，图1为IPOS算法的总流程图，基本步骤为：

步骤1：设置算法的初始化参数、粒子群规模及初始化速度、最大迭代终止次数Gmax;

步骤2：结合NEH算法生成指定规模数量的种群作为改进粒子群算法的最终初始种群;

步骤3：分别计算粒子群中个体的适应度值;

步骤4：基于Metropolis准则对粒子的个体极值进行替换，并根据粒子的适应度值对全局最优解进行更新;

步骤5：基于改进自适应权重系数和学习因子对粒子的速度位置进行替换;

步骤6：是否满足最大迭代终止次数，若满足输出最优结果;若不满足转步骤3。

3  仿真实验

选择置换流水车间标准测试库中的Car1作为仿真测试对象[16]，即11个加工工件5台加工设备。仿真优化模型在Plant Simulation软件中建立，如图3所示。

置换流水车间模型由控制参数、程序仿真和数据统计3个模块组成，其中程序仿真模块中用Simtalk语言编写改进粒子群算法和模型调度分配的程序。数据统计模块将粒子的个体极值和粒子群的全局最优解等数据进行记录。控制参数模块为仿真运行过程中需要调用的参数，如当前粒子群进化代数、所有工件的完工时间。仿真模型在硬件为AMD A10-5750M APU 2.50 GHZ的计算机上运行。设置改进粒子群算法和标准粒子群算法满足终止条件的最大迭代次数Gmax为300，每代种群的粒子数N为50，粒子最大速度为工件数和机器数乘积的0.1倍，标准粒子群算法[17]的w、c1、c2均取1。

4  结果分析

将改进前后的粒子群算法分别运行10次，10次运算中各算法的寻优结果统计如表2所示。

如表2所示，标准粒子群算法在300次迭代搜索中求解的最优值极差较大，稳定性较差，且在10次寻优中只有3次求解出全局最优解7038;而本文提出的改进粒子群算法在10次寻优中可以9次求出全局最优解7038，且最优解的极差仅为10，从而表明了在相同的迭代次数中，改进粒子群算法具有更优的全局搜索能力和稳定性。改进前后粒子群算法的迭代曲線如图3所示。

在图3所示的迭代进化曲线图中可得，虽然两种算法在300次迭代中都可以搜索到最优解7038，但IPOS算法由于对种群的初始化、个体极值的替换以及权重系数和学习因子进行了改进，提高了算法初始种群的质量，更接近全局最优解，且收敛速度也更快，在迭代进行到49代就收敛到最小值，避免出现如POS算法在202代才收敛到最小值的情况。

5  结论

针对置换流水车间调度问题，本文提出一种改进粒子群算法进行求解。该算法将自适应权重系数和学习因子引入粒子速度位置的迭代更新中;将Metropolis准则引入粒子个体的极值替换中;将NEH启发式算法引入种群的初始化中。并以最小化最大完工时间为目标对置换流水车间调度问题进行仿真实验，通过实验结果的对比分析，验证了改进粒子群算法的有效性和优越性。

参考文献

[1] Julia L， Frank W. A Permutation-Based Heuristic Method for the Blocking Job Shop Scheduling Problem[J]. PapersOnLine， 2019， 52（13）： 1403-1408.

[2] 黄佳琳， 张丫丫， 顾幸生. 基于改进生物地理学优化算法的分布式装配置换流水车间调度问题[J/OL]. 华东理工大学学报（自然科学版）： 1-12[2020-01-15].

[3] Frank B， Roland B， Karl F. Doerner， Richard F. Hartl. A machine learning approach for flow shop scheduling prob-lems with alternative resources， sequence-dependent setup times， and blocking[J]. OR Spectrum， 2019， 41（4）： 871-893.

[4] 张春燕. 基于改进遗传进化算法的复杂作业流程调度[J]. 软件， 2017， 38（12）： 98-103.

[5] 杨蕾， 梁永全. 协同进化策略的粒子群优化算法[J]. 软件， 2019， 40（08）： 152-155.

[6] Beezao A C， Cordeau J F， Laporte G， et al. Scheduling identical parallel machines with tooling constraints. Euro-pean Journal of Operational Research， 2017， 257（3）： 834- 844.

[7] Mohd S S， Azuwir M N， Mohamad E B， et al. Optimization of surface roughness in FDM 3D printer using response surface methodology， particle swarm optimization， and symbiotic organism search algorithms[J]. The International Journal of Advanced Manufacturing Technology， 2019， 105（1）： 5121-5137.

[8] 钟祾充， 钱斌， 胡蓉， 王凌. 混合布谷鸟算法求解绿色流水车间调度问题[J]. 中国机械工程， 2018， 29（22）： 2674- 2681.

[9] 刘长平， 叶春明. 置换流水车间调度问题的萤火虫算法求解[J]. 工业工程与管理， 2012， 17（03）： 56-59+65.

[10] 王柏琳， 王海凤， 李铁克. 工件可拒绝的有限等待置换流水车间调度算法[J]. 控制与决策， 2019， 34（03）： 459-469.

[11] Eltamaly A M， Al-Saud Mamdooh S， Abokhalil Ahmed G， Farh Hassan MH. Photovoltaic maximum power point tracking under dynamic partial shading changes by novel adaptive particle swarm optimization strategy[J]. Transa-ctions of the Institute of Measurement and Control， 2020，42（1）： 104-115.

[12] 施文章， 韩伟， 戴睿闻. 模拟退火下布谷鸟算法求解车间作业调度问题[J]. 计算机工程与应用， 2017， 53（17）： 249-253+259.

[13] SHI Y， EBERHART R. A modified particle swarm opti?mi-zer[J]. Advances in Natural Computation， 1998， 12： 429-439.

[14] 赵远东， 方正华. 带有权重函数学习因子的粒子群算法[J]. 计算机应用， 2013， 33（08）： 2265-2268.

[15] 尚正阳， 顾寄南， 王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J/OL]. 计算机集成制造系统： 1-16[2020-01-16].

[16] Carlier J. Ordonnancements à contraintes disjonctives[J]. RAIRO-Operations Research， 1978， 12（4）： 333-350.