SEQUENCING JOBS THROUGH TWO MACHINES
The sequencing algorithm for this case was developed by Johnson and is called Johnson’s Algorithm. In this situation n jobs must be processed through machines M_{1} and M_{2}. The processing time of all the n jobs or M_{1} and M_{2} is known and it is required to find the sequence, which minimizes the time to complete all the jobs.
Johnson’s algorithm is based on the following assumptions:
(i) There are only two machines and the processing of all the jobs is done on both the machines in the i.e. first on M_{1} and then on M_{2}.
(ii) All jobs arrive at the same time (static arrival pattern) have no priority for job completion.
Johnson’s Algorithm involves following steps :
 1. List operation time for each job on machine M_{1} and M_{2}.
 2. Select the shortest operation or processing time in the above list.
 3. If minimum processing time is on M_{1}, place the corresponding job first in the sequence. If it is on M_{2}, place the corresponding job last in the sequence. In case of tie in shortest processing time, it can be broken arbitrarily.
 4. Eliminate the jobs which have already been sequenced as result of step 3.
 5. Repeat step 2 and 3 until all the jobs are sequenced.
Example 7.3 Six jobs are to be sequenced which require processing on two machines M_{1} and M_{2}. The processing time in minutes for each of the six jobs on machines M_{1} and M_{2} is given below. All the jobs have to be processed in sequence M_{1}, M_{2}. Determine the optimum sequence for processing the jobs so that total time of all the jobs is minimum. Use Johnson’s Algorithm.
Jobs 
1 
2 
3 
4 
5 
6 

Processing Time  Machine M_{1} 
30 
30 
60 
20 
35 
45 
Machine M_{2} 
45 
15 
40 
25 
30 
70 
Sol. Step I. Operation time or processing time for each jobs on M \ and M2 is provided in the question.
Step II. The shortest processing time is 15 for job 2 on M_{2}.
Step III. As the minimum processing time is on M_{2}, job 2 has to be kept last as follows.
2 
Step IV. We ignore job 2 and find out the shortest processing time of rest of jobs. Now the least processing time is 20 minutes on machine M_{1} for job 4. Since it on M_{1}, it is to be placed first as follows.
4 
2 
The next minimum processing time is 30 minutes for job 5 on M_{2} and Job 1 on M_{1}. So job 5 will be placed at the end. Job 1 will be sequenced earlier 8S shown below.
4 
1 
5 
2 
The next minimum processing time is 40 minutes for Job 3 on M_{2}, hence it is sequenced as follows.
4 
1 
3 
5 
2 
Job 6 has to be sequenced in the gap or vacant space. The complete sequencing of the jobs is as follows.
4 
1 
6 
3 
5 
2 
The minimum time for six jobs on machine M_{1} and M_{2} can be shown with the help of a Gantt chart as shown below.
The above figure shows idle time for M_{1} (30 minutes) after the last job (2) has been processed. Idle time for M_{2} is 20 minutes before job 4 is started and 5 minutes before processing 6 and finishing job 1. The percentage utilization of M_{1} = 250 – 30/250 = 88% M_{2} = 250 – 25/250 = 90%.
Example 7.4. A bookbinder has one printing press, one binding machine and manuscript of seven different books. The time required for performing printing and binding operations for different books are shown below:
Book 
Printing Time (days) 
Binding Time (days) 
1 
20 
25 
2 
90 
60 
3 
80 
75 
4 
20 
30 
5 
120 
90 
6 
15 
35 
7 
65 
50 
Decide the optimum sequence of processing of books in order to minimize total time.
Sol. Step I. Minimum time is 15 days on printing press (M_{1}) for job 6 so it will be sequenced earlier as shown.
6 
Step II. Now book I and 4 have the least time of 20 days on printing press (M_{1}) so these two books will be sequenced as
6 
1 
4 
Step III. After eliminating jobs 6, 1 and 4, the least time is for job 7 on binding machine (M_{2}) so it will be placed last in the sequence.
6 
1 
4 
7 
Step IV. Now book 2 has least time of 60 on M_{2}. Hence it will be placed at the end.
6 
1 
4 
7 
Step V. Book 3 has the least time of 75 days on M_{2} so it will be placed as below.
6 
1 
4 
3 
2 
7 
Step VI. Job 5 will be placed in the vacant place.
6 
1 
4 
5 
3 
2 
7 
Step VII. Total processing time can be calculated as follows.
Optimum sequence of jobs (books) 
Printing 
Binding 
Idle time for Binding 

In 
Out 
In 
Out 

6 
0 
15 
15 
50 
15 
1 
15 
35 
50 
75 
– 
4 
35 
55 
75 
105 
– 
5 
55 
175 
175 
265 
70 
3 
175 
255 
265 
340 
– 
2 
255 
345 
345 
405 
5 
7 
345 
410 
410 
460 
5 
Total idle time
Printing = (460 – 410) = 50 days as the printing last job (7) is finished on 410 days but binding finishes only after 460 days, so printing machine is idle for 50 days.
Binding = 15 + 70 + 5 + 5 = 95 days
Example 7.5. A manufacturing company has 5 different jobs on two machines M_{1} and M_{2}. The processing time for each of the jobs on M_{1} and M_{2} is given below. Decide the optimal sequence of processing of the jobs in order to minimize total time.
Job No. 
Processing Time 

M_{1} 
M_{2} 

1 
8 
6 
2 
12 
7 
3 
5 
11 
4 
3 
9 
5 
6 
14 
Sol. The shortest processing time is 3 on M_{1} for job 4 so it will be sequenced as follows.
4 
Next is job 3 with time 5 and M_{1}, hence job 3 will be sequenced as
4 
3 
Next minimum time is for jobs Ion M_{2} this will be sequenced last
4 
3 
1 
After eliminating jobs 4, 3 and 1, the next with minimum time is job 5 on M_{1} so it will be placed as
4 
3 
5 
1 
Now job 2 will be sequenced in the vacant space,
4 
3 
5 
2 
1 
Recent Comments