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