Scheduling n Jobs × 2 Machines using Johnson's Rule
S. M. Johnson gave the following algorithm for finding sequence of a situation where there is a group of 'n' jobs to be processed through two successive work centers. The rule ensures minimum completion time for the group of 'n' jobs by minimizing the total idle times of the work centers.
The rule (Sequencing algorithm) is,
- Identify the job with lowest processing time among all the jobs (2n) on both the machines.
- If this shortest processing time belongs to the first machine (or work centre), then this job is placed first in sequence, if the shortest processing time appears under the second work centre, this job is put last in the sequence.
- Having placed the job, now delete it from any further consideration.
- For the remaining jobs, repeat step-2, until all the jobs are placed in the sequence.