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. 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
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
| 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
Solution :
The correct option is A-E-D-F-H-C-G-B.
Step-by-step Explanation:
To find the optimal sequence of jobs to minimize the makespan when jobs must be processed sequentially through two machines (Turning first, then Grinding), we use Johnson's Rule. Let's list the processing times of the jobs on both machines:
- Job A: Turning = 2, Grinding = 6
- Job B: Turning = 4, Grinding = 1
- Job C: Turning = 8, Grinding = 3
- Job D: Turning = 9, Grinding = 7
- Job E: Turning = 7, Grinding = 9
- Job F: Turning = 6, Grinding = 5
- Job G: Turning = 5, Grinding = 2
- Job H: Turning = 10, Grinding = 4
Johnson's Algorithm Steps:
1. Identify the smallest processing time among all remaining jobs on both machines.
2. If the smallest time is on the first machine (Turning), place the corresponding job as early as possible in the sequence (from left to right).
3. If the smallest time is on the second machine (Grinding), place the corresponding job as late as possible in the sequence (from right to left).
4. Remove the scheduled job from the list and repeat the process until all jobs are scheduled.
Let's construct the sequence step-by-step:
Step 1: The overall minimum processing time is 1 minute, which is for Job B on the Grinding machine (second machine). Since it is on the second machine, we place Job B at the very end of the sequence.
Current Sequence: [ _ , _ , _ , _ , _ , _ , _ , B ]
Step 2: The next smallest processing time among the remaining jobs is 2 minutes, which occurs for two jobs:
- Job A has 2 minutes on the Turning machine (first machine).
- Job G has 2 minutes on the Grinding machine (second machine).
Following the rule:
- Place Job A at the very beginning (left-hand side).
- Place Job G at the available spot closest to the end (right-hand side, just before B).
Current Sequence: [ A , _ , _ , _ , _ , _ , G , B ]
Step 3: The next smallest processing time among the remaining jobs (C, D, E, F, H) is 3 minutes, which is for Job C on the Grinding machine (second machine). We place Job C at the next available spot from the right.
Current Sequence: [ A , _ , _ , _ , _ , C , G , B ]
Step 4: The next smallest processing time among the remaining jobs (D, E, F, H) is 4 minutes, which is for Job H on the Grinding machine (second machine). We place Job H at the next available spot from the right.
Current Sequence: [ A , _ , _ , _ , H , C , G , B ]
Step 5: The next smallest processing time among the remaining jobs (D, E, F) is 5 minutes, which is for Job F on the Grinding machine (second machine). We place Job F at the next available spot from the right.
Current Sequence: [ A , _ , _ , F , H , C , G , B ]
Step 6: The next smallest processing time between the remaining jobs (D, E) is 7 minutes, which occurs for:
- Job E on the Turning machine (7 minutes).
- Job D on the Grinding machine (7 minutes).
Following the rule:
- Place Job E at the next available spot from the left.
- Place Job D at the next available spot from the right (which fills the remaining slot).
Current Sequence: [ A , E , D , F , H , C , G , B ]
Thus, the optimal sequence to minimize the makespan is indeed A-E-D-F-H-C-G-B.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
The GATE 2026 Mechanical Engineering (ME) examination scheduled for 14 February 2026 is one of the most important national-level competitive exams for engineering graduates aspiring for higher education and prestigious career opportunities in PSU and research organizations. Conducted annually at the national level, the GATE Mechanical Engineering paper evaluates candidates on core subjects such as Engineering Mechanics, Thermodynamics, Fluid Mechanics, Strength of Materials, Manufacturing Processes, and Machine Design, along with General Aptitude and Engineering Mathematics. This examination is a gateway for admission into M.Tech/Ph.D. programs at IITs, NITs, IISc, and other top institutions, as well as recruitment in major Public Sector Undertakings (PSUs) like ONGC, NTPC, BHEL, IOCL, and more. The GATE ME 2026 paper will test conceptual understanding, analytical thinking, and problem-solving ability, making strong preparation essential for success. Candidates are advised to practice previous year papers, mock tests, and focus on conceptual clarity for high scoring performance. This exam on 14/02/2026 is a crucial opportunity for mechanical engineering aspirants to secure their future in academia and industry.
Strengthen your preparation with this GATE 2025 Mechanical Engineering (ME) test, covering core subjects such as thermodynamics, fluid mechanics, strength of materials, theory of machines, and manufacturing engineering. With a well-balanced mix of conceptual and numerical questions, this test helps enhance problem-solving ability and technical understanding. Aligned with the latest exam pattern, it is ideal for improving accuracy, speed, and overall exam readiness.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.