Question

Solve the following job sequencing problem by giving an optimal sequence of jobs, and find the

total elapsed time also. Note that M1, M2, M3, M4, M5 and M6 are machines and A, B, C, D

are jobs.

Jobs → A B C D

M1 20 19 13 22

M2 10 8 7 6

M3 9 11 10 5

Machines M4 4 8 7 6

M5 12 10 9 10

M6 27 21 17 14

Answer 1

An optimal solution to this problem can be obtained, if either or both of the following conditions hold(s):

$min\ t_{1j}\ge max\ t_{ij}$

$min\ t_{mj}\ge max\ t_{ij}$

for i=2,3, ..., m-1

We have:

$min\ t_{1j}= t_{13}=13$

$max\ t_{ij}=\ t_{61}=27$

$min\ t_{1j}<max\ t_{ij}$

$min\ t_{mj}= t_{64}=14$

$min\ t_{mj}< max\ t_{ij}$

So, optimal solution to this problem cannot be obtained.