Solving a real-life multi-skill resource-constrained multi-project scheduling problem

Abstract

This paper addresses a multi-skill resource-constrained multi-project scheduling problem (MSRCMPSP) with different types of resources and complex industrial constraints, which originates from SNCF heavy maintenance factories. Two objective functions, that have been rarely addressed in the literature, are independently considered: (i) Minimization of the sum of the weighted tardiness of the projects and (ii) Minimization of the sum of the weighted duration of the projects. A time-indexed mixed-integer linear programming model is presented with both resource assignment and capacity constraints. To solve large instances with several thousand activities, a new memetic algorithm combining a novel hybrid simulated genetic algorithm with a simulated annealing is implemented. The memetic algorithm is compared with popular solution approaches. Computational experiments conducted on real instances and benchmark instances validate the efficiency of the proposed algorithm.