Title: A random keys genetic algorithm for a bicriterion project selection and scheduling problem

Authors: Natalia Summerville; Reha Uzsoy; Juan Gaytán

Addresses: Advanced Analytics and Optimization Services Group, SAS Institute, 100 SAS Campus Drive, Cary, NC, 27513, USA ' Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University (NCSU), Campus Box 7906, Raleigh, NC 27695-7906, USA ' School of Engineering, Mexico State University, Cerro de Coatepec, Ciudad Universitaria, Toluca México, CP 50110, Mexico

Abstract: The project selection and scheduling problem involves the allocation of limited resources to competing projects over time to optimise a given objective function. However, in practical applications, multiple criteria need to be considered, leading us to formulate the problem as a multiple objective combinatorial optimisation (MOCO) model. Activities are subject to precedence constraints, as well as a budget limiting the capital available in each planning period. Interdependencies between projects by which the selection of specific subsets of projects may result in cost savings are also represented. We propose a genetic algorithm incorporating random keys and an efficient decoding procedure into the well-known NSGA-II procedure. The performance of this algorithm is evaluated in extensive computational experiments comparing the approximations of the Pareto-optimal set it obtains to those from NSGA-II.

Keywords: multicriteria optimisation; multiobjective optimisation; genetic algorithms; random keys; project scheduling; project selection; metaheuristics; NSGA-II; efficient frontier; evolutionary algorithms; resource allocation; precedence constraints; budget limits.

DOI: 10.1504/IJPS.2015.072105

International Journal of Planning and Scheduling, 2015 Vol.2 No.2, pp.110 - 133

Received: 22 Feb 2014
Accepted: 03 Feb 2015
Published online: 30 Sep 2015 *