CPMPERT | Introduction to Management Science (10th Edition)

[Page 329 ( continued )]

CPM/PERT

Critical path method (CPM) and project evaluation and review technique (PERT) were originally developed as separate techniques. (See the TIME OUT box on page 330.) Both are derivatives of the Gantt chart and, as a result, are very similar. There were originally two primary differences between CPM and PERT. With CPM, a single estimate for activity time was used that did not allow for variation; activity times were treated as if they were known with certainty . With PERT, multiple time estimates were used for each activity that reflected variation; activity times were treated as probabilistic. The other difference was in the mechanics of drawing a network. In PERT, activities were represented as arcs, or lines with arrows, between circles called nodes , whereas in CPM activities were represented by the nodes, and the arrows between them showed precedence relationships (i.e., which activity came before another). However, over time CPM and PERT have effectively merged into a single technique conventionally known as CPM/PERT.

The advantage of CPM/PERT over the Gantt chart is in the use of a network (instead of a graph) to show the precedence relationships between activities. A Gantt chart does not clearly show precedence relationships, especially for larger networks. Put simply, a CPM/PERT network provides a better picture; it is visually easier to use, which makes using CPM/PERT a popular technique for project planners and managers.

AOA Networks

A CPM/PERT network is drawn with branches and nodes, as shown in Figure 8.5. As previously mentioned, when CPM and PERT were first developed, they employed different conventions for drawing a network. With CPM, the nodes in Figure 8.5 represent the project activities. The branches with arrows in between the nodes indicate the precedence relationships between activities. For example, in Figure 8.5, activity 1, represented by node 1, precedes activity 2, and 2 must be finished before 3 can start. This approach to constructing a network is called activity-on-node (AON) . Alternatively, with PERT, the branches in between the nodes represent activities, and the nodes reflect events or points in time such as the end of one activity and the start of another. This approach is called activity-on-arrow (AOA) , and the activities are identified by the node numbers at the start and end of an activity (for example, activity 1 2, which precedes activity 2 3 in Figure 8.5). In this chapter we will focus on the AON convention, but we will first provide an overview of the AOA network.

[Page 330]

Figure 8.5. Nodes and branches

To demonstrate how an AOA network is drawn, we will revisit the example of building a house that we used as a Gantt chart example in Figure 8.4. The comparable CPM/PERT network for this project is shown in Figure 8.6. The precedence relationships are reflected in this network by the arrangement of the arrowed (or directed) branches. The first activity in the project is to design the house and obtain financing. This activity must be completed before any subsequent activities can begin. Thus, activity 2 3, laying the foundation, and activity 2 4, ordering and receiving materials, can start only when node 2 is realized , indicating that activity 1 2 has been completed. The number 3 above this branch signifies a time estimate of 3 months for the completion of this activity. Activity 2 3 and activity 2 4 can occur concurrently; neither depends on the other, and both depend only on the completion of activity 1 2.

Figure 8.6. Expanded network for building a house, showing concurrent activities

Time Out: For Morgan R. Walker, James E. Kelley, Jr., and D. G. Malcolm

In 1956 a research team at E. I. du Pont de Nemours & Company, Inc., led by a du Pont engineer, Morgan R. Walker, and a Remington-Rand computer specialist, James E. Kelley, Jr., initiated a project to develop a computerized system to improve the planning, scheduling, and reporting of the company's engineering programs (including plant maintenance and construction projects). The resulting network approach is known as the critical path method (CPM). At virtually the same time, the U.S. Navy established a research team composed of members of the Navy Special Projects Office, Lockheed (the prime contractor), and the consulting firm of Booz, Allen, Hamilton, led by D. G. Malcolm, that developed PERT for the design of a management control system for the Polaris Missile Project (a ballistic missilefiring nuclear submarine ). The Polaris project eventually included 23 PERT networks encompassing 2,000 events and 3,000 activities.

[Page 331]

When the activities of laying the foundation (2 3) and ordering and receiving materials (2 4) are completed, activities 4 5 and 4 6 can begin simultaneously . However, notice activity 3 4, which is referred to as a dummy activity . A dummy activity is used in an AOA network to show a precedence relationship, but it does not represent any actual passage of time. These activities have the precedence relationship shown in Figure 8.7(a). However, in an AOA network, two or more activities are not allowed to share the same start and ending nodes because that would give them the same name designation (i.e., 2 3). Activity 3 4 is inserted to give the two activities separate end modes and thus separate identities, as shown in Figure 8.7(b).

Figure 8.7. A dummy activity

Returning to the network shown in Figure 8.6, we see that two activities start at node 4. Activity 4 6 is the actual building of the house, and activity 4 5 is the search for and selection of the paint for the exterior and interior of the house. Activity 4 6 and activity 4 5 can begin simultaneously and take place concurrently. Following the selection of the paint (activity 4 5) and the realization of node 5, the carpet can be selected (activity 5 6) because the carpet color is dependent on the paint color . This activity can also occur concurrently with the building of the house (activity 4 6). When the building is completed and the paint and carpet are selected, the house can be finished (activity 6 7).

AON Networks

Figure 8.8 shows the comparable AON network to the AOA network in Figure 8.6 for our house-building project. Notice that the activities and activity times are on the nodes and not on the activities, as with the AOA network. The branches or arrows simply show the precedence relationships between the activities. Also, notice that there is no dummy activity; dummy activities are not required in an AON network because no two activities have the same start and ending nodes, so they will never be confused . This is one of the advantages of the AON convention, although both AOA and AON have minor advantages and disadvantages. In general, the two methods both accomplish the same thing, and the one that is used is usually a matter of individual preference. However, for our purposes, the AON network has one distinct advantage: It is the convention used in the popular Microsoft Project software package. Because we will demonstrate how to use that software later in this chapter, we will use AON.

Figure 8.8. AON network for house-building project

(This item is displayed on page 332 in the print version)

The Critical Path

A network path is a sequence of connected activities that runs from the start to the end of the network. The network shown in Figure 8.8 has several paths. In fact, close observation of this network shows four paths, identified in Table 8.1 as A, B, C, and D.

Table 8.1. Paths through the house-building network

(This item is displayed on page 332 in the print version)

Path	Events
A	1 2 4 7
B	1 2 5 6 7
C	1 3 4 7
D	1 3 5 6 7

The project cannot be completed (i.e., the house cannot be built) until the longest path in the network is completed. This is the minimum time in which the project can be completed. The longest path is referred to as the critical path . To better understand the relationship between the minimum project time and the critical path, we will determine the length of each of the four paths shown in Figure 8.8.

[Page 332]

The critical path is the longest path through the network; it is the minimum time in which the network can be completed .

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

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

[Page 333]

Figure 8.9. Activity start time

Now let us consider the activity following node 4. Using the same logic as before, we can see that activity 7 cannot start until after 8 months (5 months at node 4 plus the 3 months required by activity 4) or after 7 months. Because all activities preceding node 7 must be completed before activity 7 can start, the soonest this can occur is 8 months. Adding 1 month for activity 7 to the time at node 7 gives a project duration of 9 months. Recall that this is the time of the longest path in the network, or 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 is a cumbersome method for determining a critical path. Next, we will discuss a mathematical approach for scheduling the project activities and determining the critical path.

Activity Scheduling

In our analysis of the critical path, we determined the soonest time that each activity could be finished. For example, we found that the earliest time activity 4 could start was at 5 months. This time is referred to as the earliest start time , and it is expressed symbolically as ES .

ES is the earliest time an activity can start .

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 8.10 shows the structure for node 1, the first activity in our example network for designing a house and obtaining financing.

Figure 8.10. Activity-on-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 time for an activity is the maximum time that all preceding activities have been completedthe time when the activity start node is realized.

[Page 334]

EF is the earliest start time plus the activity time estimate.

The earliest finish time , EF , for an activity is 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 3 months. In general, the earliest start and finish times for an activity are computed according to the following mathematical formulas:

ES = Maximum ( EF immediate predecessors)

EF = ES + t

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

Figure 8.11. Earliest activity start and finish times

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

EF = ES + t = 0 + 3 = 3 months

The earliest start time for activity 2 is,

ES	=	Max ( EF immediate predecessors)
	=	3 months

The corresponding earliest finish time is

EF = ES + t = 3 + 2 = 5 months

For activity 3 the earliest start time is 3 months, and the earliest finish time is 4 months.

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

ES	=	Max ( EF immediate predecessors)
	=	Max (5, 4) = 5 months

[Page 335]

and the earliest finish time is

EF = ES + t = 5 + 3 = 8 months

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

Companions to the earliest start and finish are the latest start ( LS ) and finish ( LF ) times. 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 9 months. Thus, the objective of determining latest times is to see how long each activity can be delayed without the project exceeding 9 months.

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

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

LS	=	LF t
LF	=	Minimum ( LS immediately following predecessors)

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 time for each activity. Because 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 9 months. This and all other latest times are shown in Figure 8.12.

Figure 8.12. Latest activity start and finish times

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

LF = 9 months

Using this value, the latest start time for activity 7 can be computed:

LS = LF t = 9 1 = 8 months

[Page 336]

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

LF	=	Min ( LS following activities)
	=	8 months

The latest start time for activity 6 is

LS = LF t = 8 1 = 7 months

For activity 4 the latest finish time is 8 months, and the latest start time is 5 months; for activity 5, the latest finish time is 7 months, and the latest start time is 6 months.

Now consider activity 3, which has two activities following it. The latest finish time is computed as follows:

LF	=	Min ( LS following activities)
	=	Min (5, 6) = 5 months

The latest start time is

LS = LF t = 5 1 = 4 months

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

Activity Slack

The project network in Figure 8.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. As a result, 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 8.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.

For those activities not on the critical path, the earliest and latest start times (or earliest and latest finish times) are not equal, and slack time exists. 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 is the amount of time an activity can be delayed without delaying the project.

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

S = LS ES

S = LF EF

For example, the slack for activity 3 is computed as follows:

S = LS ES = 4 3 = 1 month

If the start of activity 3 were delayed for 1 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 8.2 and in Figure 8.13.

[Page 337]

Table 8.2. Activity slack

Activity	LS	ES	LF	EF	Slack, S
^[*] 1			3	3
^[*] 2	3	3	5	5
3	4	3	5	4	1
^[*] 4	5	5	8	8
5	6	5	7	6	1
6	7	6	8	7	1
^[*] 7	8	8	9	9

^[*] Critical path activities

Figure 8.13. Activity slack

Notice in Figure 8.13 that activity 3 can be delayed 1 month and activity 5, which follows it, can be delayed 1 more month, but then activity 6 cannot be delayed at all, even though it has 1 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 1 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 2 months jointly without delaying the project, but not 3 months.

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

The times for the network activities are simply estimates for which there is usually not a lot of historical basis (because 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.