加工车间调度问题中禁忌搜索算法的研究与改进

摘要

加工车间调度问题是调度问题的一种，也是最难的组合优化问题之一；对加工车间调度问题进行研究和解决不但具有重要的理论意义，更有工程应用的价值。
　　 禁忌搜索算法是一种解决加工车间调度问题的有效方法，其基本思想是从一个给定解开始，通过邻域结构对邻域空间进行搜索从而找到给定解的邻域解；同时禁忌搜索算法采用禁忌列表以防止邻域搜索陷入局部最优解。本文依据邻域结构和禁忌列表这两个关键点，提出了一种基于混合邻域结构的禁忌搜索算法来对加工车间调度问题进行研究。
　　 为了扩展邻域搜索空间，本文提出了基于最长活动链的邻域结构和基于当前移动活动块的邻域结构，并对这两种邻域结构进行混合应用。为了提高禁忌列表的使用效率，本文采用了保存工序位置的禁忌方式，并且通过大量实验确定禁忌列表的长度为所有工序数量的1/7。通过仿真实验表明，本文提出的算法对于解决一部分加工车间调度问题是可行的和有效的，但是算法仍然存在一些需要解决问题，因此，在论文的最后，对全文进行了系统性的总结。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题背景

1.2加工车间调度问题的研究现状

1.3本文的研究目标及研究意义

1.4论文的组织结构

2.1加工车间调度问题

2.1.1加工车间调度问题的描述性定义

2.1.2加工车间调度问题的数学模型

2.1.3加工车间调度问题的甘特图表示方法

2.2邻域搜索算法

2.2.1邻域搜索算法的基本思想

2.2.2邻域结构

2.3禁忌搜索算法

2.3.1禁忌搜索算法的基本原理

2.3.2禁忌搜索的一般流程

2.4加工车间调度问题中禁忌搜索算法的应用

2.5基于分解方法解决加工车间调度问题的禁忌搜索算法

2.6本章小结

第三章基于混合邻域结构的禁忌搜索算法设计

3.1 HNS-TS算法中活动调度的相关概念

3.1.1活动调度

3.1.2活动调度产生算法

3.1.3活动链和活动块

3.1.4活动调度的一个实例

3.2 HNS-TS算法中初始解的产生

3.3 HNS-TS算法中邻域结构的设计

3.3.1 HNS-TS算法中最长活动链的选择方法

3.3.2 HNS-TS算法中产生邻域结构的基本移动方式

3.3.3 HNS-TS算法中一种新的邻域结构

3.3.4 HNS-TS算法中基于最长活动链的邻域结构设计

3.3.5 HNS-TS算法中基于当前移动活动块的邻域结构设计

3.3.6本节小结

3.4 HNS-TS算法中禁忌搜索的设计

3.4.1禁忌列表的禁忌方式

3.4.2禁忌列表的长度

3.4.3 HNS-TS算法中的移动选择

3.5 HNS-TS算法的终止条件

3.6 HNS-TS算法的流程图

3.7本章小结

第四章仿真实验与分析

4.1仿真实验

4.2仿真结果的比较和分析

4.3本章小结

第五章总结和展望

5.1总结

5.2展望

致谢

参考文献

附录