4. Example-2
Find solution of Processing 7 Jobs Through 2 Machines Problem
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | Machine-1 | 3 | 12 | 15 | 6 | 10 | 11 | 9 | | Machine-2 | 8 | 10 | 10 | 6 | 12 | 1 | 3 |
Solution:
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| Machine `M_1` | 3 | 12 | 15 | 6 | 10 | 11 | 9 |
|---|
| Machine `M_2` | 8 | 10 | 10 | 6 | 12 | 1 | 3 |
|---|
1. The smallest processing time is 1 hour for job 6 on Machine-2. So job 6 will be processed last.
2. The next smallest processing time is 3 hour for job 1 on Machine-1. So job 1 will be processed first.
3. The next smallest processing time is 3 hour for job 7 on Machine-2. So job 7 will be processed before job 6.
4. The next smallest processing time is 6 hour for job 4 on Machine-1. So job 4 will be processed after job 1.
5. The next smallest processing time is 10 hour for job 2,3 on Machine-2 and for this jobs 12 is smallest on Machine-1. So job 2 will be processed before job 7.
6. The next smallest processing time is 10 hour for job 3 on Machine-2. So job 3 will be processed before job 2.
7. The next smallest processing time is 10 hour for job 5 on Machine-1. So job 5 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 | Idle time
`M_2` | | 1 | 0 | 0 + 3 = 3 | 3 | 3 + 8 = 11 | 3 | | 4 | 3 | 3 + 6 = 9 | 11 | 11 + 6 = 17 | - | | 5 | 9 | 9 + 10 = 19 | 19 | 19 + 12 = 31 | 2 | | 3 | 19 | 19 + 15 = 34 | 34 | 34 + 10 = 44 | 3 | | 2 | 34 | 34 + 12 = 46 | 46 | 46 + 10 = 56 | 2 | | 7 | 46 | 46 + 9 = 55 | 56 | 56 + 3 = 59 | - | | 6 | 55 | 55 + 11 = 66 | 66 | 66 + 1 = 67 | 7 |
The total minimum elapsed time = 67
Idle time for Machine-1
`=67 - 66`
`=1`
Idle time for Machine-2
`=(3)+(19-17)+(34-31)+(46-44)+(66-59)+(67-67)`
`=3+2+3+2+7+0`
`=17`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
