Critical Path Analysis and Crushing your Project.
Optimising a project schedule can be a complex and difficult task, with several moving parts. Whenever we are faced with this challenge, ‘Operational Research‘ can serve as a coherent science of system improvement. I have put together this step by step guide that you can follow to optimise your project’s total duration time. You can use the algorithm highlighted in the example, to help you determine the earliest finishing time and the critical path (i.e. the key project activities that will directly impact your project’s completion date). I will also share with you, how you can easily use linear programming and Excel Solver to crush your project (i.e. reducing the project’s total duration time at a minimum resource cost).
Let’s consider Project P:
The table below consists of 10 activities in project P, their dependencies, their normal durations, their crush durations and the costs associated with reducing each activity duration by one week.
Activity | Must be immediately preceded by | Normal Duration (weeks) | Crush Duration (weeks) | Resource Cost of reducing activity duration by one week |
A | – | 8 | 6 | £1,000 |
B | A | 12 | 10 | £800 |
C | A | 11 | 11 | – |
D | – | 20 | 15 | £1,000 |
E | D | 6 | 6 | – |
F | B, C, E, J | 7 | 5 | £2,000 |
G | F | 10 | 8 | £1,500 |
H | E | 5 | 4 | £800 |
I | G, H | 4 | 4 | – |
J | D | 5 | 4 | £1,000 |
The diagram below is the AOA network diagram (i.e. activity-on-the-arc network format) of Project P, using the normal duration. Each node is representing an event/task/milestone and the arc is representing the project activity and their duration in brackets, i.e. arc D(20) means activity D and duration is 20:
In order to determine the critical path for this project you can use the Forward Pass and Backward Pass algorithm.
Forward Pass and Backward Pass Algorithm:
Starting with a fix initialization value of 0, the ‘Forward Pass Algorithm’ will help you calculate the project activity earliest start time and earliest finishing time and the ‘Backward Pass Algorithm’ will help you calculate the latest start time and latest finishing time of the activities in the project. The difference in value between the latest finishing time and the earliest finishing time is the slack, also known as the Total Float, with which you can use to determine the critical path of the network.
For the activity’s ‘Earliest time’ ET_{i }at node i;
For the activity’s ‘Latest time’ LT_{i} at node i;
…And T_{ij =} duration of activity (i,j)
Forward Pass
- Go through the tasks in order
- Start with ET_{1} = 0
- Find the earliest times at each node
- ET_{j} = max (ET_{i}+ T_{ij}) where max is taken over all arcs into node j
- Carry on until you reach the last node n (sink); the min project duration is ET_{n} = PD
Backward Pass
- Fix the finishing time
- Look at nodes/tasks in reverse order
- Start LT_{n}= PD
- LT(i) = min (LT_{j }– T_{ij}) where the min is taken over all arcs out of node i
Using this algorithm in practice with our project P:
Forward Pass
- ET_{1} = 0
- ET_{3} = 8 weeks
- ET_{2 }= 20 weeks
- ET_{4 }= ET_{3}+ T_{3,4}=8+11=19 weeks
- ET_{5 }= max (ET_{i}+ T_{ij}) = {ET_{3}+ T_{3,5}=8+12=20}, {ET_{3}+ T_{4,5}=8+11=19}, {ET_{2}+ T_{2,5}=20+5=25}, {ET_{2}+ T_{6,5}=20+6=26} = 26 weeks
- ET_{6 }= ET_{2}+ T_{2,6}=20+6=26 weeks
- ET_{7 }= ET_{5}+ T_{5,7}=26+7=33 weeks
- ET_{8 }= max (ET_{i}+ T_{ij}) = {ET_{7}+ T_{7,8}=33+10=43},{ET_{6}+ T_{6,8}=26+5=31} =43 weeks
- ET_{9 }= ET_{8}+ T_{8,9}=43+4=47 weeks
The Earliest finishing time of this project starting from initial time of 0 is 47 weeks.
Backward Pass
- LT_{9} = 47 weeks
- LT_{8} = LT_{9}-T_{8,9 }=47-4=43 weeks
- LT_{7} = LT_{8}-T_{7,8 }=43-10=33 weeks
- LT_{6} = LT_{8}-T_{6,8 }=43-5=38 min (LT_{j }– T_{ij}) ={ LT_{8}-T_{6,8 }=43-5=38}, {LT_{5}-T_{6,5 }=26-0=26} =26 weeks
- LT_{5} = LT_{7}-T_{5,7 }=33-7=26 weeks
- LT_{4} = LT_{5}-T_{4,5 }=26-0=26 weeks
- LT_{3} = min (LT_{j }– T_{ij}) ={LT_{4}-T_{3,4 }=26-11=15}, {LT_{5}-T_{3,5 }=26-12=14} =14 weeks
- LT_{2} = min (LT_{j }– T_{ij}) ={LT_{5}-T_{2,5 }=26-5=21}, {LT_{6}-T_{2,6 }=26-6=20} =20 weeks
- LT_{1} = min (LT_{j }– T_{ij}) ={LT_{3}-T_{1,3 }=14-8=6}, {LT_{2}-T_{1,2 }=20-20=0} =0
Node(i) | ET_{i} | LT_{i} |
1 | 0 | 0 |
2 | 20 | 20 |
3 | 8 | 14 |
4 | 19 | 26 |
5 | 26 | 26 |
6 | 26 | 26 |
7 | 33 | 33 |
8 | 43 | 43 |
9 | 47 | 47 |
Total float to determine the critical path through project P:
The Total float TF_{i,j}of an activity (i,j) is the amount by which activity (i,j) can be delayed without delaying the entire project:
TF_{i,j}=LT_{j}–ET_{i}– T_{ij}
e.g.
- For activity A {TF_{1,3}=LT_{3}–ET_{1}– T_{1,3 }=14-0-8=6}
- For activity D { TF_{1,2}=LT_{2}–ET_{1}– T_{1,2 }=20-0-20=0}
- For activity H { TF_{6,8}=LT_{8}–ET_{6}– T_{6,8 }=43-26-5=12}
Activity | TF |
A | 6 |
B | 6 |
C | 7 |
D | 0 |
E | 0 |
F | 0 |
G | 0 |
H | 12 |
I | 0 |
J | 1 |
From the table above, the critical path are the activities with 0 slack or 0 TF, also highlighted in red in the diagram above. Therefore the critical paths or the activities that determines the end date in this project schedule are:
Critical Paths:
- D–>E–>F–>G–>I
Now let’s crush this project!
I will now show you how to use linear programming and Excel Solver to optimise this constraint problem (i.e.Project P). We need to determine which activities should be crushed, in order to reduce Project P’s total duration as much as possible, whilst still keeping the total project cost at a minimum.
- Decision Variables:
X_{j}: the time that the event corresponding to node j occurs
R_{A}, R_{B}, R_{C}, R_{D}, R_{E}, R_{F}, R_{G}, R_{H}, R_{I} R_{J}: number of weeks by which duration of activity A, B, C, D, E, F, G, H, I, J can be reduced respectively i.e. Normal Duration – Crash Duration
- Objective Function:
Minimize Cost {Z=1000R_{A}+800R_{B}+1000R_{D}+2000R_{F}+1500R_{G}+800R_{H}+1000R_{J}}
- Constraints:
s.t (subject to)
R_{A}+X_{3}– X_{1}>=8 (Activity A constraint)
R_{D}+X_{2}-X_{1}>=20 (Activity D constraint)
X_{4}-X_{3}>=11 (Activity C constraint)
X_{6}-X_{2}=6 (Activity E constraint)
X_{5}-X_{6}>=0 (Dummy constraint)
X_{5}-X_{4}>=0 (Dummy constraint)
R_{B}+X_{5}-X_{3} >=12 (Activity B constraint)
R_{J}+X_{5}-X_{2} >=5 (Activity J constraint)
R_{F}+X_{7}-X_{5}>=7 (Activity F constraint)
R_{G}+X_{8}-X_{7}>=10 (Activity G constraint)
R_{H}+X_{8}-X_{6}>=5 (Activity H constraint)
X_{9}-X_{8}>=4 (Activity I constraint)
R_{A}<=2 (Reduction A constraint)
R_{D}<=5 (Reduction D constraint)
R_{B}<=2 (Reduction B constraint)
R_{J}<=1 (Reduction J constraint)
R_{F}<=2 (Reduction F constraint)
R_{G}<=2 (Reduction G constraint)
R_{H}<=1 (Reduction H constraint)
X_{9}-X_{1}<=32 (Minimum Total Duration constraint)
X_{j}, R_{A}, R_{B}, R_{C}, R_{D}, R_{E}, R_{F}, R_{G}, R_{H}, R_{I} R_{J}>=0 (Non Negativity)
Using Excel Solver here are the results (click here to learn how to use Excel Solver):
REDUCTION Decision Variables | Duration Reduction |
R_{A} | 0 |
R_{B} | 0 |
R_{D} | 5 |
R_{F} | 2 |
R_{G} | 2 |
R_{H} | 0 |
R_{J} | 0 |
Total Duration of Project = 47 – sum(reduction) = | 38 |
Objective Function | Minimize Cost Z = | 1000R_{A}+800R_{B}+1000R_{D}+2000R_{F}+1500R_{G}+800R_{H}+1000R_{J}= | 12000 |
Based on the results above, the activities D~F~G can be crushed by 5~2~2 weeks respectively, hence reducing the project’s total duration to 38 weeks at a total cost of £12000.