Memetic algorithm for multi-mode resource-constrained project scheduling problems

A memetic algorithm(MA) for a multi-mode resourceconstrained project scheduling problem(MRCPSP) is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called 'strategic oscillation' to make the search process have a higher probability to visit solutions around a 'feasible boundary'. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.