Title: A differential evolution-based memetic algorithm for project scheduling problems

Authors: Xiaoning Shen; Min Zhang

Addresses: B-DAT, CICAEET, School of Information and Control, Nanjing University of Information Science and Technology, Nanjing, 210044, China ' B-DAT, CICAEET, School of Information and Control, Nanjing University of Information Science and Technology, Nanjing, 210044, China

Abstract: A differential evolution (DE)-based memetic algorithm (MA) for solving the project scheduling problem (PSP) is proposed. In order to balance the abilities of exploration and exploitation, the proposed DE-based MA (DEMA) combines the DE-based global search with a problem-specific local search operator. In particular, DEMA applies evolutionary search schemes of DE to explore the large search space, where an improved mutation strategy that both uses vector differences for perturbation and learns from the current best solution is adopted. Besides, to make DE suitable for solving PSP which is a combinational optimisation problem, a slackness method is designed to convert between discrete dedications in PSP and continuous vectors in DE. On the other hand, a local search with two neighbourhood structures is utilised to exploit the local information around current solutions so that the solution quality can be further improved. Simulation results on real-world PSP instances validate the superiority of DEMA over state-of-the-art search-based approaches and the effectiveness of new mechanisms designed in DEMA.

Keywords: differential evolution; memetic algorithms; local search; software projects; project scheduling; exploration; exploitation; combinational optimisation; slackness; simulation.

DOI: 10.1504/IJICA.2015.072987

International Journal of Innovative Computing and Applications, 2015 Vol.6 No.3/4, pp.229 - 239

Received: 28 Oct 2014
Accepted: 26 Apr 2015
Published online: 11 Nov 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article