\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Consider the project with activities and their prerequisites given
below. It is possible to set the duration of each activity to any
value between the normal and the crash duration. The cost of
reduction from the normal to the crash duration is given: when the
duration is between the normal and the crash duration, the cost is
in proportion. A saving (from lost production) of 14 per unit
reduction of project duration can be achieved. What activity
durations do you recommend?

\begin{tabular}{ccccc}
\hline Activity&Prerequisites&Normal duration& Crash duration&Cost
of reduction\\ \hline
A&-&11&8&6\\B&-&9&6&48\\C&-&4&3&7\\D&A&9&4&25\\E&B,C&6&5&13\\
F&C&5&3&18\\G&E&8&4&32\\H&E&10&6&60\\I&D,G&4&2&10\\
J&D,G&9&6&45\\K&F,H,I&7&4&21\\ \hline
\end{tabular}


ANSWER

\setlength{\unitlength}{.5in}

\begin{picture}(5,6)

\put(1,3){\oval(.3,.3)}\put(1,3){\makebox(0,0){1}}
\put(3,5){\oval(.3,.3)}\put(3,5){\makebox(0,0){2}}
\put(3,1){\oval(.3,.3)}\put(3,1){\makebox(0,0){3}}
\put(5,3){\oval(.3,.3)}\put(5,3){\makebox(0,0){4}}
\put(7,3){\oval(.3,.3)}\put(7,3){\makebox(0,0){5}}
\put(8,5){\oval(.3,.3)}\put(8,5){\makebox(0,0){6}}
\put(8,1){\oval(.3,.3)}\put(8,1){\makebox(0,0){7}}
\put(10,3){\oval(.3,.3)}\put(10,3){\makebox(0,0){8}}


%lines from 1
\put(1.2,3.2){\vector(1,1){1.6}}\put(1.2,3){\vector(1,0){3.6}}\put(1.2,2.8){\vector(1,-1){1.6}}
%lines from 2
\put(3.2,5){\vector(1,0){4.6}}
%lines from 3
\put(3.2,1.2){\line(3,3){1.6}}\put(3.2,1){\vector(1,0){4.6}}
%lines from 4
\put(5.2,3){\vector(1,0){1.6}}
%lines from 5
\put(7.2,3.2){\vector(1,2){.7}}\put(7.2,2.8){\vector(1,-2){.7}}
%lines from 6
\put(8,4.8){\vector(0,-1){3.6}}\put(8.2,4.8){\vector(1,-1){1.6}}
%lines from 7
\put(8.2,1.2){\vector(1,1){1.6}}


\put(1.8,4.4){A,11} \put(2,3.1){B,9} \put(1.8,1.4){C,4}
\put(5,5.1){D,9} \put(5,3.3){E,6} \put(5,.7){F,5} \put(7,3.9){G,8}
\put(7,1.7){H,10} \put(8,3){I,4} \put(9,4){J,9} \put(9,1.7){K,7}

\put(0,2.8){(0,0)} \put(3,5.3){(11,14)} \put(3,.7){(4,9)}
\put(5,2.7){(9,9)} \put(7,2.7){(15,15)} \put(8,5.2){(23,23)}
\put(8,.7){(27,27)} \put(10,2.7){(34,34)}


\end{picture}

Critical path is B - E - G - I - K.

Project duration =34.

\begin{tabular}{cccc}
Activity&Normal duration& Crash duration& Unit reduction cost\\
A&11&8&2\\B&9&6&16\\C&4&3&7\\D&9&4&5 \\E&6&5&13\\F&5&3&9\\G&8&4&8
\\H&10&6&15\\I&4&2&5\\J&9&6&15\\K&7&4&7
\end{tabular}

We wish to reduce the project duration as much as possible as long
as the unit cost of reduction is less than 14. If the unit
reduction cost is $\geq14$, it will not be cost-effective to make
the reduction.

The unit reduction costs for the activities on the critical path
are 16, 13, 8, 5 and 7. The cheapest unit reduction cost is 5
(activity I). Reduce I to its crash duration of 2. The project
duration is reduced to 32 and the critical paths are B - E - G - I
- K, B - E - G - J and B - E - H - K.

We need to reduce all three critical paths. We consider all the
ways of doing this.

\begin{description}

\item[(a)]
If we reduced the duration of a single activity (B or E), we would
choose E at a unit cost of 13, since B and E lie on all three
critical paths.

\item[(b)]
Consider the cheapest individual reductions on each critical path.
Reducing the duration of G (unit cost 8, cheapest on the second
critical path, and also lies on the first) and K (unit cost 7,
cheapest on the third critical path) gives a unit cost of 8+7=15.
This is $\geq14$: too expensive.

\item[(c)]
However, reducing the durations of G and K and increasing the
duration of I gives a unit cost of $8+7-5=10$. This is therefore
the cheapest option.

\end{description}

Set I to its original duration of 4 and reduce the durations of G
and K to 6 and 5 respectively. The critical paths remain
unaltered, and the project duration is reduced to 30.

\begin{tabular}{ll}
B - E - G - I -  K& reduced by 4, increased by 2\\ B - E - G -
J&reduced by 2\\ B - E - H - K&reduced by 2
\end{tabular}

Choice (a) is still available. Reduce E to it's crash duration of
5. The project duration is reduced to 29 and the critical paths
are

B - E - G - I - K, B - E - G - J, B - E - H - K, A - D - J and A -
D - I - K

The choices are now

\begin{description}

\item[(a)]
reduce A and B at an unit cost of 18;

\item[(b)]
reduce A, G and K at a unit cost of 17.

\end{description}

These are all too expensive, there should be no further reduction
in activity durations.

Thus we set the following durations:

E to 5 at a total cost of 13 (unit cost 13)

G to 6 at a total cost of 16 (unit cost 8)

K to 5 at a total cost of 14 (unit cost 7)

to give a project duration of 29, at a total cost of 43. The
reduction in project duration is 34-29=5 so the savings from lost
production made as a result of this reduction ar $5\times14=70$.

The total overall saving is $70-43=27$.




\end{document}