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

《一类单机排序问题的改进禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一类单机排序问题的改进禁忌搜索算法一类单机排序问题的改进禁忌搜索算法　　引言　　禁忌搜索（TabularSearch或TabooSearch，简称TS）算法是继遗传算法之后出现的又一种元启发式（Meta-Heuristic）优化算法，最早于1977年由Glover提出。禁忌搜索算法已成功用于解决组合优化问题。本文应用禁忌搜索算法求解一类单机排序问题：SMTTP（theSingleMachineTotalTardinessProblem）。SMTTP是NP-hard组合优化问题，解决这类问题的方法已

2、经有各种最优化算法和启发式算法。　　本文主要研究目的：通过一种本文由.LTTP的改进禁忌搜索算法，计算实例说明此改进禁忌算法是有效的。　　本文后面内容安排如下：第二部分介绍SMTTP，并对相关的研究成果进行简单回顾；第三部分介绍禁忌搜索算法；第四、五部分结合算例介绍求解SMTTP的改进禁忌搜索算法；第六部分进行总结。　　单机总延迟问题（SMTTP）　　1、问题描述　　单机总延迟问题（SMTTP）考虑在一台机器上加工n个工作或零件，其中同一时刻只能加工一个零件且零件的加工顺序不预先设定。每一个零件j

3、（j=1，2，，n）的加工时间为Pj，且可在0时刻到达加工。另外，设dj，Cj和Tj=max{0，Cj-dj}分别为零件j的交货时间、完工时间和延迟时间。SMTTP的目标函数是在所有可能的零件排序中找到一个最优排序，使得总延迟时间最小。SMTTP是更一般的具有加权延迟问题的特例，这类问题中，每个零件都分配了一个不同的权值。　　2、研究回顾　　单机总延迟问题是NP-hard问题，因此当问题规模很大时很难找到最优解。分支定界算法和动态规划算法是寻找此类问题最优解的常用方法，而寻找加权延迟问题最优解的方

4、法通常是枚举算法。Emmons提出的几条定理和优先原则可以简化分支定界算法的搜索过程。基于Emmons的优先原则，Fisher提出了对偶变拉格朗日问题。Schrage和Baker，Lamons和Lamons的优先原理。Pane）、改进交货时间序列（MDD，theModifiedDueDate）、改进预期交货时间序列（L-MDD，Look-aheadMDD）等。本文采用以下步骤生成初始解：　　第一步：输入加工零件数n，零件加工时间ti（i=1，2，...，n），零件交货时间di（i=1，2，...，

5、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，置IN

6、DEX（K）=1；　　第八步：如果所有的零件已经调度完，算法结束，否则转第二步。　　2、邻域移动　　设零件调度序列为1，2，...，n的一个排列，其中序列S的位置i处零件标号为Si，假设序列S中位置m处出现第一个延迟时间为正的零件，将Sm与序列S前m-1以及后n-m个位置的零件标号的交换操作定义为禁忌搜索算法的邻域移动。　　3、禁忌策略　　禁忌对象选择为邻域移动，禁忌表的长度设为n-1。　　算例　　设有7件零件在一台机器上加工，它们的加工时间、交货时间以及编号如下表1所示，试安排零件加工顺序，使得

7、零件总延迟时间最短。　　以上面给出的新解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为最优解，总延迟时间。　　总结　　禁忌搜索算法在解决旅行商、车辆路径、图着色、二次分配以及流水/作业车间调度等各种组合优化问题时表现出很好的性能。针对一类特

8、殊的单机排序问题：单机总延迟问题（SMTTP），本文提出一种改进禁忌搜索算法。算例表明改进的禁忌搜索算法能快速找到问题的优质解。