Solve the following problem :
A toy manufacturing company produces five types of toys. Each toy has to go through three machines A, B, C in the order ABC. The time required in hours for each process is given in the following table.
Type | 1 | 2 | 3 | 4 | 5 |
Machine A | 16 | 20 | 12 | 14 | 22 |
Machine B | 10 | 12 | 4 | 6 | 8 |
Machine C | 8 | 18 | 16 | 12 | 10 |
Solve the problem for minimizing the total elapsed time.
Solution
Type | 1 | 2 | 3 | 4 | 5 |
Machine A | 16 | 20 | 12 | 14 | 22 |
Machine B | 10 | 12 | 4 | 6 | 8 |
Machine C | 8 | 18 | 16 | 12 | 10 |
Here min A = 12, max B = 12, min C = 8.
Since min A ≥ max B is satisfied, the problem can be converted into a two machine problem.
Let G and H be two fictitious machines such that G = A + B and H = B + C
Then the problem can be written as
Type | 1 | 2 | 3 | 4 | 5 |
Machine G | 26 | 32 | 16 | 20 | 30 |
Machine H | 18 | 30 | 20 | 18 | 18 |
Observe that Min (G, H) = 16, corresponds to Type 3 on machine G.
∴ Type 3 is placed first in sequence.
3 |
Then the problem reduces to
Type | 1 | 2 | 4 | 5 |
Machine G | 26 | 32 | 20 | 30 |
Machine H | 18 | 30 | 18 | 18 |
Now, Min (G, H) = 18, corresponds to Type 1, Type 4 and Type 5 on machine H.
∴ Type 1, 4 and 5 are placed either last, second last or third last and Type 2 on remaining in the sequence.
3 | 2 | 5 | 4 | 1 |
OR |
3 | 2 | 5 | 1 | 4 |
OR |
3 | 2 | 1 | 4 | 5 |
OR |
3 | 2 | 1 | 5 | 4 |
OR |
3 | 2 | 4 | 1 | 5 |
OR |
3 | 2 | 4 | 5 | 1 |
We take the optimal sequence as,
3 – 2 – 5 – 4 – 1
Total elapsed time
Job | Machine A | Machine B | Machine C | |||
In | Out | In | Out | In | Out | |
3 (12, 4, 16) | 0 | 12 | 12 | 16 | 16 | 32 |
2 (20, 12, 18) | 12 | 32 | 32 | 44 | 44 | 62 |
5 (22, 8, 10) | 32 | 54 | 54 | 62 | 62 | 72 |
4 (14, 6, 12) | 54 | 68 | 68 | 74 | 74 | 86 |
1 (16, 10, 8) | 68 | 84 | 84 | 94 | 94 | 102 |
∴ Total elapsed time = 102 hrs
Idle time for machine A = 102 – 84 = 18 hrs
Idle time for machine B = (102 – 94) + 12 + 16 + 10 + 6 + 10 = 62
Idle time for machine C = 16 + 12 + 2 + 8 = 38 hrs.