Applications of graph theory to pert critical path analysis

Abstract

The first part of this dissertation is concerned with the study of the detailed structure of networks sometimes referred to as directed acyclic networks. A number of new properties in theorems concerning such networks have been derived and although they do not necessarily assist in the generalization of the statistical PERT algorithms, they are useful in surveying the multiplicity of networks that might be encountered and in establishing convergence proofs and other properties of the algorithms that have been developed to date. Based upon the study of the properties of PERT networks an attempt is made to develop algorithms which at least provide approximate answers for both the statistical distribution of the project competition times as well as for their expectations. The procedure developed is an adaptation of an approximate statistical PERT technique recently developed as part of this research jointly with H. O. Hartley and R. L. Sielken. In this technique the statistical PERT algorithm developed by Hartley and Wortham (1966) and Ringer (1969) is first applied to reduce the original network to one of considerably smaller size. At that stage the distributions of the activity times in the reduced network is approximated by discrete distributions and the latter is used to obtain upper and lower bounds for both the cumulative density function and the expectation of the project completion time. In this technique there is an algorithm parameter at the disposal of the analyst and it is established that as the algorithm parameter tends to infinite the upper and lower bounds computed tend towards each other and hence to the correct answer.