Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems

Project scheduling is an inherently multi-objective problem, since managers want to finish projects as soon as possible with the minimum cost and the maximum quality. However, there are only a few papers dealing with multiobjective resource-constrained project scheduling problems (MORCPSPs). Moreover, there is no theoretical study in the literature that establishes the fundamentals for correct algorithmic developments. In this paper we try to close the gap by proving several results for MORCPSPs. With these results as a basis, both exact and heuristic procedures capable of obtaining a set of efficient solutions for several important MORCPSPs can be created. We develop algorithms for the case where all objective functions are of the same type, called regular. In this case, specific codifications, techniques, and procedures can be used. Extensive computational results help decide which algorithms or techniques are the most promising for the problem. With the aid of these algorithms we study the Pareto fronts in this case. Finally, we apply a metaheuristic algorithm to a particular example of the general case in order to analyse the differences in the Pareto fronts. The project instances and Pareto fronts obtained can be downloaded from a website to facilitate comparisons with future research efforts. (C) 2010 Elsevier Ltd. All rights reserved.