Multi-operator immune genetic algorithm for project scheduling with discounted cash flows

The resource constrained project scheduling problem with discounted cash flows (RCPSPDC) is one of the most challenging problems owing to its NP-hard characteristics. This complex combinatorial optimization problem is most relevant to project management, building and construction management, and production planning. Although several solution methods have been suggested to solve the RCPSPDC, no single method has been shown to be the best for a wide range of problems. In this study, a multi-operator immune genetic algorithm, called MO-IGA, is proposed which integrates a genetic algorithm (GA) and an immune algorithm (IA) to solve the RCPSPDC. Two different operators for each crossover, mutation, immunization, and local search operation are utilized dynamically in the MO-IGA framework. Variable insertion neighborhood search (VINS) and forward-backward improvement (FBI) are utilized for local search to enrich the searching behavior and exploration. The algorithm starts with the same probability for each crossover, mutation, immunization, and local search operator; however, the probability is updated dynamically depending on the success of each operator in producing the quality solution. An activity move rule (AMR) has been utilized to delay the task with negative cash flows as much as possible, which further improves the overall project's net present value (NPV). A standard benchmark dataset, comprising 17,280 project instances ranging from 25 to 100 activities, is used to test the performance and effectiveness of the proposed MO-IGA. The proposed MO-IGA outperforms several datasets based on both a lower value of the average percentage deviation and the number of feasible schedule generations. The proposed MO-IGA is also shown to be more effective than the multi-operator GA (MO-GA) and multi-operator IA (MO-IA). Extensive numerical analysis, statistical tests, and comparisons with state-of-the-art algorithms proves the effectiveness of the proposed approach.

Automated summary

This study proposes a multi-operator immune genetic algorithm (MO-IGA) to solve the resource constrained project scheduling problem with discounted cash flows (RCPSPDC). The MO-IGA integrates a genetic algorithm and an immune algorithm, and utilizes dynamic operators and local search strategies to optimize the solution quality. Experimental results demonstrate the superiority of the proposed MO-IGA over other methods in terms of performance metrics.