Question
For the following problem, find the sequence that minimizes total elapsed time (in hours) required to complete jobs on two machines M_{1} and M_{2} in the order M_{1}M_{2} Also find the minimum elapsed time T.
Jobs 
A 
B 
C 
D 
E 
Machine M_{1} 
5 
1 
9 
3 
10 
Machine M_{2} 
2 
6 
7 
8 
4 
Solution
Given :
Jobs 
A 
B 
C 
D 
E 
Machine M_{1} 
5 
1 
9 
3 
10 
Machine M_{2} 
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_{1}. 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 M_{1} 
5 
9 
3 
10 
Machine M_{2} 
2 
7 
8 
4 
B 
Minimum processing time in this reduced problem is 2 which correspond to job A on machine M_{2} 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 M_{1} 
9 
3 
10 
Machine M_{2} 
7 
8 
4 
Minimum processing time in this reduced problem is 3 which correspond to job D on machine M_{1} 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 M_{1} 
9 
10 
Machine M_{2} 
7 
4 
Minimum processing time in this reduced problem is 4 which correspond to job E on machine M_{2 }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 M_{1} 
Machine M_{2} 

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_{1} remains idle for 2 hours and the machine M_{2} remains idle for 3 hours
Minimum time elapse : 30 Hours