Find solution of Processing 5 Jobs Through 4 Machines Problem
| Job | 1 | 2 | 3 | 4 | 5 |
| Machine-1 | 11 | 13 | 9 | 16 | 17 |
| Machine-2 | 4 | 3 | 5 | 2 | 6 |
| Machine-3 | 6 | 7 | 5 | 8 | 4 |
| Machine-4 | 15 | 8 | 13 | 9 | 11 |
Solution:
| Job | 1 | 2 | 3 | 4 | 5 |
|---|
| Machine `M_1` | 11 | 13 | 9 | 16 | 17 |
|---|
| Machine `M_2` | 4 | 3 | 5 | 2 | 6 |
|---|
| Machine `M_3` | 6 | 7 | 5 | 8 | 4 |
|---|
| Machine `M_4` | 15 | 8 | 13 | 9 | 11 |
|---|
Since any of condition `min{T_(1j)} >= max{T_(ij)}` and/or `min{T_(mj)} >= max{T_(ij)}`, for j=2,3,...,m-1 is satisfied.
So given problem can be converted to 2-machine problem.
Machine-G
Machine-H
1. The smallest processing time is 18 hour for job 2 on Machine-H. So job 2 will be processed last.
2. The next smallest processing time is 19 hour for job 3 on Machine-G. So job 3 will be processed first.
3. The next smallest processing time is 19 hour for job 4 on Machine-H. So job 4 will be processed before job 2.
4. The next smallest processing time is 21 hour for job 1 on Machine-G. So job 1 will be processed after job 3.
5. The next smallest processing time is 21 hour for job 5 on Machine-H. So job 5 will be processed before job 4.
According to Johanson's algorithm, the optimal sequence is as below
| Job | `M_1`
In time | `M_1`
Out time | `M_2`
In time | `M_2`
Out time | `M_3`
In time | `M_3`
Out time | `M_4`
In time | `M_4`
Out time | Idle time
`M_2` | Idle time
`M_3` | Idle time
`M_4` |
| 3 | 0 | 0 + 9 = 9 | 9 | 9 + 5 = 14 | 14 | 14 + 5 = 19 | 19 | 19 + 13 = 32 | 9 | 14 | 19 |
| 1 | 9 | 9 + 11 = 20 | 20 | 20 + 4 = 24 | 24 | 24 + 6 = 30 | 32 | 32 + 15 = 47 | 6 | 5 | - |
| 5 | 20 | 20 + 17 = 37 | 37 | 37 + 6 = 43 | 43 | 43 + 4 = 47 | 47 | 47 + 11 = 58 | 13 | 13 | - |
| 4 | 37 | 37 + 16 = 53 | 53 | 53 + 2 = 55 | 55 | 55 + 8 = 63 | 63 | 63 + 9 = 72 | 10 | 8 | 5 |
| 2 | 53 | 53 + 13 = 66 | 66 | 66 + 3 = 69 | 69 | 69 + 7 = 76 | 76 | 76 + 8 = 84 | 11 | 6 | 4 |
The total minimum elapsed time = 84
Idle time for Machine-1
`=84 - 66`
`=18`
Idle time for Machine-2
`=(9)+(20-14)+(37-24)+(53-43)+(66-55)+(84-69)`
`=9+6+13+10+11+15`
`=64`
Idle time for Machine-3
`=(14)+(24-19)+(43-30)+(55-47)+(69-63)+(84-76)`
`=14+5+13+8+6+8`
`=54`
Idle time for Machine-4
`=(19)+(63-58)+(76-72)+(84-84)`
`=19+5+4+0`
`=28`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
