Question

A publisher produces 5 books on Mathematics. The books have to go through composing, printing and binding done by 3 machines A, B, C. The time schedule for the entire task in proper unit is as follows :

Book	I	II	III	IV	V
Machine A	4	9	8	6	5
Machine B	5	6	2	3	4
Machine C	8	10	6	7	11

Determine the optimum time required to finish the entire task. Also, find idle time for machines A, B, C.

Answer 1

Here min A = 4, max B = 6, min C = 6
Since min C ≥ max B is satisfied, the problem can be converted into a two machine problem.
Let G and H be two fictitious machines such that G = A + B and H = B + C
Then the problem can be written as

Books	Machines
	G = A + B	H = B + C
I	9	13
II	15	16
II	10	8
IV	9	10
V	9	15

Observe that Min (G, H) = 8, corresponds to Book III on machine H.
∴ Book III is placed last in sequence.

III

The problem now reduces to four jobs I, II, IV and V. Here, Min. (G, H) = 9, which corresponds to G. Therefore, either of the books I or IV or V is processed first of all and the remaining next to book I.

I

IV

V

III

 OR

I → V → IV, IV → I → V, V → I → IV, IV → V → I, V → IV → I

Now, the remaining book II is processed next to book V. Thus, the optimal sequence of jobs is obtained as follows :

I

IV

V

II

III

    OR

I

V

IV

II

III

 OR

IV

I

V

II

III

OR

V

I

IV

II

III

OR

IV

V

I

II

III

OR

V

IV

I

II

III

Considering the first sequence of jobs, the minimum elapsed time can be computed as follows        

Job	Machine A		Machine B		Machine C		Idle time for Machine C
	In	Out	In	Out	In	Out
I	0	4	4	9	9	17	9
II	4	10	10	13	17	24	0
II	10	15	15	19	24	35	0
IV	15	24	24	30	35	45	0
V	24	32	32	34	45	51	0
Total idle time for Machine C							9

 Total elapsed time = 51 hours
Idle time for machine A = 51 –  32 = 19 hours
Idle time for machine B = 51 – 20  = 31 hours
Idle time for machine C = 9 hours.