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

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

0.00 Avg rating0 Votes
Article ID: iaor2014857
Volume: 8
Issue: 5
Start Page Number: 1721
End Page Number: 1734
Publication Date: Jun 2014
Journal: Optimization Letters
Authors: , , ,
Keywords: combinatorial optimization, project management
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.