Integrated Column Generation and Lagrangian Relaxation Approach for the Multi-Skill Project Scheduling Problem

TitreIntegrated Column Generation and Lagrangian Relaxation Approach for the Multi-Skill Project Scheduling Problem
Type de publicationChapitre d'ouvrage
Année de publication2015
Titre de l'ouvrageHandbook on Project Management and Scheduling
Volume1
Numéro de section26
Pagination565-586
Type de documentOS chap
Auteur(s)Montoya, C., Bellenguez-Morineau O., Pinson E. et Rivreau D.
Directeur(s)Schwindt, C. et Zimmermann J.
EditeurSpringer International Publishing
Numéro ISBN978-3-319-05442-1
Mots-clésColumn Generation, Lagrangian relaxation, Multi-skilled personnel, Project scheduling, Project staffing, Resource constraints
Résumé

This chapter introduces a procedure to solve the Multi-Skill Project Scheduling Problem. The problem combines both the classical Resource-Constrained Project Scheduling Problem and the multi-purpose machine model. The aim is to find a schedule that minimizes the completion time (makespan) of a project composed of a set of activities. Precedence relations and resources constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Practical applications include the construction of buildings, as well as production and software development planning. We present an approach that integrates the utilization of Lagrangian relaxation and column generation for obtaining strong makespan lower bounds. Finally, we present the corresponding obtained results.

URLhttp://okina.univ-angers.fr/publications/ua7519
DOI10.1007/978-3-319-05443-8_26