On the concept of criticality on GPRs project network with variable activity durations

Temporal analysis of project networks has been widely studied in the literature; basically, it consists of determining the starting and finishing times of activities respecting a set of precedence constraints among them. The main output of the temporal analysis is twofold: on the one hand, it provides information on the minimum completion time of the project and, on the other hand, it determines which activity may be considered critical. Defining and determining activity criticalities on its own is a problem that has attracted the attention of many researchers over the last decades. In this paper, in an attempt to further pursue these studies, we focus on project scheduling with generalized precedence relationships where durations are not fixed in advance, but are variable within given ranges and have to be determined to minimize the makespan of the project. Analyzing activity criticalities for the same problem where activity durations are fixed has been tackled within the literature; what happens when durations are assumed variables, to the best of our knowledge, has not been investigated. We show that, in this scenario, the current knowledge on activity criticalities is no longer valid and we give new definitions of criticality together with the rules for its identification. An extensive experimental campaign on benchmark instances is presented to show that our findings are meaningful for quantitative project management.