Project Scheduling
Basic Approach
Introduction
• A project is a collection of tasks that must be
completed in minimum time or at minimal cost.
• It is made up by a set of tasks or activities,
activities some
of which must be completed before others can be
started.
• The ones that must be completed before a
particular activity can be started are called
predecessors.
predecessors
– Immediate predecessors are the ones that must be done
just prior to the commencement of a particular activity.
• A feasible scheduling is one that schedules the
activities without violating any of the immediate
predecessor scheduling constraints.
Possible Objectives
• Some objectives of project scheduling
include:
– Completing the project as early as possible by
determining an earliest start and finish time for each of
the activities
– Determining the likelihood a project will be completed
within a certain time period
– Finding a minimum cost schedule that completes the
project by a certain date
– Finding a minimum time to complete a project within
budget restrictions
– Investigating the results of possible delays in one or
more of an activity’s completion time
– Evaluating the costs and benefits of reducing the time
of performing one or more of the activities
Activities
• An activity could be:
– Quite specific
• e.g. install light switch in third bathroom
–Less detailed
• e.g. install electrical for the house
• The degree of specificity used depends on
the application and availability of data.
• Each activity has a set of immediate
predecessor activities that must be
completed immediately prior to starting the
activity.
Activity Completion Times
• Associated with each activity is an
estimated completion time. These time
could be:
– Deterministic
• The completion time is known with certainty
– Probabilistic
• The completion time varies according to some
probability distribution with an estimated mean
and standard deviation
– Determined by the amount spent to perform
the activity.
Example
KLONE COMPUTERS, INC.
• KLONE Computers manufactures computers.
• It is about to design, manufacture, and market
the Klonepalm 2000 palmbook computer.
• In broad terms, the three major tasks to
perform are to:
– Design and manufacture the computer
– Train staff and vendor representatives on the
features and use of the computer
– Advertise the computer
Detailed Activities
Activity
Activity Description
Description
AA Prototype
Prototypemodel
modeldesign
design
BB Purchase
Purchaseofofmaterials
materials
Manufacturing
Manufacturing CC Manufacture
Manufactureofofprototype
prototypemodel
model
activities
activities DD Revision
Revisionofofdesign
design
EE Initial
Initialproduction
productionrun
run
FF Staff
Stafftraining
training
Training
Trainingactivities
activities GG Staff
Staffinput
inputon
onprototype
prototypemodels
models
HH Sales
Salestraining
training
II Pre-production
Pre-productionadvertising
advertising
Advertising
Advertisingactivities
activities campaign
campaign
JJ Post-redesign
Post-redesignadvertising
advertising
campaign
campaign
Precedence Relations
Starts Completion
Activity after Immediate Predecessor's) Days
A-Prototype Design NONE 90
Starts
B-Purchase Materials After
A-Prototype Design 15
Starts
C-Manufacture Prototypes After
B-Purchase Materials 5
Starts C-Manufacture Prototypes and
D-Design Revision After
20
G-Staff Input
Starts
E-Initial Production Run After
D-Design Revision 21
Starts
F-Staff Training After
A-Prototype Design 25
Starts C-Manufacture Prototypes and
G-Staff Input After
14
F-Staff Training
Starts
H-Sales Training After
D-Design Revision 28
Starts
I-Pre-Production Advertising After
A-Prototype Design 30
Starts D-Design Revsion and
J-Post Redesign Advertising After
45
I-Pre-Production Advertising
The PERT/CPM Approach for
Project Scheduling
• PERT stands for Program Evaluation and Review
Technique and CPM stands for critical path
method.
– Both were methods for project scheduling developed
independently in the late 1950’s.
– The concepts have merged over the years so that now
we simply call the approach the PERT/CPM approach.
• It uses a network representation (a set of nodes
and a set of arcs) of the project.
– Nodes represent the activities and reflect their
completion times
– Arcs reflect immediate predecessor relationships with
arrows
• PERT/CPM is used for scheduling activities such
that the project’s completion time is minimized.
The PERT/CPM Network
E
B C
21
15 5
A F G D H
90 25 14 20 28
J
I
45
30
OBJECTIVES
• Management at KLONE would like to schedule the
activities to minimize the project completion time.
• Management wishes to know:
– The earliest start and finish times for each
activity that will allow the project to be
completed in this minimal time.
– The latest start and finish times for each activity
which will not alter this minimal time.
– Which activities must adhere to rigid schedules
and which activities have slack in their
schedules.
Earliest Start (ES) and
Earliest Finish (EF) Times
• The ES and EF times are determined by making a
forward pass through the network as follows:
– For all the activities which have no immediate
predecessors:
• The earliest start time (ES) = 0
• The earliest finish time (EF) = the activity’s duration
– Then select a node for which EF of all its immediate
predecessors has been determined.
• ES = Max EF (of all its immediate predecessors)
• EF = ES + Activity Duration
– Repeat this process until all nodes have been evaluated
Minimum Project Completion Time
is
The maximum EF in the project.
Earliest Start and Finish Times
• We enter these as (ES,EF) above each node.
(149,170)
(90, 105) (105, 110)
E
B C 21
15
15 55
MAX(110,115)
(0, 90) (90, 115) (115, 129) (129,149) (149, 177)
A F G D H
90
90 25
25 14 20 28
28
MAX(120,149)
(90, 120) (149,194)
J
I
45
45
30
30
Earliest Project completion time = MAX(EF) = 194
Latest Start (LS) and
Latest Finish (LF) Times
• The LS and LF times are determined by making a
backward pass through the network as follows:
– For all the activities which are not predecessors for any
other activity
• The latest finish time (LF) = project completion time
• The latest start time (LS) = LF – Activity Duration
– Select a node which is the immediate predecessor for
nodes whose LS times have all been determined
• LF = Min LS (all nodes for which it is a predecessor)
• LS = LF - Activity Duration
– Repeat this process until all nodes have been evaluated
Latest Start and Finish Times
• We enter these as (LS,LF) below each node.
(149,170)
(90, 105) (105,110)
E
B C 21
21
15
15 5
5
(173, 194)
(95, 110) (110, 115)
(0, 90) (90, 115) (115, 129) (129,149) (149, 177)
A F G D H
90
90 25
25 14
14 20 28
28
(0, 90) (90, 115) (115, 129) (166, 194)
(129, 149)
(90, 120) (149,194)
MIN(95, 90, 119) MIN(173, 166, 149)
J
I
45
45
30
30
(149, 194)
(119, 149)
Slack Times
• Activity start time and completion time may
be delayed by deliberate reasons as well as
by unforeseen reasons.
• Some of these delays may affect the overall
completion date.
• The effects of these delays can be
determined by the slack time,
time for each
activity.
Slack time for an activity = LS-ES or LF-EF
The Critical Path
The activities with 0 slack time form at least
one critical path of connected activities,
each of which is an immediate predecessor
for another activity on the path from the
beginning (time = 0) to the end (the
completion time of the project).
– Critical activities must be rigidly scheduled.
• Any delay in a critical activity will delay the entire
project.
– The critical path is the longest in the network
Sum of the completion times of activities on a critical path
=
Project completion time
Slack Time Calculations
• Slack time = LS - ES
Activity LS - ES = SLACK
A 0 - 0 = 0
B 95 - 90 = 5
Critical
C 110 - 105 = 5
Activities
D 129 - 129 = 0
E 173 - 149 = 24
F 90 - 90 = 0
G 115 - 115 = 0
H 166 - 149 = 17 Critical Path
I 119 - 90 = 29
A F G D J
J 149 - 149 = 0
The Critical Path
(149,170)
(90, 105) (105,110)
E
B C
21
15 5
(173, 194)
(95, 110) (110, 115)
(0, 90) (90, 115) (115, 129) (129,149) (149,177)
A F G D H
90 25 14 20 28
(0, 90) (90, 115) (115, 129) (129, 149) (166, 194)
(149,194)
(90, 120)
J
I
45
30
(149, 194)
(119, 149)
Possible Delays
• There could be a delay in just one activity.
– Any delay more than the slack time for the activity will
delay the entire project by the difference between the
activity delay and the slack time
• There could be delays in more than one activity.
– If activities are on different paths or on the same path
but separated by a critical activity, each of the delays is
evaluated separately. The project delay = max (these
delays – corresponding slack).
– Activities on the same path which are not separated by
a critical activity share the slack. Both will have the
same value for the slack and any combined delays in
these activities that exceed this common slack results
in a project delay equal to (total activity delay) –
(common slack).
– Usually with multiple delays the model is simply re-
solved!
Examples of Activity Delays
• Activity G is delayed 5 days
– G is on the critical path (has 0 slack) so the project will be delayed 5 days.
• Activity E is delayed 15 days
– E has 24 days of slack so the project will not be delayed
• Activity B is delayed 15 days
– B has 5 days of slack so the project will be delayed 10 days
• Activity E is delayed 30 days and Activity I is delayed 30 days
– E and I are on different paths. E has 24 days of slack which could cause a
30-24 = 6 day delay; I has 29 days of slack which could cause 30-29 = 1 day
delay. The project is delayed by the MAX(6,1) = 6 days.
• Activity B is delayed 4 days and Activity E is delayed 4 days
– B and E are on the same path but are separated by critical activities (G and
D). This is the same as the case above. B has 5 days slack so delaying it 4
days would not delay the project; E has 24 days of slack so a 4 day delay
will not delay the project – Net effect– No delay.
• Activity B is delayed 4 days and Activity C is delayed 4 days
– B and C are on the same path with no critical activity in between. They
share the same 5 days of slack. So sense both are delayed 4 days for a
total of 8 days, the project is delayed 8 – 5 = 3 days.
days
A Linear Programming
Approach to PERT/CPM
• Variables
– Xi = The start time of the activities for i=A, B, C, …,J
– X(FIN) = Finish time of the project
• Objective function
– Complete the project in minimum time.
• Constraints
– For each arc L M a constraint states that the
start time of M must not occur before the finish time
of its immediate predecessor, L.
The Linear Program
Minimize X(FIN) C
ST 5
X(FIN) XE + 21
Example of
X(FIN) XH + 28 Constraints
X(FIN) XJ + 45 F
G
25
XD XG + 14
XE XD + 20 XG X C+ 5 XG FOR G
START TIME
XH XD + 20 XG XF+ 25 ≥
XC Finish
Start Time for C+ +time
5 for
C’s C
Duration
XJ XD + 20 XI XD+ 90
XJ XI + 30 XF XA+ 90 and
XC XB+ 15 XG FOR G
START TIME
XD XG+ 14
≥
XB XA+ 90 XF Finish
Start Time for F++time
F’s for F
25 Duration
All X’s
Using the PERT-CPM Template
Enter activity names.
Node are names
automatically generated.
Enter precedence relations.
If an activity has more than one immediate
Enter (Constant) Activity Times predecessor, input one node entry
for each immediate predecessor.
Using the PERT-CPM Template
Go to Just click solve.
Solver The algorithm has been
in pre-programmed.
Tools menu
It will look like nothing happened,
but that’s okay.
Click the PERT OUTPUT tab.
Click Solve
Review
• Objectives of Project Scheduling
• Precedence Relation Chart showing immediate predecessors
• How to construct a PERT/CPM network
• Forward Pass for finding the earliest start/finish times
(ES,EF)
• Backwards Pass for finding the latest start/finish times
(LS,LF)
• Calculation and analysis of slack
• Finding the critical path
• Linear programming formulation
• Use of PERT-CPM template
