Solve the following problem :
A foreman wants to process 4 different jobs on three machines: a shaping machine, a drilling machine and a tapping machine, the sequence of operations being shaping-drilling-tapping. Decide the optimal sequence for the four jobs to minimize the total elapsed time. Also find the total elapsed time and the idle time for every machine.
Job | Shaping (Minutes) | Drilling (Minutes) | Trapping (Minutes) |
1 | 13 | 3 | 18 |
2 | 18 | 8 | 4 |
3 | 8 | 6 | 13 |
4 | 23 | 6 | 8 |
Solution
job | 1 | 2 | 3 | 4 |
Shaping (Minutes) | 13 | 18 | 8 | 23 |
Drilling (Minutes) | 3 | 8 | 6 | 6 |
Trapping (Minute) | 18 | 4 | 13 | 8 |
Here, Min Shaping = 8, Max Drilling = 8, Min Trapping = 4.
Since Min Shaping ≥ Max Drilling is satisfied, the problem can be converted into a two machine problem.
Let G and H be two fictitious machines such that G = Shaping + Drilling and H = Drilling + Trapping
Then the problem can be written as
Job | 1 | 2 | 3 | 4 |
Machine G | 16 | 26 | 14 | 29 |
Machine H | 21 | 12 | 19 | 14 |
Observe that Min (G, H) = 12, corresponds to Job 2 on machine H.
∴ Job 2 is placed last in sequence.
2 |
Then the problem reduces to
Job | 1 | 3 | 4 |
Machine G | 16 | 14 | 29 |
Machine H | 21 | 19 | 14 |
Now, Min (G, H) = 14, corresponds to Job 3 on machine G and Job 4 on machine H.
∴ Job 3 is placed first in the sequence, Job 4 is placed second last in the sequence and remaining Job 1 is placed second in the sequence.
∴ Optimal sequence is
3 | 1 | 4 | 2 |
Total elapsed time
Job | Shaping | Drilling | Trapping | |||
In | Out | In | Out | In | Out | |
3 (8, 6, 13) | 0 | 8 | 8 | 14 | 14 | 27 |
1(13, 3, 18) | 8 | 21 | 21 | 24 | 27 | 45 |
4 (23, 6, 8) | 21 | 44 | 44 | 50 | 50 | 58 |
2 (18, 8, 4) | 44 | 62 | 62 | 70 | 70 | 74 |
∴ Total elapsed time = 74 mins
Idle time for Shaping = 74 – 62 = 12 mins
Idle time for Drilling = (74 – 70) + 8 + 7 + 20 + 12 = 51 mins
Idle time for Trapping = 14 + 5 +12 = 31 mins.