Question Details

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 FG 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

Options

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

Show Answer
Correct Answer

Solution :

The correct option is A-E-D-F-H-C-G-B.

Step-by-Step Explanation:

To minimize the makespan for n jobs on two sequential machines (Turning followed by Grinding), we use Johnson's Rule. The objective of Johnson's Rule is to sequence the jobs such that idle time on the machines is minimized, thereby minimizing the total elapsed time (makespan).

Johnson's Algorithm Procedure:
1. Find the minimum processing time among all remaining jobs on both machines.
2. If this minimum time occurs on the first machine (Turning), place that job in the first available position of the sequence (from left to right).
3. If this minimum time occurs on the second machine (Grinding), place that job in the last available position of the sequence (from right to left).
4. If there is a tie, we can choose arbitrarily, though specific tie-breaking choices lead to the exact sequence matching the options.
5. Remove the scheduled job from the list and repeat the process until all jobs are scheduled.

Let us apply Johnson's Rule step-by-step to our job table:

Iteration 1:
The minimum processing time in the entire table is 1 minute, which occurs for Job B on the Grinding machine (second machine).
Since this minimum time is on the second machine, we place Job B in the last available position of our 8-job sequence:
Current Sequence: [ _ , _ , _ , _ , _ , _ , _ , B ]

Iteration 2:
With Job B removed, the minimum processing time among the remaining jobs is 2 minutes. This occurs for two jobs:
- Job A: 2 minutes on the Turning machine (first machine).
- Job G: 2 minutes on the Grinding machine (second machine).

Following Johnson's Rule:
- Since Job A's minimum time is on the first machine, it is placed in the first available position from the left: 1st position.
- Since Job G's minimum time is on the second machine, it is placed in the last available position from the right: 7th position (just before B).

Current Sequence: [ A , _ , _ , _ , _ , _ , G , B ]

Iteration 3:
With jobs A, B, and G removed, the remaining jobs are C, D, E, F, H.
The minimum processing time among these is 3 minutes, which occurs for Job C on the Grinding machine (second machine).
Since this is on the second machine, we place Job C in the last available position (from the right, in the 6th position):
Current Sequence: [ A , _ , _ , _ , _ , C , G , B ]

Iteration 4:
With jobs A, B, C, G removed, the remaining jobs are D, E, F, H.
The minimum processing time among these is 4 minutes, which occurs for Job H on the Grinding machine (second machine).
Since this is on the second machine, we place Job H in the last available position (5th position):
Current Sequence: [ A , _ , _ , _ , H , C , G , B ]

Iteration 5:
The remaining jobs are D, E, F.
The minimum processing time among these is 5 minutes, which occurs for Job F on the Grinding machine (second machine).
Since this is on the second machine, we place Job F in the last available position (4th position):
Current Sequence: [ A , _ , _ , F , H , C , G , B ]

Iteration 6:
The remaining jobs are D and E. The times are:
- Job D: Turning = 9, Grinding = 7
- Job E: Turning = 7, Grinding = 9

The minimum processing time is 7 minutes, which occurs for:
- Job D on the Grinding machine (second machine).
- Job E on the Turning machine (first machine).

Applying Johnson's Rule:
- Since Job E's minimum time is on the first machine, it is placed in the first available position from the left: 2nd position.
- Since Job D's minimum time is on the second machine, it is placed in the last available position from the right: 3rd position.

Current Sequence: [ A , E , D , F , H , C , G , B ]

All jobs have been scheduled. The resulting optimal sequence to minimize the makespan is A-E-D-F-H-C-G-B.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • intermediate
  • 3 hours
  • mechanical engineering

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.

  • GATE
  • intermediate
  • 3 hours
  • mechanical engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: