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

作者：Perez Angeles^*; Quintanilla Sacramento; Lino Pilar; Valls Vicente

来源：International Journal of Production Research, 2014, 52(13): 3950-3965.

DOI：10.1080/00207543.2014.923120

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

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.

• 出版日期2014