An optimization model for stochastic project networks with cash flows

Project networks - or PERT networks - can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker's problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows. The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the #-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time. This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins. © Springer-Verlag 2006.