学海网

毕业论文-基于新的动态邻域算法的车间调度问题的研究，共64页，25040字。
摘要
作业加工调度问题是NP难的，被认为是最难的组合优化问题之一。在解决工业生产、经济管理和网络通讯等诸多问题时，都要涉及求解这个问题。优质、快速地求解作业加工调度问题，既有重要的理论意义，又能带来巨大的经济效益。
转换瓶颈算法是解决作业加工调度问题的最有效的算法之一，本论文中用转换瓶颈算法来产生问题的初始值，进而提高搜索效率。动态邻域算法的基本思想是利用两个主要工具“shake（振动）”和“local search（局部搜索）”，局部搜索用于探索一个更为优的结果，振动使局部最小跳入它的下一个邻域，从而继续进行局部搜索。本论文是依据这个基本思想研究和分析并进行改进，提出一个新的算法。
为了提高振动的效率，我们根据卡里尔定理[11]和格拉博夫斯基定理[7]提出了六个推论，以避免无用的局部邻域结构的切换，并且提出了新的邻域结构，即：“向前插入”，“向后插入”，“直接交换”。同时把振动分为“正常振动”和“贪婪振动”。实验表明基于六个推论，振动更加有驱动力。基于新的邻域结构，可以找到更好的某个点的邻域最小值。
关键词： 作业加工调度 NP难问题 启发式 动态邻域算法

目录
第一章 绪论 1
1.1研究的背景与意义 1
1.2组合最优化问题 2
1.3实际难解性和NP完全问题 3
1.4启发式方法 4
1.4.1启发式方法的性能评价 5
1.4.2 常用的启发式算法 6
1.5 本文的主要内容和结构 7
第二章 作业加工调度问题及相关算法 9
2.1 作业加工调度问题的描述 9
2.2 JSSP的模型 9
2.2.1 JSSP的甘特图表示 10
2.2.2 JSSP的分离图表示 11
2.2.3 JSSP的复杂性 12
2.3 动态邻域算法 12
2.4 转换瓶颈算法 16
2.4.1转换瓶颈算法的原理 16
2.4.2转换瓶颈算法流程图 19
第三章 动态邻域算法的改进及其设计 21
3.1 作业车间调度模型的建立 21
3.1.1符号说明 21
3.1.2数学模型 22
3.2 作业车间调度的编码问题 22
3.3 IVNS中生成初始解的方法 22
3.4 IVNS中振动操作的邻域结构 24
3.4.1 振动操作的邻域结构 24
3.4.2 关于振动邻域结构的推论 25
3.5 IVNS中局部搜索操作的邻域结构 29
3.5.1 IVNS中局部搜索操作的邻域结构 29
3.3.2 VNS局部搜索部分前项插入 30
3.3.3 VNS局部搜索部分后项插入 30
3.3.4 VNS局部搜索部分的交换 31
3.6 IVNS中shake和local search的组成结构 33
3.7 新动态邻域算法的结束条件 34
3.8 IVNS的流程图 35
第四章 改进的动态邻域算法的分析 37
4.1 模拟环境 37
4.2 各种启发式算法的MakeSpan的比较 37
第五章 全文总结及展望 41
5.1主要工作总结及创新 41
5.2未来的研究方向 42
致谢语 43
References 45
附录 49