Which of the following includes all of the relationships represented on an activity on node diagram?

OR-Notes

J E Beasley

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.

---

Network analysis - activity on node

In the network diagram shown below, for the problem we considered before, each node (circle) 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 node (AON) network.

In constructing the network we:

• draw a node for each activity
• add an arrow from (activity) node i to (activity) node j if activity i must be finished before activity j can start (activity i precedes activity j). Note here that all arcs have arrows attached to them (indicating the direction the project is flowing in).

One tip that I find useful in drawing such diagrams is to structure the positioning of the nodes (activities) so that the activities at the start of the project are at the left, the activities at the end of the project at the right, and the project "flows" from left to right in a natural fashion.

Once having drawn the network it is a relatively easy matter to analyse it (using a dynamic programming algorithm to find the critical path). However we will not consider this algorithm in any detail here but will instead use the computer package to solve the problem.

Note here one key point, the above network diagram assumes that activities not linked by precedence relationships can take place simultaneously (e.g. at the start of the project we could be doing activity 1 at the same time as we are doing activity 2).

Essentially the above diagram is not needed for a computer - a computer can cope very well (indeed better) with just the lists of activities and their precedence relationships we had before. The above diagram is intended for people. Consider what might happen in a large project - perhaps many thousands or tens of thousands of activities and their associated precedence relationships. Do you think it would be possible to list those out without making any errors? Obviously not - so how can we spot errors? Looking at long lists in an attempt to spot errors is just hopeless. With a little practice it becomes easy to look at diagrams such as that shown above and interpret them and spot errors in the specification of the activities and and their associated precedence relationships.

---

Package solution

The problem (as represented by the network diagram) was solved using the package, the input being shown below. Note that we have chosen to enter the problem as a deterministic CPM problem. The various input options shown below will become more familiar to you as we progress.

The numbers entered following the above screen are as below.

The output from the package is shown below.

In the output we have a "Project Completion Time" of 24 (weeks). This means that if all the activities take exactly as long as expected the minimum time in which we can complete the project (complete all activities whilst obeying the precedence relationships) is 24 weeks.

Note here that we have (implicitly) assumed in calculating this figure of 24 weeks that we have sufficient resources to enable activities to be carried out simultaneously if required (e.g. activities 1 and 2 can be carried out simultaneously). Problems where this assumption does not hold are considered here.

In the column headed "Slack" we have, for each activity in turn, the amount of time that the activity can be delayed without altering (increasing) the overall project completion time. If delays occur in two or more activities then we must either analyse the effect on the project by hand, or rerun the problem with new data. Many textbooks also refer to slack by the term "float".

Activities with a slack of zero are called critical activities since they must all be completed on time to avoid increasing the overall project completion time. Hence, for this network, activities 1, 3, 5, 7, 8, 9 and 11 are the critical activities.

Note here that 1 3 5 7 8 9 11 constitutes a path in the network diagram from the initial node (node 1) to the final node (node 11). This is no accident because for any network there will always be a path of critical activities from the initial node to the final node. Such a path is called the critical path.

More strictly the definition of a critical path is a path of activities, each pair of activities in the path directly connected via a precedence relationship (arc), from the start (initial node) to the end (final node) of the project, where the completion times of the activities on the path sum to the overall minimum project completion time. All activities in this path must be critical by definition.

The output also lists, for each activity:

• Earliest start (ES): this is the earliest possible time that an activity can begin. All immediate predecessors must be finished before an activity can start.
• Latest start (LS): this is the latest time that an activity can begin and not delay the completion time of the overall project. If the earliest start and latest start times are the same then the activity is critical.
• Earliest finish (EF): this is the earliest possible time that an activity can be finished (= earliest start time + activity completion time).
• Latest finish (LF): this is the latest time that an activity can be finished and not delay the completion time of the overall project (= latest start time + activity completion time). As with start times, the activity is critical if the earliest finish and latest finish times are the same.
• Slack: this is the difference between the earliest start time and the latest start time (which in turn is equal to the difference between the latest start time and the latest finish time), i.e. Slack = LS-ES = LF-EF

Note also:

• there may be more than one critical path - in fact it often makes more sense to talk about critical activities rather than the critical path. For example, suppose in the above network activity 10 took 3 weeks to complete (i.e. the same as activity 9). Then activity 10 would also be critical and we would have multiple critical paths, in fact two critical paths one 1 3 5 7 8 9 11 as before and a new critical path 1 3 5 7 8 10 11.
• the larger the slack the less critical the activity e.g. what would happen to the overall project completion time if the completion time for activity 6 increased by 5?

Be warned that, both in the textbooks and in the literature, there are various different ways of performing network analysis presented - in particular:

• different definitions of slack
• different network diagrams (exchanging the role of nodes and arcs) - in fact there are two types of network diagram, activity on node (AON) which we have used above and activity on arc (AOA) which we have not discussed here
• different notation conventions.

---

Discussion

We started out by trying to answer the key question:

What is the minimum possible time in which we can complete this project?

In the course of answering this question we have encountered a number of unexpected, but extremely useful, benefits. We now know:

• the critical activities which, if delayed, will delay the completion of the overall project
• for the non-critical activities a precise numeric indication of the amount of slack associated with their completion

It is clear that this information will be of great use in managing the project though to successful completion.

Moreover we, in drawing the network diagram, have had to THINK about our project. This process of thinking clearly and logically about the project is also of great benefit.

Note here that we have stressed managing the project through to successful completion. Network analysis is not magic. We cannot just draw the network, calculate the critical path and then go on holiday, returning when the project is scheduled to finish. The project must be managed to completion. However network analysis provides us with a vital technique for the successful management of the project.

---

Effect of changes

Often we have to predict the effect on the project completion time of a change in an activity completion time. In general we have the table below indicating how the overall project completion time is affected by a change in the activity completion time.

Activity critical non-criticalActivity completion project completion project completion time increases by T time increases by time unaffected if exactly T T <= float project completion time increases by exactly (T-float) if T > floatActivity completion project completion project completion time decreases by T time may change time unaffected so recalculate

Note here that the above table only holds for a change in the completion time of a single activity. If completion times for two (or more) activities change the situation is more complex and we must recalculate the overall project completion time.

Note too here that if the activity completion time of a critical activity decreases we may for a small network (via inspection or logic) be able to see whether or not we need to recalculate. For example, if there is just one critical path and the completion time of a critical activity reduces by one time unit then (by logic) the completion time of the overall project must also reduce by one time unit.

---

Exploring the package

The package used, whilst not as powerful as commercially available (and commercially priced) packages such as Microsoft Project does have a number of features that are also present in more expensive packages. For example we can get an automatic graphical representation of the problem from our spreadsheet input (do Format and Switch to Graphic Model). This is shown below.

In this activity on node graphic representation the notation used is that the centre number in each node is the activity name (a number in this case) and the upper number in each node is the activity duration.

Once we have solved the problem to determine the critical path we have a number of different options available from the Results menu.

Activity Criticality Analysis gives us the output shown previously above.

Graphic Activity Analysis gives us:

which shows the network (as before), but now with the earliest/latest start/finish times for each node (activity). Note that the times shown for each activity are ES, EF, LS, and LF (from left to right, from top to bottom).

Show Critical Path merely gives us a listing of the critical path as below.

Gantt Chart gives us the output below (note that the chart can be altered in size using Scale).

The Gantt chart was originated by H.L. Gantt in 1918. Here the package displays both the earliest and latest times for each activity and the critical path for the project (using suitable colours). In this output each activity has two horizontal bars. The first bar represents when it will take place if it is started at its earliest start time. The second bar represents when it will take place if it is scheduled at its latest start time. Obviously for critical activities the two bars are identical.

Gantt charts are quite commonly used. They provide an easy graphical representation of when activities (might) take place.

Note here that one thing which will become crucial if we go deeper into network analysis is the non-critical activities. In the above Gantt chart we can see that (within limits) we have a choice as to when non-critical activities start. For example activity 2 can start at times: 0,1,2,...,8 i.e. at any time between 0 and 8 without affecting the overall project completion time. We can say that there is a time window [0,8] within which activity 2 can be started without affecting the overall project completion time. As we have a choice as to when in this time window we start activity 2 then we have a DECISION to be made. Making appropriate decisions as to precisely when to start non-critical activities is a key feature of network analysis/project management.

Project Completion Analysis enables us to see the state of the project at any time. For example doing that analysis after 12 weeks (say) gives:

Here we can see that it is anticipated that after 12 weeks a number of activities (activities 1,2,3,4) will have all have been completed, activity 5 will have been 75% completed and the remaining activities not yet started. This analysis assumes:

• all activities are started at their earliest start times
• all activities take exactly as long as planned

Obviously in practice these assumptions may not be true.

---

Network analysis - dynamic programming algorithm

Whilst being able to analyse a network via a computer using a package is obviously convenient we gain some additional insight if we could also analyse a network without the aid of a computer. In fact this is easily done.

Below we repeat the network diagram for the problem we were considering before. However note that we have now added a dummy activity (12) with a completion time of zero to represent the end of the project. This just makes the calculations we have to do easier to follow

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

Earliest start time calculation

Let Ei represent the earliest start time for activity i such that all its preceding activities have been finished. We calculate the values of the Ei (i=1,2,...,12) by going forward, from left to right, in the network diagram..

To ease the notation let Ti be the activity completion time associated with activity i (e.g. T5 = 4). Then the Ei are given by:

E1 = 0 (assuming we start at time zero)
E2 = 0 (assuming we start at time zero)
E3 = E1 + T1 = 0 + 6 = 6
E4 = E2 + T2 = 0 + 2 = 2
E5 = E3 + T3 = 6 + 3 = 9
E6 = E4 + T4 = 2 + 2 = 4
E7 = max[E5 + T5, E6 + T6] = max[9 + 4, 4 + 1] = 13
E8 = E7 + T7 = 13 + 1 = 14
E9 = E8 + T8 = 14 + 6 = 20
E10 = E8 + T8 = 14 + 6 = 20
E11 = max[E9 + T9, E10 + T10] = max[20 + 3, 20 + 1] = 23
E12 = E11 + T11 = 23 + 1 = 24

Hence 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 start times is given by:

Ej = max[Ei + Ti | i one of the activities linked to j by an arc from i to j]

This equation for calculating Ej 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 (consider walking from the left-hand side of the network, to the right-hand side, through the nodes, where the completion time at each node indicates how long we must wait at the node before we can move on). However, because of the risk of error, we should always carry out the above calculation explicitly, rather than relying on the eye/brain to inspect the network to spot the longest path in the network. This inspection 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 start times. We deal with this below.

Latest start times calculation

Let Li represent the latest time we can start activity i and still complete the project in the minimum overall completion time. We calculate the values of the Li (i=1,2,...,12) by going backward, from right to left, in the network diagram. Hence:

L12= 24
L11 = L12 - T11 = 24 - 1 = 23
L10 = L11 - T10 = 23 - 1 = 22
L9 = L11 - T9 = 23 - 3 = 20
L8 = min[L9 - T8, L10 - T8] = min[20 - 6, 22 - 6] = 14
L7 = L8 - T7 = 14 - 1 = 13
L6 = L7 - T6 = 13 - 1 = 12
L5 = L7 - T5 = 13 - 4 = 9
L4 = L6 - T4 = 12 - 2 = 10
L3 = L5 - T3 = 9 - 3 = 6
L2 = L4 - T2 = 10 - 2 = 8
L1 = L3 - T1 = 6 - 6 = 0

The formal definition of the latest start times is given by:

Li = min[Lj - Ti | j one of the activities 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 activity must have a latest start time of zero

In fact (as with the package solution) using the latest start times Li 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.

Float

As we know the earliest start time Ei, and latest start time Li, for each activity i it is clear that the amount of slack or float time Fi available is given by Fi = Li - Ei which is the amount by which we can increase the time taken to complete activity i without changing (increasing) the overall project completion time. Hence we can form the table below:

Activity Li Ei Float Fi 1 0 0 0 2 8 0 8 3 6 6 0 4 10 2 8 5 9 9 0 6 12 4 8 7 13 13 0 8 14 14 0 9 20 20 0 10 22 20 2 11 23 23 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 float figures derived are known as also known as total float. As in the above example a "chain" of successive activities (in this case 2, 4 and 6) share the same float and this is common with total float.

---

Free and independent float

Two other varieties of float (for non-critical activities) are also conventionally distinguished:

• free float - the delay possible for an activity if all preceding activities start as early as possible whilst all subsequent activities start at their earliest time - an equivalent (and easier) definition is the delay possible in an activity if it starts at its earliest time and all subsequent activities start at their earliest time
• independent float - the delay possible for an activity if all preceding activities start as late as possible whilst all subsequent activities start at their earliest time

where here by delay we strictly mean "the increase in completion time".

The effect of the free float calculation is to "push" the total float associated with a chain of successive non-critical activities onto the last activity in the chain. The significance of independent float is that it is associated solely with one activity and not with a chain of two or more activities.

With regard to calculating free and independent float we have that convenient formulae are:

• free float for activity i = min[earliest start time for j | j an immediate successor of i] - earliest start time for i - completion time for i
• independent float for activity i = min[earliest start time for j | j an immediate successor of i] - max[latest finish time for j | j an immediate predecessor of i] - completion time for i, where independent float is taken to be zero if this calculation returns a negative number

Recalling the table we calculated above (and adding latest finish = latest start + completion time, and earliest finish = earliest start + completion time) we have:

Activity Latest Earliest Latest Earliest Completion start start finish finish time 1 0 0 6 6 6 2 8 0 10 2 2 3 6 6 9 9 3 4 10 2 12 4 2 5 9 9 13 13 4 6 12 4 13 5 1 7 13 13 14 14 1 8 14 14 20 20 6 9 20 20 23 23 3 10 22 20 23 21 1 11 23 23 24 24 1

and recalling the network diagram

we have that free and independent float (for the non-critical activities) are:

Activity Free float Independent float 2 0 0 4 0 0 6 8 0 10 2 2

As commented before free float pushes the total float associated with a chain of successive activities onto the last activity in the chain. Activity 10, as it is by itself and not in a chain of non-critical activities, has a free float of 2 (= its previously calculated total float), as well as an independent float of 2.

---

More complicated activity dependencies

So far we have dealt solely with simple activity dependencies (such as A must be finished before B can start). It is relatively simple to deal with more complicated dependencies such as those considered below. Note here however that professional project management packages typically hide the details of incorporating such dependencies into the network from the user.

In the notation below A and B are two activities with completion times a and b. Activities starting with a D are "dummy" activities introduced in order to correctly represent the activity dependency.

• There must be a time lag of at least T between the end of A and the start of B (A finishes before B starts)

In this case the dummy activity between A and B imposes the appropriate time lag.

Note here that we have used the phrase "at least T" above. If we wished to impose a delay of precisely T then, in fact, we cannot do this in any general sense in the network diagram, instead we need to approach the network via linear programming. The same comment applies to the other examples given below.

• There must be a time lag of at least T between the start of A and the start of B (A starts before B starts)

In this case we break activity A into two activities. The first (labelled A above) indicates that A has started. The second (labelled DA above) represents the continuation of activity A once it has started. The dummy activity D imposes the appropriate time lag of T between the start of A and the start of B. Note here that the time unit of 1 used above in A(1) and D(T-1) is purely arbitrary, we could have used any small time unit > 0 to achieve the same effect.

• There must be a time lag of at least T between the end of A and the end of B (A finishes before B finishes)

In this case we break B into two activities. The first (labelled B above) represents the end of B. The second (labelled DB above) represents the start of B. The dummy activity D imposes the appropriate time lag of T between the end of A and the end of B.

• There must be a time lag of at least T between the start of A and the end of B (A starts before B finishes)

This case combines features we have already seen above. A is broken into two activities, one representing its start (labelled A above) and the other its continuation (labelled DA above). B is broken into two activities, one representing its end (labelled B above) and the other representing the start of B (labelled DB above). The dummy activity D imposes the appropriate time lag of T between the start of A and the end of B.

---

Network analysis example 1996 UG exam

The table below defines the activities within a small project.

Activity Completion time Immediate predecessor (weeks) activities A 3 - B 1 A C 2 B,A D 7 - E 8 D,A F 3 B G 1 E,F H 2 D

• Draw the network diagram.
• Calculate the minimum overall project completion time and identify which activities are critical.
• What is the slack (float) time associated with each of the non-critical activities.

Solution

The network diagram is shown below. Note the introduction of a dummy activity I with a duration of zero to represent the end of the project.

Note here that the arc AC is redundant here, since it is implied by the arcs AB and BC. However, in general, it is easier to leave redundant arcs in the network rather than run the risk of making a mistake by deleting them.

Let Ei represent the earliest start time for activity i such that all its preceding activities have been finished. We calculate the values of the Ei (i=A,B,...,I) by going forward, from left to right, in the network diagram.

To ease the notation let Ti be the activity completion time associated with activity i (e.g. TB = 1). Then the Ei are given by:

EA = 0 (assuming we start at time zero)
ED = 0 (assuming we start at time zero)
EB = EA + TA = 0 + 3 = 3
EH = ED + TD = 0 + 7 = 7
EC = max[EA + TA, EB + TB] = max[0 + 3, 3 + 1] = 4
EE = max[EA + TA, ED + TD] = max[0 + 3, 0 + 7] = 7
EF = EB + TB = 3+ 1 = 4
EG = max[EF + TF, EE + TE] = max[4 + 3, 7 + 8] = 15
EI = max[EC + TC, EG + TG, EH + TH] = max[4 + 2, 15 + 1, 7 + 2] = 16

Hence the minimum possible completion time for the entire project is 16 weeks i.e. 16 (weeks) is the minimum time needed to complete all the activities.

We now need to calculate the latest times for each activity.

Let Li represent the latest start time we can start activity i and still complete the project in the minimum overall completion time. We calculate the values of the Li (i=A,B,...,I) by going backward, from right to left, in the network diagram. Hence:

LI = 16
LG= LI - TG = 16 - 1 = 15
LC = LI - TC = 16 - 2 = 14
LH = LI - TH = 16 - 2 = 14
LF = LG - TF = 15 - 3 = 12
LE = LG - TE = 15 - 8 = 7
LB = min[LC - TB, LF - TB] = min[14 - 1, 12 - 1] = 11
LA = min[LC - TA, LB - TA, LE - TA] = min[14 - 3, 11 - 3, 7 - 3] = 4
LD = min[LE - TD, LH - TD] = min[7 - 7, 14 - 7] = 0

Note that as a check all latest times are >=0 at least one activity has a latest start time value of zero.

As we know the earliest start time Ei, and latest start time Li, for each activity i it is clear that the amount of slack or float time Fi available is given by Fi = Li - Ei which is the amount by which we can increase the time taken to complete activity i without changing (increasing) the overall project completion time. Hence we can form the table below:

Activity Li Ei Float Fi A 4 0 4 B 11 3 8 C 14 4 10 D 0 0 0 E 7 7 0 F 12 4 8 G 15 15 0 H 14 7 7

Any activity with a float of zero is critical. Note here that, as a check, all float values should be >= 0.

Hence the critical activities are D, E and G and the floats for the non-critical activities are given in the table above.

---

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

What are the four types of PDM relationships?

Which relationship model is commonly used in AOA diagrams?

Which relationship model is most commonly used in the precedence diagrams?

What is PDM explain the four types of relationship between activities used in PDM?