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.
The figure below shows a first attempt at solving the problem - it can be tidied up/improved e.g. by numbering the nodes.
Note here that there may be many different way to correctly represent the underlying network logic using different dummies. The above is only one way.
E1 = 0 (by definition)
E2 = E1 + T12 = 0 + 4 = 4
E3 = E2 + T23 = 4 + 6 = 10
E4 = E2 + T24 = 4 + 16 = 20
E5 = max[E3 + T35, E4 + T45]
= max[10 + 8, 20 + 0] = 20
E6 = max[E5 + T56, E7 + T76]
but we have not yet worked out E7 so we must leave this calculation until we know E7 (this often happens and merely indicates that a different numbering of the nodes would have been more appropriate)
E7 = max[E3 + T37, E4 + T47] = max[10 + 0, 20 + 4] = 24
We can now calculate E6 since we now know E7
E6 = max[E5 + T56, E7 +
T76] = max[20 + 8, 24 + 2] = 28
E8 = max[E2 + T28, E6 + T68,
E7 + T78] = max[4 + 24, 28 + 8, 24 + 7] = 36
Hence the minimum completion time for the project is 36.
L8 = E8 = 36 (by definition)
L7 = min[L8 - T78, L6 - T76]
and we do not yet know L6 so we must leave this calculation until we do
L6 = L8 - T68 = 36 - 8 = 28
We can now calculate L7 since we now know L6
L7 = min[L8 - T78, L6 -
T76] = min[36 - 7, 28 - 2] = 26
L5 = L6 - T56 = 28 - 8 = 20
L4 = min[L5 - T45, L7 - T47]
= min[20 - 0, 26 - 4] = 20
L3 = min[L5 - T35, L7 - T37]
= min[20 - 8, 26 - 0] = 12
L2 = min[L8 - T28, L3 - T23,
L4 - T24] = min[36 - 24, 12 - 6, 20 - 16] = 4
L1 = L2 - T12 = 4 - 4 = 0 (as required)
We have the table
Activity i j Lj Ei Tij Fij 1 1 2 4 0 4 0 2 2 3 12 4 6 2 3 3 5 20 10 8 2 4 2 4 20 4 16 0 5 5 6 28 20 8 0 6 4 7 26 20 4 2 7 7 6 28 24 2 2 8 6 8 36 28 8 0 9 2 8 36 4 24 8 10 7 8 36 24 7 5 Dummy 4 5 20 20 0 0 Dummy 3 7 26 10 0 16
Note that all floats are >= 0 as required.
Hence the critical activities are 1, 4, 5, 8 and these (together with the dummy activity between node 4 and node 5) form the critical path from the start node to the final node.
We have the following calculations.
E1 = 0 (by definition)
E2 = max[E1 + T12, E3 + T32]
but we have not yet worked out E3 so we leave this until we have calculated it
E3 = E1 + T13 = 0 + 3 = 3
We can now calculate E2
E2 = max[E1 + T12, E3 +
T32] = max[0 + 2, 3 + 0] = 3
E4 = E3 + T24 = 3 + 4 = 7
E5 =max[E2 + T25, E3 + T35,
E6 + T65]
here we have not yet worked out E6 so we leave this until we have calculated it
E6 = E3 + T36 = 3 + 3 = 6
We can now calculate E5
E5 =max[E2 + T25, E3 + T35,
E6 + T65] = max[3 + 4, 3 + 2, 6 + 1] = 7
E7 = max[E4 + T47, E5 + T57,
E6 + T67] = max[7 + 2, 7 + 4, 6 + 2] = 11
Hence the minimum overall project completion time is 11 weeks.
L7 = E7 = 11 (by definition)
L6 =min[L7 - T67, L5 - T65]
but we have not yet worked out L5 so we leave this until we have calculated it
L5 = L7 - T57 = 11 - 4 = 7
We can now calculate L6
L6 = min[L7 - T67, L5 -
T65] = min[11 - 2, 7 - 1] = 6 L4 = L7
- T47 = 11 - 2 = 9
L3 =min[L2 - T32, L5 - T35,
L6 - T36]
but we have not yet worked out L2 so we leave this until we have calculated it
L2 = min[L4 - T24, L5 - T25] = min[9 - 4, 7 - 1] = 5
We can now calculate L3
L3 =min[L2 - T32, L5 - T35,
L6 - T36] = min[5 - 0, 7 - 2, 6 - 3] = 3
L1 = min[L2 - T12, L3 - T13]
= min[5 - 2, 3 - 3] = 0
and note that L1 = 0 as required.
We have the table
Activity i j Lj Ei Tij Fij 1 1 2 5 0 2 3 2 1 3 3 0 3 0 3 2 4 9 3 4 2 4 2 5 7 3 1 3 5 3 5 7 3 2 2 6 3 6 6 3 3 0 7 6 5 7 6 1 0 8 4 7 11 7 2 2 9 5 7 11 7 4 0 10 6 7 11 6 2 3 Dummy 3 2 5 3 0 2
Note that all floats are >= 0 as required.
Hence the critical activities are 2,6,7,9 and these form the critical path from the start node to the finish node in the network.