零等待flow shop多目标调度的混合差分进化算法

针对具有零等待约束的flow shop问题,以总流程时间和最大完工时间为多目标,提出一种结合多目标变邻域搜索的混合差分进化算法(multi-objective differential evolution hybridized with variable neighborhood search,M DEVNS)进行求解。提出一种基于改进Naw az-Enscore-Ham(NEH)规则的多样化种群初始化方法;设计了差分进化的变异、试验、目标个体更新操作;为提高多目标搜索能力,在算法的进化中混合了一种多目标变邻域搜索方法。通过Taillard标准测试算例的计算试验,证明了MDEVNS算法获得的Pareto前沿解在多样性和性能方面要优于多目标模拟退火算法和非支配排序遗传算法,验证了MDEVNS算法求解多目标零等待流水车间调度问题的有效性。

Multi-objective scheduling in no-wait flow shop using a hybridized differential evolution algorithm

To sovle the no-wait flow shop scheduling with the makespan and total flow time criteria, a multi-objective differential evolution algorithm hybridized with variable neighborhood search(MDEVNS)was proposed. A diversified population initialization method was proposed by using the improved Nawaz-Enscore-Ham(NEH)heuristics. The updating operations of mutant, trial and target individuals were developed in differential evolution. To improve the multi-objective searching ability, a multi-objective variable neighborhood search was embedded in the algorithm. The computational experiments based on Taillard benchmark set revealed that the MDEVNS yielded Pareto front solutions with better diversity and performance than the multi-objective simulated annealing algorithm and the non-dominated sorting genetic algorithm, and the effectiveness of the MDEVNS for multi-objective scheduling in no-wait flow shop was proved.