PARIXO GATE · ME Open the app

GATE 2022 ME Set 1 · Question 58

2 marksNumerical answerIndustrial EngineeringTransportation, Assignment and Network Flow

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
520

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

Question from the official GATE 2022 ME paper (Set 1), IIT Kharagpur. Solutions by PARIXO AI. All 65 questions of this paper.