A Two-Stage Repair Strategy Based Evolutionary Algorithm for Solving Resource-Constrained Project Scheduling Problems

The Resource-Constrained Project Scheduling Problems (RCPSPs) are considered highly challenging NP-hard problems in the field of project management. The complexity of this type of problems lies in the limited availability of resources and the interdependence of tasks, making it very difficult to find a solution that satisfies all constraints while optimizing objectives using random search paradigms. To address this issue, this paper proposes a novel evolutionary algorithm that employs a two-stage repair strategy to enhance its constraint satisfaction ability in solving large-scale RCPSPs. The first stage of the heuristic strategy aims to quickly identify and repair solutions that violate time constraints, thereby rapidly reducing the number of infeasible solutions in the search space. The second stage applies more refined heuristic rules to further optimize solutions that violate resource constraints, in hopes of finding solutions closer to the global optimum. The design of this two-stage repair strategy increases the likelihood of finding high-quality solutions in complex search spaces. To validate the effectiveness of the proposed algorithm, this paper conducted extensive experiments on nine real-world datasets. Compared with existing advanced evolutionary algorithms, the experimental results demonstrate that the proposed algorithm has excellent performance.