the longest path through a network; it is the minimum project completion time

By summing the activity times (shown in Figure 9.8) along each of the four paths, we can compute the length of each path, as follows:

Path A: 1-2-4-7

3+ 2+ 3+ 1=9 months

Path B: 1-2-5-6-7

3+2+1+1+1=8 months

Path C: 1-3-4-7

3+1+3+1=8 months

Path D: 1-3-5-6-7

3+1+1+1+1=7 months

Figure 9.9 Activity Start Times

Because path A is the longest, it is the critical path: thus, the minimum completion time for the project is nine months. Now let us analyze the critical path more closely. From Figure 9.9 we can see that activity 3 cannot start until three months have passed. It is also easy to see that activity 4 will not start until five months have passed. The start of activity 4 is dependent on two activities leading into node 4. Activity 2 is completed after five months, but activity 3 is completed at the end of four months. Thus, we have two possible start times for activity 4, five months and four months. However, since the activity at node 4 cannot start until all preceding activities have been finished, the soonest node 4 can be realized is five months.

Now consider the activity following node 4. Using the same logic as before, activity 7 cannot start until after eight months (five months at node 4 plus the three months required by activity 4) or after seven months. Because all activities preceding node 7 must be completed before activity 7 can start, the soonest this can occur is eight months. Adding one month for activity 7 to the start time at node 7 gives a project duration of nine months. This is the time of the longest path in the network—the critical path.

This brief analysis demonstrates the concept of a critical path and the determination of the minimum completion time of a project. However, this was a cumbersome method for determining a critical path. Next, we discuss a mathematical approach to scheduling the project activities and determining the critical path.

ACTIVITY SCHEDULING

In our analysis of the critical path, we determined the earliest time that each activity could be finished. For example, we found that the earliest time activity 4 could start was five months. This time is referred to as the earliest start time, and it is expressed symbolically as ES. In order to show the earliest start time on the network as well as some other activity times we will develop in the scheduling process, we will alter our node structure a little. Figure 9.10 shows the structure for node 1, the first activity in our example network for designing the house and obtaining financing.

Figure 9.10 Node Configuration

To determine the earliest start time for every activity, we make a forward pass through the network. That is. we start at the first node and move forward through the network. The earliest start time for an activity is the maximum time in which all preceding activities have been completed— the time when the activity start node is realized.

The earliest finish time (EF), for an activity is simply the earliest start time plus the activity time estimate. For example, if the earliest start time for activity 1 is at time 0, then the earliest finish time is three months. In general, the earliest start and finish times for an activity are computed according to the following mathematical relationship.

The earliest start and earliest finish times for all the activities in our project network are shown in Figure 9.11.

The earliest start time for the first activity in the network (for which there are no predecessor activities) is always 0, or, ES = 0. This enables us to compute the earliest finish time for activity 1 as

The earliest start for activity 2 is

and the corresponding earliest finish time is

For activity 3 the earliest start time (ES) is three months, and the earliest finish time (EF) is four months.

Now consider activity 4, which has two predecessor activities. The earliest start time is

Figure 9.11 Earliest Activity Start and Finish Times

and the earliest finish time is

All the remaining earliest start and finish times are computed similarly. Notice in Figure 9.11 that the earliest finish time for activity 7, the last activity in the network, is nine months, which is the total project duration, or critical path time.

Companions to the earliest start and finish are the latest start and latest finish times. LS and LF. The latest start time is the latest time an activity can start without delaying the completion of the project beyond the project critical path time. For our example, the project completion time (and earliest finish time) at node 7 is nine months. Thus, the objective of determining latest times is to see how long each activity can be delayed without the project exceeding nine months.

Latest start time (LS):

the latest time an activity can start without delaying critical path time.

Latest finish time (LF):

the latest time an activity can be completed and still maintain the project critical path time.

In general, the latest start and finish times for an activity are computed according to the following formulas:

Whereas a forward pass through the network is made to determine the earliest times, the latest times are computed using a backward pass. We start at the end of the network at node 7 and work backward, computing the latest times for each activity. Since we want to determine how long each activity in the network can be delayed without extending the project time, the latest finish time at node 7 cannot exceed the earliest finish time. Therefore, the latest finish time at node 7 is nine months. This and all other latest times are shown in Figure 9.12.

Starting at the end of the network, the critical path time, which is also equal to the earliest finish time of activity 7. is nine months. This automatically becomes the latest finish time for activity 7, or

Using this value, the latest start time for activity 7 is

The latest finish time for activity 6 is the minimum of the latest start times for the activities following node 6. Since activity 7 follows node 6, the latest finish time is

Figure 9.12 Latest Activity Start and Finish Times

The latest start time for activity 6 is

For activity 4, the latest finish time (LF) is eight months, and the latest start time (LS) is five months; for activity 5, the latest finish time (LF) is seven months, and the latest start time (LS) is six months.

Now consider activity 3, which has two activities, 4 and 5, following it. The latest finish time is computed as

The latest start time is

All the remaining latest start and latest finish times are computed similarly. Figure 9.12 includes the earliest and latest start times, and earliest and latest finish times for all activities.

ACTIVITY SLACK

The project network in Figure 9.12, with all activity start and finish times, highlights the critical path (1-2-4-7) we determined earlier by inspection. Notice that for the activities on the critical path, the earliest start times and latest start times are equal. This means that these activities on the critical path must start exactly on time and cannot be delayed at all. If the start of any activity on the critical path is delayed, then the overall project time will be increased. We now have an alternative way to determine the critical path besides simply inspecting the network. The activities on the critical path can be determined by seeing for which activities ES = LS or EF = LF. In Figure 9.12 the activities 1, 2, 4, and 7 all have earliest start times and latest start times that are equal (and EF = LF); thus, they are on the critical path.

Table 9.1 Activity Slack

Activity

LS

ES

EF

Slack S

0

0

3

0

3

3

5

0

4

3

4

1

5

5

8

0

6

5

6

1

7

6

7

1

8

8

9

0

For activities not on the critical path for which the earliest and latest start times (or earliest and latest finish times) are not equal, slack time exists. We introduced slack with our discussion of the Gantt chart in Figure 9.4. Slack is the amount of time an activity can be delayed without affecting the overall project duration. In effect, it is extra time available for completing an activity.

Slack, S, is computed using either of the following formulas:

S = LS − ES

or

S = LF − EF

For example, the slack for activity 3 is

If the start of activity 3 were delayed for one month, the activity could still be completed by month 5 without delaying the project completion time. The slack for each activity in our example project network is shown in Table 9.1. Table 9.1 shows there is no slack for the activities on the critical path (marked with an asterisk); activities not on the critical path have slack.

Notice in Figure 9.12 that activity 3 can be delayed one month and activity 5 that follows it can be delayed one more month, but then activity 6 cannot be delayed at all even though it has one month of slack. If activity 3 starts late at month 4 instead of month 3, then it will be completed at month 5, which will not allow activity 5 to start until month 5. If the start of activity 5 is delayed one month, then it will be completed at month 7, and activity 6 cannot be delayed at all without exceeding the critical path time. The slack on these three activities is called shared slack. This means that the sequence of activities 3-5-6 can be delayed two months jointly without delaying the project, but not three months.

Slack is beneficial to the project manager because it enables resources to be temporarily diverted from activities with slack and used for other activities that might be delayed for various reasons or for which the time estimate has proved to be inaccurate.

The times for the network activities are simply estimates, for which there is usually not a lot of historical basis (since projects tend to be unique undertakings). As such, activity time estimates are subject to quite a bit of uncertainty. However, the uncertainty inherent in activity time estimates can be reflected to a certain extent by using probabilistic time estimates instead of the single, deterministic estimates we have used so far.

ALONG THE SUPPLY CHAIN A Couple of Iconic Building Renovation Projects

The National Museum of American History in Washington, DC, reopened in November, 2008 after a two-year, $85 million renovation project. The project focused on three areas—architectural enhancements to the Museum's interior, constructing a state-of-the-art gallery for the Star-Spangled Banner, and updating the 42-year-old building's infrastructure (mechanical, electrical, plumbing, lighting, fire, and security systems). The interior renovations included a five-story central atrium with a skylight that opens up the building to bright daylight, a grand staircase connecting the Museum's first and second floors, 10-foot-high artifact walls on both the first and second floors showcasing the breadth of the Museum's 3 million objects, and a welcome center on the second floor to improve visitor orientation. One of the renovation challenges was protecting the museum items. Smaller items, like Dorothy's ruby slippers from the Wizard of Oz, were moved to specially constructed storage areas and sealed in enormous boxes lined with monitors and vibration sensors, while larger artifacts, such as an 18-ton statue of George Washington, had to be protected in place. However, the project's centerpiece was a new $19 million chamber with special lighting for the museum's most prized artifact, the Star Spangled Banner.

Across the Atlantic in England a six-year project is on-going to restore and modernize the Royal Shakespeare and Company main theater in Stratford-upon-Avon, at a cost of 112.8 million British pounds. Shakespeare created his plays with an intimate environment in mind, with the audience standing right in front of the stage. However, a reconstruction of the theater in the 1930s included a traditional fanshaped seating design with the audience far from the stage, which dramatically altered Shakespeare's intended playgoer's experience. The renovation project is creating a new stage that extends into the audience on three sides and which can also be reconfigured and set up in the round, immersing the 1,000 audience members in the type of performance Shakespeare intended. Although the project plan seemed straightforward at first, like many projects involving historical building sites, the reality proved different. The new stage required a 23-foot-deep basement to be dug, but the theater is located on the banks of the River Avon. When the project team began digging the basement they discovered that the 1930s approach to keeping the river water out was to fill in an enormous hole with concrete, so instead of simply digging out the new basement, a mass of concrete had to be broken up. When the concrete was removed the basement was under the water table, so water had to be constantly pumped away from the work site and a special rig had to pump sealants into the ground around the basement's outer wall. Despite the unique problems posed by historic building renovation projects—like building a special room for the United States's flag and creating a stage for plays as the Bard intended—as he might say himself, “All's well that ends well.”

PROBABILISTIC ACTIVITY TIMES

In the project network for building a house in the previous section, all activity time estimates were single values. By using only a single activity time estimate, we are, in effect, assuming that activity times are known with certainty (i.e., they are deterministic). For example, in Figure 9.8, the time estimate for activity 2 (laying the foundation) is two months. Since only this one value is given, we must assume that the activity time does not vary (or varies very little) from two months. It is rare that activity time estimates can be made with certainty. Project activities are likely to be unique with little historical evidence that can be used as a basis to predict activity times. Recall that one of the primary differences between CPM and PERT is that PERT uses probabilistic activity times.

PROBABILISTIC TIME ESTIMATES

In the PERT-type approach to estimating activity times, three time estimates for each activity are determined, which enables us to estimate the mean and variance of a beta distribution of the activity times.

Probabilistic time estimates reflect uncertainty of activity times.

We assume that the activity times can be described by a beta distribution for several reasons. The beta distribution mean and variance can be approximated with three time estimates. Also, the beta distribution is continuous, but it has no predetermined shape (such as the bell shape of the normal curve). It will take on the shape indicated—that is, be skewed—by the time estimates given. This is beneficial, since typically we have no prior knowledge of the shapes of the distributions of activity times in a unique project network. Although other types of distributions have been shown to be no more or less accurate than the beta, it has become traditional to use the beta distribution to estimate probabilistic activity times.

The three time estimates for each activity are the most likely time (m), the optimistic time (a), and the pessimistic time (b). The most likely time is a subjective estimate of the activity time that would most frequently occur if the activity were repeated many times. The optimistic time is the shortest possible time to complete the activity if everything went right. The pessimistic time is the longest possible time to complete the activity assuming everything went wrong. The person most familiar with an activity or the project manager makes these “subjective” estimates to the best of his or her knowledge and ability.

Optimistic (a), most likely (m), and pessimistic (b):

time estimates for an activity.

These three time estimates are used to estimate the mean and variance of a beta distribution, as follows:

where

These formulas provide a reasonable estimate of the mean and variance of the beta distribution, a distribution that is continuous and can take on various shapes, or exhibit skewness.

Example 9.1 A Project Network with Probabilistic Time Estimates

The Southern Textile Company has decided to install a new computerized order processing system that will link the company with customers and suppliers. In the past, orders were processed manually, which contributed to delays in delivery orders and resulted in lost sales. The new system will improve the quality of the service the company provides. The company wants to develop a project network for the installation of the new system. The network for the installation of the new order processing system is shown in the following figure.

The network begins with three concurrent activities: The new computer equipment is installed (activity 1); the computerized order processing system is developed (activity 2); and people are recruited to operate the system (activity 3). Once people are hired, they are trained for the job (activity 6), and other personnel in the company, such as marketing, accounting, and production personnel, are introduced to the new system (activity 7). Once the system is developed (activity 2) it is tested manually to make sure that it is logical (activity 5). Following activity 1, the new equipment is tested, any necessary modifications are made (activity 4), and the newly trained personnel begin training on the computerized system (activity 8). Also, node 9 begins the testing of the system on the computer to check for errors (activity 9). The final activities include a trial run and changeover to the system (activity 11), and final debugging of the computer system (activity 10).

Figure 9.13 Examples of the Beta Distribution

The three time estimates, the mean, and the variance for all the activities in the network as shown in the figure are provided in the following table:

As an example of the computation of the individual activity mean times and variance, consider activity 1. The three time estimates (a = 6, m = 8, b = 10) are substituted in the formulas as follows:

The other values for the mean and variance are computed similarly.

Once the mean times have been computed for each activity, we can determine the critical path the same way we did in the deterministic time network, except that we use the expected activity times, t. Recall that in the home building project network, we identified the critical path as the one containing those activities with zero slack. This requires the determination of earliest and latest start and finish times for each activity, as shown in the following table and figure: