等待时间受限Flowshop调度的HGA算法  

HGA Algorithm for Flowshop Scheduling with Limited Waiting Time

作　　者：尹兆涛[1] 李铁克[1] 肖拥军[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083

出　　处：《计算机工程》2009年第21期4-6,9,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(70771008;70371057)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]