CHAPTER 4

PART 1: CPM & PERT

PART 2: SEQUENCING PROBLEMS

PART 1: CPM & PERT
 Critical path analysis
 It is an important tool for planning,
scheduling & coordinating the activities
of large scale projects.
 It is a synthesis of two independent
techniques :

1) Critical Path Method (CPM)

2) Project (Programme) Evaluation &

Review Technique (PERT)
 Importance of CPA:-

1) Forces a thorough pre-planning. Each & every activity

comprising the project is identified & recorded.
2) Increases co-ordination of tasks as technological
relationships between the activities suggest which
activities can run simultaneously & which should
succeed others.
3) Helps computation of different project durations for
different level of resources & thereby select a plan
that minimizes total project cost.
4) Indicates optimal start & finish times of each activity
of the project.
5) Defines areas of responsibility of different
departmental heads for timely execution of the
project.
6) Facilitates progress reporting & limits unnecessary
discussions at the progress meetings to minimum.
7) Identifies trouble spots often in advance &
apply remedial measures.
8) Enable the plan to be revised in accordance
with changes/changing circumstances.
9) Helps to exercise “control by exception” &
prevent cost overruns.
 Network logic:-
 A n/w is a graphical representation of
the project & is composed as series of
connected arrows & circles to describe
the inter-relationship of the activities
involved.
 A n/w is constructed of following
elements:-
1) Activity:- A task having a definite
Design
beginning & a definite end. It is
represented
2 Weeksby an arrow
2) Event:-
 Represent start & finish points of activities.
 Described by words like, “Designed”,
“started”, “completed”, “received”, “issued”,
“dispatched” etc.
 Denoted by circles.
 Each activity is bound by two events (circles).
 E.g. Starting Completion
event event

Merge Burst
event event
Combination of merge & burst:-
3) Activity relationships:-
Sr
Network Interpretation
no.

5
 4) Dummy activities
 It requires neither time nor resources.
 These are used either to signify
constraints or to avoid ambiguities or ill-
logicalities.
 Indicated by dotted lines.
 E.g. 1) A project consists of 4 activities
A, B, C, D. Activities B & C depend on A
while D depends on B & C. Draw a n/w
for the project.
Rule:- Two activities can not have
common start as well as common finish
points. They can have either common
e.g. 2) A simple project consists of 6
activities whose activity relationship is
as follows:-
Sr. Preceded
Activity
no. by
1 1-2 None
2 2-3 1-2
3 2-4 1-2
4 3-5 2-3
5 4-5 2-4
6 5-6 3-5 & 4-5
e.g. 2) A simple project consists of 6
activities whose activity relationship is
as follows:-
Sr. Preceded
Activity
no. by
1 1-2 None
2 2-3 1-2
3 2-4 1-2
4 3-5 2-3
5 4-5 2-3 & 2-4
6 5-6 3-5 & 4-5
 Rules for drawing the network
1) Every activity must have one tail
(preceding) & one head (succeeding)
event.
2) Two activities can not have common
start as well as common finish points.
They can have either common start or
finish point, but not both.
3) A n/w should be progression of
activities always moving in the forward
direction.
e.g.
4) All activities must be tied into the n/w.
Dangers should be avoided.
e.g.
5) A n/w should have only one starting &
only one completion event.
e.g.
6) Use of unnecessary dummy activities
should be avoided.
Incorre
ct
 Steps in building a network
1) Prepare a list of activities to be performed to
complete the project.
2) Establish technological relationships between the
activities.
3) Construct a precedence table with two columns
with activities recorded in the given sequence in
the second column & their precedence
(technological) relationships in the first column.
4) “Connect the first activity under the first column
to the activity opposite to it in the second
column. Locate the activity connected back in the
first column & join this activity in the second
column”. Repeat above process till one sequence
is covered which gives 1st activity chain”.
5) Start with the next activity from the
top in the 1st column which has not
been connected in the 1st sequence &
follow up step “4” & complete second
sequence & hence obtain 2nd activity
chain.
6) Repeat step 5 over again until all
activities in the first column have been
connected.
7) Build up the n/w from the above
activity chains.
8) Modify n/w (if necessary) considering
do’s & don'ts explained under rules of
Network building examples
Example 1: Draw a network for building a storage steel shed
for an industrial unit. The activities involved in the project are
as follows:
Activit Depends on / Immediate
Activity description
y predecessor activity
A Build a site workshop -
B Fence a site -
C Bend reinforcement for A
foundation
D Dig foundation B
E Fabricate steel work A
F Install concrete making B
plant
G Place the reinforcement C,D
H Concrete the foundation G,F
I Paint steel work E
J Build steel structure H,I
K Give finishing touch J
Example 2: Manufacture of a gear box. Draw the network for
following project
Activities as per
Activity description Depends on
given sequence
A Design gear box -
B Prepare engg. Drawings A
C Purchase of gears & B
shafts
D Purchase of bearings, oil B
seals.
E Make pattern for housing B
F Cast housing E
G Machine housing F
H Turn shafts C
I Heat treat shafts H
J Machine gears C
K Cut gears J
L Heat treatment of gears K
M Assemble gear box D,G,I,L
Answer:-
1) 1st activity chain:- A-B-C-H-I-M-N
2) 2nd activity chain:- B-D-M-N
3) 3rd activity chain:- B-E-F-G-M-N
4) 4th activity chain:- C-J-K-L-M-N
 Critical path method (CPM):-
 The projects in which the duration of
various activities can be determined
with great accuracy, can be planned
using CPM.
 Project managers can exactly come to
know the duration of the project (time
required for its completion).
 Critical path:- It’s the longest duration
path between the first & the last events
(nodes) of a project.
 Required
Activities Time (days)
Predecessors
- A 2
- B 3
- C 4
A D 1
B E 2
B F 5
C G 7
D,E H 2
F,G I 3
H,I J 1
1) Draw a network diagram for following
project
2) Find its critical path
3) Draw a n/w diagram for following project:-
Required
Activities Time (days)
Predecessors

- A 2
A B 3
A C 4
A D 1
A E 2
B,C F 5
F,D,E G 7
E H 2
F I 3
I,G,H J 1
Q.1 Discuss various steps in application of
CPM &
PERT.

Q.2 Draw network diagram: (SPPU Exam:

5 Marks)
Activit 1- 2- 2- 2- 3- 4- 4- 5- 6-
y 2 3 4 5 7 5 7 6 7
Duratio
n in 10 11 11 12 11 9 9 10 9
weeks
Earliest Start (ES), Earliest Finish
(EF), Latest Start (LS) & Latest Finish
(LF)
 ES &times
EF :-These are based on the condition that
every activity will be started & finished as early
as possible.
 LS & LF :-
 Total Float (TF) of an activity:
TF = LS of an activity - ES of an activity
 Slack of an event:-
Latest event time (occurrence time) of the event
–
Earliest event time (occurrence time) of the
event
ES, EF, LS, LF times of the
activities
 Rules:
1) The earliest event time of the initial event (first
event) is zero.
2) The earliest event time Te of a merge event
equals largest of the sum of Te of the
preceding events plus duration of the
activity originating from the preceding
event.
3) The Latest event time of the end event equals the
earliest event time of the end event.
4) The latest event time TL of a Burst event
equals the “smallest of the difference
between the latest event time of the head
event less duration of the activity
converging on the head event”.
 Free float (FF) of an activity:-
FF= Earliest occurrence time of succeeding activity
Minus
Earliest occurrence time of preceding activity
Minus
Performance time of the activity

 Independent float of an activity (IDF):-

The delay possible in it without affecting preceding & following

activities.

IDF= Earliest occurrence time of succeeding activity

Minus
Latest occurrence time of preceding activity
Minus
Performance time of the activity

Here the preceding event occurs as late as possible & the succeeding
event occurs as early as possible. Under this condition, the excess time
over the performance time of the activity is called the IDF.
 Example : The activities of a project & estimated times
in days for each activity are given below:
Acti 1-2 1-3 1-4 2-3 2-6 3-5 4-5 4-6 5-6
vity (A) (B) (C) (D) (E) (F) (G) (H) (I)
Dura
tion 8 10 8 10 16 17 18 14 9
1) Draw the network for this project
2) Find the critical path
3) What is the minimum time of completion
for the project?
4) Prepare activity schedule showing the ES,
EF, LS, LF & free float of all activities.
5) Compute Earliest Event times, Latest
event times & slack of all events / nodes.
 Activity
Activity Event Earliest Earliest Latest Latest
Duratio
Name Nodes Start Finish Start Finish
n

A
B
C
D
E
F
G
H
I
 Draw the network diagram for the
following list of activities: (SPPU Exam
10 Marks)
Immediate
Immediate
Activity Predecess Activity
Predecessor
or
A - L K
B A M K
C B N K
D C O D
E D P O
F E Q B
G E R N
H C S L,M
I C,F T S
J G,H,I U P,Q
Q.4. Given the following information,
a) Construct the project network diagram b)
Identify the critical path of the project c) Find
its expected duration d) Calculate Earliest Start
Time (EST) & Latest Finish Time (LFT) of all
activities.
 Most
Optimistic Pessimistic
Activit Likely
Time Time
y Time
(Weeks) (Weeks)
(Weeks)
1-2 6 8 7
1-3 1 9 2
1-4 1 7 4
2-6 1 3 2
3-5 1 9 2
4-5 1 9 5
4-7 2 8 2
5-6 4 4 4
5-7 4 10 4
6-8 2 14 5
 Numericals on CPM
1) Find the duration of following project:-
Activitie Required
Time (Days)
s Predecessors
A - 7
B A 7
C B 2
D C 4
E D 7
F B 5
G B 7
H G 7
I E,F,H 2
2) Find the duration of following project:-

Required
Activities Time (days)
Predecessors
A - 7
B A 10
C A 12
D B 3
E B 8
F B 7
G F 2
H D,E 5
I C 13
J C 6
K H 14
L E,F 5
Sr. Time
Path
no. (Weeks)
1 ABDHK 39
2 ABEL 30
3 ABFL 29
4 ABFG 26
5 ACI 32
6 ACJ 25
7 ABEHK 44
 Numerical:-
 Calculate the following for the project
given below:-
1) Critical path & duration of the project
2) ES , EF & LS, LF times for all activities
3) Floats of all the activities
4) Slacks of all the events
5) IF & FF of all the activities
6) Independent floats of all the activities
Precedence relationships Activities as per given sequence

- A
- B
- C
B,E D
C E
C F
C G
G H
A I
A J
I,D,F K
K,H L
J,L M
 Programme Evaluation & Review
Technique (PERT)
 Useful where the duration of various
activities cannot be predicted with certainty.
e.g. Research & development projects.
a) Launching a space shuttle
b) New product development

1) Optimistic time estimate (a)

2) Pessimistic time estimate (b)
3) Most likely time estimate (m)
4) Expected time estimate (te) . Formula
 Sigma
 Variance
 Te
 Variance of the project
Practice sum:-
ABC co. ltd. is willing to undertake following project. Find
1) expected duration of the project
2) probability that the project will be completed within 30
days.
Required
Activiti a
predecess m b
es (days)
ors
A - 1 2 3
B A 3 5 7
C A 6 10 14
D A 4 6 8
E B,C,D 8 9 10
F E 2 4 6
G F 1 3 5
 Example:-
 Various activities of the project are as follow. Find
a) The critical path of the project & its expected
duration
b) The probability that the project will be completed
Required
Activiti
within 50
es days.
predecess Node a m b
ors
A - 1-2 10 11 12
B A 2-3 6 10 14
C A 2-4 5 8 11
D A 2-5 1 5 9
E B 3-6 3 7 5
F C 4-6 4 9 14
G D 5-7 1 2 3
H E,F 6-7 3 7 11
I G,H 7-8 9 12 15
G,H
 Limitations of CPM & PERT
 It is difficult to identify the various activities in
complex projects, i.e. to clearly define the start &
end points of activities is not easy.
 In certain types of projects, it is not possible to
sequence all the activities according to
precedence requirements.
 The critical path is focused upon only to control
the duration of the project. There may also be
certain non critical paths which can become
critical when some of the activities get delayed.
 The duration of the activities in PERT have been
assumed to follow beta curve, & the variance of
the project duration is equal to the sum of the
variances of all the critical activities. Reality may
be different.
Difference between PERT & CPM:-
 Crashing of project:- Not
there in 2016 pattern
syllabus
 It means intentionally reducing the
duration of the project by allocating
more resources to it.
 A project can be crashed by crashing its
critical activities.
 Following table gives the normal time,
crash time, & incremental cost of
crashing for various activities in a
project.
Activit Nodes Normal Crash time Incremental cost of
y time (days) crashing (Rs/day)
(days)
A 1-2 6 5 50
B 1-3 8 7 100
C 2-5 9 8 80
D 2-4 11 7 60
E 3-4 5 1 90
F 3-6 7 7 -
G 4-7 8 2 40
H 6-7 3 3 -
I 5-7 7 6 100
J 7-8 2 1 50
 The total normal cost for performing
the 10 activities = Rs. 2000, cost of
supervision = Rs. 100 per day, penalty
= Rs. 300 per day over 25 days, reward
= Rs. 200 per day for less than or equal
to 21 days. Find the minimum possible
duration of the project & the related
total cost, & the minimum total cost &
the related duration of the project.
Practice sum on CPM,PERT,Crashing
of project.
1) For a small construction project
following table gives the normal time,
y
crash
Activit Nodestime &
Normal
time
incremental
Crash time
(days)
cost of
Incremental cost of
crashing (Rs/day)
crashing for various activities in a
(days)
A
project.
1-2 5 3 40
B 1-3 4 2 10
C 1-4 7 5 20
D 2-3 4 2 30
E 4-3 3 2 50
F 2-5 2 2 -
G 3-5 7 5 20
H 3-6 3 1 10
I 4-6 4 3 30
J 5-6 6 5 40
 The total normal cost for performing
the 10 activities = Rs. 500, cost of
supervision = Rs. 20 per day, penalty
= Rs. 10 per day over 20 days,
reward = Rs. 10 per day for less than
or equal to 18 days. Find the
minimum possible duration of the
project & the related total cost, & the
minimum total cost & the related
duration of the project.
PART 2: SEQUENCING
PROBLEMS
 Sequencing problems
 Refers to deciding the order or
sequence in which given jobs are to be
performed on the given service facilities
/ machines.
 Here the problem to be solved is to
select the most optimal (best) sequence
from many theoretically possible
sequences such that the total
elapsed time (or cost) is minimized.
 Basic terminology in sequencing
 No. of machines
 Processing order -
e.g. Composing, Printing, Binding.
 Processing time
 Total elapsed time
 Idle time on a machine
 No passing rule
 Assumptions of Sequencing
 Problems
The processing times on various machines are
independent of the order of the job in which they
are processed on them.
 The processing times are known & they do not
change.
 The time required to move jobs from one machine
to another is negligible.
 Only one job can be processed on a given machine
at a time.
 A job once started on a machine would be
completed without any interruption.
 A job is processed as soon as the concerned
machine is free, but only in the specified
sequence.
 Types of sequencing problems
1) Processing n jobs on 2 machines
2) Processing n jobs on 3 machines
3) Processing n jobs on m machines
1. Processing n jobs on 2
machines
 Here the problem is described as,
a) Only two machines are involved.
b) Each job is to be processed in the
order AB (i.e. 1st to be processed on
Machine A & then on Machine B.)
c) The expected processing times for all the
n jobs on
machine A (Say A1, A2, A3, …….., An) &
on machine
B (B1, B2, B3, ….., Bn) are given. This
can
Job
be written ……………………………
1 2 3 n
(i) as: …
……………………………
Ai A1 A2 A3 An
……
……………………………
Bi B1 B2 B3 Bn
……
Method of solution
1) Step 1: Select the smallest processing time
among A1, A2, A3…….,An & B1, B2, B3
…….,Bn together.
2) Step 2:
a) If Ar (i.e. processing time of rth job on
machine A) is the smallest, then do the rth
job first in (the available positions of)
sequence.

b) If Bs (i.e. processing time of sth job on

machine B) is the smallest, then do the sth
job last in (the available positions of)
sequence.
 Note: In case of a tie –
i. If Ar = Bs then do the rth job first & the sth job last.
ii. If there is a tie among Ar, then do any one of them
first.
iii. If there is a tie among Ar, then do any one of them
last.

3) Step 3: Remove the assigned job from the

processing times table.

4) Step 4: Repeat the steps 1 to 3 for the reduced

table until all the jobs are assigned to get the
optimum sequence.
 Example 1: A book publisher has one
printing press, one book binding
machine & the manuscript of a no. of
different books. The time required to
perform the printing & binding
operations for each book are shown
below. determine the order in which the
books should be processed in order to
minimize the total time required to turn
out all the 1
Book 2
books. 3 4 5 6
Printing
time 70 30 50 60 90 10
(Hrs.)
Binding
Time 80 80 30 40 40 20
 Considering the optimal sequence &
given processing times, we can
construct the following table for the in
& out times for the printing & binding
operations as: Idle time
Printing Binding for
Book Binding
Machine Machine
Machine
Time Time
Time In Time In
Out Out
 Idle time for the printing machine =
Binding time out for the last book –
Printing time out for the last book
 Example 2: We have seven jobs, each of
which has to go through two machines A &
B in the order AB. The processing times for
the jobs on the two machines (in hours)
are as follows:
Job 1 2 3 4 5 6 7
Machin
e 3 12 15 6 10 11 9
A
Machin
e 8 10 10 6 12 1 3
B

Determine the sequence of these jobs

that will minimise the total elapsed time.
2. Processing n jobs through 3 machines
Step 1: Identify the smallest processing times on machines
A & C.
Also find the largest processing time on machine
B.

Step 2: Check out if

i. (Smallest processing time on Machine A)
>=
(Largest processing time on Machine B)

And / Or

ii. (Smallest processing time on Machine C)

>=
(Largest processing time on Machine B)
 Step 3: If none of these conditions are
satisfies, the method fails. Otherwise go to
step 4.
 Step 4: Replace the 3 machine problem by
an equivalent 2 machine (virtual machines)
problem.
We denote virtual machines by G & H &
corresponding processing times Gi & Hi as:
Gi = Ai + Bi & Hi = Bi + Ci

 Step 5: Use Johnson’s rule to find optimum

sequence for processing n jobs on 2 machines
G & H. The resulting optimal sequence also
gives the optimal sequence for the original
problem involving 3 machines A, B, C.
 Example 1: We have seven jobs, each
of which has to go through three
machines A, B C in the order ABC. The
processing times for the jobs on the
three
Job machines
1 2(in hours)
3 4 are5as 6 7
follows:
Machine
3 8 7 4 9 8 7
A
Machine B 4 3 2 5 1 4 3
1
Machine C 6 7 5 11 5 6
2

Determine the sequence of these jobs

 Machine Machine Machine
Job
A B C
Time Time Time Time Time Time
In Out In Out In Out

1
4
7
2
6
3
5
Processing n jobs through m
machines
 Example 1: Find the optimal sequence
for the following sequencing problem of
four jobs & five machines when passing
is not allowed, of which processing time
(in hours) is given below:
Jobs
Machi
ne 1 2 3 4
A 7 6 5 8
B 5 6 4 3
C 2 4 5 3
D 3 5 6 2