基于双模式PSO算法求解置换流水车间调度问题

Dual mode PSO for solving permutation flow shop scheduling problem

针对粒子群算法求解置换流水车间调度这类NP-hard问题存在的早熟问题,本文提出了一种基于随机键编码的双模式飞行粒子群算法。首先,基于ROV规则对工件加工顺序进行随机键编码。其次,粒子在搜索过程中采用带有自适应惯性权重的双模飞行方式来更新位置和速度,避免粒子群陷入早熟收敛状态。为了提高解的质量,每次迭代过程中对PSO优化得到的种群最优解进行邻域局部搜索。最后,通过对标准测试集的数值仿真及与其他PSO算法的比较,证实了所提算法求解该问题的有效性与可行性。

Our objective in this report is to study the permutation flow shop scheduling problem, this paper proposes a dualmode particle swarm optimization algorithm based on random key code. Based on the ROV rules for random code for the processing sequence;Secondly, particles in the search process use dual flight mode with the adaptive inertia weight to update the position and velocity, avoid particle swarm into premature convergence; In order to improve the quality of the solution, in each iteration the neighborhood local search algorithm is used on PSO optimized solution.Finally a comparison through numerical simulation and comparison of different PSO algorithm on the standard test set, to verify the feasibility and effectiveness of the proposed algorithm to solve the problem.