推荐阅读：一类单机排序问题的改进禁忌搜索算法 引言 禁忌搜索（Tabular Search或Taboo Search，简称TS）算法是继遗传算法之后出现的又一种元启发式（Meta-Heuristic）优化算法，最早于1977年由Glover提出。禁忌搜索算法已成功用于解决组合优化问题。本文应用禁忌搜索
一类单机排序问题的改进禁忌搜索算法
引言
禁忌搜索（Tabular Search或Taboo Search，简称TS）算法是继遗传算法之后出现的又一种元启发式（Meta-Heuristic）优化算法，最早于1977年由Glover提出。禁忌搜索算法已成功用于解决组合优化问题。本文应用禁忌搜索算法求解一类单机排序问题：SMTTP（the Single Machine Total Tardiness Problem）。SMTTP 是NP-hard组合优化问题，解决这类问题的方法已经有各种最优化算法和启发式算法。
本文主要研究目的：通过一种 简单启发式方法产生初始解，并改进禁忌搜索算法的邻域移动与选择策略，提出一种解决SMTTP的改进禁忌搜索算法，计算实例说明此改进禁忌算法是有效的。
本文后面内容安排如下：第二部分介绍SMTTP，并对相关的研究成果进行简单回顾；第三部分介绍禁忌搜索算法；第四、五部分结合算例介绍求解SMTTP的改进禁忌搜索算法；第六部分进行总结。
单机总延迟问题（SMTTP）
1、问题描述
2、研究回顾
单机总延迟问题是NP-hard问题，因此当问题规模很大时很难找到最优解。分支定界算法和动态规划算法是寻找此类问题最优解的常用方法，而寻找加权延迟问题最优解的方法通常是枚举算法。Emmons提出的几条定理和优先原则可以简化分支定界算法的搜索过程。基于Emmons的优先原则，Fisher提出了对偶变拉格朗日问题。Schrage和Baker，Laons和Laons的优先原理。Pane）、改进交货时间序列（MDD，the Modified Due Date）、改进预期交货时间序列（L-MDD，Look-ahead MDD）等。本文采用以下步骤生成初始解：
第二步：计算所有未调度零件的总加工时间
SUMT=？鄱INDEX（i）=0ti；
第三步：计算所有未调度零件的总加工时间与交货时间的盈余Si=SUMT-di；
第四步：计算所有未调度零件单位加工时间内的盈余量
；
第五步：找到所有未调度零件单位时间内的最大盈余量，设对应的零件编号为K；
第六步：令L=L+1；
第七步：在序列位置处安排加工零件K，即设FS（L）=K，置INDEX（K）=1；
第八步：如果所有的零件已经调度完，算法结束，否则转第二步。
2、邻域移动
3、禁忌策略
禁忌对象选择为邻域移动，禁忌表的长度设为n-1。
算例
设有7件零件在一台机器上加工，它们的加工时间、交货时间以及编号如下表1所示，试安排零件加工顺序，使得零件总延迟时间最短。
总结
禁忌搜索算法在解决旅行商、车辆路径、图着色、二次分配以及流水/作业车间调度等各种组合优化问题时表现出很好的性能。针对一类特殊的单机排序问题：单机总延迟问题（SMTTP），本文提出一种改进禁忌搜索算法。算例表明改进的禁忌搜索算法能快速找到问题的优质解。
