This paper proposesed a hybrid particle swarm optimization algorithm for the minimization of makespan in permutation flow shop scheduling problems which combined particle swarm optimization algorithm with variable neighborhood search algorithm.The initial population was generated by the NEH constructive heuristic to enhance the quality of the initial solutions. A heuristic rule called the ranked order value(ROV) borrowed from the random key representation was developed, which applied the continuous particle swarm optimization algorithm to all classes of sequencing problems. A variable neighborhood search algorithm based on neighborhood structures was proposed to improve the quality of the hybrid algorithm. Finally the proposed algorithm is tested on a set of standard instances taken from the literature provided by Taillard and Watson et al, and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.

针对最大完工时间最小的置换流水车间调度问题,提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化（hybrid particle swarm optimization，HPSO）算法。在该混合算法中，采用NEH启发式算法进行种群初始化，以提高初始解质量。运用基于随机键的升序排列规则（ranked-order-value，ROV）,将连续PSO算法应用于离散置换流水车间调度问题中，提出了一种基于关键路径的变邻域搜索算法，以进一步提高算法的局部搜索能力，使算法在集中搜索和分散搜索之间达到合理的平衡。最后，运用提出的混合算法求解Taillard和Watson基准测试集，并将测试结果与一些代表算法进行比较，验证了该调度算法的有效性。

粒子群优化算法, 变邻域搜索, 置换流水车间调度, 关键路径