**CRITICAL PATH METHOD (CPM)**

CPM was developed by E.I. duPont in 1957 and was first applied to construction and maintenance of chcm1cal plants. Since then, the use of CPM has grown at a rapid rate. There are computer programs to perform the calculations.

Let the project network be drawn. Then this method consists of two phases calculations. In Phase 1, which is also called forward pass, Earliest start times (ES) of all the nodes are calculated.

In Phase 2, which is also called backward pass, Latest finish time (LF) of all the nodes are calculated.

These two calculations are displayed in the network diagram in a two chamber boxes. Upper chamber represents LF and the lower one as ES.

The critical activities (i.e., ES = LF) are identified. The critical path is obtained by joining them using double arrow.

**Example 1** . A project schedule has the following characteristics :

Activity Time Activity Time

1-2 3 5-6 5

1-3 1 5-7 8

2-4 1 6-8 1

2-5 1 7-9 2

3-5 5 8-10 4

4-9 6 9-10 6

Draw the project network and find the critical path. Also calculate the total floats and free floats

** **

** **

** **

** **

ES_{1} = 0

ES_{2} = ES_{1} + t_{12} = 0 + 3 = 3

ES _{3} = ES _{1} + t _{13} = 0 + 1 = 1

ES_{4} = ES_{2} + t_{24} = 4

ES_{5} = Max. {ES_{3} + t_{35}, ES_{2} + t_{25}} = Max. {6, 4) = 6

ES_{6} = ES_{5} + t_{56} = 1 1

ES_{7} = ES_{5} + t _{57} = 14

ES_{8} = ES_{6} + t_{68} = 1 2

ES_{9} = Max. {ES_{4} + t_{49}, ES_{7} + t_{79}} = Max { 10, 16) = 16

ES _{1 0} = Max. {ES_{9} + t_{910}, ES_{7} + t_{810}} = Max. {22, 16) = 22

Set LF_{1 0} = ES_{10} = 22

LF_{9} = LF_{10} - t_{910} = 22 - 6 = 16

LF _{8} = LF _{10} - t_{81 0} = 22 - 4 = 18

LF_{7} = LF_{9} - t_{79} = 1 6 - 2 = 14

LF _{6} = LF_{8} - t_{68} = 1 7

LF_{5} = Min. {LF_{7} - t_{57}, LF_{6} - t_{56}} = Min. {6, 12} = 6.

LF_{4} = LF_{9} - t_{49} = 10

L F _{3} = LF _{5} - t_{35} = 1

LF_{2} = Min. {LF_{4} - t_{24}, LF_{5} - t_{25}} = Min. {9, 5 } = 5.

LF_{1} = Min. {LF_{3} - t_{13}, LF_{2} - t_{12}} = Min. {0, 2} = 0.

** **

** **

** **

Activity (i, j) Duration Total Float Free float

T _{ij} TF _{i j} FF _{ij}

1 - 2 3 2 0

1 - 3 . 1 0 0

2 - 4 1 6 0

2- 5 1 2 2

3 - 5 5 0 0

4 -9 6 6 6

5- 6 5 6 0

5 – 7 8 0 0

6 - 8 1 . 6 0

7 - 9 2 0 0

8 – 10 4 6 6

9 - 1 0 6 0 0

The critical path is 1- 3- 5- 7- 9- 10

**Example 2**. Consider the following informations :

Activity Immediate Duration

predecessors

A None 2

B None 3

c A 1

D B 4

E C, D 3

F D 1

G E 2

H F 3

Draw the project network and find the critical path.

**Solution**. The network is drawn below :

Set ES _{1} = 0

ES _{2} = ES_{1} + t_{12} = 0 + 2 = 2

ES _{3} = ES_{1} + t_{ 13} = 0 + 3 = 3

ES _{4} = ES_{3} + t_{34} = 3 + 4 = 7

ES _{5 }= Max. {ES_{2} + t_{25}, ES_{4} + t_{45}}

= Max {2 + 1, 7 + 0} = 7

ES _{6} = ES_{5} + t_{56} = 10

ES _{7}= ES_{4} + t_{47} = 8

ES _{8} = Max. {ES= + t_{68}, ES_{7} + t_{78}}

= Max {10 + 2, 8 + 3 } = 12

Set LF _{8} = ES _{8} = 12

LF _{7} = LF _{8} - t_{78} = 1 2 - 3 = 9

LF _{6} = LF _{8} - t_{68} = 12 - 2 = 1 0

LF _{5} = LF _{6} - t_{56} = 1 0 - 3 = 7

LF _{4} = Min. {LF_{5} - t_{54}, LF_{7} - t_{47} }

=Min. {7, 8} = 7

LF _{3} = LF _{4} -t_{34} = 7 - 4 = 3

LF _{2} = LF _{5} -t_{25} = 7 -1 = 6

LF _{1} = Min. {LF_{2} -t _{12}, LF_{3} -t_{13}}

=Min. {4, 0} = 0.

Thus the critical path is B-D-(dummy)-E-G.

**. PROGRAM EVALUATION AND REVIEW TECHNIQUE (PERT)**

PERT was originally developed in 1958 to 1959 as part of the Polaris Fleet Ballistic Missile Program of the United States' Navy.

The primary difference . between PERT and CPM is that PERT takes explicit account of the uncertainty in the activity duration estimates. CPM is activity oriented whereas PERT is event oriented. CPM gives emphasis on time and cost whereas PERT is primarily concerned with time.

In PERT, the probability distribution is specified by three estimates of the activity duration most likely duration (t111), an optimistic duration (t0) and a pessimistic duration (t _{p}). This type of activity duration is assumed to follow the beta distribution with and

Mean = to + 4 t m + 1 p/ 6

Variance = ( T _{p} – t _{0} /6 )_{2}

The network construction phase of PERT is identical to that of CPM. Furthermore, once mean and variance are computed for each activity, the critical path determination is identical to CPM. The earliest and latest event times for the network are random variables. Once the critical path is determined, probability statements may be made about the total project duration and about the slack at any event.

**Example 3.** A project consists of the following activities and different time estimates :

Activity t _{0 }t _{m }t_{p}

1-2 3 5 8

1 - 3 2 4 8

1 -4 6 8 12

2-5 5 9 12

3-5 3 5 9

4 -6 3 6 10

5-6 2 4 8

(a) Draw the network.

(b) Determine the expected time and variance for each activity.

(c) Find the critical path and the project variance.

(d) What is the probability that the project will be completed by 22 days?

**Solution**. (a) Using the given information the resulting network is drawn as followsvvv

Expected Time = t_{0} + 4t_{m} + t_{p} / 6 = t_{ij}

T_{12} = 5.17 t_{25} = 8.83 t=4.33

T_{13} =4.33 t_{35} = 5.33

T_{14} = 8.33 t_{46} =6.17

Varience = (tp – t0/ 6)2

σ212 = 0.694 σ =225 = 1.361 σ256 = 1

σ213 = 1 σ235 = 1

σ214 = 1 σ246 = 1.361

(c) Set Es1 = Es1 + t12 =5.17

ES3 = ES1 = t13 = 4.33

ES4 = Max { ES3 = t35, ES2 + t25}

=Max {9.66,14} = 14

ES6 = Max { ES5 =t56, ES4+ t46}

=Max{18.33,14.5} = 18.33

Set LF6 = ES6 =18.33

Then LF5= LF6 – t56 = 14

LF4 =LF6 – t46 = 12.16

LF3 =LF5 – t35 = 8.67

LF2 =LF5 – t25 = 5.17

LF1 = Min { LF3 – t13, LF2 – t12, LF4 – t14}

=MIN. {4.34 , 0 , 3.83} = 0

Hence the critical path is (1) - (2)-(5)-(6)

Project variance = σ^{ 2} _{12} +σ ^{2}_{ 25} +σ ^{2} _{56} = 0.694 + 1 .361 + 1 = 3.055.

(d) Here mean project length is 18.33.

Set z =x – 18 .33/√3 .055-~ n (0,1)

x = 22 , z = 2.1

For

Then the required probability

= p ( X ≤ 22)

= P ( Z ≤ 2.1)

= 0.5 +0.4821

= 0 .9821

=> there is 98.21% chance that the project will be completed by 22 days.

**Example 4.** A PERT network consists of I 0 activities. The precedence relationships and expected time and variance of activity times, in days, are given below :

Activity a b c d e f g h i j

Immediate - a a - b c d d e,f,g h

predecessor (s)

Expected activity 4 2 6 2 3 9 5 7 1 10

time

Variance of activity time 1 1 2 1 1 5 1 8 1 16

Construct an arrow diagram. Find the critical path based on expected times. Based on this

critical path find the probability of completing the project in 25 days.

** **

** **

**Solution.** The resulting network is given in Fig. 8.4.

Set ES _{1} = 0

ES _{2} = ES_{1} + t_{12} = 4

ES _{3} = ES_{2} + t_{23} = 6

ES _{4} = ES_{2} + t_{24} = 10

ES _{5 }= ES_{1} + t_{15} = 2

ES_{6} = Max. {ES_{3} + t _{36} ES_{4} + t _{46}, ES_{5} + t_{56}} = 19

ES_{7} = ES_{5} + s_{57} = 9

ES_{8} = Max. {ES_{6} + t _{68}, ES_{7} + t_{78}} = 20

Set ES6 = LF _{8} = 20

LF _{7} = LF_{8} –t_{78} = 10

LF _{6} = LF_{8} – t _{68} = 19

LF_{5} = Min. {LF_{7} – t_{57}, LF_{6} –t_{56} } = 3

LF _{4} = LF_{6} – t _{46} = 1 0

LF _{3} = LF_{6} – t_{36} = 16

LF_{2} = Min. {LF_{3} – t _{23}, LF_{4} – t _{24}} = 4

LF_{1} = Min. {LF2 – t_{12} , LF_{5} - t5}

Hence the critical path is a – c- f- i on which ES = LF

Total expected time = 4 + 6 + 9 + 1 = 20

Project variance = 1 + 2 + 5 + 1 = 9

Z =x- 20/3 ~ N (0,1)

For x = 25, z = 1.67

Then the required probability = P(X ≤ 25)

= P(z ≤ 1.67)

= 0.5 + Φ (1.67)

= 0.5 + Q.4525

= 0.9525

::::> There is 95.25% chance that the project will be completed by 25 days.