GATE ME 2022 Set 1 — Question 58

Let the original cost matrix be $C = [c_{ij}]$, where $c_{ij}$ is the processing time of job $i$ on machine $j$. The assignment problem aims to find a permutation $\sigma$ of jobs to machines that minimizes the total processing time.The total processing time for a given assignment $\sigma$ is $Z(\sigma) = \sum_{i=1}^{4} c_{i, \sigma(i)}$.We are given that the minimum total processing time is 500 minutes. Let $\sigma^*$ be the optimal assignment for the original problem. Then:$$Z_{min} = Z(\sigma^*) = \sum_{i=1}^{4} c_{i, \sigma^*(i)} = 500$$ Due to a change in design, the processing time of Job 4 on each machine is increased by 20 minutes. Let the new cost matrix be $C' = [c'_{ij}]$. The new costs are:

• $c'_{ij} = c_{ij}$ for $i \in \{1, 2, 3\}$ and for all $j \in \{1, 2, 3, 4\}$.
• $c'_{4j} = c_{4j} + 20$ for all $j \in \{1, 2, 3, 4\}$.

This means a constant value of 20 has been added to every element of the 4th row of the cost matrix.A fundamental property of the assignment problem is that if a constant is added to or subtracted from all elements of any single row or any single column of the cost matrix, the optimal assignment (i.e., the set of assigned cells) does not change.Therefore, the optimal assignment $\sigma^*$ for the new problem is the same as for the original problem.The new minimum total processing time, $Z'_{min}$, is calculated using this same assignment $\sigma^*$ on the new cost matrix $C'$:$$Z'_{min} = \sum_{i=1}^{4} c'_{i, \sigma^*(i)}$$$$Z'_{min} = c'_{1, \sigma^*(1)} + c'_{2, \sigma^*(2)} + c'_{3, \sigma^*(3)} + c'_{4, \sigma^*(4)}$$Substituting the new cost values:$$Z'_{min} = c_{1, \sigma^*(1)} + c_{2, \sigma^*(2)} + c_{3, \sigma^*(3)} + (c_{4, \sigma^*(4)} + 20)$$Rearranging the terms:$$Z'_{min} = \left( \sum_{i=1}^{4} c_{i, \sigma^*(i)} \right) + 20$$We know that the sum in the parenthesis is the original minimum time, which is 500 minutes.$$Z'_{min} = 500 + 20 = 520$$Thus, the revised minimum total processing time will be 520 minutes.