基于位置与连接概率的EDA算法求解PFSP问题

SOLVING PFSP WITH POSITION AND CONNECTION PROBABILITY-BASED EDA

针对置换流水车间调度问题(PFSP)的特点,提出一种基于工件加工位置与连接概率相结合的混合分布估计算法。该算法将工件位置概率与工件的连接概率结合在一起,作为新一代种群的生成概率从而使得进化趋势更加合理化。为了提高局部搜索能力,算法引入了启发式方法提高初始解质量,优化了邻域搜索策略。同时引入了变异操作及限定操作来提高算法全局搜索能力。实验结果表明,该算法在求解置换流水车间调度问题时具有良好的性能。

Aiming at the characteristics of the permutation flow shop scheduling problem（ PFSP）,this paper proposed a hybrid estimation of distribution algorithm（ EDA） which is based on the combination of workpiece machining position and connection probability. The algorithm combines the probabilities of workpiece location and workpiece connection together to be the generation probability of new-generation population so as to make the evolution trend more reasonable. To improve local search ability,the algorithm introduces heuristic methods to improve the quality of initial solution,and optimises neighbourhood search strategy. At the same time,the mutation and limitation operations are introduced as well to enhance the global search ability. Experimental results demonstrated that the algorithm had good performance in solving PFSP.