Hybrid evolutionary algorithm for large-scale project scheduling problems. (August 2020) - Zaman, Forhad; Elsayed, Saber; Sarker, Ruhul; Essam, Daryl
Highlights: Proposed a new evolutionary framework for a wide range of project scheduling problems. Introduced two heuristics to rectify any infeasible schedule. Proposed a new classification technique to determine the hardness of a problem. For complex problems, a local search is developed to fine-tune the best solution. The proposed algorithm is superior to existing algorithms. Abstract: The Multi-Mode Resource Constrained Project Scheduling Problem (MMRCPSP) is a challenging NP-hard optimization problem, that schedules activities under a set of resource constraints. Although, over the last few decades, different solution approaches have been proposed, no single algorithm has consistently been the best for a wide range of MMRCPSPs. In this paper, we have proposed an effective hybrid algorithm, in which two multi-operator evolutionary algorithms perform sequentially under two sub-populations, with their sizes dynamically adapted based on their performance during the evolutionary process. In addition, two heuristics are proposed, the first one is based on a linear programming approach with an aim to obtain feasible modes, while the second one is based on a modified forward and backward justification approach with an aim of obtaining feasible schedules. Also, a classification technique is used to determine the complexity of a given problem, based on its resource's availability. The proposed approach is tested by solving a wide-range of multi-mode resource-constrained project scheduling problems, including available larger test problems, with the results revealing that the proposed method outperforms well-known algorithms.