GATE 2019 ME Set 1 · Question 64
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
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
- 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…
- GATE 2024 ME · Q65In a supplier-retailer supply chain, the demand of each retailer, the capacity of each supplier, and the…
Question from the official GATE 2019 ME paper (Set 1), IIT Madras. Solutions by PARIXO AI. All 65 questions of this paper.