A MILP Formulation for the Pre-emptive Flexible-Mode Multi-skilled Resource-Constrained Project Scheduling Problem

This paper presents a mixed integer linear programming (MILP) formulation with time indexed variables for a generalized form of the resource-constrained project scheduling problem (RCPSP) with the makespan objective. The form of the RCPSP introduced in this paper is the Pre-emptive Flexible-Mode Multi-Skilled Resource-Constrained Project Scheduling Problem (P-FM-MS-RCPSP). The proposed MILP formulation captures the pre-emptive nature of the scheduling problem, allowing tasks to be interrupted and resumed based on resource availability. Additionally, tasks can be executed in multiple modes, where each mode represents a different method of performing the task, each requiring distinct sets of resources and with corresponding distinct sets of durations, reducing resource idle times and maximizing their utilization via a flexible resource profile. Furthermore, the formulation also considers the use of multi-skilled resources, where a set of categorical skills are required to perform project activities with resources that master more than one skill. The RCPSP is a NP hard problem, and since the P-FM-MS-RCPSP is a generalized form of the RCPSP, the P-FM-MS-RCPSP is also NP hard. The effectiveness of the proposed MILP formulation is verified through computational experiments on empirical benchmark instances of the MS-RCPSP and comparison with existing solution approaches.