Branch-and-price approach for the multi-skill project scheduling problem

TitreBranch-and-price approach for the multi-skill project scheduling problem
Type de publicationArticle de revue
AuteurMontoya, Carlos , Bellenguez-Morineau, Odile , Pinson, Eric , Rivreau, David
EditeurSpringer Verlag
TypeArticle scientifique dans une revue à comité de lecture
Année2014
LangueAnglais
Pagination1721-1734
Volume8
Section5
Titre de la revueOptimization Letters
ISSN1862-4472
Résumé en anglais

This work introduces a procedure to solve the multi-skill project scheduling problem (MSPSP) (Néron and Baptista, International symposium on combinatorial, optimization (CO’2002), 2002). The MSPSP mixes 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. In addition, 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 a column generation approach embedded within a branch-and-price (B&P) procedure that considers a given activity and time-based decomposition approach. Obtained results show that the proposed B&P procedure is able to reach optimal solutions for several small and medium sized instances in an acceptable computational time. Furthermore, some previously open instances were optimally solved.

URL de la noticehttp://okina.univ-angers.fr/publications/ua6523
DOI10.1007/s11590-013-0692-8