N-Jobs 3 Machine Case

Johnson’s algorithm in regard to sequencing jobs can be further extended for using n jobs through 3 machine case. This can be done with the following conditions-

1. The least processing time for a task on machine M₃ is equal to or higher than that of the processing time for an analogous task on M₂ machine.
2. The utmost operation time for a task carried out on a machine M₁ is higher than or equal to the highest operation time for a similar task on the M₂ machine.

Assumptions

While following the above conditions, there are certain assumptions which need to be made. These presuppositions are-

1. The operation time for each task on machines – M₁, M₂, M₃, is known.
2. Each of these jobs is operated on all the above three machines. These are first processed in the chronological order- first on M₁, then on M₂ and finally on M₃.

• Passing of tasks is strictly prohibited.

In this process, two dummy machines M₁ ’ and M₃ ’ are presumed in such a way that the operation time of tasks in regard to these machines can be easily calculated.

A job’s processing time on M₁ ’ = Total processing time of  (M₁ + M₂ )

A job’s processing time on M₂ ’ = Total processing time of  (M₂ + M₁ )

Johnson’s algorithm in regard to sequencing jobs is then applied on M₁ ’ and M₂ ’ for deriving the most advantageous sequencing of tasks.

Students can have a better understanding of these machines and the processing time of tasks once they start practicing some problems based on the same. Refer to the examples and keep the above conditions and assumptions in mind.