A chance constrained optimization approach for resource unconstrained project scheduling with uncertainty in activity execution intensity

Lucio Bianco, Massimiliano Caramia, Stefano Giordani

Computers & Industrial Engineering

Abstract: We study the problem of scheduling project activities with precedence constraints and unlimited resources. The latter problem, with the objective of minimizing the completion time of the project and deterministic activity durations, is known to be polynomially solvable. In the case of stochastic durations, the objective becomes to determine the project makespan distribution which is a #P complete problem. The most common technique used in this case is PERT. However, it is known that PERT tends to underestimate the expected makespan of the project. In our work, we try to overcome this shortcoming by considering a stochastic formulation of the problem, exploiting the activity execution intensity as a stochastic variable, and a chance constrained optimization approach. The main hypotheses under which our model works are essentially two: one is to have a sufficiently large time horizon for the project and the second, differently to what happens for the durations of the activities in the PERT model, is to assume a Beta probability density function for the activity execution intensity variables. The first hypothesis appears to be realistic since, when time horizon is large, stochastic factors tend to come into play in every decision problems; the second hypothesis, is realistic as well, since a minimum and a maximum value exist for the stochastic variables used in our model. Experimental results and a comparison with the PERT model and a Monte Carlo simulation are presented.

Translate »