Critical Path Analysis and Crushing your Project.

business relayOptimising 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:

Project Network Diagram (click to expand)

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’ ETat node i;

For the activity’s ‘Latest time’ LTi at node i;

…And Tij = duration of activity (i,j)

Forward Pass

  •        Go through the tasks in order
  •        Start with ET1 = 0
  •        Find the earliest times at each node
  •        ETj = max (ETi+ Tij) 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 ETn = PD

Backward Pass

  •         Fix the finishing time
  •         Look at nodes/tasks in reverse order
  •         Start LTn= PD
  •         LT(i) = min (LTj – Tij) where the min is taken over all arcs out of node i

Using this algorithm in practice with our project P:

Forward Pass

  • ET1 = 0
  • ET3 = 8 weeks
  • ET2 = 20 weeks
  • ET4 = ET3+ T3,4=8+11=19 weeks
  • ET5 = max (ETi+ Tij) = {ET3+ T3,5=8+12=20}, {ET3+ T4,5=8+11=19}, {ET2+ T2,5=20+5=25}, {ET2+ T6,5=20+6=26} = 26 weeks
  • ET6 = ET2+ T2,6=20+6=26 weeks
  • ET7 = ET5+ T5,7=26+7=33 weeks
  • ET8 = max (ETi+ Tij) = {ET7+ T7,8=33+10=43},{ET6+ T6,8=26+5=31} =43 weeks
  • ET9 = ET8+ T8,9=43+4=47 weeks

The Earliest finishing time of this project starting from initial time of 0 is 47 weeks.

Backward Pass

  • LT9 = 47 weeks
  • LT8 = LT9-T8,9 =47-4=43 weeks
  • LT7 = LT8-T7,8 =43-10=33 weeks
  • LT6 = LT8-T6,8 =43-5=38  min (LTj – Tij) ={ LT8-T6,8 =43-5=38}, {LT5-T6,5 =26-0=26} =26 weeks
  • LT5 = LT7-T5,7 =33-7=26 weeks
  • LT4 = LT5-T4,5 =26-0=26 weeks
  • LT3 = min (LTj – Tij) ={LT4-T3,4 =26-11=15}, {LT5-T3,5 =26-12=14} =14 weeks
  • LT2 = min (LTj – Tij) ={LT5-T2,5 =26-5=21}, {LT6-T2,6 =26-6=20} =20 weeks
  • LT1 = min (LTj – Tij) ={LT3-T1,3 =14-8=6}, {LT2-T1,2 =20-20=0} =0 
Node(i) ETi LTi
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 TFi,jof an activity (i,j) is the amount by which activity (i,j) can be delayed without delaying the entire project:

TFi,j=LTj–ETi– Tij

e.g.

  • For activity A {TF1,3=LT3–ET1– T1,3 =14-0-8=6}
  • For activity D { TF1,2=LT2–ET1– T1,2 =20-0-20=0}
  • For activity H { TF6,8=LT8–ET6– T6,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
Project Network Diagram with Critical Path
Project Network Diagram with Critical Path in red (click to expand)

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:

Xj: the time that the event corresponding to node j occurs

RA, RB, RC, RD, RE, RF, RG, RH, RI RJ: 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=1000RA+800RB+1000RD+2000RF+1500RG+800RH+1000RJ}

  •  Constraints:

s.t (subject to)

RA+X3– X1>=8                                                  (Activity A constraint)

RD+X2-X1>=20                                                 (Activity D constraint)

X4-X3>=11                                                       (Activity C constraint)

X6-X2=6                                                           (Activity E constraint)

X5-X6>=0                                                         (Dummy constraint)

X5-X4>=0                                                         (Dummy constraint)

RB+X5-X3 >=12                                                (Activity B constraint)

RJ+X5-X2 >=5                                                   (Activity J constraint)

RF+X7-X5>=7                                                    (Activity F constraint)

RG+X8-X7>=10                                                 (Activity G constraint)

RH+X8-X6>=5                                                   (Activity H constraint)

X9-X8>=4                                                          (Activity I constraint)

RA<=2                                                              (Reduction A constraint)

RD<=5                                                              (Reduction D constraint)

RB<=2                                                              (Reduction B constraint)

RJ<=1                                                              (Reduction J constraint)

RF<=2                                                              (Reduction F constraint)

RG<=2                                                             (Reduction G constraint)

RH<=1                                                             (Reduction H constraint)

X9-X1<=32                                                       (Minimum Total Duration constraint)

Xj, RA, RB, RC, RD, RE, RF, RG, RH, RI RJ>=0            (Non Negativity)

Using Excel Solver here are the results (click here to learn how to use Excel Solver):

REDUCTION Decision Variables Duration Reduction
RA 0
RB 0
RD 5
RF 2
RG 2
RH 0
RJ 0
Total Duration of Project = 47 – sum(reduction) = 38

 

Objective Function Minimize Cost Z = 1000RA+800RB+1000RD+2000RF+1500RG+800RH+1000RJ= 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.

HTML Snippets Powered By : XYZScripts.com