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

基于工位的资源受限项目调度问题的模型研究与调度算法实现

作　者: 郑元利
导　师: 林友芳
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: 调度 最小化最大完工时间 工位约束 同工位任务 任务子网 联合子网
分类号: TP301.6
类　型: 硕士论文
年　份: 2014年
下　载: 10次
引　用: 0次
阅　读: 论文下载
 

内容摘要


资源受限项目调度问题(Resource-constrained Project Scheduling Problem, RCPSP)包含一组在调度过程中必须满足优先关系和资源约束的任务,常见调度目标是最小化最大完工时间(Makespan)。在生产系统或服务组织中,存在这么一类问题,相对于RCPSP,额外拥有一定数量不同类型的工位,任务需要在特定的工位上执行,每个资源只能服务有限的工位,工件或可移动的资源在工位之间移动需要一定的时间,调度目标也是最小化最大完工时间。在以前RCPSP研究中,缺少对工件和资源位置的考虑,因此上述问题不能直接使用RCPSP模型进行求解。本文将对基于工位约束的资源受限项目调度问题(Site-based and Resource-constrained Project Scheduling Problem, SRCPSP)做以下详细描述与分析。首先,本文在介绍RCPSP及其各种扩展约束后,分析了工位的基本约束,并对工位与资源、工位与工件和工位与任务之间的约束进行了详细的分析与公式化描述。结合任务优先关系与工位的约束,证明了任务的同工位特性,定义了同工位任务。基于同工位任务提出了任务子网(Sub-net, SN)和联合子网(Combined Sub-nets,CSN)的概念,并设计了SN和CSN的求解流程,将工位约束与RCPSP模型结合,给出了SRCPSP的模型。其次,为了在可接受时间内获得SRCPSP的可行解,本文提出两个基于优先规则的启发式调度算法,分别是基于任务子网的搜索算法(Sub-net Based Search algorithm, SNBS)和基于联合子网的搜索算法(Combined Sub-nets Based Search algorithm, CSNBS)。此外,为更好的解释上述算法,文中给出了SNBS算法和CSNBS算法的流程图。最后,本文使用项目调度仿真平台获得了可用于验证算法正确新的两组测试实例。实验结果表明SNBS在时间效率上优于CSNBS,但CSNBS较SNBS获得了更小的项目完工时间。并且基于测试实例,验证两个算法都优于人工调度算法。

全文目录


致谢  5-6
摘要  6-7
ABSTRACT  7-11
1 引言  11-15
  1.1 研究背景与意义  11-12
  1.2 国内外研究现状  12-13
  1.3 论文主要内容  13-14
  1.4 论文基本结构  14
  1.5 本章小结  14-15
2 资源受限项目调度问题描述  15-28
  2.1 扩展约束介绍  15-22
    2.1.1 任务约束  15-17
    2.1.2 资源约束  17-18
    2.1.3 优先关系约束  18-20
    2.1.4 广义优先关系  20-22
  2.2 问题模型分析  22-24
    2.2.3 问题求解目标  22-23
    2.2.4 问题常见模型  23-24
  2.3 算法研究现状  24-27
    2.3.1 精确算法  24-25
    2.3.2 启发式算法  25-26
    2.3.3 超启发式算法  26-27
  2.4 本章小结  27-28
3 基于工位的项目调度问题  28-43
  3.1 工位及其约束介绍  28-29
  3.2 工件约束分析  29-30
  3.3 资源约束分析  30-31
  3.4 任务约束分析  31-41
    3.4.1 同工位任务  33-36
    3.4.2 任务子网  36-38
    3.4.3 联合子网  38-41
  3.5 问题建模与分析  41-42
  3.6 本章总结  42-43
4 启发式调度算法  43-54
  4.1 算法主要思想  43-44
  4.2 基于规则的本地搜索算法  44-53
    4.2.1 实验算法框架设计  44-46
    4.2.2 SNBS算法设计  46-48
    4.2.3 CSNBS算法设计  48-50
    4.2.4 工位调度设计  50-52
    4.2.5 资源调度设计  52-53
  4.3 本章总结  53-54
5 实验及分析  54-59
  5.1 实验数据生成  54-55
  5.2 实验方案设计  55-56
  5.3 实验结果分析  56-58
  5.4 本章总结  58-59
6 总结与展望  59-60
参考文献  60-64
附录A  64-66
作者简历  66-68
学位论文数据集  68

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. BioLab面向生物计算服务的网格系统,TP399-C8
  3. 无线传感器网络上的数据聚集调度算法,TP212.9
  4. 超声速巡航导弹姿态控制系统增益调度设计的参数化方法,TJ765.23
  5. 车载FlexRay主干网的构建与性能分析,TP273
  6. 车载CAN网络的网关设计方法研究,TP273
  7. 极端气象灾害下考虑不确定断线故障的电力系统随机优化调度,TM73
  8. 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
  9. 基于遗传—牛顿算法的公交优化调度,TP18
  10. 遥感数据处理网格平台的设计与初步实现,TP79
  11. 基于遗传算法的矿山资源优化调度模型的研究,O224
  12. 水路交通突发事件应急物资配置研究,F224;U698
  13. 基站维护发电智能调度系统的研究与实现,TM734
  14. 基于无线网络的多发射功率跨层协议关键技术研究,TN92
  15. P2P视频点播系统中服务节点数据调度策略研究,TN948.64
  16. 基于GPS/GIS的城市公交信息管理系统,TP311.52
  17. 铁路综合演练系统的开发与实现,TP311.52
  18. 网格任务调度算法研究及其有色Petri网的建模与仿真,TP301.1
  19. 微粒群算法的改进与应用研究,TP18
  20. 船厂管加工车间生产计划仿真,U673.2
  21. 嵌入式实时操作系统MQX的内核分析及应用研究,TP316.2

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com