Job and their processing time on machine `M_1` and `M_2`
| Job | 1 | 2 | 3 | 4 |
... |
n |
|
Machine `M_1` |
`t_11` |
`t_12` |
`t_13` |
`t_14` |
... |
`t_(1n)` |
|
Machine `M_2` |
`t_21` |
`t_22` |
`t_23` |
`t_24` |
... |
`t_(2n)` |
Johnson's algorithm for optimal sequence
- Find out the minimum processing time out of all the `M_1` and `M_2`
- If it is from `M_1`, then place the job first in the sequence.
- If it is from `M_2`, then place the job last in the sequence.
- If there is a tie in minimum processing times, then
- If minimum processing time is same on both machines `M_1` and `M_2`, say `t_(1i)=t_(2j)`, then process the `i^("th")` job first and the `j^("th")` job last.
- If minimum processing times, `t_(1i)=t_(1j)` on machine `M_1`, then select the job i first (Here `i < j`).
- If minimum processing times, `t_(2i)=t_(2j)` on machine `M_2`, then select the job j last (Here `i < j`).
- Now eliminate the assigned job, and repeat steps 1 to 4 until an optimal sequence is found.
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
