Title: Efficient parallel evolutionary algorithms for deadline-constrained scheduling in project management

Authors: Sergio Nesmachnow

Addresses: Universidad de la República, Herrera y Reissig 565, Montevideo, 11300, Uruguay

Abstract: Deadline-constrained scheduling in project management is a NP-hard optimisation problem with major relevance in software engineering and other real-life situations dealing with the planning of activities that must be completed before specific dates. This article introduces efficient parallel versions for two evolutionary algorithms (genetic algorithm and hybrid evolutionary algorithm), to solve the deadline-constrained scheduling problem in project management. The proposed algorithms have been engineered to compute accurate solutions in reduced execution times. Specific evolutionary operators, including a parallel local search operator in the hybrid evolutionary algorithm, are proposed for efficiently solving realistic problem instances, and both a master-slave parallel strategy and a distributed subpopulation model are applied to further improve the computational efficiency and the results quality. The experimental analysis performed on both a set of standard problem instances and new large problem instances demonstrate that accurate solutions are computed by the proposed techniques, especially for the distributed subpopulation version of the hybrid evolutionary algorithm. The comparative experimental evaluation demonstrates that the parallel evolutionary algorithms are able to outperform in reduced execution times the results computed using one of the best well-known deterministic techniques for the problem, in particular when solving instances with tight deadline constraints.

Keywords: parallel evolutionary algorithms; scheduling; project management; deadline constraints; NP-hard optimisation; deadlines; genetic algorithms; local search.

DOI: 10.1504/IJICA.2016.075468

International Journal of Innovative Computing and Applications, 2016 Vol.7 No.1, pp.34 - 49

Received: 08 Sep 2015
Accepted: 15 Sep 2015
Published online: 23 Mar 2016 *

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