求解无等待流水调度的基于禁忌搜索的混合算法  

A Hybrid Algorithm Based on the Tabu Search for No-Wait Flow Shop Scheduling

作　　者：戚海英[1] 邱占芝[1] 

机构地区：[1]大连交通大学软件学院,辽宁大连116028

出　　处：《计算机工程与科学》2009年第4期60-62,共3页Computer Engineering & Science

基　　金：辽宁省教育厅计划项目(20060107)

摘　　要：本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点,首先利用调度规则构造较好的初始解,既可以加快禁忌搜索算法的收敛速度,也可以降低整个算法的运算量,使算法有更好的工程实用性;然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上,该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明,该算法是有效的。To the problem that takes the minimum makespan of no-wait flow shop scheduling, a hybrid algorithm based on the tabu search is proposed. The algorithm combines the merits of scheduling rules and the tabu search algorithm, uses the scheduling rules to construct good initial solutions, speeds up the tabu search algorithm＇s convergence rate, and also reduces the entire algorithm＇s operations, and enables the algorithm to have better project utility. Then the tabu search algorithm of varying neighborhood is applied to improving the last solution. The algorithm reduces the size of neighborhood and running time with reachability. Numerical experiments show that the algorithm is applicable and effective.

关 键 词：车间调度 调度规则 禁忌搜索 变邻域结构 

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