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

基于约束传播技术的资源受限项目调度问题求解算法

作　者: 刘露
导　师: 刘士新
学　校: 东北大学
专　业: 系统工程
关键词: 项目调度资源受限约束满足问题约束传播遗传算法分枝定界
分类号: F270
类　型: 硕士论文
年　份: 2009年
下　载: 25次
引　用: 0次
阅　读: 论文下载

内容摘要

利用企业现有资源降低生产成本、提高经济效益并为用户提供更好的服务一直是现代企业面临的重要课题,而这些问题可以通过制定合理、高效的生产计划解决,至少部分地解决。资源受限工程调度问题(RCPSPs)在单件或小批量生产方式企业中有着广泛应用,尤其在依定单生产的企业中显示出了越来越更重要的作用。在理论上,该问题模型丰富,而且多属于NP-hard问题,求解困难。因此,对RCPSPs的研究在理论上和实际应用中都有着重要意义。本文针对RCPSPs开展了以下研究工作:(1)对项目调度问题的分类与模型进行了简要说明,对累积调度问题的约束传播算法从两个方面进行了介绍,一方面是占先问题,另一方面是非占先问题。(2)基于对累积调度问题的约束传播方法的研究与分析,提出了一个新的约束传播方法一具有优先关系的累积调度问题的约束传播算法,应用问题实例说明了算法的约束传播效果。(3)设计了结合约束传播技术的求解RCPSP的遗传局域搜索算法,该算法可以缩小问题的搜索空间,使得算法的效率提高,得到的解更优。通过问题实例说明了算法的求解效果。(4)设计了基于约束传播的求解RCPSP的分枝定界算法,详细介绍了这个算法的基本思想和算法流程。通过问题实例说明了算法的求解效果。在本文最后对全文工作进行总结,并展望今后的研究方向。

全文目录

中文摘要  5-7
Abstract  7-11
第1章绪论  11-19
  1.1 引言  11-12
  1.2 RCPSP的基本概念及参数特性  12-15
  1.3 单执行模式资源受限项目调度  15-17
  1.4 本文主要研究内容与章节安排  17-19
第2章基于约束传播的调度理论与方法  19-39
  2.1 约束满足问题  19-20
  2.2 调度问题中的约束传播方法  20-21
  2.3 累积调度问题的约束传播方法  21-37
    2.3.1 占先问题  21-23
    2.3.2 非占先问题  23-37
  2.4 小结  37-39
第3章基于优先关系的累积调度问题的约束传播算法  39-49
  3.1 问题描述  39-41
  3.2 算法问题描述  41-46
    3.2.1 现有的Edge-finding  42-45
    3.2.2 带有优先关系的Edge-finding  45-46
  3.3 实验案例  46-47
  3.4 结论  47-49
第4章基于约束传播的 RCPSP的遗传局域搜索算法  49-59
  4.1 基于优先规则的启发式算法  49-50
  4.2 求解 RCPSP的遗传局域搜索算法  50-53
    4.2.1 算法流程  50-51
    4.2.2 编码和解码  51-52
    4.2.3 交叉算子  52-53
    4.2.4 局部搜索过程  53
  4.3 求解基于约束传播的RCPSP遗传局域搜索算法  53-54
  4.4 实验结果与分析  54-59
    4.4.1 问题举例  54-57
    4.4.2 结果分析  57-59
第5章基于约束传播的 RCPSP的分枝定界算法  59-73
  5.1 基本分枝定界算法  59-63
    5.1.1 分枝定界法的基本思想  59-61
    5.1.2 搜索树的剪枝  61-62
    5.1.3 分枝定界算法的实现  62-63
    5.1.4 算法分析  63
  5.2 基于约束传播的分枝定界算法  63-70
    5.2.1 搜索过程  64-65
    5.2.2 分枝定界算法  65-67
    5.2.3 基于约束传播的分枝定界算法  67-70
  5.3 基于约束传播的分枝定界算法求解案例  70-73
第6章总结与展望  73-75
  6.1 全文总结  73
  6.2 进一步的工作  73-75
参考文献  75-79
致谢  79

基于约束传播技术的资源受限项目调度问题求解算法

内容摘要

全文目录

相似论文