OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

To remind you of the problem we considered before it was a small project that consisted of 11 activities (as below):

Activity Completion number time (weeks) 1 Redesign product 6 2 Redesign packaging 2 3 Order and receive components for redesigned product 3 4 Order and receive material for redesigned packaging 2 5 Assemble products 4 6 Make up packaging 1 7 Package redesigned product 1 8 Test market redesigned product 6 9 Revise redesigned product 3 10 Revise redesigned packaging 1 11 Present results to the Board 1

with the following list of immediate precedence relationships:

Activity Activity number number 1 must be finished before 3 can start 2 4 3 5 4 6 5,6 7 7 8 8 9 8 10 9,10 11

In the network diagram shown below which represents this project, each
*arc* represents an activity and is labelled with the activity number
and the associated completion time (shown in brackets after the activity
number). This network is an *activity on arc (AOA)* network. The *nodes*
of the network represent the start (and end) of activities and are regarded
as *events*.

In constructing the network we use the precedence relationships to construct it from left to right - adding activities (arcs) to the network as the precedence relationships indicate that activities can start.

The key to constructing the network is the question: "*What activities
can start now?*"

Initially, for example, both activities 1 and 2 can start. Once activity 1 has been finished activity 3 can start, once activity 2 has been finished activity 4 can start, etc. The nodes of the network are numbered 1,2,3,...,etc. Note:

- that all arcs have arrows attached to them (indicating the direction the project is flowing in)
- the way the relationship "activities 5 and 6 must be finished before activity 7 can start" is represented

The diagram below illustrates the kinds of situation we can represent in network diagrams.

In the last situation shown above we have a dotted arc. This dotted
arc is a *dummy activity*. Dummy activities often have a zero completion
time and are used to represent precedence relationships that cannot be
easily (if at all) represented using the actual activities involved in
the project. **By convention dummies are always shown as dotted arcs in
network diagrams**.

Note the difference between the last two situations shown above. The difference between them is that in one C must be finished before B can start, and in the other there is no relationship between C finishing and B starting.

Suppose that we had included in our list of precedence relationships "activity 3 must be finished before activity 8 can start" - then the easiest way to represent this on the network diagram is by having a dummy activity, with a zero completion time, directed from node 3 (the end of activity 3) to node 7 (the start of activity 8).

Dummy activities can have a non-zero completion time, e.g. if (taking the example mentioned in the previous paragraph) there must be a two week delay between finishing activity 3 and starting activity 8.

Often in drawing large networks we find that the easiest way to represent some precedence relationships is by dummy activities. Note here however that in AOA networks there is often more than one way to correctly represent the network logic using dummies. Note too that the key to drawing dummies to to

- ensure that they correctly represent the logic you want; but also that
- they do not introduce unintended consequences (introduce precedence restrictions that you do not want)

Below we repeat the network diagram for the problem we were considering before.

In order to analyse this network *without* the aid of a computer
package we first calculate, for each node (event) in the network, the *earliest
time* we can reach that node such that all preceding activities have
been finished. We do this below.

Let E_{i} represent the **earliest time by which we can reach
node i such that all its preceding activities have been finished**. We
calculate the values of the E_{i} (i=1,2,...,10) by going forward,
from left to right, in the network diagram.

To ease the notation let T_{ij} be the activity completion time
associated with the arc from node i to node j (e.g. T_{56} = 1).
Then the E_{i} are given by:

E_{1} = 0 (assuming we start at time zero)

E_{2} = E_{1} + T_{12} = 0 + 6 = 6

E_{3} = E_{2} + T_{23} = 6 + 3 = 9

E_{4} = E_{1} + T_{14} = 0 + 2 = 2

E_{5} = E_{4} + T_{45} = 2 + 2 = 4

E_{6} = max[E_{3} + T_{36}, E_{5} + T_{56}]
= max[9 + 4, 4 + 1] = 13

E_{7} = E_{6} + T_{67} = 13 + 1 = 14

E_{8} = E_{7} + T_{78} = 14 + 6 = 20

E_{9} = E_{8} + T_{89}, but here we have two
activities running from node 8 to node 9 (activity 9 of duration 3 and
activity 10 of duration 1) so:

E_{9} = max[E_{8} + 3, E_{8} + 1] = max[20 +
3, 20 + 1] = 23

E_{10} = E_{9} + T_{9,10} = 23 + 1 = 24

Hence E_{10} = 24 and this represents the earliest time we can
reach node 10 with all preceding activities finished i.e. 24 (weeks) is
the minimum time needed to complete *all* the activities and hence
is the minimum overall project completion time.

Note here that the formal definition of the earliest times is given by:

E_{j} = max[E_{i} + T_{ij} | i one of the nodes
linked to j by an arc from i to j]

This equation for calculating E_{j} is actually a formal statement
of the dynamic programming algorithm for the problem.

Conceptually we can think of this algorithm as finding the length of
the *longest path* in the network. However, because of the risk of
error, we should always carry out the above calculation explicitly, rather
than relaying on the eye/brain to spot the longest path in the network.
The eye/brain approach is infeasible anyway for large networks.

As well as the minimum overall project completion time calculated above
we can extract additional useful information from the network diagram by
the calculation of *latest times*. We deal with this below.

Let L_{i} represent the **latest time we can leave node i and
still complete the project in the minimum overall completion time**.
We calculate the values of the L_{i} (i=1,2,...,10) by going backward,
from right to left, in the network diagram. Hence:

L_{10} = E_{10} = 24 (the minimum overall completion
time)

L_{9} = L_{10} - T_{9,10} = 24 - 1 = 23

L_{8} = L_{9} - T_{89}, but here we have two
activities running from node 8 to node 9 (activity 9 of duration 3 and
activity 10 of duration 1) so:

L_{8} = min[L_{9} - 3, L_{9} - 1] = min[23 -
3, 23 - 1] = 20

L_{7} = L_{8} - T_{78} = 20 - 6 = 14

L_{6} = L_{7} - T_{67} = 14 - 1 = 13

L_{5} = L_{6} - T_{56} = 13 - 1 = 12

L_{4} = L_{5} - T_{45} = 12 - 2 = 10

L_{3} = L_{6} - T_{36} = 13 - 4 = 9

L_{2} = L_{3} - T_{23} = 9 - 3 = 6

L_{1} = min[L_{4} - T_{14}, L_{2} - T_{12}]
= min[10 - 2, 6 - 6] = 0

Note that as a check we would expect L_{1} = 0 since if we leave
node 1 later than time zero we would not complete the project in the minimum
overall completion time of 24 weeks.

The formal definition of the latest times is given by:

L_{i} = min[L_{j} - T_{ij} | j one of the nodes
linked to i by an arc from i to j]

Note that as a check that we have done both the earliest start times and latest start times calculations correctly we have:

- all latest start times must be >= 0
- at least one node must have a latest start time of zero

In fact (as with the package solution) using the latest times L_{i}
and the concept of float we can identify which activities are critical
in the above network in the sense that if a critical activity takes longer
than its estimated completion time the overall project completion time
will increase. We deal with this below.

Consider an activity running (in the network diagram) from node i to
node j. The earliest we can start that activity is E_{i} and since
it takes T_{ij} to complete the earliest we can finish it is E_{i}
+ T_{ij}. But L_{j} is the latest we must leave node j
to avoid increasing the overall project completion time and hence L_{j}
- (E_{i} + T_{ij}) is the amount of slack or *float*
time available. Formally: F_{ij} = L_{j} - (E_{i}
+ T_{ij}) = L_{j} - E_{i} - T_{ij} is the
amount by which we can increase the time taken to complete the activity
represented on the network diagram by the arc from node i to node j without
changing (increasing) the overall project completion time. Hence we can
form the table below:

Activity i j L_{j}E_{i}T_{ij}Float F_{ij }1 1 2 6 0 6 0 2 1 4 10 0 2 8 3 2 3 9 6 3 0 4 4 5 12 2 2 8 5 3 6 13 9 4 0 6 5 6 13 4 1 8 7 6 7 14 13 1 0 8 7 8 20 14 6 0 9 8 9 23 20 3 0 10 8 9 23 20 1 2 11 9 10 24 23 1 0

Any activity with a float of zero is critical. Note here that, as a check, all float values should be >= 0 and that these float values are the same as those derived by the package.

The easiest way to remember how to do the float calculation in AOA networks is by:

**Latest time at the activity end node - Earliest time at the activity
start node - Activity time**

Note in particular how whether an activity is critical or not **CANNOT**
be reliably deduced from whether the earliest and latest times coincide
at the start and end nodes (unlike AON networks). For example consider
nodes 8 and 9 in the above network - they both have earliest and latest
times that are identical, with two activities between them - yet only one
of those activities is critical.

The table below defines the activities within a small project.

Activity Start End Completion time node node (weeks) 1 1 2 2 2 1 3 4 3 2 4 7 4 3 4 3 5 3 5 7 6 4 5 3 7 5 6 4 8 4 6 6 9 6 7 2 10 4 7 7

In addition to the above information, activity five cannot start until three weeks after the end of activity one.

- Draw the network diagram.
- Calculate the minimum overall project completion time.
- Calculate the float time for each activity and hence identify the critical path.

Comment on the potential effect upon the overall project completion time (and the critical path) of:

- Cutting the completion time of activity eight by three weeks?
- Increasing the completion time of activity four by two weeks?
- Cutting the completion time of activity seven by two weeks?

Will the project finish on time if at the end of six weeks the status of the project is:

- Finished - activities one, two and four
- In progress - activity three (five weeks to completion) and activity five (four weeks to completion)

The network diagram is shown below. Note the introduction of node 8 and the two dummy activities 11 and 12 to correctly represent the condition that activity five cannot start until 3 weeks after the end of activity one.

We then have the following calculation of earliest start times to determine the minimum overall project completion time.

E_{1} = 0 (by definition)

E_{2} = E_{1} + T_{12} = 0 + 2 = 2

E_{3} = E_{1} + T_{13} = 0 + 4 = 4

E_{4} = max[E_{2} + T_{24}, E_{3} + T_{34}]
= max[2 + 7, 4 + 3] = 9

Now we obviously need to calculate E_{8}

E_{8} = max[E_{2} + T_{28}, E_{3} +
T_{38}] = max[2 + 3, 4 + 0] = 5

E_{5} = max[E_{4} + T_{45}, E_{8} + T_{85}]
= max[9 + 3, 5 + 7] = 12

E_{6} = max[E_{4} + T_{46}, E_{5} + T_{56}]
= max[9 + 6, 12 + 4] = 16

E_{7} = max[E_{6} + T_{67}, E_{4} + T_{47}]
= max[16 + 2, 9 + 7] = 18

Hence the minimum overall project completion time is 18 weeks.

To determine the float times and which activities are critical we need to work out the latest start times.

L_{7} = 18 (by definition)

L_{6} = L_{7} - T_{67} = 18 - 2 = 16

L_{5} = L_{6} - T_{56} = 16 - 4 = 12

L_{4} = min[L_{7} - T_{47}, L_{6} - T_{46},
L_{5} - T_{45}] = min[18-7,16-6,12-3] = 9

We now need to calculate L_{8}

L_{8} = L_{5} - T_{85} = 12 - 7 = 5

L_{3} = min[L_{4} - T_{34}, L_{8} - T_{38}]
= min[9 - 3, 5 - 0] = 5

L_{2} = min[L_{4} - T_{24}, L_{8} - T_{28}]
= min[9 - 7, 5 - 3] = 2

L_{1} = min[L_{2} - T_{12}, L_{3} - T_{13}]
= min[2 - 2, 5 - 4] = 0

and note that L_{1} = 0 as required.

To calculate the float times we use the equation F_{ij} = L_{j}
- E_{i} - T_{ij} to get

Activity i j L_{j}E_{i}T_{ij}F_{ij}1 1 2 2 0 2 0 2 1 3 5 0 4 1 3 2 4 9 2 7 0 4 3 4 9 4 3 2 5 8 5 12 5 7 0 6 4 5 12 9 3 0 7 5 6 16 12 4 0 8 4 6 16 9 6 1 9 6 7 18 16 2 0 10 4 7 18 9 7 2 11 2 8 5 2 3 0 12 3 8 5 4 0 1

Note here that all float times are >= 0 as required.

Hence the critical activities (those with a float of zero) are 1,3,5,6,7,9
and 11. This means that there are *two* critical paths, namely 1-11-5-7-9
and 1-3-6-7-9.

- activity eight is not critical, therefore cutting its completion time has no effect upon the overall project completion time or on the critical paths
- activity four has a float time of 2 weeks so increasing its completion time by 2 weeks does not effect the overall project completion time. However activity four will then become critical so the critical paths will be effected.
- activity seven is critical so cutting its completion time by 2 weeks
may reduce the overall project completion time. In fact as activity seven
appears in
*all*(both) critical paths we can be sure that the overall project completion time will be reduced by*at least*one time unit (week). The critical paths may, or may not, be effected.

After six weeks the new network diagram is shown below.

The earliest start time calculation is

E_{1} = 0 (by definition)

E_{4} = E_{1} + T_{14} = 0 + 5 = 5

E_{5} = max[E_{1} + T_{15}, E_{4} + T_{45}]
= max[0 + 4, 5 + 3] = 8

E_{6} = max[E_{5} + T_{56}, E_{4} + T_{46}]
= max[8 + 4, 5 + 6] = 12

E_{7} = max[E_{6} + T_{67}, E_{4} + T_{47}]
= max[12 + 2, 5 + 7] = 14

Hence the minimum overall completion time for the remaining part of the project is 14 weeks.

As 6 weeks have already elapsed this means that we cannot finish the
complete project before week 20, i.e. so far we have slipped 2 weeks upon
the original completion time of 18 weeks and there is *no possibility*
of the project finishing upon time.

Some more network analysis examples for activity on arc can be found here.