Answer to Question #258502 in Operations Research for Manjeet

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

The processing times (in hours) are given below:

min t$_{1j}$=13, min t$_{6j}$ =14, max of t$_{2j},_{3j},_{4j},_{5j}=$10, 11,8,12

Since the conditions min t$_{6j}$≥max t$_{ij}$ for $i$ = 2, 3, 4 is satisfied, we introduce two

fictitious machines G and H whose processing times are given below:

1. The smallest processing time is 41 hour for job D on Machine H. So job D will be processed last.

2. The next smallest processing time is 46 hour for job C on Machine G. So job C will be processed first.

3. The next smallest processing time is 55 hour for job A on Machine G. So job A will be processed after job C.

4. The next smallest processing time is 56 hour for job B on Machine G. So job B will be processed after job A.

The following optimal sequence is obtained ; C A B D

The total elapsed time is obtained from the table below:

This table shows that the minimum total elapsed time is 130 hours.