Twenty years ago, network analysis was first suggested as a tool for planning, scheduling and controlling large scale projects. However, PERT, which was the first approach suggested for stochastic network analysis, still dominates the textbook literature on project management. This is in spite of the fact that PERT relies upon many simplifying assumptions and that three alternative approaches have subsequently been proposed. Monte Carlo simulation, network reduction, and the method of bounding distributions are computationally more sophisticated than PERT and this may have deterred their widespread acceptance. However, tremendous advances in computer technology over the past twenty years have made sophisticated techniques economically feasible. Therefore, Monte Carlo simulation, network reduction, and the method of bounding distributions now deserve serious reconsideration as practicable approaches for stochastic network analysis. This paper concisely presents the methods for stochastic network analysis with a view toward stimulating reconsideration of which method currently is best.
A major event in history of management science occurred twenty years ago, during 1957-1958; network analysis was introduced as a tool for planning, scheduling and controlling large scale projects. During that time, James Kelly and Morgan Walker developed the Critical Path Method (CPM), and the U.S. Navy’s Special Projects Office initiated a program to develop a new system for evaluating large scale, complex projects. The Navy’s program culminated in the development of Program Evaluation and Review Technique (PERT), which became renowned for its successful application to the Pollaris ballistic missile project.1 Since then, enormous numbers of books and articles dealing with stochastic PERT network analysis attest to the impact that this approach has had upon project management. Furthermore, applications of network analysis have extended to all types of institutions, private and public, profit and non-profit, and service and manufacturing.
Three alternatives to PERT for stochastic network analysis have subsequently been proposed. They are Monte Carlo simulation (3) (17), network reduction (8) (12) (15) and the method of bounding distributions (10). Although these methods have many good features, they have not received the publicity or acceptance of PERT. The most popular textbooks in operations management discuss the details of PERT, but give at best a cursory treatment of Monte Carlo simulation. Network reduction and the method of bounding distributions are generally ignored.2
The newer methods are perceived to be computationally sophisticated and consequently more costly to use than PERT. But, because of tremendous advances in computer technology over the last two decades, the potential value of these methods has been enhanced. Larger, faster, and cheaper computers are more readily available, thereby making computationally sophisticated techniques economically practicable. Monte Carlo simulation, network reduction and the method of bounding distributions now deserve serious considerations as viable alternatives to PERT.
In order to stimulate a reexamination of the various methods for stochastic network analysis, this paper provides a coherent overview of PERT, Monte Carlo simulation, network reduction, and the method of bounding distributions. The rationale underlying these methods, the assumptions upon which they rely, and also some criticisms that have been voiced against them are examined.
Terminology
To provide a framework for our discussion, we shall define terms often used in stochastic network analysis. We can define a network as a set of nodes (circles) connected by a set of directed arcs (arrows). More formally, a network can be described by the couple (N,A), where N is a nonempty set of nodes and A is a set of arcs. A connected network in which every arc has an orientation (direction) with no cycles or loops and which contains exactly one source and one sink is called a directed acyclic network. If has no arcs entering it, then s is the source of the network. If
has no arcs leaving it, then z is the sink of the network.
For a project network, we adopt the convention of letting arcs represent discrete activities.3 The term “discrete” refers to the separateness of the activities in terms of starting and completion time. The start and the completion of activities are represented by nodes and are referred to as project events. The orientation of the arcs indicate the technological sequence in which the activities are to be performed. In project networks, it is generally assumed that the networks are acyclic.
Associated with each arc is a non-negative random variable, ti, which has a known cumulative probability distribution, Fi(t). The random variable ti is the duration of the ith activity. Define Pj as the jth complete path from s to z. The completion time of all activities on the jth path, j = 1,…,m, is given by
If there are m complete paths from s to z, then the project completion time, T, is
where T is a random variable whose distribution is generally difficult to evaluate because of the complex geometry of networks and the intractable form of activity distributions. We shall let GT(t) be the cumulative distribution function (c.d.f.) of T. We shall also let E(T) and be the mean and variance of the distribution.
Assumptions
There are several assumptions that underlie most network models. One assumption is that a project can be decomposed into a set of predictable, discrete activities. That is, all the activities required to accomplish a project are known with certainty and the starting time of one activity can be discerned from the completion of other activities.
Another assumption of network models is that the durations of project activities are statistically independent. This means that the duration of one activity does not influence the duration of other activities in the project. For stochastic networks where the activity durations are random variables, it is assumed that the probability distributions of the durations are known. Acyclic networks possessing the above characteristics are often referred to as stochastic PERT networks.4
Wiest and Levy (18) discuss several other assumptions that underlie network models. The errors introduced by PERT assumptions have been analyzed in detail by MacCrimmon and Ryavec (11). We shall present some of their findings later on.
Why Network Models for Project Planning and Control?
Network models can considerably enhance project planning and control. They facilitate the evaluation of progress toward the attainment of project objectives. That is, they focus attention on the potential problems in project implementation. In addition, network models readily evaluate the effect of technological change on project implementation. For example, the time-cost implications of changes in resource allocation or activity sequencing can be evaluated by means of network models.
Planners use stochastic network models to make probability statements about project objectives. An important feature of stochastic models is the cumulative distribution function of the completion time of the project GT(t). This distribution indicates the probability of finishing a project by a specified time.
GT(t) is influenced by several factors:
1. The number of activities in the network.
2. The geometry of the network.
3. The probability distributions of activity durations.
The probability distribution of the completion time can be altered by changing the manner in which the project is implemented. Changes in project implementation can be effected by one or more of the following:
1. Shifting resources between activities. This might involve shifting labor from one activity to another.
2. Stripping resources off activities.
3. Adding resources to activities.
4. Delaying the start of some activities.
5. Changing the technological sequence in which the activities are to be performed.
Stochastic network analysis is concerned with determining GT(t), E(t) and We shall now give an overview of several important methods that have been proposed for achieving this.
The PERT Approach
In using PERT, is is assumed that activity durations are beta distributed. It is also assumed that three time estimates determine the mean and variance of an activity duration. These are the optimistic time (to), pessimistic time (tp) and most likely time (tm). Simple formulae are then used to estimate the standard deviation and mean
of activity duration.5 The following summarizes the familiar PERT approach:
1. Calculate for every activity in the network.
2. Determine the critical path, Pc, in the network. Pc is the longest complete path in the network based upon expected activity completion times.
3. Calculate the estimated project expected completion time, T, and variance, by
4. Assume that Pc consists of enough activities such that the Central Limit Theorem can be applied. The distribution of project completion time (T) would then be normal with estimated mean and variance
PERT is easy to use, but the errors introduced by its numerous assumptions can be significant. MacCrimmon and Ryavec (11, pp. 22-24) show that in extreme cases these errors may be as large as 33% for E(t) and 17% for σt. In more realistic situations, however, they concede that these errors will be less than 5% or 10%. Hartley and Wortham (8, p. B-479) give an example where the PERT estimate of the expected project completion time is optimistically or downward biased by 172%. Although this bias is always optimistic, its magnitude is a function of the network geometry, the number of project activities and the form of the activity distributions. The errors introduced by the PERT assumptions provided the catalyst for developing more accurate methods for stochastic network and analysis.
Monte Carlo Simulation
One of the earliest attempts to avoid the problems of PERT was made by R. M. Van Slyke in 1963 (17). Van Slyke recommended assigning to an activity a duration randomly drawn from an appropriate probability distribution. Random values selected in this manner are then used to determine the longest complete path through the network. By simulating this process many times, a series of realizations of T is generated. A histogram of these realizations would then provide an approximation to the actual distribution of T.
Assume that a network comprised of M activities is simulated n times. The duration assigned to the ith activity during the jth simulation is
where is the inverse of Fi(t) and R is a uniformly and independently distributed random variable such that 0 ≤ R ≤ 1. Similarly, all activities are randomly assigned durations based upon their c.d.f.’s and the longest complete path for the jth simulation is determined. Let Tj be the completion time of this path. Then, for all n simulations we have T1, T2, T3, …, Tn. A histogram of these n values leads to an estimate of TT(t). Also, unbiased estimates of E(T) and
can be calculated, which is a distinct advantage of simulation over PERT.
Another advantage of Monte Carlo simulation is that a “criticality index” can be associated with every activity in the network. If a particular activity were on the longest (i.e., the critical) path k times in n simulations, then its criticality index is
This is an estimate of the probability that an activity is on the critical path. In terms of project implementation, those activities with the largest index deserve the most managerial attention.
Often, the number of simulations required is large. For an M activity network simulated n times, M × n activity durations would be randomly generated. Several authors indicate that the computation time required to simulate large networks can be prohibitive.6 We might expect, for example, that Monte Carlo would require approximately n times as much CPU time as PERT, since critical path analysis is performed for each simulation.
This problem was particularly acute in 1963 when network simulation was first suggested because computer capabilities were still at a low level. Today, however, computers with tremendously increased capability are readily available, making network simulation a more practical alternative to PERT.
Concern over computation time in Monte Carlo led Burt and Garman (3) to recommend variance-reducing techniques for simulating stochastic networks. These methods are well developed in the general theory of Monte Carlo, and are shown to enhance the precision of Monte Carlo simulation while at the same time to reduce the time required for computation.7
As an example of a variance-reducing technique, consider the antithetic variate method. This approach relies upon generating pairs of simulated realizations of T which are negatively correlated. Let R be a uniformly distributed random variable such that 0 ≤ R ≤ 1. Define R as the complement
Consequently is uniformly distributed with 0 ≤ R ≤ 1.
If Fi(t) is the c.d.f. of the ith activity duration, then two negatively correlated randomly sampled values of the activity’s duration are
and
All activities in the network are sampled in this fashion, yielding two negatively correlated realizations of completion time, T and , where
is known as the antithetic variate. Therefore, n simulations of a network yield the stream of realizations
A histogram of these values leads to an estimate of GT(t).
The antithetic variate method can also be used to calculate an unbiased estimator for E(T). Burt and Garman given an example where the variance of the antithetic variate estimator for E(T) is one fifth that provided by straightforward Monte Carlo. This clearly indicates that the number of simulations required to provide the same precision can be greatly reduced by using this method.
Burt and Garman have suggested several other techniques for reducing the computation time of network simulation. These include conditional sampling and the control variate method. Such techniques are directed at making simulation a practical, less costly approach for stochastic network analysis.
Network Reduction
Analytical methods have been suggested for evaluating stochastic PERT networks. These rely upon identifying subnetworks whose probability distributions are analytically tractable. That is, it would be possible to determine the probability distribution of the completion time of the subnetwork. In that case, the subnetwork is treated as a single activity, thereby reducing the size of the network. Nevertheless, simulation or analytical approximations to activity distributions are needed to make these network reduction methods practicable.
Several network structures can be evaluated analytically. In 1965, J.J. Martin (12) suggested an algorithm to determine the distribution of completion time for series-parallel subnetworks (see Figure 1). He also indicated an approach for restructuring any acyclic network into series-paralle geometry. This means that any stochastic PERT network can be analyzed using Martin’s algorithm. However, to make series-parallel reduction computationally practicable, Martin used polynomial approximations to the probability distributions of activity durations. Commenting on this in 1966, Hartley and Wortham (8, p. B-470) note that in evaluating a series-parallel subnetwork, the number of terms in the polynomial approximations increases exponentially with the number of activities. This implies that the computation efforts needed for series-parallel reduction might be excessive.
Figure 1. An Example of a Series-Parallel Subnetwork.
In 1966, Hartley and Wortham (8) proposed an algorithm for evaluating a so-called “Wheatstone bridge” subnetwork (see Figure 2). A similar approach was developed by L. J. Ringer (15) in 1969 for evaluating a subnetwork consisting of two adjacent Wheatstone bridges (see Figure 3). Hartley-Wortham and Ringer suggest that a network first be reduced using their algorithms. The reduced network then can be analyzed economically using Monte Carlo simulation.
While network reduction methods are theoretically appealing, it is not clear whether they are computationally efficient or practical. For example, Ringer (15, p. B-141) notes that it took thirty seconds on the IBM 360-65 to recognize and evaluate a double Wheatstone bridge subnetwork. This is the CPU time needed to reduce the network by only seven activities. Concern over computation cost may then be a deterrent for widespread adoption of network reduction methods.
Figure 2. “Wheatstone Bridge” Subnetwork.
Figure 3. “Double Wheatstone Bridge” Subnetwork.
Bounding Distributions
In 1971, G. B. Kleindorfer (10) developed a method for determining bounds on GT(t), E(T) and when activity distributions are discrete. The bounding method begins with the first activity of the project and successively calculates activity bounding distributions based upon the distributions of predecessor activities. Again, let Fi(t) be the probability that the ith activity would be completed on or before time t. Let Pi(t) be the probability that the ith activity would be started on or before time t and Ai(r) be the probability that the activity requires r units of time. Let Bi be the set of activities that immediately precede activity i. By assuming independence of activity durations, it follows that for any t,
Now let and
be the respective upper bounds for Pi(t) and Fi(t). Also, let
and
be the lower bounds. Kleindorfer shows that
where
and
where
Equations (8), (9), (10), and (11) are evaluated successively beginning with the initial project activity. The first activity duration is assumed to be deterministic with duration zero. Consequently,
Kleindorfer shows how bounds on E(T) and can be easily determined by differencing the bounds on GT(t). An interesting result is that the lower bound for E(T) is at least as precise as the PERT estimator.
The bounding distribution method requires more computation effort than PERT. However, there are several obvious advantages in using it. First, the method provides a 100% probability interval for GT(t). Second, it does not rely upon simplifying assumptions concerning network geometry and the probability distribution of activities. The only assumption is that activity distributions are discrete.
Another advantage of the bounding distribution method is that it can readily yield upper and lower bounds on the mean and standard deviation of flows through the network. Such flows might be time, cost or resource utilization. Finally, the method is well-suited for computer implementation. According to Kleindorfer, the algorithm has been programmed to handle any acyclic network.
Impact of Computer Technology
Monte Carlo simulation, network reduction and the method of bounding distributions obviate the need for extensive simplifying assumptions, and therefore can provide better estimates of GT(t), E(T) and than PERT. This can make stochastic network analysis a more valuable tool for project management by removing major sources of error. Yet, such benefits do not come free; we have noted that these methods require greater computation effort.
Computation cost and the quality of estimators should be among the criteria used in selecting a suitable method for stochastic network analysis. While the quality of estimators is related to the technique employed, computation cost is determined by the technique itself and the computing facilities available. We know that the alternatives to PERT provide better estimators. We also know that computer technology has advanced dramatically during the last twenty years, thereby making the computationally sophisticated techniques more economical. In this regard, Lynn Hopewell writes:
“The cost of digital circuitry, in terms of millions of computer instructions executed per dollar, is decreasing.... In 1955, about 100,000 program instructions could be executed for one dollar. In 1960, the same dollar bought one million.… and by 1970, it bought 100 million” (9)
The cost of central processing units is expected to decline further. F. G. Withington (19), for example, has developed the cost projections given in Figure 4. He also shows that the costs of input/output devices and mass storage will follow similar trends.
Figure 4. Cost of Central Processors. Source: (16, p. 61).
The availability of larger, faster and cheaper computers makes the alternatives to PERT more appealing than ever before. For this reason, we believe that the time is ripe for reexamining and comparing all approaches for stochastic network analysis. Until such a study is conducted and the results publicized, PERT, with its inherent statistical biases, will continue to be the dominant method.
Summary and Conclusions
We have by no means discussed all the issues related to stochastic network analysis raised over the past twenty years. For example, Fulkerson (5) suggested an algorithm that provides better lower bounds on E(T) than PERT. Also, several approaches for analyzing generalized networks have been proposed.8 These and other investigations illustrate the continued interest in stochastic network analysis and attest to the impact that PERT has had upon management science.
The development of PERT introducted stochastic network analysis as a powerful tool for project planning, scheduling, and controlling. Yet the assumptions which underlie PERT can be a source of significant error. We have reviewed several techniques subsequently developed which rely less upon simplifying assumptions. Since these alternatives require greater computation effort than PERT, it is not currently obvious which technique is best. In light of advances in computer technology, however, the more recently developed methods now deserve serious reconsideration.