改进类电磁算法在资源受限项目调度问题中的应用研究

《改进类电磁算法在资源受限项目调度问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论又改进类电磁算法在资源受限项目调度问题中的应用研究作者姓名：学科专业：导师姓名：完成时间：李玉东管理科学与工程陈华平教授二。一三年五月UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeResearchonimprovedElectromagnetism--likeMechanismAlgorithmforRCPSPAuthor’SName：Speciality：Supervisor：Finish

2、edtime：LiYudongManagementScienceandEngineeringPro．fHuapingChenMay27m，2013中国科学技术大学学位论文原创性声明本人声明所旱交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特NDi：i以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文巾作了明确的说明。作者签名：庭五童签字日期：圣垒壁垒笸旦垒目中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著

3、作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部fLJ或机构送交论文的复印件和电子版，允许论文被查l列和借阅，可以将学位论文编入《中国学何论文全文数据库》等有关数据库进行检索，可以采用影E1J、缩EJJ或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。回叁开口保密(——年)作者签名：痊垂壶签字口划：垒堡纽目鲴导帅签名：摘要资源受限项目调度问题(ResourceConstrainedScheduli

4、ngProbolem，RCPSP)是项目管理问题中的关键问题之一。此类问题与一般项目调度问题的不同之处在于，RCPSP问题要求项目工序在执行时不仅要满足时序约束，同时也要满足特定的资源约束。因此RCPSP问题比一般的项目调度问题更复杂，而这类复杂的问题常见于工程建设、软件开发以及制造业之中。RCPSP问题已经被证明为NP难问题，求解算法的研究一直是该领域的研究热点和研究难点。本文所研究的是类电磁算法在RCPSP问题上的应用，类电磁算法是一种十分适用于求解RCPSP这样一类时间窗口问题的新算法，从已有的研究成

5、果中可以看出类电磁算法应用在RCPSP问题上具有较高的求解性能。但由于算法提出时间比较短，研究成果还比较少，算法本身还有一些缺陷和值得改进之处，因此研究该算法在RCPSP问题上的应用具有重大的理论和现实意义。本文对RCPSP问题应用类电磁算法进行了研究，主要做了以下工作：(1)首先本文介绍了RCPSP问题的产生与发展、研究现状与研究意义。然后介绍了该问题的一般求解方法，包括精确求解算法、基于优先规则的启发式算法以及智能算法。文章重点介绍了目前研究比较成熟的遗传算法、蚁群算法、粒子群算法及模拟退火算法，对这些

6、算法的研究情况进行了梳理和总结并指出了现有算法研究的不足之处。然后文章对本文研究的新兴的类电磁算法进行了介绍，对该算法的原理、特点以及参数设置进行了说明：文章同时指出EM算法适合于求解RCPSP问题的根本原因，并对其优势与不足之处进行了详细分析。(2)本文重点研究了类电磁算法在RCPSP问题上的改进，这同时也是文章的创新之处。鉴于标准类电磁算法求解RCPSP问题的不足，文章提m了三种相互联系但又有区别的算法：IEM、IEM—SNS以及IEM—VNS。IEM算法对原有的EM算法参数进行了改进，改进后的参数设计

7、使得算法收敛速度更快并Ⅱ．减缓了算法陷入局部最优的速度，仿真实验证f1月了改进的有效性。IEM—SNS算法在IEM算法的基础上引入了局部搜索策略，定义了粒了解的邻域空I刊，每次迭代完成之后都会对每个粒子的邻域空问进行搜索，加快算法的收敛速度。IEM—VNS是在IEM—SNS的基础上引入了变邻域搜索的概念，存邻域搜索摘要过程中有选择的跳出原搜索邻域，这样做一方面能够加快算法的收敛速度，同时也能够避免算法陷入局部最优，使得改进后的算法平衡了算法的搜索能力和探索能力。通过对比实验，IEM．VNS比IEM—SNS及

8、GA—SNS具有更好的求解性能，同时也证明本文的改进是有效的。文章最后对本文的研究内容进行了总结，并提出了未来的研究方向。关键词：资源受限项目调度变邻域局部搜索类电磁算法ABSTRACTTheresource—constrainedprojectschedulingproblemisoneofthekeyissuesinprojectmanagement．Thedifferencebetweensuchprobl