Example on CPM

Consider the following project to manufacture a simple mobile stone crasher. The list of each
activities, their relationship, and the time required to complete them are given in the following table.
We are interested to find the time it will take to complete this project. What jobs are critical to the
completion of the project in time, etc?

Table 12.1: List of Activities

Duration
Activity Symbol (weeks) Restriction
Preliminary design A 3 A < B, Cl
Engineering analysis B 1 B < Dl, F, H
Prepare layout I Cl 2 Cl < C2, Dl
prepare layout II C2 2 C2 < E
Prepare material request Dl 1 Dl < D2
Receive requested material D2 1 D2 < E
Fabricate parts E 4 E<J
Requisition parts F 1 F<G
Receive parts G 2 G<J
Place subcontracts H 1 H<I
Receive subcontracted parts I 5 I<J
Assemble J 2 I<K
Inspect and test K 1

C2
21
2

D1 D2 E
C1 31 32 40
1 1 4
2

A B F G J k
10 20 30 50 70 80 90
3 1 1 2 2 1

Figure 12.15: Network Diagram

H I
60
15
Solution:
First the network diagram is constructed by employing the principles explained in section 12.5.
Then, it is necessary to find out the earliest and latest completion time of for each activity in the
net work. The earliest and the latest times are re-calculated by using ‘forward pass’ and
‘backward pass’ computations, respectively.
The solution now starts by the forward pass computation.
Step1. Determination of Earliest Time ( E j ) : Forward Pass Computation
The purpose of the forward pass computation is to find out earliest start times for all the
activities. For this, it is necessary to assign some initial value to the starting node 10.
Usually this value is taken to be zero so that the subsequent earliest time could be
interpreted as the project duration up to that point in question.
 Rules for the computation are as follows:
Rule 1. Initial event is supposed to occur at time equal to zero, that is, E10  0
Rule 2. Any activity can start immediately when all preceding activities are completed.
The earliest time E j for node j is given by
E j  Max. [ Ei  Dij ] ,
Where i is the collection of nodes which precede node j

Rule 3. Repeat step 2 for the next eligible activity until the end node is reached.

Consider the network (Figure 12.15) by assuming E10  0 and E20  Max. [ Ei  Di 20 ]
For node 20, node 10 is the only predecessor and hence i  10 contains only one element.
Therefore,
E j  Max.[ Ei  Dij ]
E20  E10  D10, 20  0  3  3
Similarly, values of E 21 , E30 , E50 , E 60 can be computed as:
E21  E20  D20, 21  3  2  5 , E30  E20  D20,30  3  1  4 and
E50  E30  D30,50  4  1  5 , E60  E30  D30,60  4  1  5
Consider node 31, where there are two emerging activities, i.e. E31  Max. [ Ei  Di ,31 ] ,
The collection i consists of node 21 and 30 that are preceding node 31, Therefore,
E31  Max. [ E21  D21,31  5  0  5, E30  D30,31  4  0  4]  5
and values of E32 can be computed as:
E32  E31  D31,32  5  1  6
Once again, for node 40 and 70;
E40  Max.[ E21  D21, 40  5  2  7, E32  D32, 40  6  1  7]  7
E70  Max [ E 40  D40,70  7  4  11, E50  D50,70  5  2  7, E60  D60,70  5  5  10]  11
and values of E80 , and E90 can be computed as:
E80  E70  D70,80  11  2  13 , E90  E80  D80,90  13  1  14
From this computation, it can be inferred that this job will take 14 days to finish as this
the longest path of the network. Activities along this longest path are: 10 – 20 – 21 – 40 –
70 – 80 – 90. This longest path is called the critical path. In any network, it is not possible
that there can be only one critical path. For example, if in the above network, let E30  5
days, then 10 – 20 – 30 – 60 – 70 – 80 – 90 can be also critical, in that case two critical
paths exist having the same duration for completion of the project.
Step 2. Determination of Latest Time ( Li ) : Backward Pass Computation
In forward pass computation, the earliest time when a particular activity will be
completed is known. It is also seen that some activities are not critical to the completion
of the job. The question a manager would like to ask is: Can their starting time be delayed
so that the total completion time is still the same? Such a question may arise while
scheduling the resources such as manpower, equipment, finance and so on. If delay is
allowable, then what can be the maximum delay? For this, the latest time for various
activities desired. The backward pass computation procedure is used to calculate the
latest time for various activities. In forward pass computation, assignment was arbitrary,
likewise for the backward pass computation, it is possible to assign the project terminal
event the date on which the project should be over. If no such date is prescribed, then the
convention is of setting latest allowable time determined in forward pass computation.
Rules of the backward pass computation are as follows:
Rule 1. Set Li  Ei or TS
Where TS is the scheduled date for completion and E i is the earliest
terminal time.
Rule 2. Li  Min. j [ L j - Dij ] , i.e. the latest time for activities is the minimum of the latest
time of all succeeding activities reducing their activity time.
Rule 3. Repeat rule 2 until starting activity reached.
Latest times for activities of the network are calculated below:

By rule1, set L90  14 . Applying rule 2, it is to determine L80 , L70 , L60 , L50 , L40 , L32 , and
L31
L80  Min. j {L j - D80,j }  14  1  13 for j  90
L70  Min. j {L j - D70,j }  L80 - D70,80  13  2  11 (j contains only one node 80)
L60  Min. j {L j - D60,j }  L70 - D60,70  11  5  6 (j contains node 70)
L50  Min. j {L j - D50,j }  L50 - D50,70  11  2  9 (j contains node 70)
L40  Min. j {L j - D40,j }  L40 - D40,70  11  4  7 (j contains node 70)
L32  Min. j {L j - D32,j }  L32 - D32,40  7  1  6 (j contains node 40)
L31  Min. j {L j - D31,j }  L31 - D32,32  6  1  5 (j contains node 32)

Now consider node 21, for this node, there are two succeeding activities, namely 21 – 40,
and 21 – 31. Hence,
 L40  D21, 40  7  2  5
L21  Min. j (31,40){L j - D21,j }  Min.   Min. 5
 L31  D21,31  5  0  5 
Similarly, for node 20, and 30,
 L21  D20, 21  5  2  3
L20  Min. j (21,30){L j - D21,j }  Min.   Min. 3
 L30  D20, 30   4  1  3 
  L31  D30,31  5  0  5
 
L30  Min. j (31,50,60){L j - D30,j }  Min. L31  D50,31   Min.5  1  4   4
L  D  5  1  4 
 31 60, 31 

and like the other one, for node 10,

L10  Min. j {L j - D10,j }  L20 - D10,20  3  3  0
The minimum value of L10  0 is no surprising result. Since, started with Li  Ei , it is
always possible to have L10  0 . If this is not so, it means that some error is made in
calculations of forward pass or backward pass values. Figure 12.16 shows earliest and latest
times of each event.

5 5

C2
21
5 5 2 6 6 7 7

D1 D2 E
C1 31 32 40
1 1 4
2
0 0 3 3 4 5 5 9 11 11 13 13 14 14

A B F G J k
10 20 30 50 70 80 90
3 1 1 2 2 1
4 8
5 6

H I
60
1 5

Figure 12.16: Network Diagram with Critical Path

Recall that path 10 – 20 – 21 – 40 – 70 – 80 – 90 was defined as the critical path of this

network. Along this path, it is observed that the latest and earliest times are the same
implying that any activity along this path cannot be delayed without affecting the
duration of the project.

Step 3. Computation of Float ( L f )

By definition, for activity 60 – 70, the float is one day ( L60  E60  6  5  1 ). This float
represents the amount by which this particular activity can be delayed without affecting
the total time of the project.
Also, by definition, free float, if any will exist only on the activities merge points. To
illustrate the concept of free float, consider path 10 – 20 – 30 – 50 – 70, total float on
activity 50 - 70 is four days and since this is the last activity prior to merging two
activities, this float is free float also. Similarly, consider the activity 30-50 which has a
total float of 4 days but has zero free float because 4 day of free float is due to the activity
50-70. If activity 30-50 is delayed up to four days, the early start time of no activity in the
network will be affected. Therefore, the concept of free float clearly states that the use of
free float time will not influence any succeeding activity float time.
Step 4. To Identify Critical Path
Identifying the critical path is a byproduct of boundary time calculations. A critical activity
has no leeway in scheduling and consequently zero total float. It is important to note that the
value of slack, associated with an event, determines how critical that event is. The less the
slack, the more critical an event is 4.
The earlier calculation shows that the path or paths which have zero float are called the
critical ones or in other words, a critical path is the one which connects the events having
zero total float or a minimum slack time. If this logic is extended further more, it would
provide a guide rule to determine the next most critical path, and so on. Such information
will be useful for managers in the control of project. In this example, path 10 – 20 – 30 –
60 – 70 – 80 - 90 happens to be next to critical path because it has float of one day on
many of its activities.
Table 12.2: Boundary Times Duration for the Start and Finish of Activities

Activity Duration Start Finish

(i - j) Dij Earliest Latest Earliest Latest Total Float

(3) E i
(4)  (6) - (2) (5)  (3)  (2) (6) L j
(7)  (4) - (3)
(1) (2)

A 3 0 0 3 3 0
B 1 3 4 4 5 1
C1 2 3 3 5 5 0
C2 2 5 5 7 7 0
D1 1 5 5 6 6 0
D2 1 6 6 7 7 0
E 4 7 7 11 11 0
F 1 4 8 5 9 4
G 2 5 9 7 11 4
H 1 4 5 5 6 1
I 5 5 6 10 11 1
J 2 11 11 13 13 0
K 1 13 13 14 14 0
Example on PERT
A contractor has received order for constructing a cottage on a sea side resort. The delivery of
materials must be planned and the complete job finished in 13 weeks. The work involves and the
time required to complete each activities are given in the table below.

Table 12.3: A Probabilistic Time for an Activity

Time, days
Job Description
to tl tp
A Buying bricks and cement 8 10 14
B Roof tiles 20 24 30
C Preparing foundation 12 14 16
D Erecting shell structure of building 18 20 24
E Laying drains 12 14 15
F Wiring for electrical 16 20 26
G Constructing roof 8 8 10
H Plastering 12 12 18
I Landscaping 4 4 6
J Painting and cleaning 10 12 14
K Laying pathway 4 4 4
L Installing doors and fittings 4 4 4
M Plumbing 20 24 30
N Flooring 8 10 12
a) construct a logical PERT diagram.
b) find the critical path and project duration.
c) determine whether the project is completed within the planned estimated time or not?
Solution:
Before constructing the PERT diagram, the expected time (te) for each of the activities has to be
calculated by using the following formula:

(t o  4t l  t p )
te 
6
where t o = optimistic time
t l = most likely time
t p = pessimistic time
and also the precedence of the activities has to be determined.

Table 12.4: A Probabilistic Time for an Activity

Time, days
Job Description Immediate (t o  4tl  t p )
te 
predecessors to tl tp 6

A Buying bricks and cement - 8 10 14 10

 B Roof tiles buying D 20 24 30 24
C Repairing foundation A 12 14 16 14
D Erecting shell structure of building C 18 20 24 20
E Laying drains C 12 14 15 14
F Wiring for electrical installation G 16 20 26 20
G Constructing roof D 8 8 10 8
H Plastering G 12 12 18 13
I Landscaping K 4 4 6 4
J Painting and cleaning B,F,I,N 10 12 14 12
K Laying pathway E 4 4 4 4
L Installing doors and fittings G 4 4 4 4
M Plumbing G 20 24 30 24
N Flooring H,L,M 8 10 12 10

K
5 6
4

I
E 4
14
8
F
20
A C 20 G M N J
1 2 3 4 7 12 13 14
10 14 D 8 24 10 12
L
4
B H 9
24
13
10 10

Figure 12.18: Network Diagram

The network diagram of Figure 11.18 is constructed using the steps explained for CPM
(t o  4t l  t p )
except that the duration time that we have used here is t e  , similarly using
6
forward and backward computation the critical activities are as presented in Table 12.5.
38 78 42 82

K
5 6
4
72 86
I
E 4
14 8

F
0 0 10 10 24 24 44 44 52 52 20 86 86 98 98
76 76

A C D G M N J
1 2 3 4 7 12 13 14
10 14 20 8 24 10 12
L 56 76
4
B H 9
24 24 44
13 65 76

10 10

Figure 12.19: Network Diagram with Critical Path

Table 12.5: Boundary Times Duration for the Start and Finish of Activities
Activity Duration Start Finish
(i - j) Dij Earliest Latest Earliest Latest Total Float
 (1) (2) (3) E i
(4)  (6) - (2) (5)  (3)  (2) (6) L j
(7)  (4) - (3)

A 10 0 0 10 10 0
B 24 0 20 24 44 20
C 14 10 10 24 24 0
D 20 24 24 44 44 0
E 14 24 64 38 78 40
G 8 44 44 52 52 0
H 13 52 63 65 76 11
I 4 42 82 46 86 40
J 12 86 86 98 98 0
K 4 38 78 42 82 40
L 4 52 72 56 76 20
M 24 52 52 76 76 0
N 10 76 76 86 86 0

The critical path is along A-C-D-G-M-N-J (activities with total float equal to zero) which would
take 98 days.
Hence, the total project duration is greater than the planned delivery time (i.e., 91 days),
the contractor will not meet his target unless he crashes some activities.