Find solution of Processing 4 Jobs Through 5 Machines Problem
| Job | 1 | 2 | 3 | 4 |
| Machine-1 | 6 | 5 | 4 | 7 |
| Machine-2 | 4 | 5 | 3 | 2 |
| Machine-3 | 1 | 3 | 4 | 2 |
| Machine-4 | 2 | 4 | 5 | 1 |
| Machine-5 | 8 | 9 | 7 | 5 |
Solution:
| Job | 1 | 2 | 3 | 4 |
|---|
| Machine `M_1` | 6 | 5 | 4 | 7 |
|---|
| Machine `M_2` | 4 | 5 | 3 | 2 |
|---|
| Machine `M_3` | 1 | 3 | 4 | 2 |
|---|
| Machine `M_4` | 2 | 4 | 5 | 1 |
|---|
| Machine `M_5` | 8 | 9 | 7 | 5 |
|---|
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 10 hour for job 4 on Machine-H. So job 4 will be processed last.
2. The next smallest processing time is 13 hour for job 1 on Machine-G. So job 1 will be processed first.
3. The next smallest processing time is 16 hour for job 3 on Machine-G. So job 3 will be processed after job 1.
4. The next smallest processing time is 17 hour for job 2 on Machine-G. So job 2 will be processed after job 3.
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 | `M_5`
In time | `M_5`
Out time | Idle time
`M_2` | Idle time
`M_3` | Idle time
`M_4` | Idle time
`M_5` |
| 1 | 0 | 0 + 6 = 6 | 6 | 6 + 4 = 10 | 10 | 10 + 1 = 11 | 11 | 11 + 2 = 13 | 13 | 13 + 8 = 21 | 6 | 10 | 11 | 13 |
| 3 | 6 | 6 + 4 = 10 | 10 | 10 + 3 = 13 | 13 | 13 + 4 = 17 | 17 | 17 + 5 = 22 | 22 | 22 + 7 = 29 | - | 2 | 4 | 1 |
| 2 | 10 | 10 + 5 = 15 | 15 | 15 + 5 = 20 | 20 | 20 + 3 = 23 | 23 | 23 + 4 = 27 | 29 | 29 + 9 = 38 | 2 | 3 | 1 | - |
| 4 | 15 | 15 + 7 = 22 | 22 | 22 + 2 = 24 | 24 | 24 + 2 = 26 | 27 | 27 + 1 = 28 | 38 | 38 + 5 = 43 | 2 | 1 | - | - |
The total minimum elapsed time = 43
Idle time for Machine-1
`=43 - 22`
`=21`
Idle time for Machine-2
`=(6)+(15-13)+(22-20)+(43-24)`
`=6+2+2+19`
`=29`
Idle time for Machine-3
`=(10)+(13-11)+(20-17)+(24-23)+(43-26)`
`=10+2+3+1+17`
`=33`
Idle time for Machine-4
`=(11)+(17-13)+(23-22)+(43-28)`
`=11+4+1+15`
`=31`
Idle time for Machine-5
`=(13)+(22-21)+(43-43)`
`=13+1+0`
`=14`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
