摘要： 针对等待时间受限的Flowshop调度问题，提出嵌入约束满足和变邻域搜索技术的混合遗传算法。该算法基于约束满足思想，通过递归回溯和约束传播修复工件的开工时间，以解消工件在相邻阶段的等待时间受限冲突，根据回溯工件的位置信息设计相应的交叉算子和变异算子，利用变邻域搜索技术增强算法的收敛性。仿真实验表明该混合遗传算法的有效性，并分析等待时间上限对目标值的影响。

关键词: Flowshop调度, 等待时间受限, 混合遗传算法, 约束满足, 变邻域搜索

Abstract: Aiming at Flowshop scheduling problem with limited waiting time, a Hybrid Genetic Algorithm(HGA) combined with constraint satisfaction and variable neighborhood search is proposed. Based on constraint satisfaction, job starting time is repaired by recursive backtracking and constraint propagation in order to solve the violated waiting time constraints. The crossover and mutation are designed according to the job backtracking positions. The convergence is enhanced by variable neighborhood search. Simulation experiment shows that the HGA is effective and analyzes the influence of upper bound of waiting time on the objective.

Key words: Flowshop scheduling, limited waiting time, Hybrid Genetic Algorithm(HGA), constraint satisfaction, variable neighborhood search

中图分类号: 

• TP301.6