1. A book binder has one printing press, one binding machine and manuscripts of 7 different
books. The times required for performing printing and binding operations for different books are shown below.
| Book | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Printing time (hours) | 20 | 90 | 80 | 20 | 120 | 15 | 65 |
| Binding time (hours) | 25 | 60 | 75 | 30 | 90 | 35 | 50 |
Decide the optimum sequence of processing of books in order to minimize the total
time required to bring out all the books.
Solution:
| Job | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| Machine `M_1` | 20 | 90 | 80 | 20 | 120 | 15 | 65 |
|---|
| Machine `M_2` | 25 | 60 | 75 | 30 | 90 | 35 | 50 |
|---|
1. The smallest processing time is 15 hour for job 6 on Machine-1. So job 6 will be processed first.
2. The next smallest processing time is 20 hour for job 1,4 on Machine-1 and for this jobs 30 is largest on Machine-2. So job 4 will be processed after job 6.
3. The next smallest processing time is 20 hour for job 1 on Machine-1. So job 1 will be processed after job 4.
4. The next smallest processing time is 50 hour for job 7 on Machine-2. So job 7 will be processed last.
5. The next smallest processing time is 60 hour for job 2 on Machine-2. So job 2 will be processed before job 7.
6. The next smallest processing time is 75 hour for job 3 on Machine-2. So job 3 will be processed before job 2.
7. The next smallest processing time is 90 hour for job 5 on Machine-2. So job 5 will be processed before 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 | Idle time
`M_2` |
| 6 | 0 | 0 + 15 = 15 | 15 | 15 + 35 = 50 | 15 |
| 4 | 15 | 15 + 20 = 35 | 50 | 50 + 30 = 80 | - |
| 1 | 35 | 35 + 20 = 55 | 80 | 80 + 25 = 105 | - |
| 5 | 55 | 55 + 120 = 175 | 175 | 175 + 90 = 265 | 70 |
| 3 | 175 | 175 + 80 = 255 | 265 | 265 + 75 = 340 | - |
| 2 | 255 | 255 + 90 = 345 | 345 | 345 + 60 = 405 | 5 |
| 7 | 345 | 345 + 65 = 410 | 410 | 410 + 50 = 460 | 5 |
The total minimum elapsed time = 460
Idle time for Machine-1
`=460 - 410`
`=50`
Idle time for Machine-2
`=(15)+(175-105)+(345-340)+(410-405)+(460-460)`
`=15+70+5+5+0`
`=95`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
