Module 9. Project planning and network analysis

Lesson 20

CRITICAL PATH METHOD (CPM)

20.1 Introduction

After the project network plan is constructed and activity times are known, the time analysis of the network becomes essential for planning various activities of the project as well as obtaining answers to questions like when the various activities are scheduled to be performed, how long it will take the project work to be completed and what are the crucial activities. In this lesson we will learn about computation of time estimates and determination of critical path.

20.2 Time Estimate Analysis

Time estimates analysis is a critical path in network analysis once the network of a project is constructed. Time analysis of network becomes essential for planning various activities of the project. An activity time is a forecast of the time and activity expected today from its starting point to it completion point (under normal conditions). The main objective of time analysis is to prepare a planning schedule of a project. Planning schedule should include the following factors.

i) Total completion time of the project.

ii) Earliest time and each activity start.

iii) Latest time each activity can be started without delaying the total project

iv) Float for each activity i.e. the amount of time by which the completion of an activity can be delaying the total project completion

v) Identification of critical activities and critical path.

20.3 Basic Notations

The following notations for basic scheduling computations will be used

(  i−j)	=	Activity (i, j ) with tail event i and head event j.
TE or Ei	=	Earliest occurrence time of event (j).
TL or Lf	=	Latest allowable occurrence time of event (j).
Di j	=	Estimated completion time of activity (i, j).
(ES) i j	=	Earliest starting time of activity (i, j)
(Ef) i j	=	Earliest finishing time of activity (i, j).
(Ls)i j	=	Latest start time for activity (i, j).
(Lf) i j	=	Latest finish time for activity (i, j).

20.4 Forward Pass Computation (For Earliest Event Time)

Before starting computations, the occurrence time of the initial network event is fixed. The forward pass computation computes the earliest start time (E_s) and earliest finish time (E_f) for each activity. The earliest time indicates the earliest time that a given activity can be scheduled and   earliest finish time indicates the time by which the activity can be completed at the earliest. This is done in following  three steps:

Step 1:  The computations begin from the start node and move towards the end node. For the convenience in the forward pass computation start with an assumed earliest occurrence time equal to zero for the initial project events i.e. E₁=0

 Step 2: i) Earliest starting time of activity (i, j) is the earliest event time of the tail event i.e.

              ii)  Earliest finish time of activity (i, j) is the addition of earliest starting time and the activity time i.e.

Step 3: Earliest event time for activity j is the maximum of the earliest finish time of all activities ending into that event. That is

The computed values of E_i are put over the respective circles representing each event.

20.5 Backward Pass Computations (For latest allowable time)

The idea of the backward pass is to compute the latest allowable times of starting and finishing of each of the activities of a project without delaying the completion of the project. These can be computed by reversing the method of calculation used for earliest event time. This is done by using following steps

Step 1: For ending event it is presumed that E = L where all E’s are computed by previous method.

Step 2: Latest finish time for activity (i, j) is equal to the latest event time of event j. i.e., (L_f) _ij=L.

Step 3: Latest starting time for activity (i, j) is equal to latest completion time of (i, j) minus activity time (Ls)_ij = (L_f)_ij – D_ij

Step 4: Latest event time for event i is a minimum of the latest start time of all activities originating from that event.

All the computed L values are put over respective circles representing each event.

20.6 Determination of Floats and Slack Times

When the network diagram is completely drawn, properly labeled and earliest (E) and latest (L) event times are computed, the next objective is to determine the floats and slack times defined as follows. There are three kinds of floats as given below :

20.6.1 Total float

The amount of time by which the completion of an activity could be delayed beyond the earliest expected completion time without affecting the overall project duration time. In other words, total float of an activity (i-j) is the difference between latest start time and earliest start time of that activity. Hence total float for activity (i-j) , denoted by  (T_f )_ij is given as

(T_f)_ij = (Latest start-Earliest start) time for activity (i-j)

(T_f)_ij = (L_s)_ij – (E_s)_ij = (L_f – D_ij) - E_i

It refers to the amount of free time associated with an activity which can be used before, during or after the performance of this activity. This is the most important type of float because this is concerned with the overall project duration. Total float on critical activities is always taken as zero. The value of total floats for any activity is useful for drawing the following conclusions.

20.6.2 Free float

The time by which the completion of an activity can be delayed beyond the earliest finish time without affecting the earliest start of a subsequent (succeeding) activity. This is that value of the float which is consumable when the succeeding activities are started at their earliest starting times. Mathematically, free float for activity (i-j) denoted by (F_f)_ij is calculated as   (F_f)_ij = (E_j – E_i) –D_ij

Free float for (i-j) = (Earliest time for event j – Earliest time for event i) – Activity time for (i-j).Thus free float is concerned with the commencement of subsequent activity.

(T_f)_ij = (L_j− E_i) - D_{ij  ,}but L_j ≥ E_i as latest event time is always greater than equal to earliest event time. Therefore for all activities free float can take values from zero up to total float but will not exceed total float. Free float is always useful for rescheduling the activities with minimum disruption of earliest plan.

20.6.3 Independent float

The amount of time by which the start of an activity can be delayed without affecting the earliest start time of any immediately following activities, assuming that the preceding activity has finished at its latest finish time. Mathematically, independent float of an activity (i ,j) denoted by (I_f)_ij can be calculated by the formula (I_f)_ij = (E_j – E_i) – D_ij. The negative independent float is always taken as zero. This float is concerned with prior & subsequent activity. The independent float thus provides a measure of variation in starting time of a job without affecting preceding and succeeding activities.

Note:

· It can be observed that Independent float ≤ Free float ≤ Total float.

· The concept of float is useful for the management in representing underutilized resources and flexibility of the schedule and the extent to which the resources will be utilized on different activities.

· Float can be used for redeployment of resources to label the same or to reduce the project duration. Whenever a float in a particular activity is utilized the float of not only that activity but that of other activities would also change.

20.7 Slack of an Event

The basic difference between slack and float times is that slack is used for events only whereas float is applied for activities. For any given event, the event slack is defined as the difference between the latest event and earliest event times. Mathematically,  for a given activity (i-j)

Head event slack = L_j – E_j and Tail event slack = (L_i – E_i)

All the floats defined earlier can be defined in terms of head or tail events slack as under:

Total float = L_j – E_i – D_i

Free float = (E_j – E_i – D_ij) = (L_j – E_i – D_ij) – (L_ij – E_ij) = Total float – Head event slack

Independent float =E_j – L_i – D_ij= (E_j – E_i – D_ij)–(L_i–E_i) = Free float – Tail event slack

20.8 Determination of Critical Path

After determining the earliest and latest scheduled times for various activities, the next step is to find the minimum time required for the completion of whole project. Before defining this let us first discuss about the meaning of critical event and critical activity.

20.8.1 Critical event

The slack of an event is the difference between latest and earliest event time i.e. Slack (i) = L_i – E_i. The event with zero slack time is called critical event. In other words, the event (i) is said to be critical when L_i = E_i

20.8.2 Critical activity

Since the difference between the latest Start time & earliest start time of an activity is usually called as total float. Activity with zero total float are known as critical activities. In other words, an activity is said to be critical if its delay in its start will cause a further delay in the completion date of entire project.

20.8.3 Non-critical activity

A non-critical activity is such that the time between its earliest start and its latest completion date is longer than its actual duration.

20.8.4 Critical path

The sequence of critical activity in a network is called a critical path. This path is the longest path in the network from the starting event to the end of event and defines the minimum time required to complete the project. The term path is defined as a sequence of activities such that it begins at the starting event and end at the final event. The length of the path is the sum of the individual time of the activities lying on the path. If the activities on critical path are delayed by a day, the project would also be delayed by a day unless the time of the future critical activity is reduced by a day by different means. The critical path is denoted by double or darker lines in order to distinguish from the other non critical path.  

20.8.4.1 Main features of critical path

· If the project has to be shortened then some of the activities on that path must also be shortened. The application of additional resources on other activities will not give the desired results unless that critical path is shortened first.

· The variation in actual performance from the expected duration time will be completely reflected in one to one fashion in anticipation completion of the whole project.

· It plays an important role in scheduling and controlling large projects.

· It identifies all the critical activities of the project.

The computation procedure used for the time analysis of the project is described in the examples 1and 2

Example 1

Draw a network diagram of the following schedule of activities and find its critical path. Also calculate slack time for each event

Activity	1-2	1-3	1-4	2-6	3-7	3-5	4-5	5-9	6-8	7-8	8-9
Duration (in days)	2	2	1	4	5	8	3	5	1	4	3

Solution

First construct the network diagram which is depicted in fig. 20.1

Fig. 20.1 Network diagram

To determine the critical path, compute the earliest start E_i and latest finish L_j for each activity  (i, j)

Forward Pass Computation (For earliest time event): As shown in fig. 20.1 assuming E₁=0 and E₂=E₁+D₁₂=0+2=2, E₃=E₁+D₁₃=0+2=2 and E₄=E₁+D₁₄=0+1=1

E₆=E₂+D₂₆=2+4=6, E₇=E₃+D₃₇=2+5=7

From this computation it can be inferred that this project will take 15 days to complete.

Backward Pass computations (For latest allowable time): In backward computation method assign the latest allowable time determined in forward pass computation method i.e. put L₉=15

L₈=L₉-D₉₈=15-3=12, L₆=L₈-D₈₆=12-1=11, L₇=L₈-D₈₇=12-4=8 

L₅=L₉-D₉₅=31-6=25,

L₄=L₅-D₅₄=10-3=7 L₂=L₆-D₆₂=11-4=7

The path 1-3-5-9 is the critical path which is shown in Fig. 20.1 with double lines joining all those events where E_i=L_j The total duration of project is equal to 2+8+5=15 days

Computation of Float: For each non –critical activity, the total float, free float and independent float calculations are given Table 20.1

Table 20.1 Calculations of time estimates and floats

Activity (i-j) (1)	Duration Dij (2)	Start		Finish		Float
		Earliest (3)	Latest  (4)=(6)−(2)	Earliest  (5) = (3) + (2)	Latest (6)	Total (7) =(4) - (3)	Free (8) =(5) - (3) -(2)	Independent (9)= (8) - [(3)-(2)]
1-2	2	0	5	2	7	5	0	0
1-3	2	0	0	2	2	0	0	0
1-4	1	0	6	1	7	6	0	0
2-6	4	2	7	6	11	5	0	0
3-7	5	2	3	7	8	1	0	0
3-5	8	2	2	10	10	0	0	0
4-5	3	1	7	4	10	6	6	0
5-9	5	10	10	15	15	0	0	0
6-8	1	6	11	7	12	5	4	0
7-8	4	7	8	11	12	1	0	0
8-9	3	11	12	14	15	1	1	0

Example 2

Draw the network diagram for the following project and find the critical path and maximum time for completion of the project.

Activity

A

B

C

D

E

F

G

H

I

J

K

L

Preceded by

-

A

A

B

B

C

C

F

D

G, H

E

I

Duration (weeks)

10

9

7

6

12

6

8

8

4

11

5

7

Solution

Network diagram of the above problem is shown in Fig. 20.2.

Fig. 20.2 Network diagram 

To determine the critical path, compute the earliest start E_i and latest finish time L_j for each activity (i,j).The calculations are given below

Forward Pass Computation (For earliest time event): As shown in fig 20.2 assuming E₁=0 and E₂=E₁+D₁₂=0+10=10, E₃=E₂+D₂₃=10+9=19, E₄=E₂+D₂₄=10+7=17, E₅=E₃+D₃₅=19+6=25, E₆=E₃+D₃₆=19+12=31, E₇=E₄+D₄₇=17+6=23,

E₉=E₅+D₅₉=25+4=29,

From this computation it can be inferred that this project will be completed in 42 weeks.

Backward Pass computations (For latest allowable time): In backward computation method assign the latest allowable time determined in forward pass computation method i.e. put L₁₀=42

L₉=L₁₀-D₁₀₉=42-7=35, L₆=L₁₀-D₁₀₆=42-5=37, L₈=L₁₀-D₁₀₈=42-11=31,

L₅=L₉-D₉₅=35-4=31, L₇=L₈-D₈₇=31-8=23

L₁=L₂-D₂₁=10-10=0 

The path 1-2-4-7-8-10 is the critical path which shown in Fig. 20.2 with double lines joining all those events where E_i=L_j The total duration of project is equal to 10+7+6+8+11=42 weeks

Activity (i-j) (1)	Duration Dij (2)	Start		Finish		Float
		Earliest (3)	Latest (4) = (6)−(2)	Earliest (5) =(3)+(2)	Latest (6)	Total (7) =(4) - (3)	Free (8)=  (5) -(3) - (2)	Independent (9)= (8) - [(3)-(2)]
A(1-2)	10	0	0	10	10	0	0	0
B(2-3)	9	10	16	19	25	6	0	0
C(2-4)	7	10	10	17	17	0	0	0
D(3-5)	6	19	25	25	31	6	0	0
E(3-6)	12	19	25	31	37	6	0	0
F(4-7)	6	17	17	23	23	0	0	0
G(4-8)	8	17	23	25	31	6	6	0
H(7-8)	8	23	23	31	31	0	0	0
I(5-9)	4	25	31	29	35	6	2	0
J(8-10)	11	31	31	42	42	0	0	0
K(6-10)	5	31	37	36	42	6	6	0
L(9-10)	7	29	35	36	42	6	6	0

20.9  Critical Path Method (CPM)

Critical Path Method (CPM) , was developed by M.R.Walker and J. E. Kelly. They came up with arrow diagram as the most logical representation of the interrelationships between the jobs in a project to be executed in a well defined sequence. The arrow diagram designed by them, as well as the method of calculating the critical path are the same as in PERT network, except that they used the single time estimate and did not enter the problem of uncertainty of the duration of time for the individual jobs.

CPM emphasizes the relationship between applying more men or other resources to shorten the duration of given jobs in a project and the increased cost of these additional resources. With CPM the amount of time needed to complete various parts of the project is assumed to be known with certainty. Moreover, the relation between the amount of resources employed and the time needed to complete the project is also assumed to be known. The interactive procedure of determining the critical path involves the following steps:

i) Break down the project into various activities systematically. Label all activities. Arrange all the activities in logical sequence. Construct the arrow diagram.

ii) Number all the nodes (events) and activities. Find the time for each activity considering it to be deterministic. Indicate the activity times on the arrow diagram.

iii) Calculate earliest start time, earliest finish time, latest start time and latest finish time. Tabulate activity normal times, earliest time and latest time.

iv) Determine the total float for each activity by taking difference between the earliest time and the latest time for each node.

v) Identify the critical activities (the activities with zero float) and connect them with the beginning node and the ending node in the network diagram by double line arrow. This gives the critical path.

vi) Calculate the total project duration.