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

发布时间：2017-09-28 12:38

  本文关键词：抢占式资源受限项目调度问题的多Agent优化方法

  更多相关文章： 项目调度 抢占 多Agent优化 粒子群优化 蚁群优化 峰交叉算子

【摘要】：本文的研究对象是资源受限项目调度问题的一个扩展问题,“允许最多一次抢占的抢占式资源受限项目调度问题”,即1_PRCPSP。实际项目中的某些活动会因为资源没及时到位、或者需要优先满足其他活动的需要而被迫暂时终止；但出于控制进度偏差的需要,这种暂时终止不会被允许过多地存在。这是抢占式资源受限项目调度问题(PRCPSP)生的背景。1_PRCPSP是PRCPSP的特例,其中的每项活动至多只允许被抢占一次。 与RCPSP一样,1_PRCPSP是一个典型的NP-难问题,利用智能优化方法求解该问题是重要的研究方向。我们在前人已有研究的基础上,从多Agent优化方法的角度探寻该问题的求解方式。具体而言,研究方法包括粒子群优化方法(PSO)、蚁群优化方法(ACO)和多Agent优化方法(MAO)三种,其中PSO和ACO属于群智能优化方法,也都是MAO的一种。 PSO首先被用于问题求解,相应的算法为1PRCPSP_PSO。我们设计了基于活动列表的编码、基于优先权值的编码、基于活动列表和抢占点的编码,以及基于优先权值和抢占点的编码四种编码方式,采用串行进度生成机制(SSGS)和允许一次抢占的串行进度生成机制(1_SSGS)来解码,结合峰交叉算子(PX)的思想设计了相应的粒子更新机制。在PSPLIB中的RCPSP数据集上的计算实验显示,1PRCPSP_PSO不仅具有很好的收敛性,而且能求得具有竞争性的结果。 其次,我们将ACO应用于1_PRCPSP的求解中,设计了1PRCPSP_ACO。该算法同样借鉴了峰交叉算子的思想,设计了峰路径信息素增强机制,针对当前代最好的解的峰,施加一个额外的信息素增强操作。算法采用1_SSGS将蚂蚁走过的路径转化为问题的可行调度。同样的,我们使用PSPLIB中的RCPSP数据集对算法的收敛性和求解效果作了评估。 最后,我们设计了一种1PRCPSP_MAS体系及相应的优化方法1PRCPSP_MAO。1PRCPSP_MAS体系包含两类Agent:负责项目资源请求与活动执行的活动Agent,以及负责资源分配和项目调度的调度Agent。活动Agent与调度Agent之间通过协商机制完成资源分配和项目调度；通过一种迭代改进机制来实现问题解的优化。与前两类不同的是,1 PRCPSP MAO同时具有仿真和优化两种特征。Agent之间的协商机制,旨在模拟实际项目运作中经常发生的负责人或部门之间通过沟通解决冲突或改变项目计划的情形；而迭代改进机制则使得算法具有优化问题解的功能。 本文的成果具有理论和实践意义,丰富了抢占式资源受限项目调度问题的研究方式,拓展了粒子群优化方法、蚁群优化方法和多Agent优化方法的应用领域；所设计的多Agent系统可以用于项目进度管理决策中,为项目计划制定阶段的项目整体评估提供了一种基于MAS的仿真优化方法。
【关键词】：项目调度 抢占 多Agent优化 粒子群优化 蚁群优化 峰交叉算子
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：F062.4;F224
【目录】：

• 致谢4-6
• 摘要6-8
• Abstract8-10
• 目录10-13
• 图目录13-15
• 表目录15-16
• 1 绪论16-28
• 1.1 研究背景和意义17-23
• 1.2 研究问题的提出23-24
• 1.3 研究框架与论文组织24-26
• 1.4 本章小结26-28
• 2 抢占式资源受限项目调度问题28-52
• 2.1 文献综述28-34
• 2.1.1 RCPSP28-32
• 2.1.2 PRCPSP32-34
• 2.2 模型描述34-39
• 2.3 算法概述39-50
• 2.3.1 重要概念39-41
• 2.3.2 串行进度生成机制41-46
• 2.3.3 双向调整技术46-47
• 2.3.4 允许一次抢占的串行进度生成机制47-48
• 2.3.5 峰交叉算子48-50
• 2.4 本章小结50-52
• 3 多AGENT优化方法52-80
• 3.1 群智能优化方法52-53
• 3.2 粒子群优化方法53-59
• 3.2.1 产生与发展53-55
• 3.2.2 算法流程55-57
• 3.2.3 在项目调度问题上的应用57-59
• 3.3 蚁群优化方法59-67
• 3.3.1 产生与发展59-64
• 3.3.2 算法流程64
• 3.3.3 在调度问题上的应用64-67
• 3.4 多AGENT优化方法67-78
• 3.4.1 产生与发展67-71
• 3.4.2 体系结构71-77
• 3.4.3 开发工具77-78
• 3.5 本章小结78-80
• 4 抢占式资源受限项目调度问题的粒子群优化方法80-96
• 4.1 算法描述80-87
• 4.1.1 粒子编码80-83
• 4.1.2 粒子解码83-84
• 4.1.3 适应值函数84
• 4.1.4 粒子更新机制84-86
• 4.1.5 总体流程86-87
• 4.2 计算实验87-94
• 4.2.1 实验环境87
• 4.2.2 参数设置87-88
• 4.2.3 实验结果88-94
• 4.3 本章小结94-96
• 5 抢占式资源受限项目调度问题的蚁群优化方法96-106
• 5.1 算法描述96-99
• 5.1.1 路径构建方案96-97
• 5.1.2 信息素信息更新机制97
• 5.1.3 启发式信息97-98
• 5.1.4 适应值函数98
• 5.1.5 总体流程98-99
• 5.2 计算实验99-104
• 5.2.1 实验环境99
• 5.2.2 参数设置99-100
• 5.2.3 实验结果100-104
• 5.3 本章小结104-106
• 6 抢占式资源受限项目调度问题的多AGENT优化方法106-126
• 6.1 系统描述106-112
• 6.1.1 系统纵览106-108
• 6.1.2 协商模型108-109
• 6.1.3 调度Agent109-111
• 6.1.4 活动Agent111-112
• 6.2 计算实例112-123
• 6.3 计算实验123-125
• 6.3.1 实验环境123-124
• 6.3.2 实验结果124-125
• 6.4 本章小结125-126
• 7 进一步讨论126-132
• 7.1 三种MAO的比较126-130
• 7.1.1 四种Agent特征对比126-127
• 7.1.2 三种MAO效果对比127-130
• 7.2 管理实践意义130-131
• 7.3 本章小结131-132
• 8 总结与展望132-134
• 参考文献134-144
• 附录1 名词中英文对照144-150
• 附录2 PSPLIB中的RCPSP问题实例150-154
• 作者简历及在学期间所取得主要科研成果154

【共引文献】

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

1 伍京华;蒋国瑞;黄梯云;;一种基于Agent的辩论谈判中的反驳模型[J];北京工业大学学报;2007年09期

2 胡德明;;优化岩土工程勘察的探讨[J];才智;2008年13期

3 孙丹丹;苗建松;王朝翔;丁炜;;Ad Hoc网络中基于蚁群优化的路由选择算法[J];吉林大学学报(信息科学版);2007年06期

4 刘琼,杨红杰,汪永琳;Agent与基于Agent系统[J];常德师范学院学报(自然科学版);2000年01期

5 付晓;于振华;刘宇;;一种无线传感器网络形式化模型及应用研究[J];传感技术学报;2008年09期

6 杨栩;尤学一;季民;潘留明;王秀朵;赵乐军;;城市绿地土壤入渗模型及参数确定[J];城市环境与城市生态;2011年06期

7 亢孟军;王贝;杜清运;王明军;;上下文敏感的空间信息服务智能推送研究[J];测绘科学;2011年03期

8 葛继科;邱玉辉;阎艳;;基于BDI Agent的网格服务模型研究[J];重庆师范大学学报(自然科学版);2008年04期

9 曹凤雪;;多Agent系统中组织适应的形式化方法[J];江苏技术师范学院学报;2011年06期

10 李信满,赵宏;高速网络环境下的网络入侵检测系统[J];东北大学学报;2002年07期

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

1 薛宏涛;沈林成;;基于协进化方法的多智能体系统及其符号演绎理论模型[A];第二十六届中国控制会议论文集[C];2007年

2 严彬;熊伟清;程美英;叶青;;基于拥塞控制的多种群二元蚁群算法[A];第二十七届中国控制会议论文集[C];2008年

3 ;Particle Swarm Optimization of Periodic Deep Brain Stimulation Waveforms[A];中国自动化学会控制理论专业委员会A卷[C];2011年

4 张元敏;殷志锋;周雅;;蚁群算法在多用户检测中的应用及其改进[A];第十三届全国信号处理学术年会（CCSP-2007）论文集[C];2007年

5 杨俊杰;陈俊宏;;利用智能型代理人进行野外环境辐射监测之研究[A];第11届海峡两岸信息管理发展策略研讨会论文集[C];2005年

6 ;An estimation of distribution algorithm for resource-constrained project scheduling problem[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

7 ;Hybrid particle swarm optimization-simplex algorithm for inverse problem[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

8 ;Research on the Decision-making of Multi-issue/Attribute Negotiation Based on Agent Technology and the Genetic Algorithm[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

9 ;A Modified Glowworm Swarm Optimization for Multimodal Functions[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

10 蔡远利;于振华;王瑞峰;;多Agent系统形式化建模方法学[A];'2006系统仿真技术及其应用学术交流会论文集[C];2006年

中国博士学位论文全文数据库 前10条

1 汪澎;驾驶人警觉状态检测技术研究[D];江苏大学;2010年

2 应瑛;不确定资源约束下项目调度问题研究[D];浙江大学;2010年

3 许伟;基于进化算法的复杂化工过程智能建模方法及其应用[D];华东理工大学;2011年

4 傅朝阳;面向实时任务求解的自治服务协同模型、形式语义及其验证[D];浙江大学;2010年

5 李永卓;我国电力市场化进程中供应链管理研究[D];中国地质大学（北京）;2011年

6 王静;化肥供应链及其适应性研究[D];北京交通大学;2011年

7 贺利坚;多Agent系统中信任和信誉模型的研究[D];北京交通大学;2011年

8 田文迪;随机DTRTP环境下项目调度策略的比较研究[D];华中科技大学;2011年

9 彭飞;实值演化算法投资组合研究[D];中国科学技术大学;2011年

10 李玉剑;复杂系统中集体行为和临界现象的动力学研究[D];中国科学技术大学;2011年

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

1 郭凯;基于BDI的agent协商目标研究[D];郑州大学;2009年

2 蒋红进;蚁群算法在光突发交换网络路由中的研究[D];哈尔滨工程大学;2010年

3 周柏欣;无线Ad Hoc专用通信网络路由协议研究[D];哈尔滨工程大学;2010年

4 梁林娜;复杂多主体战略管控系统建模及应用研究[D];中国海洋大学;2010年

5 周绪倩;基于电子商务的Web数据挖掘系统架构研究[D];河北工程大学;2010年

6 吕海鹏;改进蚁群算法在YKK系列中型高压电机优化设计中的应用[D];哈尔滨理工大学;2010年

7 宋红星;多模式资源约束项目工期—成本优化问题研究[D];江南大学;2010年

8 温丽丹;Agent在HIS中的应用研究[D];长春工业大学;2010年

9 贾晓冬;Multi-Agent在建筑工程预算系统中的应用研究[D];长春工业大学;2010年

10 梁毅;粒子群算法搜索模式研究与应用[D];华东理工大学;2011年

，

本文编号：935903