A new algorithm for resource-constrained project scheduling with breadth and depth of skills

Abstract

This paper addresses a multi-skilled extension of the resource-constrained project scheduling problem (RCPSP). Although a handful of papers dealt with the multi-skilled RCPSP (MSRCPSP), little to no attention is given to the ideal levels of skills for multi-skilled resources. In this paper, skills are measured along two dimensions known as breadth and depth. In a project environment, the breadth of a resource is perceived as the amount of skills an employee masters. The depth of a skill is the efficiency level at which work can be performed by a resource that masters that skill. The MSRCPSP with breadth and depth consists of scheduling activities with skill requirements and assigning multi-skilled resources to those activities. To be able to efficiently solve the MSRCPSP, a genetic algorithm is developed. Using the created activity schedules and resources assignments, the best workforce characteristics are analysed. Key aspects in this analysis are the breadth and depth. The problem-specific procedure combines a new representation, a new crossover and tailor-made local searches. Computational experiments measure the impact of different multi-skilled resources and their efficiency levels on the makespan of the project.