一类单机排序问题的改进禁忌搜索算法

摘 要：机器排序问题通常指在给定数量的机器上进行工件加工调度，是生产计划中的中心任务。本文考虑一种特殊的单机排序问题——单机总延迟问题（SMTTP）。针对这种NP-hard问题，提出了改进的禁忌搜索算法，算例表明了这种改进的禁忌搜索算法能快速找到优质解。

关键字：禁忌搜索算法 单机总延迟问题 单机排序问题

引言

禁忌搜索（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），本文提出一种改进禁忌搜索算法。算例表明改进的禁忌搜索算法能快速找到问题的优质解。

（作者单位：国防信息学院）