Find the sequence that minimizes the total elapsed time to complete the following jobs in the order AB. Find the total elapsed time and idle times for both the machines.
Job | I | II | IIII | IV | V | VI | VII |
Machine A | 7 | 16 | 19 | 10 | 14 | 15 | 5 |
Machine B | 12 | 14 | 14 | 10 | 16 | 5 | 7 |
Solution
Observe that Min(A, B) = 5, corresponds to job VI on machine B and job VII on machine A.
∴ Job VI is placed last and job VII is placed first in sequence.
VII | VI |
Then the problem reduces to
Job | I | II | IIII | IV | V |
Machine A | 7 | 16 | 19 | 10 | 14 |
Machine B | 12 | 14 | 14 | 10 | 6 |
Now, Min(A, B) = 7, corresponds to job I on machine A.
∴ Job I is placed second in sequence.
VII | I | VI |
Then the problem reduces to
Job | II | III | IV | V |
Machine A | 16 | 19 | 10 | 14 |
Machine B | 14 | 14 | 10 | 16 |
Now, Min(A, B) = 10, corresponds to job IV on machine A as well as on machine B.
∴ Job IV is placed second or second last in sequence.
VII | I | IV | VI |
OR
VII | I | IV | VI |
Then the problem reduces to
Job | II | III | V |
Machine A | 16 | 19 | 14 |
Machine B | 14 | 14 | 16 |
Now, Min (A, B) = 14, corresponds to job II and job III on machine B and job V on machine A.
∴ These three jobs can be placed in the sequence in order: V – III – II or V – II – III
∴ The optimal sequence can be
VII | I | IV | V | III | II | VI |
OR
VII | I | V | III | II | IV | VI |
OR
VII | I | IV | V | II | III | VI |
OR
VII | I | V | II | III | IV | VI |
∴ We consider the optimal sequence as VII – I – IV – V – III – II – VI
Total Elapsed Time
Job | Machine A | Machine B | ||
In | Out | In | Out | |
VII (5, 7) | 0 | 5 | 5 | 12 |
I (7, 12) | 5 | 12 | 12 | 24 |
IV (10, 10) | 12 | 22 | 24 | 34 |
V (14, 16) | 22 | 36 | 36 | 52 |
III (19, 14) | 36 | 55 | 55 | 69 |
II (16, 14) | 55 | 71 | 71 | 85 |
V (15, 5) | 71 | 86 | 86 | 91 |
∴ Total elapsed time = 91 units
Idle time for Machine A = 91 – 86 = 5 units
Idle time for Machine B = 5 + 2 + 3 + 2 + 1 = 13 units.