Evolutionary Algorithms for Resource Constrained Project Scheduling

Abstract

Resource constrained project scheduling problems (RCPSPs) are well-known NP hard combinatorial problems. Due to the drawbacks of existing solution approaches, many researchers have proposed different evolutionary algorithms (EAs) for solving them. Although EAs are able to achieve near-optimal solutions, they cannot guarantee optimality and, in fact, no single EA has consistently been able to solve all types of problems. This has led to the emergence of hybrid methods which have shown good performances but their search capabilities for solving RCPSPs have not yet been fully explored. In this thesis, to efficiently solve RCPSPs, an algorithmic framework involving multiple methodologies is introduced. Firstly, a memetic algorithm (MA) consisting of a new heuristic for converting infeasible solutions to feasible ones in the initial population and multiple local search (MLS) strategies for increasing the exploitation capability of the algorithm is proposed. Secondly, an improved differential evolution (DE) algorithm containing new search operators that can guarantee the generation of feasible solutions, even from infeasible ones, is introduced. Finally, motivated by the encouraging performances of the proposed MA and DE, a bi-evolutionary algorithm (bi-EA) that utilizes the good search features of both these algorithms by automatically switching between them according to their performance, which implies placing more emphasis on the best-performing one during the evolutionary process, is proposed. In addition, two heuristic approaches developed to guide the solutions in both the initial population and every generation towards feasibility are adopted. All the algorithms proposed in this thesis are tested on a set of well-known project scheduling problems taken from the PSPLIB, with the results for instances of 30, 60, 90 and 120 activities compared with both each other and state-of-the-art algorithms. It is found that: (1) the heuristic method improves the performance of the traditional GA by 80.66% in terms of quality of solutions; (2) the use of MLS techniques leads to much better solutions (11.83%) and saves 20.21% of the GA’s computational time; (3) adopting the heuristic method in DE improves the quality of solutions by 28.96% and saves 10.62% of CPU time; (4) the improved DE operators provide much better solutions and greater savings in computational time than a traditional one; (5) bi-EA outperforms both MA and DE in terms of solution quality, especially for large-scale problems as, on average, it obtains 4.33% and 3.5% higher-quality solutions than MA and DE, respectively, and also provides competitive solutions compared with those from state-of-the-art-algorithms.