文件格式：word
文件大小：8.82MB
适用专业：工业工程
适用年级：大学
论文编号：204353
下载咨询：点击联系客服 论文简介：
毕业论文-一类开放车间调度问题的近似算法研究，共103页，57739字
中文摘要
开放车间模型是调度领域的经典模型，其调度问题也是复杂而又常见的工业
问题。在实际生产中，虽然很难将整个系统完全抽象成此类经典模型，但是，实
际系统的某一部分或某个子系统往往能够用开放车间模型予以描述，因此，对于
该经典模型及其调度问题的研究具有重要的意义。
本文研究的是最小化完成时间平方和的开放车间调度问题，其被证明为强
难问题，这就意味着想在多项式时间内使问题精确求解是不可能的，因此本文专
注于对开放车间调度问题的近似算法的探索，力求在可接受的时间范围内，为该
问题的不同规模实例都找到足够接近精确解的近似解。
本文为该问题分别设计和实现了具有渐近最优性的 SPTB 构造启发式算法，对
中小规模问题解的收敛性有显著提升的局部搜索算法和遗传算法，解的质量更容
易评估的拉格朗日松弛算法。
通过对多种近似算法的探索、设计及实现，已经能够较为高效的为不同规模的
研究问题提供足够接近精确解的近似解。这不仅具有重要的学术意义，同样能够
在实际生产中加以改进和利用。
关键词：开放车间；完成时间平方和；SPTB 局部搜索；遗传算法；拉格朗日
松弛算法
目录
第 1 章 引言 ........ 1
1.1 研究背景 ... 1
1.2 研究问题与意义 1
1.3 研究内容 ... 2
1.4 小结 .. 3
第 2 章 文献综述 5
2.1 常见调度问题类型描述 ...... 5
2.1.1 常见机器环境描述 ....... 5
2.1.2 常见目标函数类型 ....... 6
2.2 调度研究方法 .... 7
2.2.1 第一个十年：组合分析 ........ 7
2.2.2 第二个十年：分支定界 ........ 8
2.2.3 第三个十年：复杂度和分类 ....... 10
2.2.4 第四个十年：近似解 . 12
2.2.5 第五个十年：增强型调度模型 ... 16
2.3 小结 17
第 3 章 启发式算法研究 .... 19
3.1 SPTB 构造启发式算法....... 19
3.1.1 算法设计 ... 19
3.1.2 运行结果分析 .... 21
3.2 局部搜索算法 .. 33
3.2.1 基于工作的局部搜索算法设计 ... 34
3.2.2 基于操作的局部搜索（禁忌搜索）算法设计 ...... 37
3.3 遗传算法 . 41
3.3.1 算法设计 ... 41
3.3.2 运行结果分析 .... 43
3.4 小结 46
第 4 章 拉格朗日松弛算法 47
4.1 算法设计 . 47
4.1.1 整数规划模型 .... 47
4.1.2 工作层子问题 .... 48
4.1.3 子问题动态规划算法 . 49
4.1.4 可行调度构造 .... 52
4.1.5 拉格朗日松弛算法框架 ...... 53
4.1.6 减少动态规划状态空间 ...... 53
4.2 运行结果分析 .. 55
4.3 小结 57
第 5 章 结论与展望 ... 58
5.1 本文总结 . 58
5.2 未来研究展望 .. 59
插图索引 ... 60
表格索引 ... 62
参考文献 ... 63
致 谢 67
声 明 68
附录A 外文资料的书面翻译 ...... 69
论文文件预览：
共1文件夹，1个文件，文件总大小：8.82MB，压缩后大小：2.74MB
- 毕业论文-一类开放车间调度问题的近似算法研究
毕业论文-一类开放车间调度问题的近似算法研究.doc [8.82MB]
下载地址：
发表于 2012-12-30 05:46:28