学位论文 > 优秀研究生学位论文题录展示

作业车商调度问题的效率算法

作　者: 曾凡丽
导　师: 黄志
学　校: 华中科技大学
专　业: 计算机软件与理论
关键词: 组合优化启发式算法邻域搜索作业车间调度
分类号: O224
类　型: 硕士论文
年　份: 2011年
下　载: 9次
引　用: 0次
阅　读: 论文下载

内容摘要

作业车间调度问题是公认的最难的组合优化问题之一，也是一个典型的NP难度问题。研究作业车间调度问题具有很高的理论价值。同时，作业车间调度问题是实际工业生产调度问题的抽象表述，不仅可以应用十生产调度方面，而且可以应用在经济管理、交通运输以及网络通讯等各个领域。所以，对作业车间调度问题的研究也具有很高的实际意义。数十年来，国内外的许多学者对作业车间调度问题进行了深入研究，提出了许多算法。用精确算法求解该问题时，计算时间随着问题规模的增大呈指数级增加，其实际价值并不大。因此，设计高效的求解作业车间调度问题的启发式算法成为当前研究的重点。针对作业车间调度问题，提出了一种高效的解的可行性判定算法T。用该算法对8组不同规模的国际标准算例进行了测试，并与基于深度优先遍历思想的判定算法DFS算法进行了比较。实验结果表明，T算法的效率比DFS算法要高很多。设计了一种新的邻域结构和一种有效的搜索机制，形成了混合邻域搜索算法DSP。该算法能够防止搜索过早的卡壳在局部最优的陷阱。DSP算法采用了一种新的优先指派算法Vip-SP来生成初始解。同时，采用了T算法对解进行可行性判断，效率提高了很多。用该算法计算了42个国际标准算例。实验结果表明，该算法是一种高效的启发式算法。

全文目录

摘要  4-5
Abstract  5-8
1 引言  8-18
  1.1 选题本背景太研究意义  8-9
  1.2 国内研究现状  9-13
  1.3 问题描述  13-16
  1.4 本文的主要工作及结构安排  16-18
2 解的可行性判定算法  18-25
  2.1 算本缩述对分析  18-21
  2.2 算本 T 本测试本究对分析  21-24
  2.3 本章小结  24-25
3 一种新的优先规则指派算法  25-32
  3.1 优先使则本设计  25-26
  3.2 算本 Vip-SP 本实现文本  26-28
  3.3 算本 Vip-SP 本测试本究本分析  28-30
  3.4 本章小结  30-32
4 邻域搜索算法  32-40
  4.1 关键路径的定义和求解方法  32-36
  4.2 邻域搜检算法的思想  36
  4.3 邻域结构及其性质  36-38
  4.4 两种常用的邻域搜索方式  38
  4.5 本章小结  38-40
5 一种新的混合邻域搜索算法  40-46
  5.1 算本 DLS 本邻域本或对搜检策略  40-41
  5.2 算本 DLS 本实现文本  41-43
  5.3 算本 DLS 本测试本究本分析  43-45
  5.4 本章小结  45-46
6 全文总结与展望  46-49
  6.1 主要工作总结  46-47
  6.2 未来研究方向和目标  47-49
致谢  49-50
参考文献  50-54
附录附图列表  54

作业车商调度问题的效率算法

内容摘要

全文目录

相似论文