抢占式资源受限项目调度问题的多agent优化方法

《抢占式资源受限项目调度问题的多agent优化方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学硕士学位论文抢占式资源受限项目调度问题的多Agent优化方法姓名：赖昌涛申请学位级别：硕士专业：管理科学与工程指导教师：寿涌毅20120222浙江大学硕士学位论文摘要摘要本文的研究对象是资源受限项目调度问题的一个扩展问题，“允许最多一次抢占的抢占式资源受限项目调度问题”，即1PRCPSP。实际项目中的某些活动会因为资源没及时到位、或者需要优先满足其他活动的需要而被迫暂时终止；但出于控制进度偏差的需要，这种暂时终止不会被允许过多地存在。这是抢占式资源受限项目调度问题(PRCPSP)产生的背景。lPRCPSP是PRCPSP的特例，其中的每项活动至多只允许被抢占一次。与RC

2、PSP一样，1PRCPSP是一个典型的NP．难问题，利用智能优化方法求解该问题是重要的研究方向。我们在前人已有研究的基础上，从多Agent优化方法的角度探寻该问题的求解方式。具体而言，研究方法包括粒子群优化方法(PSO)、蚁群优化方法(ACO)和多Agent优化方法(MAO)三种，其中PSO和ACO属于群智能优化方法，也都是MAO的一种。PSO首先被用于问题求解，相应的算法为1PRCPSPPSO。我们设计了基于活动列表的编码、基于优先权值的编码、基于活动列表和抢占点的编码，以及基于优先权值和抢占点的编码四种编码方式，采用串行进度生成机制(SSGS)和允许一次抢占的串行进度生成

3、机制(1SSGS)来解码，结合峰交叉算子(PX)的思想设计了相应的粒子更新机制。在PSPLIB中的RCPSP数据集上的计算实验显示，1PRCPSPPSO不仅具有很好的收敛性，而且能求得具有竞争性的结果。其次，我们将ACO应用于1PRCPSP的求解中，设计了1PRCPSPACO。该算法同样借鉴了峰交叉算子的思想，设计了峰路径信息素增强机制，针对当前代最好的解的峰，施加一个额外的信息素增强操作。算法采用lSSGS将蚂蚁走过的路径转化为问题的可行调度。同样的，我们使用PSPLIB中的RCPSP数据集对算法的收敛性和求解效果作了评估。最后，我们设计了一种1PRCPSPMAS体系及相应

4、的优化方法1PRCPSPMAO。1PRCPSPMAS体系包含两类Agent：负责项目资源请求与活动执行的活动Agent，以及负责资源分配和项目调度的调度Agent。活动Agent与调度Agent之间通过协商机制完成资源分配和项目调度；通过一种迭代改进机制来实现问题解的优化。与前两类不同的是，1PRCPSPMAO同时具有仿真和III浙江大学硕士学位论文摘要优化两种特征。Agent之间的协商机制，旨在模拟实际项目运作中经常发生的负责人或部门之间通过沟通解决冲突或改变项目计划的情形；而迭代改进机制则使得算法具有优化问题解的功能。本文的成果具有理论和实践意义，丰富了抢占式资源受限项目

5、调度问题的研究方式，拓展了粒子群优化方法、蚁群优化方法和多Agent优化方法的应用领域；所设计的多Agent系统可以用于项目进度管理决策中，为项目计划制定阶段的项目整体评估提供了一种基于MAS的仿真优化方法。关键词：项目调度；抢占；多Agent优化；粒子群优化；蚁群优化；峰交叉算子IV浙江大学硕士学位论文AbstractTheresearchsubjectofthispaperisrelatedtooneoftheextensionissuesofclassicresource—constrainedprojectschedulingproblem，namelyone—tim

6、epreemptiveresource—constrainedprojectschedulingproblem,abbreviatedas1一PRCPSP．Inrealprojects，someoftheactivitiesmaybepreemptedbecausetheresourcesarenotinplaceintimeorduetotheneedsofotheractivitiesshouldbemetfirst；anyway,toomanysuchpreemptionswouldnotbeallowed．Tllisisthebackgroundofthepreemp

7、tiveresource-constrainedprojectschedulingproblem(PRCPSP)．1一PRCPSPisaspecialissueofPRCPSP,inwhichtheactivitiesareallowedtobeinterruptednotmorethanonce．LikeRCPSP,1——PRCPSPisanNP-hardproblem，whichmakesitbecomeanimportantresearchdirectiontouseintelligentopti