Robustness against dependence in PERT: An application of duality and distributions with known marginals.

*(English)*Zbl 0592.90048Summary: A PERT-type project planning problem is considered, under the assumption (to be relaxed in Section 4) that the marginal distributions of the durations of the activities are known. Instead of the assumption of independence a minimax approach is proposed. A complete characterization of worst-case joint distributions, which by definition maximize the mean delay of the project completion time over a fixed target time T, is given. In the same framework also an optimal value for T is determined: it balances the costs of delay with the costs for large values of T in a two-stage stochastic program.

The main tool of analysis is duality. Worst-case distributions can be described as the solutions of a generalized transportation problem. The complementary slackness conditions of this linear program and its dual characterize the worst-case distributions by means of a condition on their support.

Due to the special structure, the dual problem can be reduced to a finite-dimensional convex program. By dualizing the reduced dual again, a flow problem on the PERT-network is derived. Optimal flows appear to be the criticality numbers of the worst-case distributions. In Section 2 special attention is paid to the characterization of the so-called NW rule solution for a generalized transportation problem.

The main tool of analysis is duality. Worst-case distributions can be described as the solutions of a generalized transportation problem. The complementary slackness conditions of this linear program and its dual characterize the worst-case distributions by means of a condition on their support.

Due to the special structure, the dual problem can be reduced to a finite-dimensional convex program. By dualizing the reduced dual again, a flow problem on the PERT-network is derived. Optimal flows appear to be the criticality numbers of the worst-case distributions. In Section 2 special attention is paid to the characterization of the so-called NW rule solution for a generalized transportation problem.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90B10 | Deterministic network models in operations research |

90C15 | Stochastic programming |