作业排序与作业计划是服务业、运输、科研以及各种企业生产中普遍遇到的问题。工厂里几台机器出了故障,在现有的维修能力下,如何安排这几台机器的修理顺序,使总体损失最小,这就是一个作业排序与作业计划问题。车间调度是一类作业排序问题,对于在现有资源条件下提高工作效率和经济效益有重要作用。车间调度问题按工件加工路线的特征不同可以分为单件车间(Job-shop)的排序和流水车间(Flow shop)的排序。在加工过程中工件不允许等待的流水车间调度问题即为约束流水车间调度问题,也称为无等待流水车间调度问题(no-wait flow shop)。这种约束对于当今动态的加工生产环境和产品的质量来说具有很大的实际性和重要意义,如在金属加工业、食品加工工厂里都存在这样的约束。由于无等待流水车间调度问题具有实际性和广泛的应用性,所以引起了广大研究者的注意并且提出了许多算法来解决这类问题。车间调度是一类典型的NP-hard问题,已被证明在多项式时间内得不到最优值。近年来对于车间调度问题的求解方法主要有启发式算法和元启发式算法,但各有其不足之处:元启发式算法的运行时间长,可获得较好的解,但其解不稳定;启发式方法可以在较短的时间内得到鲁棒性较强的解,但是极少获得较优的解。为了更好解决问题,研究者将一些解决某类问题较好的算法组合起来已成为目前研究的热点。针对单一地使用各种启发式方法或元启发式方法不能有效地获得较好的解,本文提出了一种将启发式方法与禁忌搜索TS(Tabu Search)方法相结合的混合禁忌搜索算法HTS(Hybrid Tabu Search)来求解无等待流水车间调度问题。也就是通过改进类型的启发式方法产生一个较好的初始解,然后通过禁忌搜索方法对初始解的质量进行提高。大量的实验证明这种混合禁忌搜索算法比已往的启发式方法具有更高的求解效率。