Question

For the following problem, find the sequence that minimizes total elapsed time (in hours) required to complete jobs on two machines M₁ and M₂ in the order M₁-M₂ Also find the minimum elapsed time T.

Jobs	A	B	C	D	E
Machine M1	5	1	9	3	10
Machine M2	2	6	7	8	4

Answer 1

 

Given :

Jobs	A	B	C	D	E
Machine M1	5	1	9	3	10
Machine M2	2	6	7	8	4

finding the optimal sequence :

The minimum processing time on two machines is 1 which correspond to task B on machine M₁. This shows that task B will be preceding first. After assigning task B, we are left with 4 tasks on two machines

 

Jobs	A	C	D	E
Machine M1	5	9	3	10
Machine M2	2	7	8	4

 

B

Minimum processing time in this reduced problem is 2 which correspond to job A on machine M₂ therefore task A will be processed in the last.

B

A

The problem now reduces to following 3 tasks on two machines with processing time as follows:

Jobs	C	D	E
Machine M1	9	3	10
Machine M2	7	8	4

Minimum processing time in this reduced problem is 3 which correspond to job D on machine M₁ therefore task D will be processed in the next to B.

B

D

A

The problem now reduces to following 2 tasks on two machines with processing time as follows:

Jobs	C	E
Machine M1	9	10
Machine M2	7	4

Minimum processing time in this reduced problem is 4 which correspond to job E on machine M₂ therefore task E will be processed in the next to last.

B

D

C

E

A

Further, it is also possible to calculate the minimum elapsed time corresponding to the optimal sequencing B→D→C→E→A

Job Sequence	Machine M1		Machine M2
	Time In	Time Out	Time In	Time Out
B	0	1	1	7
D	1	4	7	15
C	4	13	15	22
E	13	23	23	27
A	23	28	28	30

 

Hence the total elapsed time for this proposed sequence  staring from job B to completion of job A is 30 hours .During this time machine M₁ remains idle for 2 hours and the machine M₂ remains idle for 3 hours

Minimum time elapse : 30 Hours