Memetic algorithm for solving resource constrained project scheduling problems.

The resource constrained project scheduling problem (RCPSP) has a wide variety of practical applications in construction, manufacturing, project planning, and other areas. Since the 1960s many optimization algorithms have been proposed to solve this NP-hard problem, and their performances are evaluated in well-known test problems with different complexities. Although it is desirable to find an algorithm which can provide promising solutions with reasonable computational efforts for any problem under consideration, no single algorithm can meet that condition. To deal with this challenge, we present a genetic algorithm based memetic algorithm (MA) for solving RCPSP. The algorithm is initiated by a critical path-based heuristic and a variant of the Nawaz, Enscore, and Ham (NEH) heuristic. The algorithm involves a similar block order crossover and a variable insertion based local search. An automatic restart scheme is also presented which assists the algorithm to escape from local optima. In addition, a design-of-experiment (DOE) method is used to determine the set of suitable parameters for the proposed MA. Numerical results, statistical analysis and comparisons with state-of-the-art algorithms demonstrate the effectiveness of the proposed approach. • This paper developed a Genetic algorithm based Memetic Algorithm (MA) for solving classical RCPSPs. • This work proposed an effective heuristic to initialize MA. • Our proposed algorithm was evolved by effective crossover and mutation operators, local search and a restart scheme. • The proposed MA outperformed many state-of-the-art algorithms in PSPLIB and RG benchmarks. • The proposed algorithm showed promising performance in solving practical problems. [ABSTRACT FROM AUTHOR]