One of the tools used to manage large projects is known as the critical path method (CPM). In CPM the manager builds a network of all phases of a project and then evaluates the network to determine critical aspects of the project. In a CPM network, each vertex is an event, such as the start or completion of a task. The arcs connecting the vertices represent the duration of the activity. Unlike the examples in the text, they also store the name of the activity. To better understand the concept, let's look at a possible CPM plan to build a house. The network for this project is shown in Figure 11-26.
Figure: Steps for Building a House
In the plan we see that it will take 10 days to prepare the building plan (A) and 5 days to get it approved (B). Furthermore, we can't start building until we have selected the contractor (C). We could construct the shortest path from the start to the end for our plan, but it would be of little value. On the other hand, if we determined the maximum path-that is, the path with the greatest sum of the weights-we would know which steps in our plan are critical. If a critical step slips even one day, we slip our end date. We can slip noncritical dates, however, without slipping our end date, so long as the slip does not change the critical path for the project.
Modify Algorithm 11-12, "Minimum Spanning Tree of a Graph," to determine the maximum path through the graph. Then provide a menu that allows the project manager to answer the following questions:
a. What is the shortest possible completion time (SPCT)? The SPCT is the longest path through the graph from beginning to end.
b. What is the earliest start time (EST) for each activity? The EST is the sum of the weights in the maximum spanning tree up to the activity.
c. What is the latest start time (LST) for each activity? The LST is the SPCT for the whole project minus the SPCT for the rest of the project (starting from the current activity).
d. What is the slack time for each activity? The slack time is LST - EST.
e. Is an activity a critical path item? (Critical path items have a slack time of zero.)
f. What is the critical path for the project? (The critical path is the sub graph consisting of the maximum spanning tree.)