柔性作业车间调度的动态禁忌粒子群优化算法

Dynamic Tabu Particle Swarm Optimization Algorithm for Flexible Job-Shop Scheduling

针对复杂的多目标柔性作业车间调度问题(FJSP),提出一种基于全知型粒子群优化(FIPS)和动态禁忌搜索(TS)的混合Pareto算法,它在利用FIPS的全局搜索能力确定搜索方向后,通过TS进行有效的局部搜索以提高算法的搜索性能.该算法采用基于强度的适应度函数来评价粒子,以使非劣解均匀分布于Pareto前沿;采用基于公共关键块的多种邻域结构,既保持了种群的多样性,避免算法陷入局部最优,又有效提高了算法的收敛速度.算法中还引入了基于变异的自适应扰动策略来进一步增加解的多样性.对不同规模实例的比较实验表明,文中所提出的算法具有较好的搜索性能,是一种求解大、小规模多目标FJSP的有效算法.

Based on the fully-informed particle swarm optimization（FIPS） and the dynamic tabu search（TS）,a hybrid Pareto algorithm is proposed to solve the complex multi-objective flexible job-shop scheduling problem（FJSP）,which takes advantage of the global search capability of FIPS to determine the search direction and then performs a local search with TS to effectively improve the search performance.In this algorithm,first,a strength-based fitness function is adopted to evaluate the quality of particles,which makes the non-dominated solutions uniformly distribute along the Pareto front.Then,several neighbourhoods based on public key blocks are employed to keep the diversity of the swarm,which avoids the trapping in the local optimum and effectively accelerates the convergence of the algorithm.Moreover,a self-adaptive perturbation based on mutation is introduced in the algorithm to enhance the diversity of solutions.The results of comparative experiments in different scales indicate that the proposed algorithm is of good search performance and is effective in solving the multi-objective FJSPs in both large and small scales.