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.

We need to decide whether to use an investment opportunity or not so
let x_{j} = 1 if we use investment opportunity j (j=1,...,10),
0 otherwise

- total amount of capital available for these investments is Q

SUM{j=1,...,10}C_{j}x_{j} <= Q

- investment opportunities 3 and 4 are mutually exclusive and so are 5 and 6

x_{3} + x_{4} <= 1

x_{5} + x_{6} <= 1

- neither 5 nor 6 can be undertaken unless either 3 or 4 is undertaken

x_{5} <= x_{3}+ x_{4}

x_{6} <= x_{3}+ x_{4}

- at least two and at most four investment opportunities have to be undertaken from the set {1,2,7,8,9,10}

2 <= x_{1} + x_{2} + x_{7} + x_{8}
+ x_{9} + x_{10} <= 4

The objective is to maximise the total estimated long-run profit i.e.

maximise SUM{j=1,...,10}P_{j}x_{j}

Note here that sometimes it is possible to correctly represent the problem, but using different constraints. For example for this problem we could replace

x_{5} <= x_{3}+ x_{4}

x_{6} <= x_{3}+ x_{4}

by the single constraint

x_{5} + x_{6 }<= x_{3}+ x_{4}

since we have x_{5} + x_{6} <= 1

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) is chosen for activity
C, 0 otherwise

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

E_{i} = 1 if a completion time of i (i=8,7,6) is 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_{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_{I }>= x_{H} +3

x_{I} <= 17 (to complete within 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}

Note here that essentially in this question we have extended cost/time tradeoff which we considered before from involving a linear assumption to the situation we we can have a diverse range of possible completion times, and any associated costs we wish.