) There are four jobs to be assigned to five machines. Only one job can be assigned to one machine. The amount of time in hours required for the jobs per machine are given in the following matrix:
Machines
Jobs A B C D E
1 4 3 6 2 7
2 10 12 11 14 16
3 4 3 2 1 5
4 8 7 6 9 6
Find an optimum assignment of jobs to the machines to minimize the total processing time and also find out for which machine no job is assigned. What is the total processing time to complete the jobs?
To find the optimum assignment of jobs to machines, we can use the Hungarian Algorithm or the Munkres Algorithm. However, since the matrix provided is small, we can use a brute force approach to find the minimum total processing time.
We will create all possible assignments of jobs to machines and calculate the total processing time for each assignment. We will then select the assignment with the minimum total processing time.
Here are all possible assignments with their total processing times:
Assignment 1: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine C, Job 4 -> Machine D, Job 5 -> Machine E
Total Processing Time: 4 + 12 + 2 + 9 = 27
Assignment 2: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine C, Job 4 -> Machine E, Job 5 -> Machine D
Total Processing Time: 4 + 12 + 2 + 6 = 24
Assignment 3: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine D, Job 4 -> Machine C, Job 5 -> Machine E
Total Processing Time: 4 + 12 + 1 + 6 = 23
Assignment 4: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine D, Job 4 -> Machine E, Job 5 -> Machine C
Total Processing Time: 4 + 12 + 6 + 5 = 27
Assignment 5: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine E, Job 4 -> Machine C, Job 5 -> Machine D
Total Processing Time: 4 + 12 + 5 + 9 = 30
Assignment 6: Job 1 -> Machine A, Job 2 -> Machine B, Job 3 -> Machine E, Job 4 -> Machine D, Job 5 -> Machine C
Total Processing Time: 4 + 12 + 7 + 6 = 29
Assignment 7: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine B, Job 4 -> Machine D, Job 5 -> Machine E
Total Processing Time: 4 + 3 + 11 + 9 = 27
Assignment 8: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine B, Job 4 -> Machine E, Job 5 -> Machine D
Total Processing Time: 4 + 3 + 11 + 6 = 24
Assignment 9: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine D, Job 4 -> Machine B, Job 5 -> Machine E
Total Processing Time: 4 + 3 + 9 + 1 = 17
Assignment 10: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine D, Job 4 -> Machine E, Job 5 -> Machine B
Total Processing Time: 4 + 3 + 6 + 6 = 19
Assignment 11: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine E, Job 4 -> Machine B, Job 5 -> Machine D
Total Processing Time: 4 + 3 + 5 + 9 = 21
Assignment 12: Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine E, Job 4 -> Machine D, Job 5 -> Machine B
Total Processing Time: 4 + 3 + 7 + 6 = 20
Assignment 13: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine B, Job 4 -> Machine C, Job 5 -> Machine E
Total Processing Time: 4 + 2 + 7 + 1 = 14
Assignment 14: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine B, Job 4 -> Machine E, Job 5 -> Machine C
Total Processing Time: 4 + 2 + 7 + 5 = 18
Assignment 15: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine C, Job 4 -> Machine B, Job 5 -> Machine E
Total Processing Time: 4 + 2 + 6 + 1 = 13
Assignment 16: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine C, Job 4 -> Machine E, Job 5 -> Machine B
Total Processing Time: 4 + 2 + 6 + 6 = 18
Assignment 17: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine E, Job 4 -> Machine B, Job 5 -> Machine C
Total Processing Time: 4 + 2 + 6 + 5 = 17
Assignment 18: Job 1 -> Machine A, Job 2 -> Machine D, Job 3 -> Machine E, Job 4 -> Machine C, Job 5 -> Machine B
Total Processing Time: 4 + 2 + 9 + 1 = 16
Assignment 19: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine B, Job 4 -> Machine C, Job 5 -> Machine D
Total Processing Time: 4 + 7 + 7 + 9 = 27
Assignment 20: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine B, Job 4 -> Machine D, Job 5 -> Machine C
Total Processing Time: 4 + 7 + 7 + 6 = 24
Assignment 21: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine C, Job 4 -> Machine B, Job 5 -> Machine D
Total Processing Time: 4 + 7 + 6 + 1 = 18
Assignment 22: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine C, Job 4 -> Machine D, Job 5 -> Machine B
Total Processing Time: 4 + 7 + 6 + 6 = 23
Assignment 23: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine D, Job 4 -> Machine B, Job 5 -> Machine C
Total Processing Time: 4 + 7 + 5 + 9 = 25
Assignment 24: Job 1 -> Machine A, Job 2 -> Machine E, Job 3 -> Machine D, Job 4 -> Machine C, Job 5 -> Machine B
Total Processing Time: 4 + 7 + 9 + 1 = 21
From the above calculations, we can see that Assignment 9 (Job 1 -> Machine A, Job 2 -> Machine C, Job 3 -> Machine D, Job 4 -> Machine B, Job 5 -> Machine E) has the minimum total processing time of 17.
Therefore, the optimum assignment of jobs to machines to minimize the total processing time is:
- Job 1 -> Machine A
- Job 2 -> Machine C
- Job 3 -> Machine D
- Job 4 -> Machine B
- Job 5 -> Machine E
No job is assigned to Machine E.
The total processing time to complete the jobs is 17 hours.