GATE 2022 ME (ME1) – Question 58

Operations Research · Transportation and assignment problems · 2 marks · Numerical answer

An assignment problem is solved to minimize the total processing time of four jobs (1, 2, 3 and 4) on four different machines such that each job is processed exactly by one machine and each machine processes exactly one job. The minimum total processing time is found to be 500 minutes. Due to a change in design, the processing time of Job 4 on each machine has increased by 20 minutes. The revised minimum total processing time will be _____________ minutes (in integer).

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 520

Explanation

Job 4 is assigned to exactly one machine in every assignment, so every feasible assignment has its total time increased by exactly 20 minutes. The optimal assignment does not change, and the new minimum is $500 + 20 = 520$ minutes.