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

《求解rcpsp问题的迭代局部搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、１００学校代码：０４密级：公开胆新ＭＩＢＥＩＪＩＮＧＪＩＡＯＴＯＮＧＵＮＩＶＥＲＳＩＴＹｉｎ｜｜硕：ｔ学位论文ｊ求解ＲＣＰＳＰ问题的迭代局部搜索算法研究誦名赵源学科专业计算机科学与技术．’、帛誦麵旨類諭；培养縣體机与信龍术学院禮Ｐ盛ｙ麵齡交遺乂＃硕±学位论文求解民ＣＰＳＰ问题的迭代局部搜索算法研究Ｉｔｅｒａｔｅｄｌｏｃａｌｓｅａｒｃｈ过Ｉｏｒｉｔｈｍｓｆｏｒｔｈｅｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｅｄｒｏｅｃｔｇｐｊｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｇｐ作者：赵巧导师：董兴业北京交通大学

2、２０１６年３月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、、缩印或扫描等复制手段保存汇编Ｗ供查阅和借阅。同意学校向国家有关部口或机构送交论文的复印件和磁盘。学校可Ｗ为存在馆际合作关系的兄弟高校用户提供文献传递服务和交换服务。（保密的学位论文在解密后适用本授权说明）学位论文作者签名；导师签名：案少、乂签字曰期：２〇１（年午月１５曰签字曰期：年月（方曰１密级：公开学校代码：０００４北京交通大学硕±学

3、位论文求解ＲＣＰＳＰ问题的迭代局部搜索算法研巧Ｉｔｅｒａｔｅｄｌｏｃａｌｓｅａｒｃｈａｌｏｒｉｔｈｍｓｆｏｒｔｈｅｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｅｄｐｒｏｊｅｃｔｇｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｇｐ１３１２０４５８：作者姓名；赵轩学号：导师姓名：董兴业职称副教授学位类别：工学学位级别；硕±学科专业：计算机科学与技术研究方向：人工智能北京交通大学２０１６年３月ｉ致谢、在即将毕业之际，衷屯对在研究生ｓ年期间为我提供帮助的各位老师、朋友及家人表示感谢。本论文是在我的导师董兴业副教授的悉也指导下完成的。董老

4、师严谨的治学态度和科学的工作方法对我有很多的帮助和影响，最主要的是他教会了我许多做、人４事的方法，并且在学习上和生活上都给予了我无私的关屯和帮助。在此衷也感谢研究生期间董兴业老师对我的教导与关也。、指导我完成了实验室的科研项目林友芳教授悉屯。他认真做事的方式给我留，非常值得我去学习，下了很深的印象。此外他在学习上和生活上同样给了我很多的帮助。在此向林友芳教授表示衷也的感谢。韩升老师在我的日常科研工作和项目中提供了很多的意见和帮助，并且在日、常生活中给予我很多照顾和帮助，在此表示衷屯的感谢。还要感谢花大量时间审阅我论文的诸位评审老师！最后，特别感谢

5、帮助我、爱护我的家人，因为有了他们的理解和支持我才能走到今天。北京交通大学硕古学位论文摘要摘要ｅｓｏｕｒｃｅ－ｃｏｎｓａｎｅｄＰｒｏｅｃｃｈｅｄｕｎｒｏｅｍ资源约束项目调度问题（Ｒｔｒ，ｉｔＳｌｉＰｂｌｊｇＲＣＰＳＰ）的主要任务是为调度项目的活动安排时间和资源，合理使用资源实现既定目标的最优化，该问题。近年来由于企业信息化的快速发展和项目管理的需要一被越来越广泛地研究和应用，对该问题的进步研究也具有很高的研究价值和应＾用前景。本文提出了种应用于资源约束项目调度问题的迭代局部搜索算法（ＩｔｅｒａｔｅｄＬｏｃａｌＳｅａｒｃｈ，ＩＬＳ。）

6、一迭代局部搜索算法是类简单而高效的元肩发式算法，成功地应用于诸多组一合优化问题，。本文将ＩＬＳ算法应用于ＲＣＰＳＰ问题通过对算法的进步改进和优化，使其更适用于ＲＣＰＳＰ问题。首先研究产生初始解的方法。本文通过实验比较了多种求解较优的启发式算法，最终选择最早开始时间（ＥａｒｌｉｅｓｔＳｔａｒｔＴｉｍｅＥＳＴ）优先规则配合串行调度生，成方案（ＳｅｒｉａｌＳｃｈｅｄｕｌｅＧｅｎｅｒａｔｉｏｎＳｃｈｅｍｅ，ＳＳＧＳ）的方式生成初始解。同时为了一进步优化局部搜索过程使其更适用于ＲＣＰＳＰ问题，研究了插入和交换两种局部搜索方法的求解性能，设计了使用迭代交换

7、的方式优化当前解的局部搜索过程。一为克服局部搜索过程容易陷入局部最优的缺点，ＲＣＰＳＰ问针对题，本文提出了种扰动策略一，通过动态扰动多个任务的方式防止过早陷入局部最优。为进步提高搜索效率，本文分别研巧了在局部搜索过程中使用关键链和关键路径信息的方法。通过上改进策略，最终完成了应用于ＲＣＰＳＰ问题的迭代局部搜索算法。本文的优化目标是最小化项目的完工时间。在标准数据集上的实验表明提出的算法是有效的。关键词：迭；资源约束项