PARIXO GATE · ME Open the app

GATE 2021 ME Set 1 · Question 38

2 marksMultiple choiceIndustrial EngineeringSequencing and Scheduling

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

  1. A

    A-E-D-F-H-C-G-B

  2. B

    A-D-E-F-H-C-G-B

  3. C

    G-E-D-F-H-C-A-B

  4. 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
(A)

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

Question from the official GATE 2021 ME paper (Set 1), IIT Bombay. Solutions by PARIXO AI. All 65 questions of this paper.