GATE 2022 ME (ME2) – Question 41
Parts P1-P7 are machined first on a milling machine and then polished at a separate machine. Using the information in the following table, the minimum total completion time required for carrying out both the operations for all 7 parts is ______ hours.
| Part | Milling (hours) | Polishing (hours) |
|---|---|---|
| P1 | 8 | 6 |
| P2 | 3 | 2 |
| P3 | 3 | 4 |
| P4 | 4 | 6 |
| P5 | 5 | 7 |
| P6 | 6 | 4 |
| P7 | 2 | 1 |
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 33
Explanation
This is a two-machine flow shop (milling, then polishing), so **Johnson's rule** gives the order with the shortest total completion time.
**Step 1: split the parts.**
- Parts with milling time ≤ polishing time: P3 (3, 4), P4 (4, 6), P5 (5, 7). Put them **first**, in increasing order of milling time: P3, P4, P5.
- The other parts: P1 (8, 6), P2 (3, 2), P6 (6, 4), P7 (2, 1). Put them **last**, in decreasing order of polishing time: P1 (6), P6 (4), P2 (2), P7 (1).
**Step 2: sequence.** P3 – P4 – P5 – P1 – P6 – P2 – P7.
**Step 3: timetable** (a part is polished when milling of it is done and the polisher is free).
| Part | Milling ends | Polishing starts | Polishing ends |
|---|---|---|---|
| P3 | 3 | 3 | 7 |
| P4 | 7 | 7 | 13 |
| P5 | 12 | 13 | 20 |
| P1 | 20 | 20 | 26 |
| P6 | 26 | 26 | 30 |
| P2 | 29 | 30 | 32 |
| P7 | 31 | 32 | 33 |
The last polishing ends at **33 hours**, which is the minimum (milling alone takes 31 hours and P7 still needs 1 hour of polishing, and Johnson's rule is optimal).