← 2013 Paper 2

UPSC 2013 Maths Optional Paper 2 Q4a — Step-by-Step Solution

15 marks · Section A

Assignment problem (Hungarian method) · Linear Programming · asked 6× in 13 yrs · Read the full method →

Question

Solve the minimum time assignment problem:

Technique

Threshold (parametric) approach to bottleneck matching; binary search over threshold $T$ for smallest feasible value.

Solution

Interpretation. The “minimum time” assignment problem (Hindi: न्यूनतम समय नियतन समस्या) — also called the bottleneck assignment problem — minimises the maximum time among the chosen assignments, on the assumption that jobs run in parallel and the total elapsed time is determined by the slowest job. (This is distinct from the standard sum-minimisation Hungarian assignment problem.)

Strategy. Find the smallest threshold $T$ such that the bipartite graph with edges $\{(J_i,M_j):c_{ij}\le T\}$ admits a perfect matching.

Step 1 — Distinct cost values (sorted)

The cost matrix entries (deduplicated, ascending): $3,\,4,\,5,\,6,\,7,\,8,\,9,\,10,\,11,\,12,\,14$.

Step 2 — Test thresholds from low to high

Threshold $T=10$: Cells $c_{ij}\le 10$:

No row has access to $M_4$ (column max = 11). So at most 3 machines $\{M_1,M_2,M_3\}$ are reachable, but 4 jobs need distinct machines. No perfect matching at $T=10$.

Threshold $T=11$: Cells $c_{ij}\le 11$:

Now $J_4$ can take $M_4$. Try $J_4\to M_4$; remaining bipartite graph on $\{J_1,J_2,J_3\}\times\{M_1,M_2,M_3\}$:

Try $J_1\to M_1,\;J_2\to M_2,\;J_3\to M_3$:

• $J_1$-$M_1$: cost 3 ✓
• $J_2$-$M_2$: cost 9 ✓
• $J_3$-$M_3$: cost 10 ✓
• $J_4$-$M_4$: cost 11 ✓

Maximum cost = 11. Feasible at $T=11$.

Step 3 — Optimal solution

Since $T=10$ is infeasible and $T=11$ is feasible, the minimum maximum time is 11.

Answer