Solve the following problem :
Find the sequence that minimizes the total elapsed time to complete the following jobs. Each job is processed in order AB.
Machines | Jobs (Processing times in minutes) | ||||||
I | II | III | IV | V | VI | VII | |
Machine A | 12 | 6 | 5 | 11 | 5 | 7 | 6 |
Machine B | 7 | 8 | 9 | 4 | 7 | 8 | 3 |
Determine the sequence for the jobs so as to minimize the processing time. Find the total elapsed time and the idle times for both the machines.
Solution
Machines | Jobs (Processing times in minutes) | ||||||
I | II | III | IV | V | VI | VII | |
Machine A | 12 | 6 | 5 | 11 | 5 | 7 | 6 |
Machine B | 7 | 8 | 9 | 4 | 7 | 8 | 3 |
Observe that Min (A, B) = 3, corresponds to job VII on machine B.
∴ Job VII is placed last in sequence.
VII |
Then the problem reduces to
Machines | Jobs (Processing times in minutes) | |||||
I | II | III | IV | V | VI | |
Machine A | 12 | 6 | 5 | 11 | 5 | 7 |
Machine B | 7 | 8 | 9 | 4 | 7 | 8 |
Now, Min (A, B) = 4, corresponds to job IV on machine B
∴ Job IV is placed before VII in sequence.
IV | VII |
Then the problem reduces to
Machines | Jobs (Processing times in minutes) | ||||
I | II | III | V | VI | |
Machine A | 12 | 6 | 5 | 5 | 7 |
Machine B | 7 | 8 | 9 | 7 | 8 |
Now, Min (A, B) = 5, corresponds to job III and V on machine A.
∴ Job III and V is placed either first or second in sequence.
III | V | IV | VII |
OR |
V | III | IV | VII |
Then the problem reduces to
Machines | Jobs (Processing times in minutes) | ||
I | II | VI | |
Machine A | 12 | 6 | 7 |
Machine B | 7 | 8 | 8 |
Now, Min (A, B) = 6, corresponds to job II on machine A
∴ Job II is placed on third place in sequence.
III | V | II | IV | VII |
OR |
V | III | II | IV | VII |
Then the problem reduces to
Machines | Jobs (Processing times in minutes) | |
I | VI | |
Machine A | 12 | 7 |
Machine B | 7 | 8 |
Now, Min (A, B) = 7, corresponds to job I on machine B and VI on machine A.
∴ Job I is placed before IV and job VI on remaining in sequence.
III | V | II | VI | I | IV | VII |
OR |
V | III | II | VI | I | IV | VII |
We take the optimal sequence as,
III | V | II | VI | I | IV | VII |
Total elapsed time
Job | Machine A | Machine B | ||
In | Out | In | Out | |
III (5, 9) | 0 | 5 | 5 | 14 |
V (5, 7) | 5 | 10 | 14 | 21 |
II (6, 8) | 10 | 16 | 21 | 29 |
VI (7, 8) | 16 | 23 | 29 | 37 |
I (12, 7) | 23 | 35 | 37 | 44 |
IV (11, 4) | 35 | 46 | 46 | 50 |
VII (6, 3) | 46 | 52 | 52 | 55 |
∴ Total elapsed time = 55 mins
Idle time for machine A = 55 – 52 = 3 mins
Idle time for machine B = 5 + 2 + 2 = 9 mins.