GATE ME 2019 Set 1 — Question 64
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0MediumTransportation & AssignmentOperations ResearchIndustrial Engineering
Industrial Engineering → Operations Research → Transportation & Assignment
Last updated
Question
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 |
Correct answer
146 to 146
Solution
This is an assignment problem that can be solved using the Hungarian Method to minimize total time.Step 1: Row Reduction (subtract minimum of each row from all elements in that row)
Step 3: Optimal Assignment
By drawing minimum lines to cover zeros and iterating (or by inspection for small matrices), we find the optimal assignment:
- J1: min 30 [10, 0, 20, 20, 28]
- J2: min 26 [0, 12, 34, 0, 12]
- J3: min 24 [16, 10, 4, 0, 6]
- J4: min 28 [0, 12, 12, 4, 20]
- J5: min 22 [6, 10, 16, 0, 22]
- M1: min 0, M2: min 0, M3: min 4, M4: min 0, M5: min 6
| M1 | M2 | M3 | M4 | M5 | |
|---|---|---|---|---|---|
| J1 | 10 | 0 | 16 | 20 | 22 |
| J2 | 0 | 12 | 30 | 0 | 6 |
| J3 | 16 | 10 | 0 | 0 | 0 |
| J4 | 0 | 12 | 8 | 4 | 14 |
| J5 | 6 | 10 | 12 | 0 | 16 |
By drawing minimum lines to cover zeros and iterating (or by inspection for small matrices), we find the optimal assignment:
- J1 M2: 30
- J2 M5: 38
- J3 M3: 28
- J4 M1: 28
- J5 M4: 22
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE ME question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Operations Research
2026 Set 1 Q46An objective function of primal variables ( and ) is described below: Minimize…2026 Set 1 Q47Four jobs are on order in a factory. As on day 20 of the production calendar, the corresponding due…2026 Set 1 Q60The actual demand for castings in a factory is units and units for the months of…2026 Set 1 Q61The inventory holding cost of an item is ₹ 0.50 per unit per month and the ordering cost per order…2026 Set 1 Q65The activities of a PERT network and their corresponding activity time estimates (in weeks) i.e.,…