您现在正在浏览:首页 > 论文 > 建筑化工 > 毕业论文-一类开放车间调度问题的近似算法研究

免费下载毕业论文-一类开放车间调度问题的近似算法研究

  • 资源类别:论文
  • 资源分类:建筑化工
  • 适用专业:工业工程
  • 适用年级:大学
  • 上传用户:xuehi
  • 文件格式:word
  • 文件大小:2.74MB
  • 上传时间:2012-12-23 23:35:39
  • 下载次数:0
  • 浏览次数:0

安全检测:瑞星:安全 诺顿:安全 卡巴:安全

资料简介
毕业论文-一类开放车间调度问题的近似算法研究,共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
  • 毕业论文-一类开放车间调度问题的近似算法研究
    • Microsoft Word文档毕业论文-一类开放车间调度问题的近似算法研究.doc  [8.82MB]
下载地址
资料评论
注意事项
下载FAQ:
Q: 为什么我下载的文件打不开?
A: 本站所有资源如无特殊说明,解压密码都是www.xuehai.net,如果无法解压,请下载最新的WinRAR软件。
Q: 我的学海币不多了,如何获取学海币?
A: 上传优质资源可以获取学海币,详细见学海币规则
Q: 为什么我下载不了,但学海币却被扣了?
A: 由于下载人数众多,下载服务器做了并发的限制。请稍后再试,48小时内多次下载不会重复扣学海币。
下载本文件意味着您已经同意遵守以下协议
1. 文件的所有权益归上传用户所有。
2. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
3. 学海网仅提供交流平台,并不能对任何下载内容负责。
4. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
5. 本站不保证提供的下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
论文相关下载
返回顶部