GATE 2019 ME (ME1) – Question 64
Assign each of five jobs to a distinct machine to minimize total processing time. Times in minutes for M1, M2, M3, M4, M5 are:
J1: 40, 30, 50, 50, 58.
J2: 26, 38, 60, 26, 38.
J3: 40, 34, 28, 24, 30.
J4: 28, 40, 40, 32, 48.
J5: 28, 32, 38, 22, 44.
Find minimum total time (min).
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 146 to 146
Explanation
A minimum assignment is J1→M2, J2→M5, J3→M3, J4→M1, J5→M4. Total processing time is $30+38+28+28+22=\mathbf{146}$ min. Checking all $5!=120$ one-to-one assignments confirms no smaller total. Independent row minima would reuse machines and violate the constraint.