CONTENTS 1.0 Introduction
2.0 Intended Learning Outcomes 4.0 Main Content
3.1 Historical Background
3.2 Methodology of CPA and PERT 3.3 Notation and Construction 4.0 Conclusion
5.0 Summary
6.0 Self-Assessment Exercises 7.0 References/Further Reading
1.0 INTRODUCTION
Network model is a powerful tool in the management of projects, particularly those consisting of large number of activities related in complex ways. Most realistic projects that organisations undertake are large and complex. Almost every industry worries about how to manage their large-scale and complicated projects effectively. Drawing a network model provides a visual display of these relationships concerned and a way of answering various questions about the project. Programme Evaluation and Review Techniques (PERT) and the Critical
Path Analysis (CPA) are two popular techniques that help managers
plan, schedule, monitor and control large and complex projects. Some common application of network analysis occurs in project scheduling for:
CIT907 ADVANCED OPERATION RESEARCH
167 Construction
Engineering Manufacturing
The management of administrative systems.
2.0 INTENDED LEARNING OUTCOMES At the end this unit, you should be able to:
define a network model
explain what a project is
differentiate between Programme Evaluation and Review Techniques (PERT) and the Critical Path Analysis (CPA)
3.0 MAIN CONTENT 3.1 Historical Background
A basic form of network model was being used in the mid 1950 s in an attempt to reduce project times. In 1958 , the US Naval special project office set up a team to devise a technique to control the planning of complex projects. The outcome of the team‟s efforts was the development of the network known as PERT (Programme Evaluation and Review Technique). PERT was used to plan and control the development of the Polaris missile and was credited with saving two years in the missile‟s development. Since 1958 , the technique has been developed and nowadays network model is operated in various forms under a number of titles which include the following:
Critical Path Method (CPM )
Programme Evaluation and Review Technique (PERT)
Critical Path Planning (CPP)
Critical Path Analysis (CPA)
Critical Path Scheduling (CPS)
Minimal Spanning Tree
Shortest routes problem, etc.
In this unit, we shall discuss the first two technique (i.e. CPA and PERT ).
3.2 Methodology of CPA and PERT
Using any of the above network techniques involves the following steps:
Define the project and all its significant activities.
Develop the relationship among the activities by deciding which activities must proceed and follow others.
Draw the network connecting all of the activities.
Assign time and/or cost estimates of each activity.
Compute the longest time path through the network (this is called the critical path).
Use the network to help plan, scheduled, monitor and control project.
Differences between CPA and PERT
CIT907 ADVANCED OPERATION RESEARCH
168
CPA PERT
It is a deterministic approach It is a probabilistic
technique which
allows us to find the probability that the entire project will finish at a given date.
Uses two-time estimates – Uses three-time normal time and crash time. estimate – optimistic
time, most likely time and pessimistic time.
3.3 Notation and Construction
(a)Activity
This is a task or job that consumes time or resources e.g.
„Verify debtors in a sales ledger‟; „Dig foundation‟; „Type report‟, etc.
The symbol used is an arrow
The head of the arrow indicates where the job ends and the tail where the job starts.
Dummy Activity
This is an activity that does not require time or resources. It is used merely to show logical dependencies between activities so as not to violate the rules of drawing networks.
The symbol used is an arrow with broken lines.
It should be noted that the method of network construction presented in this course material is “activity on the arrow” (the alternative is referred to as “activity on the node‟).
Event/Node
It is a point in time that marks the start or end of an activity. The symbol used is a circle with a number to locate its position.
Network
This is a combination of activities, dummy activities and events in a logical sequence according to the rules of drawing networks. See the example below of a network diagram.
Example of a Network Diagram
Rules for Drawing Network Diagrams
CIT907 ADVANCED OPERATION RESEARCH
169
A complete network should have only one point of entry (a start event) and only on point of exit (a finish event).
Every activity must begin with one tail event (predecessors) and end with one head event (successor).
A B Tail event
Head events C
A Tail events
B
Head event C
Note: An activity must not share the same head and tail event with other activity.
A Tail event
B
Head event
This is not allowed.
No activity can start until its tail event is reached.
A D
B F
C
E
CIT907 ADVANCED OPERATION RESEARCH
170
Event F cannot start until all activities ( D and E ) leading to it are completed.
Loops are not allowed. Loops are activities leading to the same event.
These are not allowed.
Dangling activities are not allowed; in other words, all activities must contribute to the Network diagram otherwise they are discarded as irrelevant.
Dangling
Network proceeds from left to right.
Note
Network diagram are not drawn to scale as arrows does not represent time elapse.
Arrows need not be drawn in the horizontal plane.
Events should be progressively numbered from left to right e.g. 0 , , 2 ,… or 0 , 10 , 20 , 30 ,…etc.
Activities can be identified by their:
Short description e.g. Type a report.
Alphabetic or numeric code e.g. A , B , C ,… or 1, 2 , 3 ,…
Tail and head events numbers e.g. 1 - 2 , 2 - 3 , 3 - 5 ,etc.
Use of Dummy Activities
Dummy activities are merely used to complete a network diagram, for a good logical relationship.
EXAMPLE 1
Assume that part of the network involves a car arriving at a service station during which two independent activities take place: „filling with petrol‟ ( A) and „topping up with oil‟ (B) . This could be shown thus:
(Incorrect)
Note: This is wrong because it contravenes rule II . By the use of a dummy activity it could be shown thus:
CIT907 ADVANCED OPERATION RESEARCH
171
A
B Or,
B A
EXAMPLE 2
This illustration is wrong.
This illustration is correct.
Now, we can give illustration on how to draw Network diagram EXAMPLE 3
A project consists of the following activities as tabulated below:
Activity Preceding Activity
A -
B -
C -
D A
E A
F B
G B
H C , F
I D , G , H
CIT907 ADVANCED OPERATION RESEARCH
172 Required
Construct the network of the above project using activity-on-arrow diagram.
SOLUTION Stage 1
The first three activities A , B and C start the event of the network diagram because nothing precedes them. Thus, we have:
A B C Note
The order of arrangement is not important. This may change in the course of during the complete diagram.
Stage 2
Case 1: Activities D and E preceded by activity A . Or,
Case 2: Activities F and G are preceded by activity B .
These two events are independents. That is, there drawing does not affect one another.
Thus, we have:
D E A
F
B C
Note G
Also the position of D and E can be interchanged depending on the relationships that may exist further.
Similarly, F and G . Stage 3
Activity H is preceded by activities C and F . This implies that C and
CIT907 ADVANCED OPERATION RESEARCH
173
must end at the same point before H can start. This can be achieved in the diagram by drawing the arrows of C and F to meet at the same node, then the arrow of H then takes off.
Note that positions of G and F are interchange for proper connection.
D E A
B G
C
F H Stage 4
Activity I is preceded by activities D , G and H . This implies that D , G and H must end at the same point before I can start. This can be achieved drawing the arrows of D , G and H to meet at the same node, then the arrow of I is then drawn.
Thus:
E
A D
B G I
C F H
Note
Positions of D and E were interchanged for proper connection. Since dangling is not allowed in Network diagram, hence we have below a complete Network diagram to the problem.
2 E
6
A D
I
1 B G 5
3
CIT907 ADVANCED OPERATION RESEARCH
174
C FH
4
Note
a. The events have been numbered 1 7 with 1 as start event and as finish event.
The shape of the diagram does not matter but the logical arrangement must be correct.
Under examination condition, you are not expected to draw network diagram stage by stage as illustrated above; but a complete diagram is necessary. This is for illustration purpose. However, in drawing a network diagram, you will still have to go through those stages, but you need not break them down.
The various paths through the network are:
A E A D I B G I B F H I C H I
EXAMPLE 4
Activities necessary for test launch.
Activity Description Preceding
Label Activity
A Decide test market area -
B Agree marketing strategy -
C Agree production -
Specification
D Decide brand name B
E Prepare advertising plan A
F Agree advertising package E
G Design packaging D
H Production of test batch C
I Package and distribute G , H
J Monitor media support F , D
E F
A J
B D G I
CIT907 ADVANCED OPERATION RESEARCH
175 C
H
The various paths through the network are:
A E F J
B D G I
B D Dummy J
C H I
EXAMPLE 5
The network below shows a list of activities which must be done in order to complete a building project. The duration of each activity is in weeks.
3
6
7
9
2
3
6 11
3
4
1 8
5 8 5
4 3
2 5
6
10 4
5
4 3 7
Required
Identify all possible paths together with their duration through the network.
SOLUTION
Paths Duration
1. 1 2 4 7 10 11 4 4 3 5 5 21 2. 1 2 4 7 10 8 11 4 4 3 5 3 4 23 3. 1 2 4 5 7 10 11 4 4 5 6 5 5 29 4. 1 2 4 5 7 10 8 4 4 5 6 5 3 4
CIT907 ADVANCED OPERATION RESEARCH
176
11 31
5. 1 2 4 5 8 11 4 4 5 3 4 20 6. 1 2 4 5 9 11 4 4 5 6 2 21
7. 1 3 9 11 3 7 2 12
Paths Duration
1 3 6 9 11 3 6 3 2 14
1 5 9 11 8 6 2 16
1 5 8 11 8 3 4 15
1 5 7 10 11 8 6 5 5 24
1 5 7 10 8 11 8 6 5 3 4 26
Time Analysis
Critical Path/Time Determination ( CPA Method)
The critical path of a project or a network is the shortest time by which the whole project can be completed. In other words, it is the path of activities with the longest duration time. To determine the critical path, we use the following methods:
Calculating Earlier Start Time (EST) and Latest Start Time (LST) which employ the forward and backward pass
rule respectively. However, to be sure, you need to check that the measure called total float is equal to zero (we shall deal with this in later section)
Listing the possible paths in the network. The path with the longest duration is the critical path.
Calculating EST and LST
Each node is divided into three parts as shown below:
EST
D
EFT
ETT EHT
1 LST 2LFT
LTT LHT
Tail Time Head Time
Numbers 1 and 2 are the event numbers while D is the activity duration.
Earliest Tail Time [ETT] Earlier Start Time [EST] . Latest Tail Time [LTT] Latest Start Time [LST] . Earliest Head Time [EHT] Earlier Finish Time [EFT] . Latest Head Time [LHT] Latest Finish Time [LFT] .
CIT907 ADVANCED OPERATION RESEARCH
177 EXAMPLE 6
For the network diagram below use:
Forward and backward pass method, and
Possible routes method to calculate the critical path method.
Earliest Head Time [EHT] Earlier Finish Time [EFT] . Latest Head Time [LHT] Latest Finish Time [LFT] . SOLUTION
Forward Pass ( EST / EFT )
Note
a. Node 1 is the start of events. Activities A , B and C start the event simultaneously. We usually start at the Earliest [EST]
Time Zero [0] i.e. EST for activities A , B and C is 0 .
b. Node 2 is the end of event 1 (through A ) and the start of event 2 . Activities E and D will start after the completion of activity A . Therefore, EST for activities E and D is the EST of activity A plus the duration of activity A i.e. (0 5 5) .
c. Node 3 is the end of event 1 (through B ) and the start of event 3 . Activities G and F will start after the completion of activity B . Therefore, EST for activities G and F is the EST of activity B plus the duration of activity B i.e. (0 7 7) .
d. Node 4 is the end of event 1 (through C ) and event 3 (through
CIT907 ADVANCED OPERATION RESEARCH
178
F ). Activity H will start after the completion of activities C
and F . Note, however that these two activities might end at different times. If these occur, we select the maximum of these completion times. This will then be the EST for activity H .
Hence:
Completion time for activity C is:
EST for activity C plus duration of activity C i.e (0 8 8) .
Completion time for activity F is:
EST for activity F plus duration of activity F i.e (7 +6 = 13) .
The maximum is 13 . Therefore, the EST for activity H at node 4 is 13 .
e. Node 5 is the end of events 2 (through D ), 3 (through G ) and 4 (through H ). Activity I will start after the completion of activities D , G and H . Following the same procedure as in (d ) above, the EST for activity I is the maximum of the completion time for activities D , G or H .
Hence:
Completion time for activity D is:
EST for activity D plus duration of activity D i.e (5 + 8 = 13) .
Completion time for activity G is:
EST for activity G plus duration of activity G i.e (7 + 4 =11) .
Completion time for activity H is:
EST for activity H plus duration of activity H i.e (13 + 4 = 17) .
Of these, the maximum is 17 . Therefore, the EST for activity I at node 5 is 17 .
Node 6 is the end of project. Here, we talk of EFT [Earliest Finish Time].
Two activities ( E and I ) finished at node 6 . Following the same procedure as in (d ) above, the EFT at node
will be the maximum of the completion time for activities E or I . Hence:
Completion time for activity E is:
EST for activity E plus duration of activity E i.e (5 +10 = 15) .
Completion time for activity I is:
EST for activity I plus duration of activity I i.e (17 + 5 = 22) .
Of these, the maximum is 22 . Therefore, the EFT / project duration is 22 days.
Note
From the above diagram, you will notice that the EFT of an activity is the EST of the preceding activity.
Backward Pass ( LST )
CIT907 ADVANCED OPERATION RESEARCH
179
This time around, we start from the last event (node 6 ) backward.
Note
a. At Node 6 , the LFT is the same as the EFT . Therefore, LFT = 22 .
At Node 5 , the LST of activity I is LFT at Node 6 minus Duration of activity I i.e. (22 - 5 = 17) .
At Node 4 , the LST of activity H is LST at Node 5 minus Duration of activity H i.e. (17 - 4 = 13) .
At Node 3 , this is the LST for activities G and F . Since, we have more than one activity in this situation, the LST of the minimum of the two shall be consider.
LST at Node 3 through G is:
LST at Node 5 minus Duration of activity G i.e.
(17 - 4 = 13) .
LST at Node 3 through F is:
LST at Node 4 minus Duration of activity F i.e.
(13 - 6 = 7) .
Of these, 7 is the least. Therefore, the LST at Node 3 is 7 .
At Node 2 , this is the LST for activities D and E . Using the same procedure as in (d ) above:
LST at Node 2 through D is:
LST at Node 5 minus Duration of activity D i.e.
(17 - 8 = 9) .
LST at Node 2 through E is:
LFT at Node 6 minus Duration of activity E i.e.
(22 -10 = 12) .
Of these, 9 is the least. Therefore, the LST at Node 2 is 9 .
At Node 1, this is the LST for activities A , B and C . Using the same procedure as in (d ) above:
LST at Node 1 through A is:
LST at Node 2 minus Duration of activity A i.e.
(9 - 5 = 4) .
LST at Node 1 through B is:
LST at Node 3 minus Duration of activity B i.e.
(7 -7 = 0) .
LST at Node 1 through C is:
LST at Node 1 minus Duration of activity C i.e.
CIT907 ADVANCED OPERATION RESEARCH
180 (13 - 8 = 5) .
Of these, 0 is the least. Therefore, the LST at Node 1 is 0 . Note
The LFT of an activity is the same as the LST of the preceding activity.
Combined Diagram showing forward and backward Pass
The critical paths are paths that gave equal EST / EFT and LST / LFT which are:
B G I B F H I C H I .
Possible Path Method
From the diagram, the possible paths with duration are:
Paths Duration
A E 5 10 15
A D I 5 8 5 18
B G I 7 4 5 16
B F H I 7 6 4 5 22
C H I 8 4 5 17
The critical paths are path(s) with the highest duration i.e.
B F H I . Float or Spare Time
CIT907 ADVANCED OPERATION RESEARCH
181
Floats are spare time (idle time or unused time) available on non-critical activities.
Activities on the critical paths always have zero (0) or no float.
Types of Float
There are three types of float. They are:
Total float Free float
Independent float.
Total Float
This is the amount of time a path of activity could be delayed without affecting the overall project duration. The measure is as follows:
Total float (TF) =LFT - EST - D .
Free Float
This is the amount of time an activity can be delayed without affecting the commencement of a subsequent activity at its Earliest Start Time, but may affect float of previous activity.
The measure is as follows:
Free float (FF) = EFT - EST - D .
Independent Float
This is the amount of time an activity can be delayed when all preceding activities are completed as late as possible and all succeeding activities are completed as early as possible. The measure is as follows:
Independent float (IF ) = EFT - LST - D . EXAMPLE 7
With reference to Example 4 , calculate the total float, free float and independent float for each of the activity.
SOLUTION
Activity D EST LST EFT LFT TF FF IF
Duration
A 5 0 0 5 9 4 0 0
B 7 0 0 7 7 0 0 0
C 8 0 0 13 13 5 5 5
D 8 5 9 17 17 4 4 0
E 10 5 9 22 22 7 7 3
F 6 7 7 13 13 0 0 0
G 4 7 7 17 17 6 6 6
H 4 13 13 17 17 0 0 0
I 5 17 17 22 22 0 0 0
Visual Representation of Floats Consider the following activity P :
12
P
22
10 11
15 5 24
CIT907 ADVANCED OPERATION RESEARCH
182 12 13 14 15 16 17 18 19
2
0 21 22 23 2 4 Da
y
Maximum Time
Available
Minimum Time
Available
P
Total
Float
(5 days)
(24-12-5)
P
Free
Float (5 days) (22-12-5) Independent
Float
P
(5
days)
It can be seen that total float is seven days, free float is five days and independent float is two days.
Project Time Reduction
One important aspect of project management is looking at ways of reducing the overall project time at an acceptable cost. Where an activity involves some chemical process, it may be impossible to reduce the time taken successfully, but in most other activities the duration can be reduced at some cost. Time reduction may be achieved by using a (different) machine, adopting a new method of working, allocating extra personnel to the task or buying in a part or a service. The minimum possible duration for an activity is known as the crash duration.
Considerably, care must be taken when reducing the time of activities on the network to make sure that the activity time is not reduced by so much that it is no longer critical. New critical paths will often arise as this time reduction exercise continues.
The project given in the table
below will have a critical
path consisting of
activities A and D , a project
time of 18 days and a cost of
#580 if the normal activity
times are used as shown in
the figure below.
CIT907 ADVANCED OPERATION RESEARCH
183
Activity Duration Preceding Cost Crash Crash (Days) Activities (#) duration cost
(Days) (#)
A 8 - 100 6 200
B 4 - 150 2 350
C 2 A 50 1 90
D 10 A 100 5 400
E 5 B 100 1 200
F 3 C , E 80 1 100
Cost = N580 .
Since cost is likely to be of prime importance in deciding whether or not to take advantage of any feasible time reductions, the first step is to calculate the cost increase per time period saved for each activity. This is known as the slope for each activity.
For activity A , this would be: Increase in cost Decrease in time 100/2= 50 .
The slopes for each activity are shown in the table below:
Activity A B C D E F
Slope 50 100 40 60 25 10
A second step is to find the free float time for each non-critical activity.
Free float times are shown in the table below:
Activity EFT EST D Free float
B 4 0 4 0
C 10 8 2 0
E 10 4 5 1
F 18 10 3 5
To reduce the project time, select that activity on the critical path with the lowest slope (here, A ) and note the difference between its normal duration and its crash duration (here, 8 - 6 = 2 ). Look for the smallest (non-zero) free float time (here, 1 for activity E ), select the minimum
of these two numbers and
reduce the chosen activity by this
amount (here,
now has a reduction of
7 ).
Cost will increase by the time
reduction multiplied by the
slope (1 50) .
It is now necessary to
reconstruct the network as
shown in figure below.
CIT907 ADVANCED OPERATION RESEARCH
184
The procedure is now repeated and the new free float times are shown in the table below.
The activity on the critical path with the lowest slope is still A , but it can only be reduced by one further time period. If this is done, we have the situation shown in the figure below:
Activity EFT EST D Free
float
B 4 0 4 0
C 9 7 2 0
E 9 4 5 0
F 17 9 3 5
Crash duration
Critical path: A D .
Cost #630 ( 1 #50 ) #680 .
Any further reduction in the project time must involve activity D , since activity A is now at its crash duration time. If we reduced activity D to six days (i.e. 10 - 4 ), we have the situation shown in figure below:
CIT907 ADVANCED OPERATION RESEARCH
185
There are now two critical paths through the network and thus for any further reduction in the project time, it will be necessary to reduce both of these by the same amount. On the original critical path, only activity
can be reduced and only by 1 time period at a cost of #60 . For the second critical path, the activity with the lowest slope is F , at a cost of #10 . If this is done, we have the situation in figure below:
There are number of variations on this type of cost reduction problem and again, we have just tried to illustrate the general principles.
Uncertainty
So far, in all our calculations, we have assumed a certainty about the time required to complete an activity or activities. In practice, there will always be some uncertainty about the times taken by future activities. It is known that many activities are dependent upon the weather, and the element of chance is to be expected e.g. when building a wall or completing a long sea journey.
CIT907 ADVANCED OPERATION RESEARCH
186
Other types of activity are also subject to uncertainty. How certain can we be, that new software will work or be understood first time? How certain can we be, that the response rate will allow interviewing to be completed in an exact time?
To manage this uncertainty, we work with three estimates of time: Optimistic, Most likely and Pessimistic. Activity time is usually assumed to follow the beta distribution (which need not concern us too much, here). The mean and the variance for each activity given the three time estimates and the assumption of the beta distribution is:
Mean
O 4M P
. 6
Variance 2
O P
2
. 6
Where O is the optimistic time, M is the most likely time and P is the pessimistic time.
However, when managing a project, we are particularly interested in the overall duration, which is the sum of individual activity times. The sum of activity times (which individually follow the beta distribution) follows the normal distribution – an important statistical result. If we now consider the critical path:
The mean = the sum of activity means The variance = the sum of activity variances
An example is given in the table below where the critical path is given by the activities A , D , H and K .
The mean of the critical path is 21.666 and the variance 2
2.694 .
The standard deviation is 1.641.
Activity Optimistic Most Pessimistic Mean Variance
(O) likely (P)
(M )
A 8 10 14 10.333 1.000
D 3 4 6 4.167 0.250
H 2 3 6 3.333 0.444
K 1 3 7 3.333 1.000
21.166 2.694
We are now able to produce a confidence interval (and make other probability statements).
The 95% confidence interval for the total project time (activities A , D ,
and K ):