求解RCPSP问题的迭代局部搜索算法研究

发布时间：2017-10-22 13:01

  本文关键词：求解RCPSP问题的迭代局部搜索算法研究

  更多相关文章： 迭代局部搜索 资源约束项目调度问题 扰动 关键链 双对齐

【摘要】：资源约束项目调度问题(Resource-constrained Project Scheduling Problem, RCPSP)的主要任务是为调度项目的活动安排时间和资源,合理使用资源实现既定目标的最优化。近年来由于企业信息化的快速发展和项目管理的需要,该问题被越来越广泛地研究和应用,对该问题的进一步研究也具有很高的研究价值和应用前景。本文提出了一种应用于资源约束项目调度问题的迭代局部搜索算法(Iterated Local Search,ILS)。迭代局部搜索算法是一类简单而高效的元启发式算法,成功地应用于诸多组合优化问题。本文将ILS算法应用于RCPSP问题,通过对算法的进一步改进和优化,使其更适用于RCPSP问题。首先研究产生初始解的方法。本文通过实验比较了多种求解较优的启发式算法,最终选择最早开始时间(Earliest Start Time,EST)优先规则配合串行调度生成方案(Serial Schedule Generation Scheme,SSGS)的方式生成初始解。同时为了进一步优化局部搜索过程使其更适用于RCPSP问题,研究了插入和交换两种局部搜索方法的求解性能,设计了使用迭代交换的方式优化当前解的局部搜索过程。为克服局部搜索过程容易陷入局部最优的缺点,针对RCPSP问题,本文提出了一种扰动策略,通过动态扰动多个任务的方式防止过早陷入局部最优。为进一步提高搜索效率,本文分别研究了在局部搜索过程中使用关键链和关键路径信息的方法。通过以上改进策略,最终完成了应用于RCPSP问题的迭代局部搜索算法。本文的优化目标是最小化项目的完工时间。在标准数据集上的实验表明提出的算法是有效的。
【关键词】：迭代局部搜索 资源约束项目调度问题 扰动 关键链 双对齐
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-10
• 1 引言10-17
• 1.1 研究背景与意义10-12
• 1.2 国内外研究现状12-14
• 1.3 迭代局部搜索算法简介14-15
• 1.4 论文主要内容15-16
• 1.5 论文基本结构16
• 1.6 本章小结16-17
• 2 经典资源约束项目调度问题及求解算法17-27
• 2.1 不考虑资源约束的项目调度17-18
• 2.2 约束描述18-20
• 2.2.1 逻辑约束19
• 2.2.2 资源约束19-20
• 2.3 问题目标20-21
• 2.4 模型描述21-23
• 2.5 算法研究现状23-26
• 2.5.1 精确算法23-24
• 2.5.2 启发式算法24-26
• 2.6 本章小结26-27
• 3 应用于RCPSP问题的ILS算法27-40
• 3.1 基本定义27-29
• 3.2 算法思想29
• 3.3 算法框架29-30
• 3.4 算法描述30-38
• 3.4.1 产生初始解和解的标准化31-32
• 3.4.2 关键链方法32-34
• 3.4.3 局部搜索过程34
• 3.4.4 扰动策略34-35
• 3.4.5 交换过程35-36
• 3.4.6 提出的ILS算法36-38
• 3.5 算法的可行性分析38-39
• 3.6 本章小结39-40
• 4 参数评估和实验结果分析40-51
• 4.1 实验数据集及环境40-42
• 4.2 优化策略42-47
• 4.2.1 扰动方式对比42-43
• 4.2.2 验证精英解池43-44
• 4.2.3 验证局部搜索过程的交换方式44-45
• 4.2.4 关键路径和关键链对比45-46
• 4.2.5 验证算法扰动过程的交换方式46-47
• 4.3 参数评估47-49
• 4.3.1 扰动强度评估47
• 4.3.2 参数max_cnt的确定47-48
• 4.3.3 迭代终止条件的选择48-49
• 4.4 实验结果49
• 4.5 本章小结49-51
• 5 总结与展望51-53
• 5.1 论文总结51-52
• 5.2 论文展望52-53
• 参考文献53-58
• 作者简历及攻读硕士学位期间取得的研究成果58-60
• 学位论文数据集60

【相似文献】

中国期刊全文数据库 前10条

1 张雁;黄永宣;魏明海;;一种求解最大团问题的自适应过滤局部搜索算法[J];信息与控制;2011年04期

2 肖进杰,朱大铭,马绍汉,潘锐;多服务中心设置问题局部搜索算法的分析与实验[J];计算机工程;2005年12期

3 谢啸虎;黄樟灿;焉炳艳;;多目标遗传局部搜索算法的研究进展[J];武汉理工大学学报(信息与管理工程版);2006年12期

4 潘锐;朱大铭;董林光;董颖;;求解k中间点问题的新局部搜索算法[J];计算机工程与应用;2008年04期

5 詹青青;;启发式局部搜索算法在电路划分中的应用[J];福建电脑;2010年04期

6 韦炜;藤村茂;席裕庚;;求解旅行锦标赛问题的改进混合局部搜索算法[J];计算机仿真;2012年10期

7 吴贵芳,徐科,徐金梧;边界局部搜索算法与应用[J];计算机应用;2005年02期

8 肖进杰;谢青松;牛翠霞;;设备定位问题局部搜索算法的实验[J];计算机工程与应用;2010年02期

9 陈萍;黄厚宽;董兴业;;基于多邻域的车辆路径优化迭代局部搜索算法[J];北京交通大学学报;2009年02期

10 王健;赵娜;刘超;孙志礼;;粒子群及局部搜索算法在串并联系统结构优化中的应用[J];机械与电子;2014年01期

中国重要会议论文全文数据库 前1条

1 刘心报;叶强;;基于模块设计的蚁群算法研究综述[A];'2008系统仿真技术及其应用学术会议论文集[C];2008年

中国硕士学位论文全文数据库 前6条

1 赵轩;求解RCPSP问题的迭代局部搜索算法研究[D];北京交通大学;2016年

2 咸爱勇;合取范式最大不全满足与最大可满足问题的局部搜索算法研究[D];山东大学;2012年

3 高超;随机局部搜索算法及其应用研究[D];中国科学技术大学;2015年

4 殷茜;基于局部搜索的最小可满足问题求解算法研究[D];东北师范大学;2015年

5 温真真;需求可拆分车辆路径问题的迭代局部搜索算法研究[D];北京交通大学;2015年

6 颜远辉;赋权MAX-SAT问题的动态凸化方法[D];福州大学;2011年

，

本文编号：1078432