Critical Path Analysis

Critical Path Analysis
For large projects where there are many activities which must be done in sequence we use Critical Path
Analysis (CPA).
It is used as:
1. A housekeeping method
2. An estimation of the duration of a project
3. An identification of critical activities. i.e. it identifies those activities that matter to the project as a
whole if they are delayed.
Project Scheduling consists of three basic phases:
1. Planning
2. Scheduling
3. Controlling
Planning Phase
The project is broken down into distinct activities. e.g. For the building of a house the project could be
broken down as follows:
1. Buy site
2. Obtain planning permission
3. Lay foundations
4. Hire tradesmen to complete building
The time estimates for each activity in a project are determined as well as a precendence relationship, (we
need a site before we lay foundations etc...). A network or arrow diagram is then constructed, according to
the following rules, which is used to develop a schedule for the project.
Rules for drawing a network
Rule 1
Each activity is represented by one and only one arc in the Network
The following are not allowed:
• An activity with more than one arc
• An arc with more than one activity
Rule 2
No two activities can have the same start and finish node. The reason for this is that an activity
is uniquely identified by its start and end nodes.
To overcome this problem Dummy Activities are introduced. A dummy activity does not consume
time or resources. Dummy activities are used to establish logical sequence.
Rule 3
When the network is complete there must be some path from every node to the finish.
1

---

General Note:
To ensure the correct precedence relationship in the network diagram, the following questions must be
answered as each activity is added to the network.
• Are all activities that must be completed before this activity is commenced actually complete?
• What are the activities that must follow this activity?
• What activities must occur concurrently with this activity?
This completes the planning phase.
Scheduling Phase
The object of this phase is to construct a chart showing the start and finish times of each activity and
their interdependence with each other in the project. It is also necessary to find critical activities for the
completion of the project on time.
We also calculate the amount of slack or float times available to other
activities.
An activity is said to be critical if a delay in its start will cause a delay in the completion of the project
as a whole. A non critical activity is such that the time between its earliest start and its latest completion
dates is longer than its actual duration. this difference gives rise to slack or float time.
Numbering the nodes in a network
1. Count the number of nodes in the network, n.
2. Label the end node n-1.
3. Put the lengths on all of the arcs coming into this node.
4. Find the next node with only incoming unlabeled arcs and label that node. All the outgoing arcs are
going to be labeled arcs.
5. Repeat number 4 until all arcs have been labeled.
Calculating earliest start of nodes
1. Base case - boundary condition - ES(project) = 0.
2. Recursive procedure - ES(P articula N ode) = M ax[ (ES(P revious N ode)+D(i → j)] over all incoming
arcs.
This procedure defines ES(j) in terms of ES(i) s so we must know the ES(i) s before ES(j) can be found.
Dijis the duration of activity (i, j). The earliest starting calculations can be obtained from the algorithm
ESj = M ax(ESi + Dij)
For the network diagram we look at the arrows going INTO a node. Each node can only start when ALL
the activities going into it have been completed.
To find the Critical Activities we backtrack through the ES times.
The latest completion times are also important to ensure when an activity can finish without delaying
the end of the project as a whole. They can also be used to verify the Critical Path.
LCj =Latest completion time for all activities coming into node j.
The algorith for the latest completion times is:
LCi = M in(LCj − Dij)
We start at the end node and backtrack.
As the last node is the starting node this must finish at zero.
We can now check our critical path by combining the results of the two algorithms.
An activity is on the critical path if the following three conditions are satisfied:
2

---

1. ESi = LCi
2. ESj = LCj
3. ESi − ESj = LCj − LCi = Dij
The critical path represents therefore the shortest duration needed to complete the project and must form
a chain of connected activities from the start node to the end node.
Floats
We will now consider floats. They only applu to non-critical activities. There are two types of
floats:
1. Total Float (TF) - The amount of absorbtion possible by the project.
2. Free Float (FF) - The amount of absorbtion proosible by the activity.
The calculations are as follows:
T otal F loat = T F = LCj − ESi − Dij
F ree F loat = F F = ESj − ESi − Dij
Therefore Total Float is calculated by finishing the activity (i,j) as late as possible LCj and also starting
as early as possible ESi to get the maximum spread. We then subtract the actual length of time it takes and
we are left with the Total Float. If the activity lies on the Critical Path the Total Float will be zero. If an
activity is delayed by less than its total Float then the project will not be delayed. Free Float is calculated
on the basis of assuming that all activities start as early as possible.
In summary therefore we have the following
1. Total Float ≥Free Float always.
2. If the start of an activity is delayed by less than or equal to its Free Float then there is no rescheduling
necessary.
3. If the start of an activity is delayed by more that its Free Float but less than or eqyual to its Total
Float then the activities immediately afterwards will ahve to be rescheduled, but the project as a whole
will not be delayed.
4. If the delay is greater then the Total Float then rescheduling is necessary and the project will be
delayed.
The Critical Activities are those activities with both zero Total and Free Floats.
Construction of a Bar or Gannt Chart
These charts are used to move a non-critical activity between
its maximum allowable limits, using Total Floats, to lower the maximum resource requirments.
We construct the chart as follows:
1. Schedule the Critical Activities
2. Schedule the non-critical activities with respect to their earliest starting and latest completion times.
3. Put the duration of the activities on the chart.
The role of the Total and Free floats in scheduling the non-critical activities is explained in terms of two
general rules.
1. If the T F = F F the activity can be scheduled anywhere between ESiand LCj.
2. If the F F < T F the activity can be delayed relative to its ES by no more than the amount of its Free
Float without affecting the scheduling of its immediate succeeding activities.
3

---

Resource Levelling
Tis is used to develop a time schedule that will level the resource requirments during
the project. At present no algorithm exists so we just shuffle the activities by eye.
Cost Considerations in Project Scheduling
We define the cost-duration relationship for each activity
in the project.
The duration can be shortened by increasing the resources and therefore increasing the cost. At a certain
point known as the CRASH POINT no further reduction in duration is possible.
It is assumed that the
relationship between cost and duration is linear.
After defining the cost-duration relationships the activities of the project are assigned their normal
durations. The Critical Path is then calculated and the direct costs recorded. The next step is to consider
reducing the duration of the project by reducing the length of the Critical Path activities.
We do this by
looking at those activities having the smallest cost-duration slope first. We reduce this activity to its crash
point. We then compute the new costs and the new critical path. This new critical path may be different
from the previous one. We continue until all the Critical Activities are at their Crash times.
Probabilistic Activity Times
The preceding method assumed activity durations were known and not
subject to variation or else the network, critical path and floats would have to be recalculated.
Therefore
we require a probabilistic approach to take into account the fact that variability is often a factor.
It can be shown that the Beta Distribution is the best distribution to model activity duration.
This distribution has 3 paramaters:
a = OP T IM IST IC T IM E , i.e. if all goes well.
b = P ESSIM IST IC T IM E , i.e. if all goes badly.
m = M OST LIKELY T IM E , most probable amount of time that will be required.
In network analysis we are interested in the average or expected time for each activity, te, and the variance
of each activity σ2.
The expected time is computed as a weighted average of the above three time estimates as follows:
a + 4m + b
te =
6
and the variance is given by:
(b − a)2
σ2 =
36
The process for incorporating probability theory into network analysis is called PERT (Program Evalu-
ation and Review Technique).
The steps are as follows:
1. For each activity estimates of a, b,and m must be made.
2. teand σ2are calculated for each activity.
3. The critical activities and critical path are identified using tefor each activity
4. The expected project duration is calculated as the sum of all the t s on the critical path.
e
5. The variance of the project duration is calculated as the sum of all the σ2’s on the critical path.
6. The central limit theorem from mathematics is invoked to justify the assumption that the project
distribution is normally distributed.
7. Probabilistic statments about the project duration are made once the average and variance are known.
e.g. After 1 year it is estimated that the project has a 90% chance of being finished etc...
4

---

Example
Activity
Preceeded by
m
b
a
A
-
7
13
4
B
-
6
9
3
C
A
4
6
2
D
B
3
10
2
E
B
3
11
1
F
C,D
6
8
4
G
E
5
15
1
Calculate the probability of completing the project in less than 16 days
Calculate the mean and variance for all the activities
Activity
Preceeded by
m
b
a
te
σ2
A
-
7
13
4
7.5
2.25
B
-
6
9
3
6
1.00
C
A
4
6
2
4
0.44
D
B
3
10
2
4
1.78
E
B
3
11
1
4
2.78
F
C,D
6
8
4
6
0.44
G
E
5
15
1
6
5.44
Calculate the Earliest Starts
ES1 = 0
ES2 = M ax(ES1 + D12) = 7.5
ES3 = M ax(ES1 + D13) = 6
ES4 = M ax(ES2 + D24; ES3 + D34) = M ax(11.5, 10) = 11.5
ES5 = M ax(ES3 + D35) = 6 + 4 = 10
ES6 = M ax(ESs + D56; ES4 + D46) = M ax(10 + 6; 11.5 + 6) = 17.5
LC6 = ES6 = 17.5
LC5 = M in(LC6 − D56) = 11.5
LC4 = M in(LC6 − D46) = 11.5
LC3 = M in(LC4 − D34; LC5 − D35) = 7.5
LC2 = M in(LC4 − D24) = 7.5
LC1 = M in(LC2 − D12; LC3 − D13) = 0
F F (A) = ES2 − ES1 − D12 = 7.5 − 0 − 7.5 = 0
F F (B) = ES3 − ES1 − D13 = 6 − 0 − 6 = 0
F F (C) = ES4 − ES2 − D24 = 11.5 − 7.5 − 4 = 0
F F (D) = ES4 − ES3 − D34 = 11.5 − 6 − 4 = 1.5
F F (E) = ES5 − ES3 − D35 = 10 − 6 − 4 = 0
F F (F ) = ES6 − ES4 − D46 = 17.5 − 11.5 − 6 = 0
F F (G) = ES6 − ES5 − D56 = 17.5 − 10 − 6 = 1.5
5

---

T F (A) = LC2 − ES1 − D12 = 7.5 − 0 − 7.5 = 0
T F (B) = LC3 − ES1 − D13 = 7.5 − 0 − 6 = 1.5
T F (C) = LC4 − ES2 − D24 = 11.5 − 7.5 − 4 = 0
T F (D) = LC4 − ES3 − D34 = 11.5 − 6 − 4 = 1.5
T F (E) = LC5 − ES3 − D35 = 11.5 − 6 − 4 = 1.5
T F (F ) = LC6 − ES4 − D46 = 17.5 − 11.5 − 6 = 0
T F (G) = LC6 − ES5 − D56 = 17.5 − 10 − 6 = 1.5
Activity
ES
LC
Free Float
Total Float
A
0
7.5
0
0
B
0
7.5
0
1.5
C
7.5
11.5
0
0
D
6
11.5
1.5
1.5
E
6
11.5
0
1.5
F
11.5
17.5
0
0
G
10
17.5
1.5
1.5
Critical activities are A, C and F.
Expected Project Duration = 7.5 + 4 + 6 = 17.5
Variance of project = 2.25 + 0.44 + 0.44 = 3.13
P robability(days < 16) = P (Z < 16−17.5
√
) = P (z < −0.85) = 0.198
3.13
i.e. approx 20% of the time project will be < 16 days.
Z is the Standard Normal Random Variable.
This is based on the assumption that a Normal Distribution is followed by the estimating errors. In
general estimates are too optimistic, rather than too pessismistic.
To allow for this the curve may be deliberately skewed, using the following formula:
a + 3m + 2b
te =
6
using this formula we arrive with critical activities B, E and G. with an expected duration of 19.5 and
12.5% probability that the project will complete in less than 16 days. This is only as a point of comparisson,
we cannot calculate this with the Standard Normal Distribution becausew of the skewness.
Risk and Uncertainty
These are directly related to the differences between pessimistic and optimistic
times, b and a. If no uncertainty or risk exists then a = m = b and the standard deviation is 0.
Using PERT analysis we see that activities with a large standard deviation will have high uncertainty/risk.
The risk/uncertainty can be classified by the project manager as Low (L), Medium (M), and High (H). It
can be effected by any one of a numeber of causes, e.g. capability etc.
A simple guideline is
b − a
Risk R =
a
Low Risk R < 0.25
Medium Risk 0.25 < R < 0.5
High Risk R > 0.5
In our above example using these criteria, F is classified as Medium Risk whereas all the other activities
are given high risk.
Criteria for classifying Risks as High, Medium or Low
6

---

High
Cost:
• Requires outside resources at unknown cost
• No quotations available
• Lack of full definition therefore no accurate estimate available
Schedule:
• Extensive research required
• Extensive evaluation required
• Technical problems
• Lack of suitable personnel
• New type of tasks
• Facilities not yet available
• Personnel to be recruited
Technical:
• Research required
• No in house experience
• New technology required
• Approach to design uncertain
• Proper personnel availability uncertain
Medium
Cost:
• Within budget on similar projects
• Estimates based on extrapolations
Schedule:
• Research started
• Prototype development in progress
• Acceptable hardware available
• Acceptable Software available
• Some facilities to be modified
• Proper skills identified
Technical:
• State of art facilities
• Research in progress
• Capabilities available
• Technology being implemented or planned
• Some prior experience
7

---

Low
Cost:
• Good past history on similar jobs
• Under cost on similar jobs
• Reliable quotations received
• Multiple sources of supplies exist.
Schedule:
• Good past history on similar jobs
• Existing Hardware
• Existing Software
• Similar jobs performed below or within schedule
• Facilities committed
• Proper Personnel assigned
Technical:
• Research completed
• Technology demonstrated
• Proper personnel committee
• Extensive experience
• Prototype developed
• User as well as manufacturer
• Relevant performance data exists
8

---