无等待调度的邻域搜索方法研究

摘要

无等待流水车间调度问题是一类应用广泛的组合优化问题。在常用优化目标函数下，无等待流水车间调度都是NP难问题，最优化算法由于具有指数时间复杂度，从而只适用于中小规模实例；对大规模实例，常采用启发式方法以在合理时间求得次优解。邻域搜索算法是一类最为常用的启发式方法。
　　 本文针对最大误工时间、总完工时间以及最大完工时间三个目标函数，研究无等待流水车间调度问题的邻域搜索算法，主要工作有：(1)基于任务块分解的分析方法。通过将当前解分解为任务块，给出了四个常用基本操作在最大误工时间目标函数下的加速性质，并设计了一个对偶倒置邻域。借助这些性质，搜索插入、交换、倒置以及对偶倒置邻域的时间复杂度以及NEH构造算法的时间复杂度均从O(n3)降至O(n2)。(2)邻域扩展及其加速性质。通过将任务块分解方法推广到邻域设计，给出了三个新的较大规模邻域：D(n4)规模的不相邻任务块交换邻域以及O(n3)规模的相邻任务块对换邻域和扩展单任务交换邻域，分析了三个邻域基本操作在最大误工时间和总完工时间目标函数下的加速性质。这些邻域亦可作为通用邻域派生出新的O(n2)规模的邻域。(3)基于最短路径的邻域搜索算法。针对最大完工时间目标函数，为指数规模的动态规划邻域，设计了一个O(n2)时间复杂度的动态规划搜索算法；为O(n4)规模的不相邻任务块交换邻域，通过重用中间计算结果，设计了一个O(n2)时间复杂度的搜索算法。两个算法均等价于搜索对应有向无环图中的一条最短路径。(4)有效的元启发方法。通过选取合适的禁忌属性及邻域基本操作禁忌状态的条件，给出了一个有效的禁忌搜索算法：选取相邻任务对作为禁忌属性，邻域基本操作的禁忌状态是该基本操作试图添加到当前解的相邻任务对的禁忌状态的合取；采用二维矩阵作为禁忌表的数据结构，使得该禁忌表可以容纳多种邻域并可在常量时间内判邻域基本操作的禁忌状态。通过在迭代局部搜索中使用变换邻域下降，提出了一个迭代变换邻域搜索算法，并比较了不同邻域组合用于迭代变换邻域搜索算法求解总完工时间以及最大完工时间目标函数时的相对性能。
　　 模拟实验得出如下结论：(1)插入类型的邻域比相同渐进规模的交换类型的邻域更有效；(2)相对于并集，变换邻域是更有效的多邻域搜索方式；(3)若相邻解的评估时间复杂度为常量，则采用邻域搜索好于进化算法；(4)目标函数是影响邻域设计和评估的重要因素之一。

目录

文摘

英文文摘

第1章 绪论

1.1 研究背景

1.2 问题描述与实例数据转换

1.3 无等待流水调度算法研究现状

1.4 组合优化问题的元启发方法研究现状

1.4.1 多重启方法

1.4.2 动态邻域方法

1.4.3 动态评估函数方法

1.5 研究现状分析

1.6 论文研究内容及结构

第2章 基于任务块分解的分析方法

2.1 快速NEH启发式算法

2.2 邻域基本操作的加速性质

2.3 快速禁忌搜索算法

2.4 模拟实验

2.4.1 参数选取

2.4.2 比较试验

2.5 本章小结

第3章 邻域扩展及其加速性质

3.1 邻域基本操作及其目标增量

3.2 基于目标增量的搜索算法

3.2.1 目标增量模拟退火算法

3.2.2 目标增量禁忌搜索算法

3.2.3 迭代变化邻域下降算法

3.3 模拟试验

3.3.1 邻域比较

3.3.2 扰动机制选择

3.3.3 比较实验

3.4 最大误工时间下的加速性质

3.5 本章小结

第4章 基于最短路径的邻域搜索方法

4.1 动态规划邻域搜索算法

4.2 不相邻块交换邻域搜索算法

4.3 模拟实验

4.4 本章小结

第5章 总结与展望

致谢

参考文献

攻读博士学位期间发表和撰写的学术论文

攻读博士学位期间参与的科研项目