Priority-based heuristics for the multi-skill resource constrained project scheduling problem

• The proposed heuristic achieves near-optimal solutions in different sized instances.
• The heuristic is based on the well-known parallel scheduling scheme (RCPSP).
• Two new concepts were introduced to cope with the existence of multi-skilled resources.
• The heuristic outperforms a commercial solver both in time and solution quality.

In this paper we investigate one of the most recent extensions of the Resource Constrained Project Scheduling Problem (RCPSP): the Multi-Skill Resource Constrained Project Scheduling Problem (MSRCPSP). For this complex problem we propose the use of a parallel scheduling scheme. Such scheme has been successfully applied to the RCPSP. Nevertheless, in order to apply it to the MSRCPSP two new concepts are developed: resource weight and activity grouping. We discuss such concepts and use them for the new heuristic framework proposed. A series of computational tests performed using a large number of instances and reported in this paper shows that the new heuristic is very effective in finding high quality solutions within very small CPU times.