Question

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

Answer 1

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 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.