NJOBS 3 MACHINE CASE
Johnson’s algorithm’ which we have just applied can be extended and made use of n jobs 3 machine case, if the following conditions hold good:
a) Maximum processing, time for a job on machine M_{1} is greater than or equal to processing time for the same job.
or
b) Minimum processing time for a job on machine M_{3} is greater than or equal to maximum processing time for a job on machine M_{2}.
The following assumptions are made :
a) Every job is processed on all the three machines M_{1}, M_{2} and M_{3} first processed on M_{1} then on M_{2} and then on M_{3}.
b) The passing of jobs is not permitted.
c) Processing time for each job on the machine M_{1}, M_{2} and M_{3} are known.
In this procedure two dummy machines M_{1}’ and M_{3}’ are assumed in such a manner that the processing time of jobs on these machines can be calculated as
Processing time of jobs on M_{1}‘ = Processing time (M_{1} + M_{2})
Processing time of a job on M_{2}‘ = Processing time (M_{2} + M_{1})
After this Johnson’s algorithm is applied on M_{1}‘ and M_{2}’ to find out the optimal sequencing of jobs.
Example 7.6. In a manufacturing process three operations have to be performed on machines M_{1}, M_{2 }and M_{3} in order M_{1}, M_{2} and M_{3}. Find outthe optimum sequencing when the processing time for four jobs on three machines is as follows:
Sol. Step I. As the minimum processing time for job 2 on M_{1} > maximum processing time for job 2 on M_{2}, Johnson’s algorithm can be applied to this problem.
Step II. Let us combine the processing time of M_{1} & M_{2} and M_{3} to form two dummy machines M_{1}’ and M_{2}’. This is shown in the matrix below.
Job 
M_{1}’ 
M_{2}’ 
1 
11 (3+8) 
21 (8+13) 
2 
18 (12+6) 
20 (6+4) 
3 
9 (5+4) 
13 (4+9) 
4 
8 (2+6) 
18 (6+12) 
Step III. Apply Johnson’s algorithm. Minimum time of 8 occurs for job 4 on M’_{1} hence it is sequenced first.
4 
3 
1 
The next minimum time is for job 3 on M’_{1} so it is sequenced next to job 4. Next is job 1 and so on. So the optimal sequencing is
4 
3 
1 
2 
Example 7.7. Six jobs have to be processed on machines M_{1}, M_{2} and M_{3} in order M_{1}, M_{2} and M_{3}. Time taken by each job on these machines is given below, Determine the sequence so as to minimize the processing time.
Job 
M_{1} 
M_{2} 
M_{3} 
1 
12 
7 
3 
2 
8 
10 
4 
3 
7 
9 
2 
4 
11 
6 
5 
5 
10 
10 
3 
6 
5 
5 
4 
Sol. Step 1. As the minimum processing time for jobs 1 and 4 on M_{1} is greater than on M_{2}, Johnson’s algorithm can be applied.
Step II. Combine the processing time of M_{1} and M_{2} and M_{3} and develop new matrix for machine M_{1}‘ and M_{2}‘ as follows.
Job 
M’_{1} 
M’_{2} 
1 
19 (12+7) 
10 (7+3) 
2 
18 (8+10) 
14 (10+4) 
3 
16 (7+9) 
11 (9+2) 
4 
17 (11+6) 
11 (6+5) 
5 
20 (10+10) 
13 (10+3) 
6 
10 (5+5) 
9 (5+4) 
Step III. Use Johnson’s algorithm and sequence the jobs Minimum processing time of 9 occurs for job 6 on M’_{1} so it will be sequenced the last.
6 
Next minimum processing time of 10 occurs for job 1 on M_{2} so job 1 will be sequenced next to job 6.
1 
6 
Next minimum processing time is 11 for jobs 3 and 4 on machine M’_{2} so these will be sequenced as shown.
3 
4 
1 
6 
Next minimum is 13 for jobs 5 on machine M_{2} and after that job 2 has minimum processing time of 14 on M_{2}‘, hence the sequencing is as follows.
2 
5 
3 
4 
1 
6 
‘n’ Jobs ‘m’ Machine Case
Let there be ‘n’ jobs 1,2,3, …. n and ‘m’ machine M_{1} ,M_{2}, M_{3 }…. m. The order of processing is M_{1}, M_{2}, M_{3} …. m and no passing is permitted. The processing time for the machine is shown below:
Job 
M_{1} 
M_{2} 
M_{3} 
m 
1 
a_{1} 
b_{1} 
c_{1} 
M_{1} 
2 
a_{2} 
b_{2} 
c_{2} 
M_{2} 
3 
a_{3} 
b_{3} 
c_{3} 
M_{3} 
: : 
: : 
: : 
: : 
: : 
n 
a_{n} 
b_{n} 
c_{n} 
M_{n} 
If the following conditions are used, we can replace ‘m’ machines by an equivalent of two machines problem.
(a) Min a_{i} ≥ max of M_{2}, M_{3} …. (m – 1)
(b) Min m ≥ max M_{2}, M_{3} …. (m – 1)
when M_{1}‘=a+b_{i}+c_{i}+…. +(m1)_{ i}
M_{2}‘ = b_{i} + c_{i} +…. + (m – 1)_{ i} + m_{i}
Example 7.8. Determine the optimal sequence of performing 5 jobs on 4 machines. The machines used in the order M_{1}, M_{2}, M_{3} and M_{4} and the processing time is given below
Job 
M_{1} 
M_{2} 
M_{3} 
M_{4} 
1 
8 
3 
4 
7 
2 
9 
2 
6 
5 
3 
10 
6 
6 
8 
4 
12 
4 
1 
9 
5 
7 
5 
2 
3 
Sol. Step 1. Let us find out if any of the conditions stipulated is satisfied or not.
Condition 1. Min a_{i} ≥ max of M_{2} and M_{3}.
Min a_{i} >7
Max b_{i }> 6
Max c_{i}=6
Hence the condition is satisfied.
Step II. Let us form the matrix of new processing time by creating two fictitious machine M_{1}’ and M_{2}’.
Job 
M_{1}’=a_{i}+b_{i}+c_{i} 
M_{2}’=b_{i}+c_{i}+d_{i} 
1 
15 (8+3+4) 
14 (3+4+7) 
2 
17 (9+2+6) 
13 (2+6+5) 
3 
22 (10+6+6) 
20 (6+6+8) 
4 
17 (12+4+1) 
14 (4+1+9) 
5 
14 (7+5+2) 
10 (5+2+3) 
Step III. Now solve 5 jobs 2 machine problem.
Minimum time of processing is for job 5 on machine M_{2}‘ so it will be sequenced last.
5 
Next minimum time is 13 for jobs 2 on machine M’_{2} so it will be sequenced as shown.
2 
5 
Next minimum time is for jobs 1 and 4 on machine M’_{2} so it will be sequenced as shown.
1 
4 
2 
5 
Next minimum time is 20 for job 3 on machine M_{2}‘.
3 
1 
4 
2 
5 
Example 7.9. Solve the following sequencing problem when passing off is not allowed.

A 
B 
C 
D 
I 
15 
5 
4 
15 
II 
12 
2 
10 
12 
III 
16 
3 
5 
16 
IV 
17 
3 
4 
17 
Sol. Let us find out if one of the two conditions is satisfied.
Step 1. min a_{i} ≥ max b_{i} and c_{i}
or min d_{i} ≥ max b_{i} and c_{i}
Here both the conditions are satisfied.
Step II. The problem can be converted into 4 jobs 2 machines problem by introducing two fictitious machines M_{1}‘ and M_{2}‘ as follows.
Job 
M_{1}’ 
M_{2}’ 
I 
24 (15+5+4) 
24 (5+4+15) 
II 
24 (12+2+10) 
24 (2+10+12) 
III 
24 (16+3+5) 
24(3+5+16) 
IV 
24 (17+3+4) 
24 (3+4+17) 
Where M_{1}’=a_{i}+b_{i}+c_{i}
M_{2}’=b_{i}+c_{i}+d_{i}
Since all the processing times are equal, the jobs can be sequenced in any manner and all sequences are optimal and will give the same minimum time.
Total time can be worked out from the table below.
Job 
Machine A 
Machine B 
Machine C 
Machine D 

In 
Out 
In 
Out 
In 
Out 
In 
Out 

I 
0 
15 
15 
20 
20 
24 
24 
39 
II 
15 
27 
27 
29 
29 
39 
39 
51 
III 
27 
43 
43 
46 
46 
51 
51 
67 
IV 
43 
60 
60 
63 
63 
67 
67 
84 
Total time = 84 hours
Idle time Machine A = 84 – 60 = 24 hours
Machine B = 15 + 7 + 14 + 14 + (84 _ 63)
=1 5 + 7 + 14 + 14 + 21 = 71 hours
Machine C = 20 + 5 + 7 + 12 + (84 – 67) = 61 hours
Machine D = 24 hours
Example 7.10 Four Jobs 1.2.3 and 4 are to be processed on each of the five machines M_{1}, M_{2}, M_{3}, M_{4} and M_{5} in the order M_{1}, M_{2}, M_{3}, M_{4}, M_{5}. Determine total minimum elapsed time if no passing off is allowed. Also find out the idle time of each of the machines. Processing time are given in the matrix below.
Job 
Machine 

M_{1} 
M_{2} 
M_{3} 
M_{4} 
M_{5} 

1 
8 
4 
6 
3 
9 
2 
7 
6 
4 
5 
10 
3 
6 
5 
3 
2 
8 
4 
9 
2 
1 
4 
6 
Sol. Step I. Find out if the condition minimum e_{i} ≥ max b_{i}, c_{i} and d_{i} is satisfied.
Job 
Machine 

M_{1} 
M_{2} 
M_{3} 
M_{4} 
M_{5} 

1 
8 
4 
6 
3 
9 
2 
7 
6 
4 
5 
10 
3 
6 
5 
3 
2 
8 
4 
9 
2 
1 
4 
6 

Min 6 
Max 6 
Max 6 
Max 5 
Min 6 
This condition is satisfied hence we can convert the problem into four jobs and two ficticious machines M_{1}’ and M_{2}’.
Step II.
Job 
M_{1}’ 
M_{2}’ 
1 
21 (8+4+6+3) 
22 (4+6+3+9) 
2 
22 (7+6+4+5) 
25 (6+4+5+10) 
3 
16 (6+5+3+2) 
18 (5+3+2+8) 
4 
16 (9+2+1+4) 
13 (2+1+4+6) 
Step III. The optimal sequence can be determined as minimum of processing time of 13 occurs on M_{2}‘ for job 4 it will be processed last. Next minimum time is for job 3, on machine M_{1}‘ so it will be processed earliest. Next shortest time is for machine 1 on M_{1}’ so it will be sequenced next to job 3 and so on.
3 
1 
2 
4 
Step IV. Total time can be calculated with the help of the matrix shown below.
Job 
M_{1} 
M_{2} 
M_{3} 
M_{4} 
M_{5} 

In 
Out 
In 
Out 
In 
Out 
In 
Out 
In 
Out 

1 
0 
8 
8 
12 
12 
18 
18 
21 
21 
30 
2 
8 
15 
15 
21 
21 
25 
25 
30 
30 
40 
3 
15 
21 
21 
26 
26 
29 
29 
32 
40 
48 
4 
21 
30 
30 
32 
30 
31 
32 
36 
48 
54 
Hence total minimum elapsed time is 51
Idle time for machines M_{1} = 24 hours
M_{2} = 3 + 4 + 22 = 29
M_{3} = 3 + 1 + 1 + 23 = 28
M_{4} =4 + 18 = 22
Recent Comments