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

A TABU ESTIMATION OF DISTRIBUTION ALGORITHM TO SOLVE THE MIXED NO-IDLE PERMUTATION FLOWSHOP SCHEDULING PROBLEM

作　　者：张晓霞[1] 吕云虹 

机构地区：[1]辽宁科技大学软件学院,辽宁鞍山114051

出　　处：《计算机应用与软件》2017年第1期270-274,292,共6页Computer Applications and Software

基　　金：辽宁省教育厅科学研究项目(L2015265)

摘　　要：结合混合零空闲置换流水车间调度问题MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性,运用基于概率模型的分布估计算法解决该问题。算法将启发式算法融入分布估计算法中提高了初始解的质量。为了避免算法陷入局部最优,将禁忌算法融入分布估计算法中,提出一种禁忌分布估计算法求解混合零空闲置换流水车间问题。为了提高种群的多样性,加入了三种邻域搜索。实例测试结果显示,该算法求解混合零空闲置换流水车间问题具有很好的优势。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.

关 键 词：混合零空闲置换流水车间调度问题算法 分布估计算法 启发式算法 禁忌算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]