Project Network | Sahithyan's Notes

Project management represents a project as a network of activities and events, used to schedule and analyze the project’s timeline.

A project completes only when every activity finishes. Since activities have predecessors, the project duration is bounded by its slowest chain of dependent activities, the path from initial to final event with the largest sum of durations.

Activity

A task consuming time and resources. Represented as an arrow between 2 events.

Predecessor

An activity that must finish before another can start.

Successor

An activity that cannot start until another finishes.

Chain

A sequence of activities in which each is a predecessor of the next.

Dummy Activity

Consumes 0 time and resources. Added only to preserve correct precedence when 2 activities share the same start and end events, or to represent a precedence relationship the diagram couldn’t otherwise express.

Logical Dummy

A dummy activity that represents a precedence relationship between activities. It shows that one activity must finish before another can start, without implying any additional activity.

Identity Dummy

A dummy activity that distinguishes activities with the same start and end events. It preserves the rule that no 2 activities can share both events.

Event

An instantaneous point in time marking the start or completion of one or more activities. Represented as a node.

An event isn’t a task and consumes no time or resources itself. It’s a milestone: the moment every activity ending there has finished, so every activity starting there is now free to begin.

Incoming Activity

An activity ending at that event.

Outgoing Activity

An activity starting at that event.

Network Construction Rules

Every activity has exactly one start and one end event.
No 2 activities can share both the same start and end event (use a dummy activity to separate them).
The network must have no cycles: an event can’t depend on an activity that (directly or indirectly) depends on it.

Critical Path Method

Critical Path Method finds that duration, and identifies the activities on that slowest chain.

Course Scope

Network analysis is treated through the LP approach in this course. Dijkstra’s algorithm was not covered in class.

Earliest Start Time

$ES_{ij}$ is the largest total duration of any chain that ends at a predecessor of $(i,j)$ , or $0$ if $(i,j)$ has no predecessors.

Earliest Finish Time

$EF_{ij} = ES_{ij} + t_{ij}$ , the earliest time activity $(i,j)$ can end.

When 2 activities affect the start of a milestone, the milestone’s earliest start time is the maximum of the 2 incoming early finish times. Reordering a dummy arrow can change an intermediate milestone value without changing the actual activity’s early finish time or the total project duration.

Latest Start Time

$LS_{ij} = LF_{ij} - t_{ij}$ , the latest time activity $(i,j)$ can begin without delaying the project.

Latest Finish Time

$LF_{ij}$ is the project duration minus the largest total duration of any chain that starts at a successor of $(i,j)$ , or the project duration if $(i,j)$ has no successors.

Project Duration

The largest total duration of any chain of activities. Every activity on that chain must finish in sequence before the project ends.

Critical Path

The chain of activities from the initial to the final event in which every activity has total float $0$ . Delaying any activity on the critical path delays the entire project.

Every activity still has to complete for the project to finish, not only the ones on the critical path. An activity off the critical path has slack, room to start later or take longer without pushing the project duration past what the critical path already fixes.

Steps

Forward pass
Compute $ES$ and $EF$ for every activity, from the first activity to the last.
Backward pass
Compute $LF$ and $LS$ for every activity, from the last activity back to the first. Each $LS$ uses its own $LF$ , so no step needs a value that is computed later.
Project duration is the largest $EF$ .
Critical path
The activities with total float $0$ .

Float

The slack in an activity’s schedule, how much it can be delayed without consequence. 0 for every activity on the critical path.

For an activity $(i,j)$ starting at event $i$ and ending at event $j$ , with duration $t_{ij}$ :

Total Float

\text{Total float} = LF_{ij} - EF_{ij} = LS_{ij} - ES_{ij}

How much an activity can be delayed without delaying the project’s completion. Delaying it by more than its total float may still delay other activities.

Free Float

\text{Free float} = \min_{s} ES_{s} - EF_{ij}

Here $s$ ranges over the successors of $(i,j)$ . If $(i,j)$ has no successors, use the project duration in place of $\min_{s} ES_{s}$ .

How much an activity can be delayed without delaying the earliest start of any following activity.

Independent Float

\text{Independent float} = \max\Big(\min_{s} ES_{s} - \min_{k} LS_{k} - t_{ij},\ 0\Big)

Here $s$ ranges over the successors of $(i,j)$ , and $k$ ranges over every activity starting at event $i$ . Use the project duration in place of $\min_{s} ES_{s}$ if $(i,j)$ has no successors.

How much an activity can be delayed without affecting any preceding or following activity’s float. Negative values are treated as 0.

\text{Independent float} \le \text{Free float} \le \text{Total float}

Worked Example

A project has 6 activities. The table gives the duration and predecessors of each activity.

Activity	Duration	Predecessor
$A$	4	none
$B$	3	none
$C$	2	$A$
$E$	5	$B$
$F$	3	$B$ , $C$
$G$	4	$E$

Construct the network from the table, one activity at a time, then compute the earliest and latest times of every activity and the floats.

Solution Reveal Hide

1 /

$A$ runs from event 1 to event 2, duration $4$ .

$B$ runs from event 1 to event 3, duration $3$ .

$C$ runs from event 2 to event 4, duration $2$ . It starts only after $A$ finishes.

$D$ runs from event 3 to event 4, duration $0$ . It consumes no time or resources.

$E$ runs from event 3 to event 5, duration $5$ .

$F$ runs from event 4 to event 6, duration $3$ . Its predecessors are $C$ and $D$ .

$F$ depends on both $B$ and $C$ , but $B$ ‘s arrow already ends at event 3, where $E$ starts, and an activity can only have one end event. Merging events 3 and 4 would make $E$ depend on $C$ too. The dummy $D$ makes $F$ wait for $B$ without making $E$ wait for $C$ .

$G$ runs from event 5 to event 6, duration $4$ . The network is complete.

/* This block is passed through unscoped, so every rule keeps the .walkthrough prefix explicitly. */ .walkthrough [data-live] { display: none; } .walkthrough .stack { display: block; } .walkthrough .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .walkthrough .stack .step [data-stage] { display: revert; } .walkthrough .stack .step [data-stage] table { display: revert; } .walkthrough .foot { display: none; }

Each event gets 2 squares above it. The left square holds the earliest finish time ( $EF$ ), and the right square the latest finish time, $LF$ .

The forward pass fills $EF$ from event 1 to event 6, $EF_j = \max_i (EF_i + t_{ij})$ over the activities $i \to j$ entering event $j$ . The backward pass fills $LF$ from event 6 back to event 1, $LF_i = \min_j (LF_j - t_{ij})$ over the activities $i \to j$ leaving event $i$ .

1 /

Event 1 has no predecessors, so $EF_1 = 0$ . Each of events 2 and 3 has a single incoming activity from event 1, so $EF_2 = 0 + 4 = 4$ and $EF_3 = 0 + 3 = 3$ .

Event 4 waits for both incoming activities, $C$ and the dummy $D$ . $EF_4 = \max(EF_2 + 2,\ EF_3 + 0) = \max(6,\ 3) = 6$ .

Event 5 has the single incoming activity $E$ , so $EF_5 = EF_3 + 5 = 3 + 5 = 8$ .

$EF_6 = \max(EF_4 + 3,\ EF_5 + 4) = \max(9,\ 12) = 12$ . The project duration is $12$ .

Event 6 has no successors, so $LF_6$ is the project duration, $LF_6 = 12$ .

$LF_5 = LF_6 - t_G = 12 - 4 = 8$ .

$LF_4 = LF_6 - t_F = 12 - 3 = 9$ .

Event 3 has 2 outgoing activities, the dummy $D$ and $E$ , so the smaller value wins. $LF_3 = \min(LF_4 - 0,\ LF_5 - 5) = \min(9,\ 3) = 3$ .

$LF_2 = LF_4 - t_C = 9 - 2 = 7$ .

Event 1 has 2 outgoing activities, $A$ and $B$ . $LF_1 = \min(LF_2 - 4,\ LF_3 - 3) = \min(3,\ 0) = 0$ .

Every float can be read from the graph. For an activity from event $i$ to event $j$ with duration $t$ , use the boxes at its two events:

The EF box at $i$ is the earliest the activity can start.
The LF box at $j$ is the latest the activity can finish.
The EF box at $j$ is the earliest any successor of the activity can start.
The LF box at $i$ is the latest any predecessor of the activity can finish.

This gives the three floats directly:

\text{Total float} = LF_j - EF_i - t

\text{Free float} = EF_j - EF_i - t

\text{Independent float} = \max\big(EF_j - LF_i - t,\ 0\big)

For $A$ , which runs from event 1 to event 2 with $t = 4$ , the boxes show $EF_1 = 0$ , $LF_1 = 0$ , $EF_2 = 4$ and $LF_2 = 7$ .

Total float is $7 - 0 - 4 = 3$
Free float is $4 - 0 - 4 = 0$
Independent float is $\max(4 - 0 - 4,\ 0) = 0$

For $C$ , which runs from event 2 to event 4 with $t = 2$ , the boxes show $EF_2 = 4$ , $LF_2 = 7$ , $EF_4 = 6$ and $LF_4 = 9$ .

Total float is $9 - 4 - 2 = 3$
Free float is $6 - 4 - 2 = 0$
Independent float is $\max(6 - 7 - 2,\ 0) = 0$

For $F$ , which runs from event 4 to event 6 with $t = 3$ , the boxes show $EF_4 = 6$ , $LF_4 = 9$ , $EF_6 = 12$ and $LF_6 = 12$ .

Total float is $12 - 6 - 3 = 3$
Free float is $12 - 6 - 3 = 3$
Independent float is $\max(12 - 9 - 3,\ 0) = 0$

The other activities are read the same way.