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
