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.