An optimization model for stochastic project networks with cash flows

The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using some heuristic rule, then the expected net present value (npv) must be calculated, but, due to the stochastic job completion times, it is a problem that belongs to the $\sharp$-P complete difficulty class, e.g. problems that are equivalent to finding all the Hamiltonian cycles of a network. Now consider that it is not enough to evaluate one project, but the optimal one has to be selected, so that the computational time increases even further! In this paper, a stochastic optimization model is proposed to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project net present value. A feature of this approach is that the scheduling rule is fully deterministic and determined at time t=0, therefore an upper bound of the expected net present value, that is an optimistic estimate, and a lower bound, that is a pessimistic estimate, can be calculated at the beginning of the project. Moreover, the full information of the net present value distribution lower bound is attainable by simulation, therefore the model is able to provide strategic information to the decision maker in the project evaluation phase.