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:
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
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 Ei 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 Ei (i=1,2,...,10) by going forward, from left to right, in the network diagram.
To ease the notation let Tij be the activity completion time associated with the arc from node i to node j (e.g. T56 = 1). Then the Ei are given by:
E1 = 0 (assuming we start at time zero)
E2 = E1 + T12 = 0 + 6 = 6
E3 = E2 + T23 = 6 + 3 = 9
E4 = E1 + T14 = 0 + 2 = 2
E5 = E4 + T45 = 2 + 2 = 4
E6 = max[E3 + T36, E5 + T56]
= max[9 + 4, 4 + 1] = 13
E7 = E6 + T67 = 13 + 1 = 14
E8 = E7 + T78 = 14 + 6 = 20
E9 = E8 + T89, 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:
E9 = max[E8 + 3, E8 + 1] = max[20 + 3, 20 + 1] = 23
E10 = E9 + T9,10 = 23 + 1 = 24
Hence E10 = 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:
Ej = max[Ei + Tij | i one of the nodes 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. 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 Li 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 Li (i=1,2,...,10) by going backward, from right to left, in the network diagram. Hence:
L10 = E10 = 24 (the minimum overall completion
time)
L9 = L10 - T9,10 = 24 - 1 = 23
L8 = L9 - T89, 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:
L8 = min[L9 - 3, L9 - 1] = min[23 -
3, 23 - 1] = 20
L7 = L8 - T78 = 20 - 6 = 14
L6 = L7 - T67 = 14 - 1 = 13
L5 = L6 - T56 = 13 - 1 = 12
L4 = L5 - T45 = 12 - 2 = 10
L3 = L6 - T36 = 13 - 4 = 9
L2 = L3 - T23 = 9 - 3 = 6
L1 = min[L4 - T14, L2 - T12]
= min[10 - 2, 6 - 6] = 0
Note that as a check we would expect L1 = 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:
Li = min[Lj - Tij | 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:
In fact (as with the package solution) using the latest 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.
Consider an activity running (in the network diagram) from node i to node j. The earliest we can start that activity is Ei and since it takes Tij to complete the earliest we can finish it is Ei + Tij. But Lj is the latest we must leave node j to avoid increasing the overall project completion time and hence Lj - (Ei + Tij) is the amount of slack or float time available. Formally: Fij = Lj - (Ei + Tij) = Lj - Ei - Tij 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 Lj Ei Tij Float Fij 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.
Comment on the potential effect upon the overall project completion time (and the critical path) of:
Will the project finish on time if at the end of six weeks the status of the project is:
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.
E1 = 0 (by definition)
E2 = E1 + T12 = 0 + 2 = 2
E3 = E1 + T13 = 0 + 4 = 4
E4 = max[E2 + T24, E3 + T34]
= max[2 + 7, 4 + 3] = 9
Now we obviously need to calculate E8
E8 = max[E2 + T28, E3 +
T38] = max[2 + 3, 4 + 0] = 5
E5 = max[E4 + T45, E8 + T85]
= max[9 + 3, 5 + 7] = 12
E6 = max[E4 + T46, E5 + T56]
= max[9 + 6, 12 + 4] = 16
E7 = max[E6 + T67, E4 + T47]
= 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.
L7 = 18 (by definition)
L6 = L7 - T67 = 18 - 2 = 16
L5 = L6 - T56 = 16 - 4 = 12
L4 = min[L7 - T47, L6 - T46,
L5 - T45] = min[18-7,16-6,12-3] = 9
We now need to calculate L8
L8 = L5 - T85 = 12 - 7 = 5
L3 = min[L4 - T34, L8 - T38]
= min[9 - 3, 5 - 0] = 5
L2 = min[L4 - T24, L8 - T28]
= min[9 - 7, 5 - 3] = 2
L1 = min[L2 - T12, L3 - T13]
= min[2 - 2, 5 - 4] = 0
and note that L1 = 0 as required.
To calculate the float times we use the equation Fij = Lj - Ei - Tij to get
Activity i j Lj Ei Tij Fij 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.
After six weeks the new network diagram is shown below.
The earliest start time calculation is
E1 = 0 (by definition)
E4 = E1 + T14 = 0 + 5 = 5
E5 = max[E1 + T15, E4 + T45]
= max[0 + 4, 5 + 3] = 8
E6 = max[E5 + T56, E4 + T46]
= max[8 + 4, 5 + 6] = 12
E7 = max[E6 + T67, E4 + T47]
= 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.