A multi-objective approach for a project scheduling problem with due dates and temporal constraints infeasibilities

Abstract

In this paper, we study a multi-mode resource-constrained project scheduling problem (RCPSP) which considers time and work generalised precedence relationships with minimal and maximal time lags and due dates where each activity requires only one unit of resource (e.g. a worker, a machine, etc.). To find a feasible solution for this problem is NP-hard and therefore for instances where a feasible solution has not been found, an appropriate real-life approach would consist of providing the decision-maker with a collection of quality solutions with a trade-off between due dates and temporal constraints violations. We propose a multi-objective evolutionary algorithm for the generation of an approximation to the optimal Pareto front with the objectives of minimising the project tardiness, and the time and work precedence relationships infeasibilities. The algorithm is basically a genetic algorithm with a multi-objective management of the evolution and is complemented by several local searches. Local Searches are based on justification of strong components. In the literature, this methodology has been previously used successfully with activities, but never with strong components. Computational experiments have been carried out to test the relative efficiency of different versions of the algorithm.

Keywords:

• multi-mode project scheduling
• multi-objective optimisation
• evolutionary algorithms
• generalised precedence relationships
• due dates

Funding

This research was partially supported by the Ministerio de Educación y Ciencia under contract DPI2007-63100 and Ministerio de Ciencia e Innovación under contract MTM2011-23546.