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.

E_{1} = 0 (by definition)

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

E_{3} = E_{2} + T_{23} = 4 + 6 = 10

E_{4} = E_{2} + T_{24} = 4 + 16 = 20

E_{5} = max[E_{3} + T_{35}, E_{4} + T_{45}]
= max[10 + 8, 20 + 0] = 20

E_{6} = max[E_{5} + T_{56}, E_{7} + T_{76}]

but we have not yet worked out E_{7} so we must leave this calculation
until we know E_{7} (this often happens and merely indicates that
a different numbering of the nodes would have been more appropriate)

E_{7} = max[E_{3} + T_{37}, E_{4} +
T_{47}] = max[10 + 0, 20 + 4] = 24

We can now calculate E_{6} since we now know E_{7}

E_{6} = max[E_{5} + T_{56}, E_{7} +
T_{76}] = max[20 + 8, 24 + 2] = 28

E_{8} = max[E_{2} + T_{28}, E_{6} + T_{68},
E_{7} + T_{78}] = max[4 + 24, 28 + 8, 24 + 7] = 36

Hence the minimum completion time for the project is 36.

L_{8} = E_{8} = 36 (by definition)

L_{7} = min[L_{8} - T_{78}, L_{6} - T_{76}]

and we do not yet know L_{6} so we must leave this calculation
until we do

L_{6} = L_{8} - T_{68} = 36 - 8 = 28

We can now calculate L_{7} since we now know L_{6}

L_{7} = min[L_{8} - T_{78}, L_{6} -
T_{76}] = min[36 - 7, 28 - 2] = 26

L_{5} = L_{6} - T_{56} = 28 - 8 = 20

L_{4} = min[L_{5} - T_{45}, L_{7} - T_{47}]
= min[20 - 0, 26 - 4] = 20

L_{3} = min[L_{5} - T_{35}, L_{7} - T_{37}]
= min[20 - 8, 26 - 0] = 12

L_{2} = min[L_{8} - T_{28}, L_{3} - T_{23},
L_{4} - T_{24}] = min[36 - 24, 12 - 6, 20 - 16] = 4

L_{1} = L_{2} - T_{12} = 4 - 4 = 0 (as required)

We have the table

Activity i j L_{j}E_{i}T_{ij}F_{ij }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.

E_{1} = 0 (by definition)

E_{2} = max[E_{1} + T_{12}, E_{3} + T_{32}]

but we have not yet worked out E_{3} so we leave this until
we have calculated it

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

We can now calculate E_{2}

E_{2} = max[E_{1} + T_{12}, E_{3} +
T_{32}] = max[0 + 2, 3 + 0] = 3

E_{4} = E_{3} + T_{24} = 3 + 4 = 7

E_{5} =max[E_{2} + T_{25}, E_{3} + T_{35},
E_{6} + T_{65}]

here we have not yet worked out E_{6} so we leave this until
we have calculated it

E_{6} = E_{3} + T_{36} = 3 + 3 = 6

We can now calculate E_{5}

E_{5} =max[E_{2} + T_{25}, E_{3} + T_{35},
E_{6} + T_{65}] = max[3 + 4, 3 + 2, 6 + 1] = 7

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

Hence the minimum overall project completion time is 11 weeks.

L_{7} = E_{7} = 11 (by definition)

L_{6} =min[L_{7} - T_{67}, L_{5} - T_{65}]

but we have not yet worked out L_{5} so we leave this until
we have calculated it

L_{5} = L_{7} - T_{57} = 11 - 4 = 7

We can now calculate L_{6}

L_{6} = min[L_{7} - T_{67}, L_{5} -
T_{65}] = min[11 - 2, 7 - 1] = 6 L_{4} = L_{7}
- T_{47} = 11 - 2 = 9

L_{3} =min[L_{2} - T_{32}, L_{5} - T_{35},
L_{6} - T_{36}]

but we have not yet worked out L_{2} so we leave this until
we have calculated it

L_{2} = min[L_{4} - T_{24}, L_{5} -
T_{25}] = min[9 - 4, 7 - 1] = 5

We can now calculate L_{3}

L_{3} =min[L_{2} - T_{32}, L_{5} - T_{35},
L_{6} - T_{36}] = min[5 - 0, 7 - 2, 6 - 3] = 3

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

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

We have the table

Activity i j L_{j}E_{i}T_{ij}F_{ij}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.

- the float for activity 1 is 3 weeks so increasing its completion time by 2 weeks does not affect the overall project completion time which remains at 11 weeks
- activity 10 is not a critical activity so decreasing its completion time does not affect the overall project completion time which remains at 11 weeks
- activity 6 is a critical activity so increasing its completion time
by 2 weeks increases the overall project completion time by 2 weeks to
13 weeks. In fact increasing the completion time for
*any*critical activity increases the overall project completion time by the same amount.