GATE 2021 ME Set 1 · Question 38
A set of jobs A, B, C, D, E, F, G, H arrive at time for processing on turning and grinding machines. Each job needs to be processed in sequence – first on the turning machine and second on the grinding machine, and the grinding must occur immediately after turning. The processing times of the jobs are given below.
| Job | A | B | C | D | E | F | G | H |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| Turning (minutes) | 2 | 4 | 8 | 9 | 7 | 6 | 5 | 10 |
| Grinding (minutes) | 6 | 1 | 3 | 7 | 9 | 5 | 2 | 4 |
If the makespan is to be minimized, then the optimal sequence in which these jobs must be processed on the turning and grinding machines is
- A
A-E-D-F-H-C-G-B
- B
A-D-E-F-H-C-G-B
- C
G-E-D-F-H-C-A-B
- D
B-G-C-H-F-D-E-A
GATE 2021 · Mechanical Engineering · Set 1 · IIT Bombay · printed as Q.28 in the ME section
Answer
From the official answer key published by IIT Bombay.
Worked solution
To minimize the makespan for jobs on two machines in sequence (Turning then Grinding), we apply Johnson's rule:
1. The minimum processing time is for job B on Grinding Place B at the last position: .
2. The next smallest time is for job A on Turning and job G on Grinding:
- Job A is placed at the first available position: .
- Job G is placed at the last available position: .
3. Next smallest is for job C on Grinding .
4. Next smallest is for job H on Grinding .
5. Next smallest is for job F on Grinding .
6. Among remaining jobs D and E, the smallest time is (E on Turning, D on Grinding):
- E on Turning goes to the front: .
- D fills the remaining slot: .
Thus, the optimal sequence is A-E-D-F-H-C-G-B.
Answer: (A) A-E-D-F-H-C-G-B
Practise Sequencing and Scheduling
6 GATE questions from this chapter, in short untimed sets, with the formula sheet beside them. Free.
More from Sequencing and Scheduling
- GATE 2018 ME Set 1 · Q62Processing times (including setup times) and due dates for six jobs waiting to be processed at a work centre…
- GATE 2017 ME Set 1 · Q52Following data refers to the jobs (P, Q, R, S) which have arrived at a machine for scheduling. The shortest…
- GATE 2026 ME · Q47Four jobs are on order in a factory. As on day 20 of the production calendar, the corresponding due date and…
- GATE 2024 ME · Q34A set of jobs U, V, W, X, Y, Z arrive at time t = 0 to a production line consisting of two workstations in…
- GATE 2022 ME Set 2 · Q41Parts P1-P7 are machined first on a milling machine and then polished at a separate machine. Using the…
Question from the official GATE 2021 ME paper (Set 1), IIT Bombay. Solutions by PARIXO AI. All 65 questions of this paper.