Modeling frameworks for the multi-skill resource-constrained project scheduling problem: a theoretical and empirical comparison

摘要

In this paper, we study and compare several integer and mixed-integer linear programming formulations for the multi-skill resource-constrained project scheduling problem. This is a problem characterized by a set of activities to be executed that in addition to the usual precedence constraints require several resources for each skill needed for their execution. A set of multi-skill resources is assumed. The objective is to minimize the project's makespan.We revisit two existing models for the problem and propose two newones. Additionally,we perform a theoretical comparison between the lower bounds provided by the linear programming relaxations of the models. Furthermore, a numerical experiment is performed on a set of instances from the literature to evaluate the suitability of an off-the-shelf solver to compute optimal solutions and lower bounds to the studied problem, using the aforementioned models.