基于改进NSGA-II算法求解多目标资源受限项目调度问题

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

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

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.