资源受限项目调度问题编码分析及进化优化

来源 :西安电子科技大学 | 被引量 : 0次 | 上传用户:greenwin
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
资源受限项目调度问题(Resource-Constrained Project Scheduling Problems,RCPSPs)是一类重要的调度问题,它要求在满足项目优先关系约束和资源约束的条件下,安排所有任务的开始时间和结束时间,以达到某一目标的最优化,例如项目的总工期最短,项目的总资源成本最小,项目的鲁棒性最强或项目的资源均衡使用等。该问题广泛地存在于软件开发、建筑工程、飞机及轮船制造等企业中。RCPSPs不仅在实践中应用广泛,在理论上,该问题模型丰富,而且多属于NP-hard问题,许多组合优化问题都是RCPSPs的特例,例如作业车间调度,军事调度或车辆调度等。因此研究RCPSPs具有重要的实践和理论意义,本文主要研究内容如下:1.分析了RCPSPs的五种不同的编码方式,采用研究适应度景观的一种统计方法——适应度距离相关系数(Fitness Distance Correlation, FDC)来分析采用不同编码方式的进化算法解决RCPSPs的性能差异。2.提出了一种基于多智能体进化算法的资源受限项目调度方法。与传统遗传算法中种群的模型相比,智能体网格的模型更接近于真正的自然进化机制,能够得到更好的调度方案。实验部分对标准问题库Patterson set,J30,J60和J120进行了测试,并且与一种已有进化算法进行了比较分析。实验结果表明该算法在评定求解资源受限项目调度问题方法效用的两个方面(求得最优解的比例和偏离最优解的平均偏差)都有优势。3.设计了一种不确定情况下多模态资源投资问题(Multi-Mode ResourceInvestment Problems, MMRIPs)的风险评估方法,把最小化风险水平作为该问题除最小化项目工期和最小化项目资源成本的又一目标。实验部分采用三种多目标进化算法对多模态实例集J10,J16和J30进行了测试,并且对这三种算法进行了比较分析。实验结果表明该风险评估方法能有效的对不确定情况下多模态资源投资问题进行鲁棒性分析。
其他文献
学位