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 table below defines the activities within a small project.

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

- 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.

In the above network there are a number of options for the completion time for activities C, D and E as shown below:

Activity Completion time Cost (£'000) C 4 3 3 7 2 10 1 15 D 3 12 2 16 1 25 E 8 5 7 9 6 14

For example choosing a completion time for activity E of 6 weeks costs £14,000.

Formulate the problem of deciding the completion time for C, D and E so as to ensure that the project is completed within 17 weeks as an integer program.

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.

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

To ease the notation let T_{i} be the activity completion time
associated with activity i (e.g. T_{B} = 3). Then the E_{i}
are given by:

E_{A} = 0 (assuming we start at time zero)

E_{B} = 0 (assuming we start at time zero)

E_{C} = E_{A} + T_{A} = 0 + 2 =2

E_{D} = max[E_{A} + T_{A}, E_{B} + T_{B}]
= max[0 + 2, 0 + 3] = 3

E_{E} = max[E_{C} + T_{C}, E_{D} + T_{D}]
= max[2 + 4, 3 + 3] = 6

E_{F} = E_{C} + T_{C} = 2 + 4 = 6

E_{G} = E_{E} + T_{E} = 6 + 8 = 14

E_{H} = max[E_{F} + T_{F}, E_{G} + T_{G}]
=max[6 + 3, 14 + 2] = 16

E_{I} = E_{H} + T_{H} = 16 + 3 = 19

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

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

Let L_{i} 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 L_{i} (i=A,B,...,I) by going backward,
from right to left, in the network diagram. Hence:

L_{I} = 19

L_{H}= L_{I} - T_{H} = 19 - 3 = 16

L_{G} = L_{H} - T_{G} = 16 - 2 = 14

L_{F} = L_{H} - T_{F} = 16 - 3 = 13

L_{E} = L_{G} - T_{E} = 14 - 8 = 6

L_{D} = L_{E} - T_{D} = 6 - 3 = 3

L_{C} = min[L_{E} - T_{C}, L_{F} - T_{C}]
= min[6 - 4, 13 - 4] = 2

L_{B} = L_{D} - T_{B} = 3 - 3 = 0

L_{A} = min[L_{C} - T_{A}, L_{D} - T_{A}]
= min[2 - 2, 3 - 2] = 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 E_{i}, and latest start time
L_{i}, for each activity i it is clear that the amount of slack
or *float* time F_{i} available is given by F_{i}
= L_{i} - E_{i} 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 L_{i}E_{i}Float F_{i}A 0 0 0 B 0 0 0 C 2 2 0 D 3 3 0 E 6 6 0 F 13 6 7 G 14 14 0 H 16 16 0

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 A,B,C,D, E,G and H and the float for the only non-critical activity F is 7 weeks.

In order to formulate the problem of deciding the completion time for C, D and E so as to ensure that the project is completed within 17 weeks we make use of integer programming.

Let the x variables (suitably subscripted) represent feasible start times for each activity (>=0 and integer). Note here that we deal with feasible start times in formulating this program rather than (as above) with earliest start times.

Introduce zero-one variables:

C_{i} = 1 if a completion time of i (i=4,3,2,1) chosen for activity
C, 0 otherwise

D_{i} = 1 if a completion time of i (i=3,2,1) chosen for activity
D, 0 otherwise

E_{i} = 1 if a completion time of i (i=8,7,6) chosen for activity
E, 0 otherwise

then the constraints relating to the choice of completion time are:

C_{4} + C_{3} + C_{2} + C_{1} =1

D_{3} + D_{2} + D_{1} = 1

E_{8} + E_{7} + E_{6} = 1

i.e. exactly one completion time must be chosen for C, D and E respectively.

The constraints relating to the network logic are:

x_{A}= x_{B} = 0

x_{C} >= x_{A} + 2

x_{D} >= x_{B} + 3

x_{D} > = x_{A} + 2

x_{E} >= x_{C} + 4C_{4} + 3C_{3}
+ 2C_{2} +1C_{1}

where 4C_{4} + 3C_{3} + 2C_{2} +1C_{1}
is the completion time for activity C (remember C_{4}, C_{3},
C_{2} and C_{1} are zero-one variables).

x_{E} >= x_{D} + 3D_{3} + 2D_{2}
+1D_{1}

x_{F} >= x_{C} + 4C_{4} + 3C_{3}
+ 2C_{2} +1C_{1}

x_{G} >= x_{E} + 8E_{8} + 7E_{7}
+ 6E_{6}

x_{H} >= x_{F} + 3

x_{H} >= x_{G} + 2

x_{H} <= 17 - 3 (to complete in 17 weeks)

and the objective is:

minimise 3C_{4} + 7C_{3} + 10C_{2} +15C_{1}
+ 12D_{3} + 16D_{2} +25D_{1} + 5E_{8} +9E_{7}
+14E_{6}

A project consists of 8 activities. The activity completion times and the precedence relationships are as follows:

Activity Completion time Immediate predecessor (days) activities A 5 - B 7 - C 6 - D 3 A E 4 B,C F 2 C G 6 A,D H 5 E,F

- Draw the network diagram.
- Calculate the minimum overall project completion time and identify which activities are critical.
- If activity E is delayed by 3 days how is the project completion time affected?
- If activity F is delayed by 3 days how is the project completion time affected?

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.

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

To ease the notation let T_{i} be the activity completion time
associated with activity i (e.g. T_{B} = 7). Then the E_{i}
are given by:

E_{A} = 0 (assuming we start at time zero)

E_{B} = 0 (assuming we start at time zero)

E_{C} = 0 (assuming we start at time zero)

E_{D} = E_{A} + T_{A} = 0 + 5 = 5

E_{G} = max[E_{A} + T_{A}, E_{D} + T_{D}]
= max[0 + 5, 5 + 3] = 8

E_{E} = max[E_{B} + T_{B}, E_{C} + T_{C}]
= max[0 + 7, 0 + 6] = 7

E_{F} = E_{C} + T_{C} = 0 + 6 = 6

E_{H} = max[E_{E} + T_{E}, E_{F} + T_{F}]
= max[7 + 4, 6 + 2] = 11

E_{I} = max[E_{G} + T_{G}, E_{H} + T_{H}]
= max[8 + 6, 11 + 5] = 16

Hence the minimum possible completion time for the entire project is
16 days, i.e. 16 days is the minimum time needed to complete *all*
the activities.

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

Let L_{i} 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 L_{i} (i=A,B,...,I) by going backward,
from right to left, in the network diagram. Hence:

L_{I} = 16

L_{G} = L_{I} - T_{G} = 16 - 6 = 10

L_{H} = L_{I} - T_{H} = 16 - 5 = 11

L_{D} = L_{G} - T_{D} = 10 - 3 = 7

L_{A} = min[L_{D} - T_{A}, L_{G} - T_{A}]
= min[7 - 5, 10 - 5] = 2

L_{E} = L_{H} - T_{E} = 11 - 4 = 7

L_{F} = L_{H} - T_{F} = 11 - 2 = 9

L_{C} = min[L_{E} - T_{C}, L_{F} - T_{C}]
= min[7 - 6, 9 - 6] = 1

L_{B} = L_{E} - T_{B} = 7 - 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 E_{i}, and latest start time
L_{i}, for each activity i it is clear that the amount of slack
or *float* time F_{i} available is given by F_{i}
= L_{i} - E_{i} 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 L_{i}E_{i}Float F_{i}A 2 0 2 B 0 0 0 C 1 0 1 D 7 5 2 E 7 7 0 F 9 6 3 G 10 8 2 H 11 11 0

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 B, E and H and the floats for the non-critical activities are given in the table above.

If activity E is delayed by 3 days then as E is critical the project completion time increases by exactly 3 days.

If activity F is delayed by 3 days then as F has a float of 3 days the project completion time is unaffected.

A project consists of 8 activities named A to H.

Construct a network so as to satisfy the scheduling requirements shown in the table below.

Activity Completion time Immediate predecessor (days) activities A 3 - B 6 A C 7 A D 5 A E 13 B,C F 8 C,D G 11 D,F H 6 G,E

Find the least time required to complete the whole project and identify the critical activities.

How is the project completion time affected if:

- activity F is delayed by 3 days
- activity E is delayed by 7 days
- activity G is finished 7 days early

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.

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

To ease the notation let T_{i} be the activity completion time
associated with activity i (e.g. T_{B} = 7). Then the E_{i}
are given by:

E_{A} = 0 (assuming we start at time zero)

E_{B} = E_{A} + T_{A} = 0 + 3 = 3

E_{C} = E_{A} + T_{A} = 0 + 3 = 3

E_{D} = E_{A} + T_{A} = 0 + 3 = 3

E_{E} = max[E_{B} + T_{B}, E_{C} + T_{C}]
= max[3 + 6, 3 + 7] = 10

E_{F} = max[E_{C} + T_{C}, E_{D} + T_{D}]
= max[3 + 7, 3 + 5] = 10

E_{G} = max[E_{F} + T_{F}, E_{D} + T_{D}]
= max[10 + 8, 3 + 5] = 18

E_{H} = max[E_{E} + T_{E}, E_{G} + T_{G}]
= max[10 + 13, 18 + 11] = 29

E_{I} = E_{H} + T_{H} = 29 + 6 = 35

Hence the minimum possible completion time for the entire project is
35 days, i.e. 35 days is the minimum time needed to complete *all*
the activities.

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

Let L_{i} 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 L_{i} (i=A,B,...,I) by going backward,
from right to left, in the network diagram. Hence:

L_{I} = 35

L_{H} = L_{I} - T_{H} = 35 - 6 = 29

L_{G} = L_{H} - T_{G} = 29 - 11 = 18

L_{E} = L_{H} - T_{E} = 29 - 13 = 16

L_{F} = L_{G} - T_{F} = 18 - 8 = 10

L_{B} = L_{E} - T_{B} = 16 - 6 = 10

L_{C} = min[L_{E} - T_{C}, L_{F} - T_{C}]
= min[16 - 7, 10 - 7] = 3

L_{D} = min[L_{F} - T_{D}, L_{G} - T_{D}]
= min[10 - 5, 18 - 5] = 5

L_{A} = min[L_{B} - T_{A}, L_{C} - T_{A},
L_{D} - T_{A}] = min[10 - 3, 3 - 3, 5 - 3] = 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 E_{i}, and latest start time
L_{i}, for each activity i it is clear that the amount of slack
or *float* time F_{i} available is given by F_{i}
= L_{i} - E_{i} 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 L_{i}E_{i}Float F_{i}A 0 0 0 B 10 3 7 C 3 3 0 D 5 3 2 E 16 10 6 F 10 10 0 G 18 18 0 H 29 29 0

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 A, C, F, G and H and the floats for the non-critical activities are given in the table above.

If activity F is delayed by 3 days then as F is critical the project completion time increases by exactly 3 days.

If activity E is delayed by 7 days then as E has a float of 6 days the project completion time is affected. The project completion time will increase by exactly (7-6) = 1 day to 36 days.

If activity G is finished 7 days early then as G is a critical activity
the overall project completion time will (potentially) be reduced. To see
the effect of this change we need to redo the calculation for the earliest
times given above but with a completion time for G of 4 days. The only
change is in the calculation of E_{H} and E_{I} and these
now are:

E_{H} = max[E_{E} + T_{E}, E_{G} + T_{G}]
= max[10 + 13, 18 + 4] = 23

E_{I} = E_{H} + T_{H} = 23 + 6 = 29

Hence the overall project completion time falls to 29 days (a decrease
of 6 days).