QBUS6820 - Prescriptive Analytics
Week 9
Project Management
• Formulating the CPM/PERT Network as a
Linear Programming Model
• Project Crashing and Time-Cost Trade-Off
Formulating an AON project network as an LP
• Recall the project network from last week:
H
25 33
8
E
17 25
8
J
33 38
5
I
33 38
5 K
38 42
4
L
38 40
2
M
42 46
4A
0 3
3
F
17 21
4
G
17 23
6
D
7 17
10
C
7 10
3
B
3 7
4
0 3 3 7
22 25
177
17 25
21 25
2519
25 33
33 38
35 40
42
4240
42 46
38
Formulating an AON project network as an LP
• Suppose we want to use Linear Programming to
figure out the critical path
• How would we formulate the model?
• Recall the critical path is the longest path through
the network
• This equates to the total time it will take to complete
the project
Formulating an AON project network as an LP
• How should we define our decision variables?
Let xi = the time we start activity i
and let ti = the time it takes to do activity i
Formulating an AON project network as an LP
• How should we define our objective function?
Min xM
Formulating an AON project network as an LP
• How should we define our constraints?
Generally, xi >= xj + tj
where j is an immediate predecessor activity and tj is
the time it takes to do activity j
Formulating an AON project network as an LP
• How should we define our constraints?
xB >= xA + 3
xC >= xB + 4
xD >= xB + 4
xE >= xD + 10
xF >= xD + 10
xG >= xD + 10
xH >= xC + 3
xH >= xE + 8
xH >= xF + 4
xH >= xG + 6
Formulating an AON project network as an LP
• How should we define our constraints?
xI >= xH + 8
xJ >= xH + 8
xK >= xI + 5
xL >= xJ + 5
xM >= xK + 4
xM >= xL + 2
xi >= 0 for i =A,…,M
Formulating an AON project network as an LP
• What does the solution to this model tell us?
The minimum possible project completion time
(the objective function value at the optimum x*M to which we add tM
for the minimum project completion time)
Formulating an AON project network as an LP
• How can we use this information to determine the critical path?
We know that activities on the critical path have zero slack. So we can
take x*M and use that to solve 2 further LPs:
1. For each i, min xi subject to the constraints previously listed +
additional constraint xM = x*M
2. For each i, max xi subject to the constraints previously listed +
additional constraint xM = x*M for all i
Activities for which the value of x*i is equal across these 2 LPs are
activities on the critical path

Project Crashing
• It is often possible to complete activities faster than
normal by applying more resources (better
equipment, overtime, etc).
• This is referred to as “crashing” the project.
• We may want to determine the optimal way of
crashing a project to:
- complete it more quickly than originally scheduled
- keep it on schedule if critical activities were
delayed
• Crashing a project increases its cost.
• The decision whether to crash or not is based on the
trade-off between the time saved and cost.
Project Crashing
Computing Crash Times and Costs
Project Crashing
We can determine minimum cost way of crashing the
project to achieve a certain completion time by solving an
LP problem
Defining the decision variables
Let xi = the time we start activity i
ti = the time it takes to do activity i
ci = the number of time units by which we
choose to crash (reduce) the completion time
of activity i
T = the target project completion time
i = A,…, M
Defining The Objective
Minimise the cost of achieving a certain completion time T:
Min
1000cA+3000cB+500cC+1250cD+667cE+1000cF+500cG
+500cH+750cI+500cJ+750cK+500cL+1000cM
Defining The Constraints
We need to modify the previous constraints and add some more:
xB >= xA + 3 - cA
xC >= xB + 4 - cB
xD >= xB + 4 - cB
xE >= xD + 10 - cD
xF >= xD + 10 - cD
xG >= xD + 10 - cD
xH >= xC + 3 - cC
xH >= xE + 8 - cE
xH >= xF + 4 - cF
xH >= xG + 6 - cG
Defining The Constraints
xI >= xH + 8 - cH
xJ >= xH + 8 - cH
xK >= xI + 5 - cI
xL >= xJ + 5 - cJ
xM >= xK + 4 - cK
xM >= xL + 2 - cL
xi >= 0 for i =A,…,M
xM = T – (tM – cM) = T – 4 + cM
Defining The Constraints
0 <= cA <= 1
0 <= cB <= 1
0 <= cC <= 1
0 <= cD <= 4
0 <= cE <= 3
0 <= cF <= 1
0 <= cG <= 2
0 <= cH <= 3
0 <= cI <= 2
0 <= cJ <= 3
0 <= cK <= 2
0 <= cL <= 1
0 <= cM <= 2
Project Crashing
We can also find the minimum project completion time that satisfies a certain crashing
cost constraint.
Let N be a dummy activity that follows activity M where tN = 0 and xN is the time we
start this dummy activity (so N is now the last activity in the project)
Objective function?
Min xN
Constraints?
All previous constraints but we replace xM = T – 4 + cM with xN = xM + 4 - cM
Anything else?
Need to add the cost constraint:
1000cA+3000cB+500cC+1250cD+667cE+1000cF+500cG+500cH+750cI+500cJ+7
50cK+500cL+1000cM <= Cost Limit
Project Crashing Manual Solution
A(7)
B(3)
C(4)
D(5)
E(2)
F(4)
G(5)
Crash the project by 4 days
Crashing the Project: Time – Cost Analysis
The aim is to crash the project by 4 days
Crashing the Project - Process
Step 1: Find critical path
Step 2: Crash activity with cheapest crash cost
Step 3: Revert to step 1 (watch for multiple critical paths)
Path Length Crash A Crash C Crash F Crash F Crash D
ABDFG 24 23 23 22 21 20
ABDEG 22 21 21 21 21 20
ACDFG 25 24 23 22 21 20
ACDEG 23 22 21 21 21 20
Note: 4 day
reduction
achieved
One more
crash for
illustration
Crash Costs $1,000 $1,200 $1,500 $1,500 $1,500
Cumulative $2,200 $3,700 $5,200 $6,700
Crashing the Project - Process
Step 1: Find critical path
Step 2: Crash activity with cheapest crash cost
Step 3: Revert to step 1 (watch for multiple critical paths)
Path Length Crash A Crash C Crash D Crash F Crash F
ABDFG 24 23 23 22 21 20
ABDEG 22 21 21 20 20 20
ACDFG 25 24 23 22 21 20
ACDEG 23 22 21 20 20 20
Note: 4 day
reduction
achieved
One more
crash for
illustration
Crash Costs $1,000 $1,200 $1,500 $1,500 $1,500
Cumulative $2,200 $3,700 $5,200 $6,700
Crashing the Project - Process
Step 1: Find critical path
Step 2: Crash activity with cheapest crash cost
Step 3: Revert to step 1 (watch for multiple critical paths)
Path Length Crash A Crash C Crash F Crash D Crash F
ABDFG 24 23 23 22 21 20
ABDEG 22 21 21 21 20 20
ACDFG 25 24 23 22 21 20
ACDEG 23 22 21 21 20 20
Note: 4 day
reduction
achieved
One more
crash for
illustration
Crash Costs $1,000 $1,200 $1,500 $1,500 $1,500
Cumulative $2,200 $3,700 $5,200 $6,700
End of lecture
Questions?