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

张源 王加冕

摘  要： 针对置换流水车间调度问题，本文以最小化最大完工时间为优化目标建立仿真模型，并设计一种改进粒子群算法（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]。最初主要用于模拟社会行为，作为鸟群或鱼群中有机个体运动的表现形式，后经改进使得该算法同样适用于求解生产线调度问题，但是粒子群算法在流水车间调度问题的应用中仍存在收敛精度低、稳定性差等缺点。……