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

• Author: Francisco Saldanha‐da‐Gama,Bernardo F. Almeida,Isabel Correia
• DOI: http://doi.org/10.1111/itor.12568
• Date: 01 May 2019
• Published date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 946–967

DOI: 10.1111/itor.12568

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Modeling frameworks for the multi-skill resource-constrained

project scheduling problem: a theoretical

and empirical comparison

Bernardo F. Almeidaa,b, Isabel Correiacand Francisco Saldanha-da-Gamaa,b

aDepartamento de Estat´

ıstica e Investigac¸˜

ao Operacional, Faculdade de Ciˆ

encias da Universidade Lisboa,

1749-016 Lisboa, Portugal

bCentro de Matem´

atica, Aplicac¸˜

oes Fundamentais e Investigac¸˜

ao Operacional, Faculdade de Ciˆ

encias da Universidade

Lisboa, 1749-016 Lisboa, Portugal

cDepartamento de Matem´

atica/Centro de Matem´

atica e Aplicac¸˜

oes, Faculdade de Ciˆ

encias e Tecnologia, Universidade

Nova Lisboa, 2829-516 Caparica, Portugal

E-mail: bernardo.almeida@alunos.fc.ul.pt [Almeida]; isc@fct.unl.pt [Correia];

fsgama@ciencias.ulisboa.pt [Saldanha-da-Gama]

Received 2 July2017; received in revised form 23 May 2018; accepted 25 May 2018

Abstract

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 precedenceconstraints 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’smakespan. Werevisit two existing models for the problemand propose two new ones.Additionally, we

perform a theoretical comparison between the lower bounds provided by the linear programmingrelaxations

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.

Keywords:project scheduling; multi-skill resources; MILP models; continuous time; discrete time; lower bounds

1. Introduction

A resource-constrained projectscheduling problem (RCPSP) consists of scheduling a set of activities

and assigning resources to them in such a way that the makespan is minimized. The activities are

linked by precedencerelations and require specific amounts of each resource type for being executed.

The resources are limited and each resourcecan meet a single and specific requirement. This problem

and many of its variants have been extensively studied in the literature. For additional information,

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

B. F. Almeida et al. / Intl. Trans. in Op. Res.26 (2019) 946–967 947

the reader should refer to Brucker et al. (1999), Demeulemeester and Herroelen (2002), Hartmann

and Briskorn (2010), Weglarz et al. (2011), and to the references therein.

Among the research trends that we observe in the study of RCPSPs, mathematical programming-

based approaches have played an important role. In particular, researchers have studied differ-

ent types of integer and mixed-integer formulations that can be better tackled by a general

purpose solver. This is important for practitioners, who usually do not dominate more ad-

vanced optimization techniques and tools. For comprehensive reviews on mathematical formu-

lations for RCPSPs, the reader should refer to the works by Demassey (2008) and Kon´

eetal.

(2011).

The mathematical models developed in the context of project scheduling problems are usually

classified as discrete- or continuous-time models, according to how time is looked at. In discrete-

time models, often also referred to as time-indexedformulations, one looks at time as being discrete:

the planning horizon of interest is split into smaller portions, each of which representing a time

unit (day, week, and so on). This type of mathematical models is known for usually requiring a

large number of binary variables, each of which associated with some event that may occur at a

specific moment in time. The events are usually associated with the status of the activities: starting,

finishing, or in progress. The number of binary variables involved in this type of models renders

heavy mathematical programming formulations that easily become intractable if one wishes to solve

medium- or large-sized instances to optimality using an optimization solver. Nevertheless, these

formulations are known to yield sharper linear programming relaxation bounds. Some examples

of discrete-time models proposed in the context of RCPSPs can be found in Pritsker et al. (1969),

Christofides et al. (1987), and Mingozzi et al. (1998). Recently, Artigues (2017) analyzed the strength

of discrete-time formulations for the RCPSP.

Another type of model that has been proposed for RCPSPs leads to the so-called continuous-

time formulations that make use of continuous variables to represent the start time of the activities

involved in the project.These formulations require less binary variables than the time-indexed ones.

However, typically the optimal values of the corresponding linear programming relaxations provide

poor lower bounds on the optimal value of the problems. Continuous-timemodels for RCPSPs have

been proposed by Alvarez-Vald ´

es and Tamarit (1993) and Artigues et al. (2003). Another class of

continuous-time models are the event-based formulations proposed by Kon´

e et al. (2011). These

formulations use continuous variables that are indexed to a set of events corresponding to the start

and finish times of the activities.

The current work is motivated by the need to extend and deepen the development of formulations

to an important extension of the RCPSP. In fact, real-world projects often deal with resources that

master a wide range of functions/skills. This is particularlytrue when human resources are involved.

In this case, we find activities requiring simultaneously several skills for being properly executed.

Moreover, it is often the case that for each such skill several resource units are necessary. When this

is the case, we face a multi-skill resource-constrained project scheduling problem (MSRCPSP) that

is the object of study in this paper.

The MSRCPSP extends the RCPSP and hence falls in the class of NP-hard combinatorial opti-

mization problems. Moreover, it can also be lookedas a multimode RCPSP. In fact, the requirements

of an activity may be met by multiple sets of resources. The same set of resources can even be allo-

cated to an activity in different ways depending on the skill that each resource is going to perform

in that activity. Since each possible assignment of resources to an activity can be seen as a mode,

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies