D1 4.3 - Critical paths and event times

D1 4.3 - Critical paths and event times

Find a project's minimum completion time using a forward pass, then work backwards to find how late each event may occur without delaying completion. You will identify all critical paths and calculate earliest and latest start and finish times for individual activities.

Forward pass for earliest events

If two branches take the same time, can the project have two critical paths? And if one branch becomes longer, what changes elsewhere? A small network will let us trace both effects exactly.

Use activities A:1→2A:1\to2 of duration 44, B:1→3B:1\to3 of duration 66, C:2→4C:2\to4 of duration 55, D:3→4D:3\to4 of duration 33, E:4→5E:4\to5 of duration 22, with dummy 2→32\to3 of duration zero. Durations are in days; project time starts at 00. Activities may run at the same time when dependencies allow, and sufficient workers and equipment are available.

[DIAGRAM: asset_name: A project with two branches; asset_slug: critical-path-network; caption: Event 4 must wait for both C and D; the dummy also makes D wait for A.; description: Directed activity-on-arc network A 1 to 2 duration4 B 1 to 3 duration6 C 2 to 4 duration5 D 3 to 4 duration3 E 4 to 5 duration2 and dashed dummy2 to3 duration0.]
Event 4 must wait for both C and D

The earliest event time, eie_i, is the earliest that event ii can occur. It must wait for every incoming activity, so choose the maximum candidate arrival time. This differs from Dijkstra's shortest-path calculation: project completion cannot choose to ignore its slower required branch.

Forward pass

Set estart=0e_{\text{start}}=0. For each later event jj,

ej=max⁡i→j(ei+dij),e_j=\max_{i\to j}(e_i+d_{ij}),

where dijd_{ij} is the duration of that activity, including zero for a dummy. The earliest finish event time is the minimum project duration under the stated resource assumptions. Not in the formula booklet: learn it.

Worked example 1: earliest event times

Find the earliest event times for the pictured project.

Plan. Move in arrow order, calculating every incoming candidate before taking a maximum.

e1=0e2=0+4=4e3=max⁡(0+6,4+0)=6e4=max⁡(4+5,6+3)=9e5=9+2=11\begin{aligned} e_1&=0\\ e_2&=0+4=4\\ e_3&=\max(0+6,4+0)=6\\ e_4&=\max(4+5,6+3)=9\\ e_5&=9+2=11 \end{aligned}

Answer. Earliest times 0,4,6,9,110,4,6,9,11 at events 1,2,3,4,51,2,3,4,5; minimum project duration 1111 days.

Check. Both real branches A,C,EA,C,E and B,D,EB,D,E take 1111 days. Starting activities as early as possible attains the calculated finish, so 1111 is feasible as well as necessary.

Change only BB's duration from 66 to 77. The dummy still has duration zero, but its start event is not necessarily simultaneous with its finish event.

Worked example 2: a longer branch

Find the new earliest event times when B=7B=7.

Plan. Repeat the maximum comparisons wherever the changed duration can affect a successor.

e1=0,e2=4,e3=max⁡(7,4)=7,e_1=0,\quad e_2=4,\quad e_3=\max(7,4)=7, e4=max⁡(4+5,7+3)=10,e5=10+2=12.e_4=\max(4+5,7+3)=10,\qquad e_5=10+2=12.

Answer. Earliest times 0,4,7,10,120,4,7,10,12; minimum duration 1212 days.

Check. The branch B,D,EB,D,E now takes 7+3+2=127+3+2=12, whereas A,C,EA,C,E takes 1111. Event 44 must wait for the longer one.

A zero-duration dummy enforces “not before”, not “must happen at the same time”. Event 33 still waits for BB.

Backward pass for latest events

The latest event time tells you how late an event may occur while retaining the minimum project duration.

Write lil_i for this time. At an event with several outgoing activities, every successor's deadline must be respected. Subtract each outgoing duration from its successor's latest time and take the minimum: the tightest restriction controls.

Backward pass

For completion in the minimum duration, set lfinish=efinishl_{\text{finish}}=e_{\text{finish}}. Working against the arrows,

li=min⁡i→j(lj−dij).l_i=\min_{i\to j}(l_j-d_{ij}).

Earliest times use maximum incoming values; latest times use minimum outgoing values. Not in the formula booklet: learn it.

Worked example 3: latest times for the original project

Use the original B=6B=6 project, whose minimum duration is 1111 days.

Plan. Set the finish deadline to 1111, then work backwards through all outgoing constraints.

l5=11l4=11−2=9l3=9−3=6l2=min⁡(9−5,6−0)=4l1=min⁡(4−4,6−6)=0\begin{aligned} l_5&=11\\ l_4&=11-2=9\\ l_3&=9-3=6\\ l_2&=\min(9-5,6-0)=4\\ l_1&=\min(4-4,6-6)=0 \end{aligned}

Answer. Latest times 0,4,6,9,110,4,6,9,11, equal to the earliest times here.

Check. Each arc satisfies li+dij≤ljl_i+d_{ij}\le l_j. At event 22, taking the larger candidate 66 would make CC finish at 6+5=116+5=11, too late for event 44's deadline 99.

Change only to the B=7B=7 version, whose finish deadline is now 1212.

Worked example 4: latest times with a longer branch

Find the revised latest event times.

Plan. Recalculate backwards from the revised minimum finish time, rather than retaining the old deadline.

l5=12l4=12−2=10l3=10−3=7l2=min⁡(10−5,7−0)=5l1=min⁡(5−4,7−7)=0\begin{aligned} l_5&=12\\ l_4&=12-2=10\\ l_3&=10-3=7\\ l_2&=\min(10-5,7-0)=5\\ l_1&=\min(5-4,7-7)=0 \end{aligned}

Answer. Latest times 0,5,7,10,120,5,7,10,12. Event 22 may occur between its earliest 44 and latest 55.

Check. Event 22 at time 55 permits CC to finish at 1010, exactly on time. At time 66, CC would finish at 1111, delaying EE and the project.

[DIAGRAM: asset_name: Earliest and latest event times; asset_slug: critical-event-times; caption: With B taking 7 days, event 2 has earliest time 4 and latest time 5.; description: The same five-event project with B duration7, each event drawn with its earliest time above latest time: event1 0 and0 event2 4 and5 event3 7 and7 event4 10 and10 event5 12 and12.]
With B taking 7 days, event 2 has earliest time 4 and latest time 5.

Check that ei≤lie_i\le l_i at every event. A computed earliest time greater than a latest time means an error, or an impossible supplied deadline if the question fixes one shorter than the required duration.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account