中文摘要：

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.

英文摘要：

The well known NP-hard permutation flow shops problem with total flowtime minimization is considered in this paper.An algorithm framework is presented in which an initial solution is generated by an efficient hybrid heuristic algorithm and improved by a tabu search algorithm.Based on characteristics of different heuristics,three hybrid tabu search algorithms HA1,HA2,and HA3 are proposed.Taillard＇s benchmark program is used to generate a large number of random instances.Experiment results show that the quality of solutions is improved using three algorithms with a bigger searching scope.The performance of three proposed methods are all superior to the most efficient heuristics currently used.Comparing with the result from the best existing heuristics,the average relative percentage deviation from the best-known solution is reduced about 30% and the percent of optimal solutions increases obviously.