Question

Find the sequence of the following five jobs to be processed on three machines M₁ M_2,, M₃ that will minimize the total elapsed time to complete the tasks. Each job is to be processed in the order M₁ - M₂ - M₃:

Jobs	1	2	3	4	5
Machine M1	5	11	5	7	6
Machine M2	1	4	2	5	3
Machine M3	1	5	2	3	4

Answer 1

Min(M₁) = 5, Max(M₂) = 5, Min(M₃) =  1

Min (M₁) ≥ Max (M₂) 

∴ Min(M₃) ≥ Max (M₂) is satisfied.

G = M₁ + M₃ and H = M₂ + M₃

Jobs	1	2	3	4	5
MG	6	15	7	12	9
MH	2	9	4	8	7

∴ The required sequence is 

2

4

5

3

1

The table of total elapsed time is as follows: 

Job	Machine (M1)		Machine (M2)		Machine (M3)
	In	Out	In	Out	In	Out
2	0	11	11	15	15	20
4	11	18	18	23	23	26
5	18	24	24	27	27	31
3	24	29	29	31	31	33
1	29	34	34	35	35	36

Total elapsed time = 36 units. 

Idle time for M₁ = 2 units

Idle time for M₂ = 21 units

Idle time for M₃ = 21 units