Critical Path

The principal result of our analysis is a schedule for the project, which provides a start time for each activity. This allows managers to set due dates, organize the means of production, alter suppliers to the need for resources, and track progress. Generally, the project has a due date and the goal is to complete all activities before it is reached. If there were no precedence relations all the activities could be performed simultaneously and the project would be complete at the time when the activity with the largest duration was finished. If the activities must be performed sequentially rather than simultaneously, then the completion time is the sum of the activity times.

The interesting situation arises when activities can be on-going simultaneously and precedence relations restrict the order of performance. This is the case addressed in this lesson. Our goal is to find the critical time-- the minimum time required to complete the project. We also wish to discover the critical path--the set of activities that must be performed in strict sequence to finish the project a soon as possible. The process of finding the critical time and path determines two schedules, the earliest schedule and the latest schedule.

The scheduling is even more complicated when there are limited resources and when the cash flow over time is relevant. We do not consider these problems in this course, but they can be handled by the Project Management add-in.

 Goals
 A project is given by a set of activities, precedence relations and activity times. For a project, our goals are to: Sort the activities so that each in the ordered list follows all of its predecessors. Construct a schedule that does not violate precedence relations. Display a schedule on a Gantt chart. Find the earliest start and finish times for the activities. Find the latest start and finish times for the activities. Find the free and total slack times and identify the critical activities. Show the critical path on the project network. Use the Project Management add-in to find the critical path and the associated earliest start schedule. Learn how to change the schedule by adding delays to the start times of non-critical activities. Use delays to find the latest start schedule.
 Text

Ready Section 9.5 to see how to construct a Gantt chart for a specified schedule.

 9.5 Gantt Chart

The assigned text develops the critical path method for the activity-on-node (AON) model. Section 9.6 describes the activity-on-arc (AOA) model. Although the latter is more familiar to many, the construction of the project network is more difficult, so we focus on the AON model.

 9.7 Activity on Node
 Early Schedule

We illustrate a schedule with the example from the previous lesson. The figure below shows a screen shot of a portion of the worksheet created by the Project Management add-in. To clarify the discussion, not all of the columns used by the add-in are shown. A schedule specifies a start time for each activity as shown in the Scheduled Start column. The Scheduled Finish column is computed by adding the activity time to the scheduled start time. This happens to be the early schedule for the project. Start and finish times are shown as numbers of periods (in this case days) from the start of the project.

The Gantt chart of the early schedule is below.

The schedule has activities A, B and C starting right away at time 0. Activity E begins immediately after B is complete at day 1. Activity D begins at day 2 after the completion of A. Activities F and G start at day 3 with the completion of C. Activity H depends on the completion of D and E. E is finished at time 3, but D is not finished until 5. The start of activity H must wait until all of its predecessors are finished, so it can't start until day 5. This illustrates an important requirement of a valid schedule.

 An activity cannot begin until all of its predecessors are finished.

Continuing the example, we have scheduled the start time of each activity at the maximum of the finish times of its predecessors. The End activity has predecessors M and N. (Recall that the table does not show predecessors of the end activity. These are implicitly defined as the set of activities that have no successors.) Activity N finishes at 11, but activity M finishes at 12, so the project is complete at day 12. We have scheduled the activities as early as possible, so the project can be completed no earlier than 12 days after it starts. This is the critical time.

The column at the left of the activity data indicates the critical activities with red fields. These activities cannot be scheduled later than the start time indicated without delaying the completion of the project. In our example, activities A, D, H, J, L and M are critical. If the time for any of these activities increases or if any are delayed beyond their scheduled start times, the project will require more than 12 days to complete. When the project is ongoing, managers focus on critical activities because these determine the completion time of the project.

The Gantt chart is a visual representation of the schedule. In practice, it is used to communicate a schedule to all concerned. Each activity with nonzero time is shown as a bar on the schedule. The critical activities are red bars and the non-critical activities are maroon. Placing the critical bars end to end, results in a solid red line, while the non-critical activities have flexibility in scheduling called slack. To obtain the critical time, the critical activities must be performed in sequence with no idle time between the end of one and the start of the next.

 Late Schedule

The late schedule has the activities beginning as late as possible without delaying the completion of the project. To find the late schedule we set the finish time of the end activity to the due time. In this case we select the due time to be the same as the critical time, that is 12.

Working backwards up the list, we then schedule the finish times of M and N. When the project must end at 12, both finish times are set to 12. Using the activity times for M and N, we compute their start times as 10 and 11, respectively. Activity L has both M and N as successors, so the latest it can finish is the earliest of the start times for M and N. The general rule is below.

 An activity must finish before any of its successors can begin.

Following this rule we can sequentially discover the latest start and finish time for each activity. The results are shown in the schedule columns. We show an additional column called Activity Delay. This column indicates how much each activity is delayed to obtain the latest schedule. In the column on the far left we see that all the activities are now critical. Indeed if we further delay any activity, the project will finish after the due time. With the late schedule all the activities are critical.

The Gantt chart for this case shows that the activities in red are the same as those found with the early schedule. Some of the non-critical activities show a black as well as a maroon bar. The black bars show how much each of the non-critical activities are delayed to obtain the late schedule.

When compared to the early schedule, the late schedule doesn't look like a very good idea. The early schedule has slack. It allows the time for some activities to increase without delaying the project completion time, while the late schedule has no slack. There are benefits to delaying activities however. In particular, if a critical activity and a non-critical activity use the same limited resource, a better schedule might result if the non-critical activity were delayed. Time value of money also argues for delays. Most activities will involve cash flow and putting off spending money is a good policy in some cases. With these considerations neither the early nor the late schedule may be the best.

 Earliest Time Analysis

With this section we begin a more mathematical treatment of the scheduling problem. We call this critical path analysis because the goal is to identify the critical activities of the project. Critical path analysis solves two simple sets of equations. The purpose is to find bounds on the start and finish time of each activity. Here we use the AON model along with the term node rather than activity. The notation used in the discussion is as follows.

The analysis assumes that the nodes are indexed in precedence order. That is, the index of each node is greater than any of its predecessors. Similarly, the index of each node is less than any of its successors. This is possible because the project network is acyclic, that is, it has no cycles. We will not formalize the process of arranging the nodes in precedence order because the examples we consider are small and the ordering can be done by observation. It happens that in our example the nodes are already indexed in predecessor order.

We start with the problem of finding the earliest start and finish times.

The early start time for a node is based on the logical requirement that a node can begin only when all its predecessors have finished. The earliest this can happen is the maximum of the finish times. The earliest finish time is the start time plus the duration of the activity.

The equations describe the process for computing the earliest start and finish times. First set the earliest start of node 1 (the start node) to zero. Then proceed in the order of increasing node indices finding the earliest start and finish time for each node. At any node the earliest start time can be determined because the equations have previously been solved for all its predecessors. Click the icon to see a tabular solution of the equations for the example.

 Earliest Time Table

Hand calculations are more easily accomplished directly on the project network. The figure below shows the notation for solving for the important scheduling times. The box holds the name and index of the node. The various start and finish times are shown at the corners.

Click the icon to see a movie that shows the process. In this presentation, we show the calculations of the earliest start and finish times.

 Solving for the Earliest Times

The process begins at node 1, the start node, and ends at node 16, the end node. We have computed the earliest start and finish times for all nodes.

 Latest Time Analysis

The project schedule can also be described by the latest time activities can begin and end.

The latest finish time for a node is based on the logical requirement that a node must be complete before its successor nodes can begin. This is reflected in the equation that requires that the latest finish time of the general node i must be the minimum of the latest start times of its successor nodes. Further, the latest starting time is the latest finish time less the time required for the node.

Only the end node has no successors, so we define its latest time as the due time for the project. The remaining times are found by solving the equations below in the reverse orders of the indices We add the condition for feasibility that the latest starting time for the start node must be greater than 0. If the constraint is violated, the project cannot be scheduled to finish by the due time.

The latest time table shows some of the calculations for the example. The process begins with the largest indexed node and ends at node 1.

 Latest Time Table

For hand calculations it is convenient to work directly on the project network. In this presentation below we find the latest start and finish times.

 Solving for the Latest Times

By solving the two sets of equations we have four numbers for each node (or activity) indicating the earliest and latest start and finish times. With these we will identify the critical activities.

 Critical Path

Given the results of the last two sections, we compute two slack times for each node. The total slack for a node is the maximum its start time can be delayed without delaying the completion time of the project. The free slack for a node is the maximum that its start time can be delayed without delaying any of its successor nodes.

Slack times are computed from the early and late times. Click the icon to see the example.

 Slack Times

The critical path is the set of nodes (or activities) that have the minimum total slack time. When the latest time for the end node is selected as the earliest completion time for the project, the minimum slack value is zero.

Click the icon to see a movie that shows the determination of the critical path. For the example, the minimum total slack time is zero.

 Construction of the Critical Path

The nodes on the critical path define a path through the project network. In the terms of network analysis this is the longest path.

 The Critical Path

The Project Management add-in computes the earliest and latest time automatically. The link below shows the results for the example. The column labeled Slack shows the total slack. Free slack is not computed by the add-in.

 Schedules

This lesson describes how to construct two schedules for the project. One has all the activities scheduled as early as possible. Click the icon to see the early-start schedule.

 Early-Start Schedule

The other has the activities scheduled as late as possible. Click the icon to see the late-start schedule.

 Late-Start Schedule

What about schedules somewhere between these two limits? The slack times give some ideas about possible variations, but the changes described by the slack times concern only the modification of a single activity. Delaying or lengthening an activity within the free slack time only affects the schedule of that activity. When the delay is greater the free slack but less than the total slack, the schedules of other activities are also affected.

Knowing the critical activities is important to the managers of a project. They can take action to assure that all the means of production are ready to go when a critical activity is ready to begin. While the activity is under way, all necessary resources should be available throughout the activity duration so that it is finished on or before its planned finish time. A delayed critical activity means that the project completion is delayed. But what about the non-critical activities? They certainly cannot be neglected. Even if there is slack, unplanned delays will often cause activities to become critical. The next lesson involves uncertainty in activity durations when the length of the critical path is a random variable and the identity of the critical activities is uncertain.

 Summary
 Critical Path Summary

Engineering Finance
by Paul A. Jensen