GATE CSE 1987 | Question: 11c

Question

The relative costs of assigning jobs $J_{1}, J_{2}$ and $J_{3}$ to machines $M_{1}, M_{2}$ and $M_{3}$ are given below:
$$\begin{array}{|c|cccc|}\hline\textbf{JOBS} && \textbf{Machines}  \\ & \textbf{$M_{1}$} & \textbf{$M_{2}$} & \textbf{$M_{3}$}  \\\hline \text{$J_{1}$} & \text{25} & \text{32} & \text{35} \\ \text{$J_{2}$} & \text{15} & \text{23} & \text{21}\\  \text{$J_{3}$} & \text{19}& \text{21} & \text{17}\\\hline  \end{array}$$
Using the assignment method find the assignment involving minimum cost. Is this an optimal assignment?

Comments

can't understand the question

Answer 1

To understand the Assignment Problem and How to get the optimal solution , 

Please refer this link :- http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

Now ,here we have to assign Jobs to the given machines in such a way that total cost should be minimum.

So, We will use Hungarian Method which is mentioned in the above link.

\begin{array}{|c|ccc|} \hline \bf{JOBS} &&\textbf {Machines }& \\\hline &\textbf {$m_1$} &\textbf {$m_1$} &\textbf {$m_1$}  \\\hline  \textbf {$J_1$} &25&32&35 \\\hline\textbf {$J_2$}  & 15&23&21\\\hline \textbf {$J_3$}& 19&21 &17 \\\hline \end{array}

Cost matrix = $\begin{bmatrix} 
25 & 32 & 35\\
15&23&21\\19&21&17 
\end{bmatrix}_{3 \times 3}$ so, n= 3

now using Hungarian Method -

step 1 : $\begin{bmatrix} 
25 & 32 & 35\\
15&23&21\\19&21&17 
\end{bmatrix} \Rightarrow \begin{bmatrix} 
0 & 7 & 10\\
0&8&6\\2&4&0 
\end{bmatrix}$

step 2 : $\begin{bmatrix} 
0 & 7 & 10\\
0&8&6\\2&4&0 
\end{bmatrix} \Rightarrow \begin{bmatrix} 
0 & 3& 10\\
0&4&6\\2&0&0 
\end{bmatrix}$

step 3: - $$

 

 

So, Answer = Optimal Assignment is :-

Job J1 to Machine M2

Job J2 to Machine M1

Job J3 to Machine M3

and Minimum cost is = 64

Comments

is it in GATE-19 syllabus ?

---

No sir,  It is not in gate.. It is the part of operational research which is not in gate.

Answer 2

J1 - M1

J2 - M2

J3 - M3

if given that they are to be assigned to different machines