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

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

引言

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