Abstract

This paper addresses the resource-constrained project scheduling problem with uncertain activity durations. An adaptive robust optimization model is proposed to derive the resource allocation decisions that minimize the worst-case makespan, under general polyhedral uncertainty sets. The properties of the model are analyzed, assuming that the activity durations are subject to interval uncertainty where the level of robustness is controlled by a protection factor related to the risk aversion of the decision maker. A general decomposition approach is proposed to solve the robust counterpart of the resource-constrained project scheduling problem, further tailored to address the uncertainty set with the protection factor. An extensive computational study is presented on benchmark instances adapted from the PSPLIB.

Introduction

The resource-constrained project scheduling problem (RCPSP) consists in sequencing and scheduling project activities usually related by precedence and resource constraints involving renewable scarce resources. As comprehensively investigated in the literature, the RCPSP is an outstanding and challenging problem both in practice, since it arises in many important application fields (construction industry [20, 40], rolling ingots production [55, 57], to mention a few), and in theory.

The majority of the scientific contributions considers the model parameters deterministic ([41]). However, in the last years a frank acknowledgment of the uncertainties characterizing the project environment and a growing attention on the project execution, have highlighted the need of incorporating the uncertainty in problem parameters as an inevitable feature of the decision-making process [2, 52]. In fact, due to employees’ absenteeism, delays in materials supply, bad weather conditions and many other uncontrollable factors, some project activities may last longer than expected, threatening the operational viability of the planned schedule.