摘要：本文提出了解决最小完工时间的无等待流水调度问题的基于禁忌搜索的混合算法。算法结合了调度规则和禁忌搜索算法的优点，首先利用调度规则构造较好的初始解，既可以加快禁忌搜索算法的收敛速度，也可以降低整个算法的运算量，使算法有更好的工程实用性；然后使用变邻域结构的禁忌搜索算法改进当前解。在保持可达性的基础上，该算法缩小了邻域规模和减少了计算时间。数值仿真实验表明，该算法是有效的。

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

单位：大连交通大学软件学院 辽宁大连116028