3. Example-3
Find solution of Processing 7 Jobs Through 3 Machines Problem
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | Machine-1 | 3 | 8 | 7 | 4 | 9 | 8 | 7 | | Machine-2 | 4 | 3 | 2 | 5 | 1 | 4 | 3 | | Machine-3 | 6 | 7 | 5 | 11 | 5 | 6 | 12 |
Solution:
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| Machine `M_1` | 3 | 8 | 7 | 4 | 9 | 8 | 7 |
|---|
| Machine `M_2` | 4 | 3 | 2 | 5 | 1 | 4 | 3 |
|---|
| Machine `M_3` | 6 | 7 | 5 | 11 | 5 | 6 | 12 |
|---|
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 6 hour for job 5 on Machine-H. So job 5 will be processed last.
2. The next smallest processing time is 7 hour for job 1 on Machine-G. So job 1 will be processed first.
3. The next smallest processing time is 7 hour for job 3 on Machine-H. So job 3 will be processed before job 5.
4. The next smallest processing time is 9 hour for job 4 on Machine-G. So job 4 will be processed after job 1.
5. The next smallest processing time is 10 hour for job 2,6 on Machine-H and for this jobs 11 is smallest on Machine-G. So job 2 will be processed before job 3.
6. The next smallest processing time is 10 hour for job 6 on Machine-H. So job 6 will be processed before job 2.
7. The next smallest processing time is 10 hour for job 7 on Machine-G. So job 7 will be processed after 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 | Idle time
`M_2` | Idle time
`M_3` | | 1 | 0 | 0 + 3 = 3 | 3 | 3 + 4 = 7 | 7 | 7 + 6 = 13 | 3 | 7 | | 4 | 3 | 3 + 4 = 7 | 7 | 7 + 5 = 12 | 13 | 13 + 11 = 24 | - | - | | 7 | 7 | 7 + 7 = 14 | 14 | 14 + 3 = 17 | 24 | 24 + 12 = 36 | 2 | - | | 6 | 14 | 14 + 8 = 22 | 22 | 22 + 4 = 26 | 36 | 36 + 6 = 42 | 5 | - | | 2 | 22 | 22 + 8 = 30 | 30 | 30 + 3 = 33 | 42 | 42 + 7 = 49 | 4 | - | | 3 | 30 | 30 + 7 = 37 | 37 | 37 + 2 = 39 | 49 | 49 + 5 = 54 | 4 | - | | 5 | 37 | 37 + 9 = 46 | 46 | 46 + 1 = 47 | 54 | 54 + 5 = 59 | 7 | - |
The total minimum elapsed time = 59
Idle time for Machine-1
`=59 - 46`
`=13`
Idle time for Machine-2
`=(3)+(14-12)+(22-17)+(30-26)+(37-33)+(46-39)+(59-47)`
`=3+2+5+4+4+7+12`
`=37`
Idle time for Machine-3
`=(7)+(59-59)`
`=7+0`
`=7`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
