基于改进NSGA-II算法求解多目标资源受限项目调度问题
CSTR:
作者:
作者单位:

(武汉大学计算机学院,武汉430072)

作者简介:

通讯作者:

E-mail: fengwang@whu.edu.cn.

中图分类号:

TP18

基金项目:

国家自然科学基金面上项目(61773296);国家重点研发计划项目(2017YFC1502902).


An improved NSGA-II algorithm for multi-objective resource-constrained project scheduling problem
Author:
Affiliation:

(School of Computer Science,Wuhan University,Wuhan430072,China)

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    资源受限项目调度问题(resource constrained project scheduling problem,RCPSP)要求在满足相关约束的条件下安排各活动开始时间,从而达到某一目标的最优,具有很强的应用背景,并受到众多学者的广泛关注.经典的RCPSP模型以最小化项目工期为单一目标,忽略了资源使用率等因素对项目整体的影响,使其与实际应用仍有较大差距.基于经典的RCPSP模型,引入最优资源均衡为另一目标,将模型扩展为多目标模型,丰富了RCPSP模型的应用场景.同时,考虑到新模型中各活动间存在大量的控制关系,使用传统的启发式多目标算法需要耗费大量的时间对不可行解进行判断,求解性能较低,提出一种新的算法框架NSGA-IIs.该算法框架基于活动间控制关系将各活动分成若干子集,并在初始化和交叉变异等阶段以子集为基本单位产生新的个体,能够较好地避免不可行解的产生,提高算法的效率.使用解集覆盖度作为评价指标,通过实例数据集的实验表明,与已有的求解RCPSP的经典算法相比,所提出的算法具有明显的优越性.

    Abstract:

    The resource constrained project scheduling problem(RCPSP) requires that the starting time of each activity should be scheduled so as to achieve an optimal target under the condition of satisfying the relevant constraints. It has attracted many researchers’ attention and has been applied to many research fields. The classical RCPSP model only focuses on the minimization of project duration time and ignores the impact of other factors on the overall project, which is not suitable for real applications. Based on the classical RCPSP model, this paper introduces a multi-objective model by exploring the optimal resource equalization as the optimization objective, which can enrich the application scenario of RCPSP models. Due to the large number of control relationships between activities in the proposed new model, it takes a lot of time to evaluate the infeasible solutions by using traditional heuristic multi-objective algorithms. In order to improve the efficiency of the algorithm, this paper proposes a new algorithm known as NSGA-IIs. The NSGA-IIs algorithm divides each activity into several subsets based on the control relationship between activities and generates new individuals based on subsets in the initialization and crossover mutation stages, which can avoid the generation of infeasible solutions and improve the performance of the algorithm effectively. The set coverage measure is employed as a performance indicator, and the experimental results show that the proposed algorithm outperforms the classical RCPSP algorithms.

    参考文献
    相似文献
    引证文献
引用本文

王峰,韩孟臣臣,赵耀宇,等.基于改进NSGA-II算法求解多目标资源受限项目调度问题[J].控制与决策,2021,36(3):669-676

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2021-03-01
  • 出版日期: 2021-03-20
文章二维码