Next: Crashing the Project Up: A Tutorial on Network Previous: Minimum Cost Flow

PERT/CPM

The final network models we discuss are the PERT and CPM models for project scheduling. The successful management of large projects, be they construction, transportation, financial, or what-have-you, relies on careful scheduling and coordinating of various tasks. CPM (Critical Path Method) and PERT (Project Evaluation and Review Technique) attempt to analyze project scheduling. This allows for better control and evaluation of the project. For instance, CPM allows you to answer such questions as: CPM and PERT have been used in a wide variety of projects, from designing and producing computers to scheduling a complex surgery. The essential ideas behind these techniques are quite straightforward (not as complicated as maximum flow for instance). We will begin with CPM.

CPM uses a project network to portray graphically the relationships among the tasks in a project. This is illustrated in the following diagram for building a house. Here excavation must be done before foundation and the foundation done before the rough wall. After that, three tasks may be done (rough electrical, rough exterior plumbing, and roof).

 

Each arc of the project represents a task, or activity. This is the activity on arc (AOA) representation. Each node represents an event (like finishing foundation is node 3). The direction of the arcs gives the sequences in which activities must be achieved. An event must precede the beginning of successive activities, and an event occurs only when all the activities immediately preceding it occur.

There are two special nodes, the start node and the finish node. The start node has no activities enter it; the finish node has no activity leave it.

Each arc has two roles: it represents an activity and it defines the precedence relationships among the activities. Sometimes it is necessary to add arcs that only represent precedence relationships. These dummy arcs are represented by dashed arrows. In our example, the arc from 5 to 8 represents the fact that exterior plumbing must be completed in order to begin exterior painting.

There are generally rules restricting the form of a project network. Some of these are:

To satisfy the second requirement, dummy nodes can be added (like node 11). Because of the third requirement, we can number the nodes so that if one node precedes another then the first gets a lower number than the second (as in our example).

Once we have the form of a project network, we can estimate the time required by each activity. Dummy activities get time 0. This number is in parentheses on the preceding diagram. These times are used to calculate two basic quantities: the early time and the late time.

The early time is the earliest time for an event assuming each activity is started as soon as possible. This is obtained by making a forward pass through the network. The start of the project is set to have early time 0. Every following event gets an early time based on the latest time a preceding event finishes. This is illustrated in table 3.1.

  
Table 1: Calculation of Early Time

The late time for an event is the latest time an event can occur without delaying the completion of the project beyond its early time. In this project, it takes 44 days to build a house. What is the latest the roofing can finish (or equivalently the latest exterior siding can start) without delaying the entire project?

The late time is calculated in a manner analogous to the early time. This time, begin at the end and work backwards. Here is the result for this project.

 
Table 2: Calculation of Late Time

Therefore, roofing must be done by time 26 or the completion of the building will be delayed. Note that it can finish as early as 22 days and as late as 26 days without affecting the completion time. Associated with each activity is a value called the total float for the activity. The total float for an activity is the amount of time an activity can be delayed beyond its earliest time without affecting the final completion time of the project. The total float for an arc from i to j is the difference between the late time of job j and (the early time for job i plus the activity time).

An alternative measure for the flexibility of an activity is the free float. This is the amount of time an activity can be delayed without pushing any job past its early time. This is calculated as the difference between the early time of job j and (the early time of job i plus the activity time). The following table illustrates this concept.

 
Table 3: Calculation of Float

If an activity with a total float of 0 is delayed for whatever reason, then the entire project is delayed. Such an activity is called a critical activity. Any path (there may be more than one) from the start node to the finish node made up solely of critical activities is a critical path. In our example, a critical path is 1-2-3-4-5-7-9-12-13.

This information on early and late times, critical jobs, and critical paths in invaluable to a manager, for it allows her to investigate the effect of possible improvements to the project plan.

Using Linear Programming

It is possible to use linear programming to find a critical path and to determine the overall completion time. Although this approach is much slower than the above algorithm, we will be able to extend the model to identify activities that should be ``crashed'' (speeded up, perhaps at some cost).

To do this, let  be the time that event j occurs. The objective, for this example is to minimize . Each activity corresponds to a constraint. For instance, the activity between 1 and 2 is the constraint

 

The other constraints are

 

If  is set to 0, optimizing this linear program will give the optimal completion time. Furthermore, one critical path will be identified. The arcs on this path will correspond to constraint with a shadow price of -1.
 


Next: Crashing the Project Up: A Tutorial on Network Previous: Minimum Cost Flow