Question

A manufacturing shop processes sheet metal jobs, wherein each job must pass through two machines (M1 and M2, in that order). The processing time (in hours) for these jobs is:

Machine	Jobs
	P	Q	R	S	T	U
M1	15	32	8	27	11	16
M2	6	19	13	20	14	7

The optimal make-span (in hours) of the shop is:

1. 120
2. 115
3. 109
4. 79

Answer 1

Correct Answer - Option 2 : 115

According to Johnson’s algorithm sequencing of jobs is

R

T

S

Q

U

P

Now,

Job	M1		M2
	In	Out	In	Out
R	0	8	8	21
T	8	19	21	35
S	19	46	46	66
Q	46	78	78	97
U	78	94	97	104
P	94	109	109	115

From this the optimal make span of the shop is 115.