Question

There are 5 jobs, each of which is to be processed through three machines A,B and C, in order ABC. Processing time in hours are

Job	A	B	C
1	3	4	7
2	8	5	9
3	7	1	5
4	5	2	6
5	4	3	10

Optimal sequence of 5 jobs using Johnson algorithm is

• A. 1 5 4 3 2
• B. 4 1 5 2 3
• C. 3 2 1 4 5
• D. 1 2 3 5 4

Answer 1

The correct option is B 4 1 5 2 3

$\text{Minimum,}{A}_i=3,Max.B_i=5andmini.C_i=5$

$\text{Since min.}{C}_i\text{= Max.}{B}_i\text{,}$

$\text{we can solve problem by Johnson's algorithm.}$

Job	$G_i=A_i+B_i$	$H_i=B_i+C_i$
1	7	11
2	13	14
3	8	6
4	7	8
5	7	13

$\text{Required sequence: 4 1 5 2 3}$