The GATE Grind

GATE 2021 ME (ME1) – Question 38

Production Planning and Control · Aggregate production planning, scheduling and material requirement planning · 2 marks · Multiple choice

A set of jobs A, B, C, D, E, F, G, H arrive at time t = 0 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.

JobABCDEFGH
Turning (minutes)248976510
Grinding (minutes)61379524

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-E-D-F-H-C-G-B
  2. A-D-E-F-H-C-G-B
  3. G-E-D-F-H-C-A-B
  4. B-G-C-H-F-D-E-A

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) A-E-D-F-H-C-G-B

Explanation

For ordinary two-machine flow-shop scheduling, Johnson’s rule places jobs with shorter turning times first and jobs with shorter grinding times last. It gives A,E followed by D,F,H,C,G,B.

For the printed no-wait condition, compute each next turning start with separation max(tᵢ,tᵢ+gᵢ−tⱼ). This gives 53 minutes for A, versus 55,56,64 for B,C,D. Thus **A** is best among the choices. However, exhaustive enumeration finds a 52-minute no-wait sequence, ACDEHFGB; the printed “optimal” wording is inaccurate.