USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Critical Path Method (CPM)

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

 

 

 

 

 

Solution :

ES1 = 0

ES2 = ES1 + t12 = 0 + 3 = 3

ES 3 = ES 1 + t 13 = 0 + 1 = 1

ES4 = ES2 + t24 = 4

ES5 = Max. {ES3 + t35, ES2 + t25} = Max. {6, 4) = 6

ES6 = ES5 + t56 = 1 1

ES7 = ES5 + t 57 = 14

ES8 = ES6 + t68 = 1 2

ES9 = Max. {ES4 + t49, ES7 + t79} = Max { 10, 16) = 16

ES 1 0 = Max. {ES9 + t910, ES7 + t810} = Max. {22, 16) = 22

Set                   LF1 0 = ES10 = 22

LF9 = LF10 - t910 = 22 - 6 = 16

LF 8 = LF 10 - t81 0 = 22 - 4 = 18

LF7 = LF9 - t79 = 1 6 - 2 = 14

LF 6 = LF8 - t68 = 1 7

LF5 = Min. {LF7 - t57, LF6 - t56} = Min. {6, 12} = 6.

LF4 = LF9 - t49 = 10

L F 3 = LF 5 - t35 = 1

LF2 = Min. {LF4 - t24, LF5 - t25} = Min. {9, 5 } = 5.

LF1 = Min. {LF3 - t13, LF2 - t12} = 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 = ES1 + t12 = 0 + 2 = 2

ES 3 = ES1 + t 13 = 0 + 3 = 3

ES  4 = ES3 + t34 = 3 + 4 = 7

ES 5 = Max. {ES2 + t25, ES4 + t45}

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

ES 6 = ES5 + t56 = 10

ES 7= ES4 + t47 = 8

ES 8 = Max. {ES= + t68, ES7 + t78}

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

 

Set       LF 8 = ES 8 = 12

LF 7 = LF 8 - t78 = 1 2 - 3 = 9

LF 6 = LF 8 - t68 = 12 - 2 = 1 0

LF  5 = LF 6 - t56 = 1 0 - 3 = 7

LF 4 = Min. {LF5 - t54, LF7 - t47 }

=Min. {7, 8} = 7

LF 3 = LF 4 -t34 = 7 - 4 = 3

LF 2 = LF 5 -t25 = 7 -1 = 6

LF 1 = Min. {LF2 -t 12, LF3 -t13}

=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                            tp

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 = t0 + 4tm + tp / 6 = tij

T12 = 5.17             t25 = 8.83              t=4.33

T13 =4.33              t35 = 5.33

T14 = 8.33             t46 =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 122 252 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 = ES1 + t12 = 4

ES 3 = ES2 + t23 = 6

ES 4 = ES2 + t24 = 10

ES 5 = ES1 + t15 = 2

 

ES6 = Max. {ES3 +  t 36 ES4 + t 46, ES5 + t56} = 19

ES7 = ES5 + s57 = 9

ES8 = Max. {ES6 + t 68, ES7 + t78} = 20

Set  ES6 =       LF 8 = 20

 

LF 7 = LF8 –t78 = 10

 

LF 6 = LF8 – t 68 = 19

 

LF5 = Min. {LF7 – t57, LF6 –t56 } = 3

 

LF 4 = LF6 – t 46 = 1 0

 

LF 3 = LF6 – t36 = 16

 

LF2 = Min. {LF3 – t 23, LF4 – t 24} = 4

 

LF1 = Min. {LF2 – t12 , LF5 - 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.