Johnsons Algorithm for n Jobs and Two Machines

Johnson’s algorithm is used for sequencing of ‘n’ jobs through two work centres. The purpose is to minimise idle time on machines and reduce the total time taken for completing all the jobs.As there are no priority rules since all job have equal priority, sequencing the jobs according to the time taken may minimise the idle time taken by the jobs on machines. This reduces the total time taken.

The algorithm can be fulfilled in the following steps.

  • Step 1: Find the minimum among the time taken by machine 1 and 2 for all the jobs.
  • Step 2a: If the minimum processing time is required by machine 1 to complete the job, place the associated job in the first available position in the final sequence. Then go to step 3. (If it is a tie you may choose either of them, for applying the above rule.)
  • Step 2b: If the minimum processing time is required by machine 2 to complete the job, place the associated job in the last available position in final sequence. Then go to step 3. (If it is a tie you may choose either of them, for applying the above rule.)
  • Step 3: Remove the assigned job from consideration and return to step 1 until all the positions in the sequence are filled.

Consider the following example:

PARTS

MACHINES P1 P2 P3
M1 30 14 30
M2 25 18 19

The minimum time taken is 14, by P2, on M1. So P2 will be first in the sequence; since P2 is assigned, we remove it from consideration.

The next least time is 19, taken by P3 on M2. Since it is on M2, it is assigned is the last position in the sequence.

The remaining middle position is then taken up by P1.

One thought on “Johnsons Algorithm for n Jobs and Two Machines

Leave a Reply

error: Content is protected !!
%d bloggers like this: