GATE 2022 ME Set 1 · Question 58
An assignment problem is solved to minimize the total processing time of four jobs ( and ) 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)*.
GATE 2022 · Mechanical Engineering · Set 1 · IIT Kharagpur
Answer
From the official answer key published by IIT Kharagpur.
Worked solution
In an assignment problem, each job must be assigned to exactly one machine, and each machine is assigned exactly one job.
Let be the processing time of Job on Machine . Increasing the processing time of Job 4 on all machines by a constant value modifies the cost matrix such that:
Subtracting a constant from any row or column of the cost matrix does not change the optimal assignment. Since Job 4 is assigned to exactly one machine in any feasible assignment, its contribution to the objective function increases by precisely regardless of the machine selected.
Thus, the optimal assignment remains unchanged, and the revised minimum total processing time is:
Answer: 520
Practise Transportation, Assignment and Network Flow
8 GATE questions from this chapter, in short untimed sets, with the formula sheet beside them. Free.
More from Transportation, Assignment and Network Flow
- GATE 2019 ME Set 1 · Q64Five jobs (J1, J2, J3, J4 and J5) need to be processed in a factory. Each job can be assigned to any of the…
- GATE 2018 ME Set 2 · Q61The arc lengths of a directed graph of a project are as shown in the figure. The shortest path length from…
- GATE 2017 ME Set 2 · Q48A product made in two factories, P and Q, is transported to two destinations, R and S. The per unit costs of…
- GATE 2014 ME Set 2 · Q28If there are m sources and n destinations in a transportation matrix, the total number of basic variables in…
- GATE 2014 ME Set 3 · Q31A minimal spanning tree in network flow models involves
- GATE 2014 ME Set 4 · Q28The total number of decision variables in the objective function of an assignment problem of size n × n (n…
Question from the official GATE 2022 ME paper (Set 1), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.