โ Scribed by J. M. Burt Jr.; D. P. Gaver; M. Perlas
No coin nor oath required. For personal study only.
An extensive literature now exists describing and solving various problems related to aspects of project graph analysis. Attention is called in particular to the papers of Charnes, Cooper, and Thompson (21, Hartley and Wortham [S], Kelley [7], Martin [9], and Jewel1 [6J, although there are many others as well. We mention also the systematic book-length treatment of Moder [lo].
Initially, project graph analysis (also mnemonically called PERT, GERT, CPM, etc.) assumed that individual task completion times were fixed and known in advance. The unreality of such an assumption in many contexts is apparent. Consequently attempts to introduce the probability distributions of completion times have been made; noteworthy for such work are [2], [S], and [9] above. Thus, for example, one may be interested in the expectation or other summary of the entire project's completion time as the latter depends upon the distributions of the inidvidual task times. Alternatively, it may be of interest to seek the probability that a particular path will be "critical," i.e., will be the last to be completed. Decision problems of one sort or another may be considered; cf. [Z] and [6].
This paper deals with stochastic network problems of the sort just mentioned. Since most stochastic networks of realistic scale are practically impossible to analyze mathematically, we begin by discussing simulation, in particular illustrating the gains possible by use of Monte Carlo approaches for improving naive "straightforward" simulation techniques. Considerable improvement in simulation efficiency can be made if an approximate, analytically tractable, model is available, so we next introduce such models and illustrate their use as a "control variate." The analytical network models suggested utilize families of task length (link time) distributions based on the simple exponential density, and profit by the Markovian or memoryless property associated with the exponential.
๐ SIMILAR VOLUMES
## Abstract The network interdiction problem involves interrupting an adversary's ability to maximize flow through a capacitated network by destroying portions of the network. A budget constraint limits the amount of the network that can be destroyed. In this article, we study a stochastic version