一类单机排序问题的改进禁忌搜索算法
一类单机排序问题的改进禁忌搜索算
引言
禁忌搜索（Tabular Search 或 Taboo Search，简称 TS）算法是继遗传算法之后出现
的又一种元启发式（Meta-Heuristic）优化算法，最早于 1977 年由 Glover 提出。禁忌搜
索算法已成功用于解决组合优化问题。本文应用禁忌搜索算法求解一类单机排序问题：
SMTTP（the Single Machine Total Tardiness Problem）。SMTTP 是 NP-hard 组合优化问
题，解决这类问题的方法已经有各种最优化算法和启发式算法。
本文主要研究目的：通过一种本文由论文联盟 收集整理简单
启发式方法产生初始解，并改进禁忌搜索算法的邻域移动与选择策略，提出一种解决
SMTTP 的改进禁忌搜索算法，计算实例说明此改进禁忌算法是有效的。
本文后面内容安排如下：第二部分介绍 SMTTP，并对相关的研究成果进行简单回顾；
第三部分介绍禁忌搜索算法；第四、五部分结合算例介绍求解 SMTTP 的改进禁忌搜索算
法；第六部分进行总结。
单机总延迟问题（SMTTP）
1、问题描述
单机总延迟问题（SMTTP）考虑在一台机器上加工 n 个工作或零件，其中同一时刻只
能加工一个零件且零件的加工顺序不预先设定。每一个零件 j（j=1，2，…，n）的加工时
间为 Pj，且可在 0 时刻到达加工。另外，设 dj，Cj 和 Tj=max{0，Cj-dj}分别为零件 j 的交
货时间、完工时间和延迟时间。SMTTP 的目标函数是在所有可能的零件排序中找到一个最
优排序，使得总延迟时间 最小。SMTTP 是更一般的具有加权延迟问题的特例，这类问题
中，每个零件都分配了一个不同的权值。
2、研究回顾
单机总延迟问题是 NP-hard 问题，因此当问题规模很大时很难找到最优解。分支定界
算法和动态规划算法是寻找此类问题最优解的常用方法，而寻找加权延迟问题最优解的方
法通常是枚举算法。Emmons 提出的几条定理和优先原则可以简化分支定界算法的搜索过
程。基于 Emmons 的优先原则，Fisher 提出了对偶变拉格朗日问题。Schrage 和 Baker，
Lawler 采用动态规划算法求解 SMTTP，而 Potts 和 Van Wassenhove 将 Schrage 和 Baker
的方法与 Lawler 的分解定理结合起来实现了一个有效的算法。Szwarc、Mukhopadhyay
和 Della Croce 等在 Emmons 和 Lawler 的基础上提出了分支定界方法。
在实际应用中，例如在柔性制造系统（FMS）中，由于计算量的原因，启发式方法与
最优化算法相比更适合。Wilkerson 和 Irwin（WI）通过相邻配对交换（an adjacent pair
interchange，API）操作来改进基本可行解。Fry 等通过选择 9 种相邻配对交换策略中最优
的一种来改进 Wilkerson 和 Irwin（WI）的启发式方法。Holsenback 和 Russell 提出了一种
不受成对交换限制的启发式方法，这种方法基于重排序的净收益（the net benefit of
relocation，NBR）以及 Emmons 的优先原理。Panwalkar 等改进了 PSK 启发式方法，这
种方法劣于 NBR，但通过正确编码，其效率要大大优于 P-S-K 启发式方法。
禁忌搜索算法
禁忌搜索算法的基本思想就是在搜索过程中将近期历史上的搜索结果存放在禁忌表（
Tabu List）中，阻止算法重复进入，这样就有效地防止了搜索过程的循环。禁忌表模仿人
类的记忆功能，禁忌搜索因此得名，所以称它为一种智能优化算法。
具体的思路如下：禁忌搜索算法采用了邻域优先的搜索方法，为了能逃离局部最优解
，算法必须能够接受劣解，也就是每一次迭代得到的解不一定优于原来的解。但是，一旦
接受了劣解，迭代就可能陷入循环。为了避免循环，算法将最近接受的一些解或移动存放
在禁忌表中，在以后的迭代中加以禁止。即只有不在禁忌表中的较好解（可能比当前解差
）才被接受作为下一次迭代的初始解。随着迭代的进行，禁忌表不断更新，经过一定迭代
次数后，最早进入禁忌表的移动就从禁忌表中解禁出来。
求解 SMTTP 的改进禁忌搜索算法
禁忌搜索算法在求解 NP-hard 的优化问题时具有很好的找到优质解的能力，因此适合
求解 SMTTP。初始解的构造、邻域移动与禁忌策略对禁忌搜索算法的性能影响很大，针对
SMTTP 的特殊性，禁忌搜索算法可以在这三个环节上设置特殊策略，从而能够快速找到问
题的优质解。
1、初始解的构造
禁忌搜索算法对初始解的依赖很大，好的初始解能够加快算法的搜索过程。在 SMTTP
中，产生好的初始解的的常用算法是启发式方法，主要有：最早交货时间序列（EDD，
the earliest Due Date）、最短处理时间序列（SPT，the shortest processing time）、改
进交货时间序列（MDD，the Modified Due Date）、改进预期交货时间序列（L-MDD，
Look-ahead MDD）等。本文采用以下步骤生成初始解：
第一步：输入加工零件数 n，零件加工时间 ti（i=1，2，...，n），零件交货时间 di（
i=1，2，...，n）；初始时，所有零件未排序，标记为 INDEX（i）=0，i=1，2，...，n，
且初始序列的最后位置 L 为 0；
第二步：计算所有未调度零件的总加工时间
SUMT=？鄱 INDEX（i）=0ti；
第三步：计算所有未调度零件的总加工时间与交货时间的盈余 Si=SUMT-di；
第四步：计算所有未调度零件单位加工时间内的盈余量
；
第五步：找到所有未调度零件单位时间内的最大盈余量，设对应的零件编号为 K；
第六步：令 L=L+1；
第七步：在序列位置处安排加工零件 K，即设 FS（L）=K，置 INDEX（K）=1；
第八步：如果所有的零件已经调度完，算法结束，否则转第二步。
2、邻域移动
设零件调度序列为 1，2，...，n 的一个排列，其中序列 S 的位置 i 处零件标号为 Si，
假设序列 S 中位置 m 处出现第一个延迟时间为正的零件，将 Sm 与序列 S 前 m-1 以及后
n-m 个位置的零件标号的交换操作定义为禁忌搜索算法的邻域移动。
3、禁忌策略
禁忌对象选择为邻域移动，禁忌表的长度设为 n-1。
算例
设有 7 件零件在一台机器上加工，它们的加工时间、交货时间以及编号如下表 1 所示
，试安排零件加工顺序，使得零件总延迟时间最短。
以上面给出的新解 S 中第一个出现延迟时间为正的零件序号 S3=3 构造邻域移动，分
别为（3，6）、（3，2）、（3，1）、（3，5）、（3，7）、（3，4）。当前解的邻域
中所有移动都不能改善总延迟时间，证明当前解 S=6，2，3，1，5，7，4 为局部最优解
，由 SMTTP 的特殊性，此解也为最优解。即解 S=6，2，3，1，5，7，4 为最优解，总
延迟时间 。
总结
禁忌搜索算法在解决旅行商、车辆路径、图着色、二次分配以及流水/作业车间调度
等各种组合优化问题时表现出很好的性能。针对一类特殊的单机排序问题：单机总延迟问
题（SMTTP），本文提出一种改进禁忌搜索算法。算例表明改进的禁忌搜索算法能快速找
到问题的优质解
