置换流水车间调度粒子群优化与局部搜索方法研究

Particle swarm optimization and local search method for permutation flow shop scheduling problem

采用粒子群优化算法求解置换流水车间调度问题,提出了一种基于工件次序和粒子位置的二维粒子编码方法。为提高粒子群算法的优化性能,在描述了面向置换流水车间调度问题的粒子邻域结构后,提出了三种基于粒子邻域操作的局部搜索方法,分别是基于互换操作、基于插入操作和基于逆序操作的局部搜索方法。计算结果说明,粒子群算法的优化性能好于遗传算法和NEH启发式算法。三种局部搜索算法均能有效地提高粒子群算法的优化性能,采用基于互换操作局部搜索的粒子群算法的优化性能要好于其它两种局部搜索算法。

Particle swarm optimization is employed to optimize the permutation flow shop scheduling problem and a two -dimension particle encoding approach based on the job sequence and the particle position is introduced. To improve the performance of particle swarm optimization,after the neighborhood structure of the particle for the permutation flow shop scheduling problem is described,three kinds of local search method based on different particle neighborhood operation are presented.Three kinds of local search method are respectively the local search based on crossing -over operation,the local search based on inserting operation and the local search based on reserving operation.Experimental results show that particle swarm optimization algorithm has better performance than GA and NEH.Three kinds of local search method all can improve the performance of particle swarm optimization algorithm,and the local search based on crossing-over operation has better optimization performance than the other of three local search method.