Genetic Algorithm for Singular Resource Constrained Project Scheduling Problems

Abstract

The Resource-Constrained Project Scheduling Problem (RCPSP) is a challenging optimization problem. In RCPSPs, it is very common to consider homogeneous activities, which means all activities require all types of resources. In practice, the activities are often singular because they usually require one single resource to execute an activity. The existing algorithms may be used for solving this variant of RCPSPs with a simple modification. However, they are computationally expensive due to unnecessary resource constraints. In this paper, we propose a customised evolutionary algorithm integrated with three heuristics for the singular activities. The first heuristic is based on the earliest start time with an aim to rectify an infeasible schedule. The second heuristic is based on neighbourhood swapping which is used to find the best possible alternatives. The third heuristic is used to further enhance the quality of the schedule. The performance of the proposed framework has been tested by solving a wide range of benchmark problems and the obtained results revealed that the proposed approach outperformed the existing algorithms. In addition, statistical and parametric testing show the value and characteristics of the proposed approach.

Keywords

• Resource-Constrained Project Scheduling
• singular activities
• genetic algorithm
• neighbourhood swapping
• forward-backward improvement