一种多目标置换流水车间调度问题的优化算法

A Hybrid Particle Swarm Optimization Algorithm for Multi-objective Permutation Flow Shop Scheduling Problem

针对最大完工时间最小和总流经时间最小的多目标置换流水车间调度问题(permutation flow shop scheduling problem,PFSP),提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particle swarm optimization algorithm,HPSO)算法,并使算法在集中搜索和分散搜索之间达到合理的平衡.在该混合算法中,采用NEH启发式算法进行种群初始化,以提高初始解质量;运用随机键表示法设计基于升序排列规则(ranked-order-value,ROV),将连续PSO算法应用于置换流水车间调度问题;引入外部档案集存贮Pareto解,并采用强支配关系和聚集距离相结合的混合策略保证解集的分布性;采用Sigma法和基于聚集距离的轮盘赌法进行全局最优解的选择;提出变邻域搜索算法,对外部集中的Pareto解作进一步地局部搜索.最后,运用提出的混合算法求解Taillard基准测试集,并将测试结果与SPEA2算法进行比较,验证该调度算法的有效性.

This paper proposes a hybrid particle swarm optimization algorithm for the minimization of makespan and total flowtime in permutation flow shop scheduling problems, which combines particle swarm optimization algorithm with variable neighborhood search algorithm. The initial population is 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 is developed, which apply the continuous particle swarm optimization algorithm to all classes of sequencing problems. The strategy of constructing external data set based on combining strong predominance ranking and crowding distance ranking was introduced. The global best solution was updated based on the strategy of combining Sigma method and roulette method. VNS was applied to enhance the local search for the pareto solutions. Finally, the proposed algorithm is tested on a set of standard instances taken from the literature provided by Taillard and compared with SPEA2. The computation results validate the effectiveness of the proposed algorithm.