一种求解混合零空闲置换流水车间调度禁忌分布估计算法

摘要

According to the characteristics of the mixed no-idle permutation flowshop scheduling problem, an estimation of distribution algorithm based on probability model is used to solve this problem.What's more, the heuristic algorithm is designed into the estimation of distribution algorithm in order to improve the quality of the initial solution.In order to avoid the algorithm into local optimum, the tabu algorithm is designed into the estimation of distribution algorithm.The tabu estimation of distribution algorithm is proposed to solve the mixed no-idle permutation flowshop scheduling problem with three added kinds of local searches in order to improve the diversity of population.Experimental result shows that the algorithm has advantages to solve this problem.%结合混合零空闲置换流水车间调度问题MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性,运用基于概率模型的分布估计算法解决该问题.算法将启发式算法融入分布估计算法中提高了初始解的质量.为了避免算法陷入局部最优,将禁忌算法融入分布估计算法中,提出一种禁忌分布估计算法求解混合零空闲置换流水车间问题.为了提高种群的多样性,加入了三种邻域搜索.实例测试结果显示,该算法求解混合零空闲置换流水车间问题具有很好的优势.