PARIXO GATE · ME Open the app

GATE 2019 ME Set 1 · Question 64

2 marksNumerical answerIndustrial EngineeringTransportation, Assignment and Network Flow

Five jobs (J1, J2, J3, J4 and J5) need to be processed in a factory. Each job can be assigned to any of the five different machines (M1, M2, M3, M4 and M5). The time durations taken (in minutes) by the machines for each of the jobs, are given in the table. However, each job is assigned to a specific machine in such a way that the total processing time is minimum. The total processing time is _______ minutes.

| | M1 | M2 | M3 | M4 | M5 |
|---|---|---|---|---|---|
| J1 | 40 | 30 | 50 | 50 | 58 |
| J2 | 26 | 38 | 60 | 26 | 38 |
| J3 | 40 | 34 | 28 | 24 | 30 |
| J4 | 28 | 40 | 40 | 32 | 48 |
| J5 | 28 | 32 | 38 | 22 | 44 |

GATE 2019 · Mechanical Engineering · Set 1 · IIT Madras · printed as Q.54 in the ME section

Answer
146

From the official answer key published by IIT Madras.

Worked solution

The cost (time) matrix is:

Step 1: Row reduction (subtract row minimums: 30, 26, 24, 28, 22):

Step 2: Column reduction (subtract column minimums: 0, 0, 4, 0, 6):

The minimum number of lines to cover all zeros is 4 (columns 1, 2, 4 and row 3). The minimum uncovered element is 6. Subtracting 6 from uncovered elements and adding 6 to doubly-covered elements gives the optimal assignments:

  • with time
  • with time
  • with time
  • with time
  • with time

Answer: 146

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 2019 ME paper (Set 1), IIT Madras. Solutions by PARIXO AI. All 65 questions of this paper.