Question

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.

Answer 1

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.