# 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 tutorial solution

The network diagram is shown below. Note the use of a dummy activity (activity 10, with a completion time of zero) to represent the end of the project. Any nodes (activities) which, in the original network, have no precedence relationships coming out from them must be connected to this dummy activity to ensure that we correctly account for the end of the project. For this problem this means that activities 8 and 9 must be connected to activity 10.

We shall adopt the same notation as in the lecture notes - namely

Ei is the earliest start time for node i
Li is the latest start time for node i
Ti is the completion time for activity i
Fi is the float for activity i

We then have the following calculations.

#### Earliest start times

We calculate the values of the Ei (i=1,2,...,10) by going forward, from left to right, in the above network diagram.

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

Hence the minimum overall project completion time is 14 weeks.

#### Latest start times

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 = 14
L9 = L10 - T9 = 14 - 1 = 13
L8 = L10 - T8 = 14 - 6 = 8
L7 = L9 - T7 = 13 - 3 = 10
L6 = L9 - T6 = 13 - 5 = 8
L5 = L8 - T5 = 8 - 2 = 6
L4 = L7 - T4 = 10 - 6 = 4
L3 = min[L5 - T3, L6 - T3] = min[6 - 2, 8 - 2] = 4
L2 = min[L5 - T2, L6 - T2, L4 - T2] = min[6 - 4, 8 - 4, 4 - 4] = 0
L1 = L3 - T1 = 4 - 1 = 3

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

#### Float

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          3           0            3
2          0           0            0
3          4           1            3
4          4           4            0
5          6           4            2
6          8           4            4
7          10          10           0
8          8           6            2
9          13          13           0
10         14          14           0```

Any activity with a float of zero is critical.

Hence (ignoring the dummy activity) the critical activities are 2,4,7 and 9 and these form the critical path.

With respect to the changes in completion times:

• Increasing the activity completion time for any activity only affects the overall project completion time if the increase in the completion time is greater than the float for the activity. In this case the increase in the activity completion time for activity 6 is 2 weeks (from 5 weeks to 7 weeks) and the float for activity 6 is 4 weeks so the overall project completion time is unchanged.
• For any activity, cutting the activity completion time only affects the overall project completion time if the activity is critical. In this case activity 8 is not critical and so the overall project completion time is unchanged.

With respect to cutting the completion time for activity 4 (a critical activity) by 3 weeks the completion time for the project will (in general) be changed. The exception to this rule is the case where there are two or more critical paths and there exists a critical path which does not contain the activity whose completion time is being cut.

However we cannot automatically assume the completion time for the project will also fall by 3 weeks. We need to recalculate the earliest times for the network when the activity completion time for activity 4 is 6-3=3 weeks. We get:

E1 = 0 (assuming we start at time zero)
E2 = 0 (assuming we start at time zero)
E3 = E1 + T1 = 0 + 1 = 1
E4 = E2 + T2 = 0 + 4 = 4
E5 = max[E3 + T3, E2 + T2] = max[1 + 2, 0 + 4] = 4
E6 = max[E3 + T3, E2 + T2] = max[1 + 2, 0 + 4] = 4
E7 = E4 + T3 = 4 + 3 = 7
E8 = E5 + T5 = 4 + 2 = 6
E9 = max[E6 + T6, E7 + T7] = max[4 + 5, 7 + 3] = 10
E10 = max[E8 + T8, E9 + T9] = max[6 + 6, 10 + 1] = 12

Hence cutting the activity completion time for activity 4 by 3 weeks, from 6 weeks to 3 weeks, cuts the overall project completion time by 2 weeks, from 14 weeks to 12 weeks. Clearly what has happened here is that the critical path has changed.

Note here that a number of the Ei are unaffected by any change in the completion time of activity 4 (as can be easily seen from the network diagram). In fact only those earliest times "downstream" from activity 4 change. By eye we can see that these downstream activities are just 7, 9 and 10. Using this information we need only have recomputed E7, E9 and E10 above.

Given the information in the question on the status of the project we can revise the network diagram to that shown below where:

• we remove from the network all completed activities and their corresponding precedence relationships; and
• relabel all activities currently in progress with their revised completion times.

This revised network diagram is shown below.

We need to recalculate the earliest times for the network shown above to find how long it will take to complete the project. If we do this we find that it will take us 7 weeks to complete the project (with activities 5 and 8 being the critical activities).

As 8 weeks have already elapsed we will complete the entire project in 8+7 = 15 weeks and this compares with the completion time of 14 weeks calculated initially. Hence, at some stage, we have slipped a week and the project is currently a week late.