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 ongoing 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
paththe 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 addin. 

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 addin 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 noncritical 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.
The assigned text develops the critical
path method for the activityonnode (AON) model. Section
9.6 describes the activityonarc (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.


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 addin. To clarify the discussion, not all
of the columns used by the addin 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 noncritical activities
are maroon. Placing the critical bars end to end, results in
a solid red line, while the noncritical 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 noncritical activities show a black as well as a maroon
bar. The black bars show how much each of the noncritical 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
noncritical activity use the same limited resource, a better schedule
might result if the noncritical 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.
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.
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.
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.


Project Addin 

The Project Management addin 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 addin.


Project Management
Addin Solution 




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 earlystart schedule.
The other has the activities scheduled
as late as possible. Click the icon to see the latestart 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 noncritical 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 


Return to Top of Page 