Distributionally Robust Project Crashing with Partial or No Correlation Information

Crashing is a method for optimally shortening the project makespan by reducing the time of one or more activities in a project network by allocating resources to it. Activity durations are however uncertain and techniques in stochastic optimization, robust optimization and distributionally robust optimization have been developed to tackle this problem. In this paper, we study a class of distributionally robust project crashing problems where the objective is to choose the first two moments of the activity durations to minimize the worst-case expected makespan. Under a partial correlation information structure or no correlation information, the problem is shown to be solvable in polynomial time as a semidefinite program or a second order cone program respectively. However in practice, solving the semidefinite program is challenging for large project networks. We exploit the structure of the problem to reformulate it as a convex-concave saddle point problem over the first two moment variables and the arc criticality index variables. This provides the opportunity to use first order saddle point methods to solve larger sized distributionally robust project crashing problems. Numerical results also provide an useful insight that as compared to the crashing solution for the multivariate normal distribution, the distributionally robust project crashing solution tends to deploy more resources in reducing the standard deviation rather than the mean of the activity durations.

Article

Download

View PDF