Johnson's Rule

Johnson's rule gives a schedule with the minimum makespan (total time needed to complete a set of jobs) when the following assumptions apply:

• each job has two operations that are performed on two different machines
• the times required for the operations are fixed and independent of job sequence
• in every case, the first operation is on machine 1 and the second is on machine 2

From a list of jobs and operation times a sequence of the jobs is created by repeatedly applying Johnson's rule. The rule tells which job to put into the sequence next and whether the job should be placed toward the beginning or the end of the sequence.

The rule says to select the job with the shortest operation time (for either operation). If this shortest time is for the operation on machine 1, schedule this job as early as possible in the sequence, not displacing any jobs previously scheduled. If the shortest operation is for the second machine, schedule the job as late in the sequence as possible, not displacing any jobs already sequenced. You will be putting jobs into the sequence starting from the back and front of the list and working towards the middle. If there is ever a tie for shortest operation, arbitrarily choose one of the jobs.

Suppose you had five jobs with the following times:

To sequence these using Johnson's rule:

Select Job A, time = 3, put at end of list: _ _ _ _ A

Select Job E, time = 6, put at beginning of list: E _ _ _ A

Select Job D, time = 9, put at beginning of list: E D _ _ A

Select Job B, time = 11, put at end of list: E D _ BA

Select Job C, time = 13, put at end of list: E D C B A