Answer to Question #168325 in Operations Research for Ra

Question

To find the sequence of jobs that maximises the total elapsed time required to complete the following task on two machines -

Task A B C D E F G

1 2 5 4 9 8 5 4

2 6 8 7 4 9 8 11

Also to find the optimal elapsed time.

Answer 1

The solution of the problem is also known as Johnsons procedure.

The minimum processing time on two machines is 2 which correspond to task A on machine 1. This shows that task A will be preceding first. After assigning task A, we are left with 6 tasks on two machines. Minimum processing time in this reduced problem is 4 which correspond to jobs C and G (both on machine 1) and job D on machine 2. Therefore, the task C which has less processing time on 2 machine will be processed first (2^th place) and then task G (3^th) , and task D will be placed at the last (7^th sequence cell). Here since the minimum processing time is 5 which occurs for tasks B and F on machine 1. Because of the fact that both times on B and E are the same, it's not important which job should be first. Both variants are valid. Hence B and E take 4^th and 5^th places. And the last job E take 6^th place.

Finally, we have two optimal sequences of jobs: ACGBFED and ACGFBED.

Look at the table below corresponding to ACGBFED:

The total elapsed time for this proposed sequence staring from job A to completion of job D is 55 hours.