An Immune Genetic Algorithm for Solving NPV-Based Resource Constrained Project Scheduling Problem
Open Access
- 5 February 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 9, 26177-26195
Abstract
The net present value (NPV)-based resource constrained project scheduling problem (RCPSP) is a well-known scheduling problem in many industries, such as construction, software development, and manufacturing. Over the last five decades, although different approaches have been proposed to solve the problem, no single approach has been shown to achieve satisfactory performances with quality solutions for a wide range of problems. This study presents a hybrid immune genetic algorithm (IGA) to solve NPV-based RCPSPs. Hybridizing a genetic algorithm (GA) with an immune algorithm (IA) enhances the overall performance of their standalone components (i.e., only GA or IA). Performance of the proposed IGA is further improved by applying a variable insertion based local search (VINS) and forward-backward improvement (FBI). A restart mechanism is presented to the algorithm which induces diversity and helps to avoid becoming trapped in local optima. Moreover, an activity move rule (AMR) is implemented to shift the negative cash flow associated activities to further improve the NPV. Taguchi Design of Experiment (DOE) is conducted to investigate the impact of various parameters and to determine the appropriate set of parameters for the proposed IGA. The performances of the proposed algorithms are tested on 17,280 standard benchmark instances ranging from 25 to 100 activities. Comparison with the state-of-art algorithms through extensive numerical experiments reveal the effectiveness of the proposed algorithms. Overall, the proposed algorithm outperforms existing algorithms, particularly the projects with 0% and 100% negative cash flow associated activities, the 75-activity instances, and the projects with two resources usage in terms of a lower value of average percentage deviation.Keywords
This publication has 96 references indexed in Scilit:
- A Danger‐Theory‐Based Immune Network Optimization AlgorithmThe Scientific World Journal, 2013
- An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problemComputers & Operations Research, 2012
- Minimizing the total completion time in a two-machine flowshop with sequence-independent setup timesJournal of the Operational Research Society, 2012
- A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flowsInternational Journal of Production Research, 2009
- A novel genetic algorithm based on immunityIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2000
- Using discounted cash flow heuristics to improve project net present valveJournal of Operations Management, 1996
- The resource constrained time/cost tradeoff project scheduling problem with discounted cash flowsJournal of Operations Management, 1996
- Relative Power of the Wilcoxon Test, the Friedman Test, and Repeated-Measures ANOVA on RanksThe Journal of Experimental Education, 1993
- USING A LATE‐START RESOURCE‐CONSTRAINED PROJECT SCHEDULE TO IMPROVE PROJECT NET PRESENT VALUE*Decision Sciences, 1987
- A generalized Wilcoxon test for comparing arbitrarily singly-censored samplesBiometrika, 1965