Question

There are found jobs to be completed. Each job must go through machines M₁ , M₂ , M₃ in the order M₁ - M₂ - M₃.  Processing time in hours is given below. Determine the optimal sequesnce and idle time for machine M₁ .

Jobs	A	B	C	D
M1	5	8	7	3
M2	6	7	2	5
M3	7	8	10	9

Answer 1

Given ,

Jobs	A	B	C	D
M1	5	8	7	3
M2	6	7	2	5
M3	7	8	10	9

Here Min. (M₁) = 3 , Min. (M₃) = 7 . Max.(M₂) = 7  Min. (M₃) ≥ Max.(M₂)

∴ The problem can be converted into

2 machine , 4 jobs problem.

Let G = M₁ + M₂ , H = M₂ + M₃

	A	B	C	D
G	11	15	9	8
H	13	15	12	14

Here Min . (G_i1 , H_i2 ) = 8

corresponding to machine G , job D.

∴ job D is processed first.

D

The problem now reduced to 2 machines , 3 job problem.

Now Min. (G_i1 , H_i2 ) = 9 ,  corresponding to machine G , job C

∴ job C is processed second.

D

C

Here Min . (G_i1 , H_i2 ) = 11 , corresponding to machine G , job A.

∴ job A is processed third.

D

C

A

The optimal sequence of jobs is obtained as follows : 

D

C

A

B

 

Job	`"M"_1`		`"M"_2`		`"M"_3`
	Time in	Time out	Time in	Time out	Time in	Time out
D	0	3	3	8	8	17
C	3	10	10	12	17	27
A	10	15	15	21	27	34
B	15	23	23	30	34	42

The minimum elapsed time = 42 hrs.
Ideal time for `M_1` = 42 – 23 = 19 hrs.