P1: OSO
JWDD004-app-E JWDD004-Halpin-v6 August 4, 2005 12:12
Appendix E
Arrow Notation Scheduling Calculations
E.1. CPM CALCULATIONS (ARROWNOTATION)
In making calculations with arrow notation, the arrow and its two associated nodes have
attributes that are formally defined as symbols for mathematical purposes. This formal
notation associated with the arrow is shown in Figure E.1.
The left-hand node on the arrow represents the event time at which the activity begins.
It is referred to as the i node. The right-hand node represents the end time of the activity. It
is referred to as the j node. Associated with each node is an earliest time, which is shown as
TE
i for the i node and TE
j for the j node. Similarly, each node can have a latest event time,
which is shown in the figure as TL
i for the i node and TL
j for the j node. This establishes
four events, two associated with starting and two with ending nodes, which are of interest
in calculating the critical path of the network. The duration of the activity (as shown in the
figure) is given as tij. Because the starting and ending nodes in arrow notation are referred
to as i and j, arrow notation is sometimes referred to as i-j notation.
A schematic diagram representing the application of the forward-pass algorithm using
arrow notation is shown in Figure E.2. The objective of the forward-pass algorithm is to
calculate the earliest point in time at which a given event can occur. That is, the algorithm
calculates the earliest event time of a given node. The earliest event time for a given node
is controlled by the earliest event times of each of the set of events that precede it. The
algorithm is given as follows:
All i
j = max[TE
i + tij]
iM
where M is the set of all i events that immediately precede j.
The earliest event time for a given node j is controlled by the earliest event times of
each of the i nodes that precede it. Each i node plus the duration of the associated activity,
tij which links it to the j node, must be investigated. The maximum of the preceding i node
early event times plus the durations of the appropriate activity ij controls the earliest time
at which a given event j, can occur.
To demonstrate this, consider Figure E.2. Node 30 is preceded by nodes 22, 25, and
26. The durations of the activities emanating from each of these nodes are as follows:
Act 22,30 t22,30 = 7 days
Act 25,30 t25,30 = 2 days
Act 26,30 t26,30 = 6 days
The earliest event times for each of the preceding nodes are as follows:
22 = 10
25 = 13
26 = 15
347
348 Appendix E
Figure E.1 Arrow notation symbols.
The algorithm for the early event time for node 30 is then
30 = max(TE
22 + t22,30, TE
25 + t25,30, TE
26 + t26,30)
or
30 = max(10 + 7, 13 + 2, 15 + 6) = 21
E.2. CALCULATING THE EARLY EVENT TIMES (ARROWNOTATION)
In order to understand howthe forward-pass algorithm is applied, consider the arrownotation
network model of the small gas station in Figure E.3. In order to record the calculated values
of the early event time (TE
i), a partitioned oval is located above each node. The calculated
early event time is recorded in the left side of the oval. During the backward pass, the late
event times for each node will be recorded in the right side.
The forward-pass algorithm is applied repetitively starting with the source node (node
A) and moving from left to right in a ÒbootstrappingÓ fashion. The starting node A is given
an early event time of zero (0). Moving to node B, the set of preceding events consists of
only one event. Therefore, TE
B is max (TE
A + tAB) = max (0 + 10) = 10. Calculations for
all of the nodes are shown in Table E.1. The values for each node are shown in Figure E.3.
The earliest time at which each activity can begin is given by the TE
i value for the i
node associated with the activity of interest. In addition to this information, it is now clear
that the minimum duration of the project is 96 days since the earliest time at which node S
can be realized has been calculated as 96 time units.
E.3. BACKWARD-PASS ALGORITHM (ARROWNOTATION)
A schematic diagram representing the application of the backward-pass algorithm is shown
in Figure E.4. The backward-pass algorithm calculates the latest time at which each event
can occur. The latest event time for a node i is controlled by the latest event times of the
set of events that follow it. The late event time of each j node minus the duration of the
associated activity, ij, must be investigated. The minimum of the following j node late event
times minus the duration of activity ij controls the latest time at which the i event can occur.
To demonstrate this, consider Figure E.4.
Figure E.2 Schematic of forward-pass calculation.
Appendix E 349
Figure E.3 Expanded Project Model with Early Event Times.
350 Appendix E
Table E.1 Calculation of Early Event Times
Node Formula Numerical Value T E
i
A N/A N/A 0
B TE
B = max (TE
A + tAB) max (0 + 10) 10
C TE
C = max (TE
B + tBC, TE
A + tAC ) max (10 + 8, 0 + 15) 18
D TE
D = max (TE
C + tCD) max (18 + 0) 18
E TEE
= max (TE
C + tCE) max (18 + 0) 18
F TE
F = max (TE
B + tBF, TE
C + tCF, TE
D + tDF,
TEE
+ tEF)
max (10 + 12, 18 + 2, 18
+ 5, 18 + 6)
24
G TEG
F + tFG) max (24 + 8) 32
H TE
H = max (TEG
+ tGH) max (32 + 10) 42
I TEI
H + tHI ) max (42 + 0) 42
J TEJ
H + tHJ) max (42 + 15) 57
K TEK
H + tHK, TEI
+ tIK ) max (42 + 14, 42 + 4) 56
L TE
L = max (TEJ
+ tJL, TEK
+ tKL) max (57 + 10, 56 + 0) 67
M TEM
L + tLM) max (67 + 0) 67
N TEN
= max (TEO
+ tON) max (77 + 0) 77
O TEO
L + tLO, TEM
+ tMO) max (67 + 6, 67 + 10) 77
P TE
P = max (TEO
+ tOP) max (77 + 0) 77
Q TE
Q = max (TEK
+ tKQ, TEN
+ tNQ, TEO
+ tOQ,
P + tPQ, TE
L + tLO)
max (56 + 12, 77 + 3,
77 + 6, 77 + 8, 67 + 25)
92
R TE
R = max (TE
Q + tQR) max (92 + 1) 93
S TE
S = max (TE
R + tS ) max (93 + 3) 96
Node i, labeled 18, is followed by nodes 21, 23, and 25. The durations of the associated
ij activities are:
Act 18,21 t18,21 = 12
Act 18,23 t18,23 = 3
Act 18,25 t18,25 = 10
...
Januszek66