Project Planning: Jesper Larsen

Informatics and Mathematical Modelling / Operations Research
Project Planning
Jesper Larsen
jla@imm.dtu.dk
Informatics and Mathematical Modeling

Technical University of Denmark
Jesper Larsen 1
Project Management
Project Management is a set of techniques that
helps management manage large-scale projects;
projects that typically require coordination of
numerous tasks throughout the organisation.
PERT = Program Evaluation and Review

Technique
CPM = Critical Path Method
The methods were developed independently but are

now often used interchangeably and are combined
in one acronym: PERT/CPM.
Jesper Larsen 2
Example
The Reliable Construction Company has just made
the winning bid of a $ 5.4 million contract to
construct a new plant.
There are the following constraints:

a penalty of $ 300,000, if Reliable has not
completed construction by the deadline of 47
weeks from now, and
a bonus for speedy construction of $ 150,000 to
be paid if the plant is ready within 40 weeks.
Jesper Larsen 3
Questions
How can the project be displayed graphically to
better visualize the flow of the activities?
What is the total time required to complete the
project if no delays occur?
When do the individual activities need to start
and finish (at the latest) to meet this project
completion time?
When can the individual activities start and
finish (at the earliest) if no delays occur?
Jesper Larsen 4
More questions
Which are the critical bottleneck activities where
any delays must be avoided to prevent delaying
project completion?
For the other activities, how much delay can be
tolerated without delaying the project
completion?
If extra money is spent to expedite the project,
what is the least expensive way of attempting to
meet the target completion time?
Jesper Larsen 5
Project Networks
Project networks consists of a number of nodes and
a number of arcs. There are two alternatives for
presenting project networks.
Activity-on-arc (AOA): Each activity is

presented as a an arc. A node is used to
separate an activity from each of its immediate
predecessors.
Activity-on-node (AON): Each activity is
represented by a node. The arcs are used to
show the precedence relationships.
Jesper Larsen 6
AON vs. AOA

AON are considerably easier to construct than
AOA.
AON are easier to understand than AOA for
inexperienced users.
AON are easier to revise that AOA when there
are changes in the network.
Jesper Larsen 7
Critical path
A path through a project network is one of the
routes following the arcs from the START node to
the FINISH node. The length of a path is the sum of
the (estimated) durations of the activities on the
path.
St->A->B->C->D->G->H->M->Fi 40
St->A->B->C->E->H->M->Fi 31
St->A->B->C->E->F->J->K->N->Fi 43
St->A->B->C->E->F->J->L->N->Fi 44
St->A->B->C->I->J->K->N->Fi 41
St->A->B->C->I->J->L->N->Fi 42
Jesper Larsen 8
Scheduling individual activities

The PERT/CPM scheduling procedure begins
by addressing when the activities need to start
and finish at the earliest if no delays occur?
Having no delays mean 1) actual duration
equals estimated duration and 2) each activity
begins as soon as all its immediate
predecessors are finished.
ES = Earliest start for a particular activity
EF = Earliest finish for a particular activity
where EF = ES + duration
Jesper Larsen 9
Earliest Start Time Rule

The earliest start time of an activity is equal to the
largest of the earliest finish times of its immediate
predecessors, or
ES = max { EF of immediate predecessors }
Jesper Larsen 10
Finding latest start and finish times

The latest start time for an activity is the latest
possible time that it can start without delaying the
completion of the project (so the finish node still is
reached at its earliest finish time), assuming no
subsequent delays in the project. The latest finish
time has the corresponding definition with respect
to finishing the activity.
LS = latest start time for a particular activity

LF = latest finish time for a particular activity
where LS = LF - duration
Jesper Larsen 11
Latest Finish Time Rule

The latest finish time of an activity is equal to the
smallest of the latest start times of its immediate
successors, or
LF = min { LS of the immediate successors }
Jesper Larsen 12
Identifying slack
The slack for an activity is the difference between
its latest finish time and its earliest finish time.
Slack Activities
0 A, B, C, E, F, J, L, N
pos. D, G, H, I, K, M
Each activity with zero slack is on a critical path

through the project network such that any delay
along this path will delay project completion.
Jesper Larsen 13
Crashing an activity
Crashing an activity refers to taking (costly)
measures to reduce the duration of an activity
below its normal time. Crashing the project refers
to crashing a number of activities in order to reduce
the duration of the project below its normal value.
Crash
crash cost
Normal
normal cost
crash time normal time
Jesper Larsen 14
Considering Time-Cost trade-offs

What is the least expensive way of crashing some
activities to reduce the estimated project duration to
the specified level?
One way: look at marginal costs.
Jesper Larsen 15
Using LP to make crashing decisions

Restatement of the problem: Let Z be the total cost
of crashing activities. The problem then is to
minimize Z, subject to the constraint that project
duration must be less than or equal to the time
desired by the project manager.
Jesper Larsen 16
Modelling using LP
What are our decision variables? xj = reduction
in the duration of activity j due to crashing this
activity.
How will our objective function look like? The
objective function is to minimize the total cost of
crashing activities:
min 100, 000xA + 50, 000xB + . . . + 60, 000xN .
To impose the constraint that the project must
be finished in less than or equal to a certain
number of weeks we impose another variable:
yF i .
Jesper Larsen 17
Modelling using LP (cont)

To help the LP assign the appropriate value to
yF given the values of xA , xB , . . . it is convenient
to introduce: yj = start time of activity j.
NOW since the start time of each activity is
directly related to to the start time and duration
of each of its immediate predecessors we get:
start time of this activity ≥ (start time -
duration) for this immediate predecessor
Jesper Larsen 18
Putting it all together

1. min 100, 000xA + 50, 000xB + . . . + 60, 000xN
2. Maximum reduction constraints:
xA ≤ 1, xB ≤ 2, . . . , xN ≤ 3.
3. Non-negativity constraints:
xj ≥ 0, yj ≥ 0, yF i ≥ 0
4. Start time constraints: For each arc we get a
relationship between the two end points:
yC ≥ yB + 4 − xB , yD ≥ yC + 10 − xC etc.
5. Project duration constraints: yF i ≤ 40
Jesper Larsen 19

Project Planning: Jesper Larsen

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Project Planning: Jesper Larsen

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Project Planning: Jesper Larsen

Uploaded by

Copyright:

Available Formats

Informatics and Mathematical Modelling / Operations Research

Informatics and Mathematical Modeling

PERT = Program Evaluation and Review

The methods were developed independently but are

There are the following constraints:

Activity-on-arc (AOA): Each activity is

AON vs. AOA

Scheduling individual activities

Earliest Start Time Rule

Finding latest start and finish times

LS = latest start time for a particular activity

Latest Finish Time Rule

Each activity with zero slack is on a critical path

crash time normal time

Considering Time-Cost trade-offs

Using LP to make crashing decisions

Modelling using LP (cont)

Putting it all together

You might also like