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 need to find the assignment that minimizes the total processing time.
We can solve this problem using the Hungarian algorithm, which is a combinatorial optimization algorithm that solves the assignment problem in polynomial time.
Step 1: Subtract the minimum value from each row of the matrix. This ensures that there is at least one zero in each row.
Machines
Jobs A B C D E
1 1 0 3 0 5
2 6 8 7 10 12
3 2 1 0 0 3
4 1 0 0 2 0
Step 2: Subtract the minimum value from each column of the matrix. This ensures that there is at least one zero in each column.
Machines
Jobs 0 1 2 3 4
1 1 0 3 0 5
2 6 8 7 10 12
3 2 1 0 0 3
4 1 0 0 2 0
Step 3: Draw lines through the rows and columns to cover all the zeros in the matrix while minimizing the number of lines. In this case, we can draw three lines as shown below:
Machines
Jobs 0 1 2 3 4
1 X 0 X 0 X
2 6 8 7 10 12
3 X 1 X X 3
4 X 0 X X 0
Step 4: Determine the minimum number of lines needed to cover all the zeros. In this case, it is three.
Step 5: Subtract the minimum uncovered value from all the uncovered values, and add it to all the values that are covered by two lines.
Machines
Jobs 0 1 2 3 4
1 X 1 X 0 X
2 6 8 7 10 12
3 X 2 X X 4
4 X 1 X X 0
Step 6: Repeat steps 3-5 until there are no zeros left uncovered.
Machines
Jobs 0 1 2 3 4
1 X 1 X 0 X
2 5 7 6 9 11
3 X 2 X X 4
4 X 1 X X 0
Step 7: Determine the assignments based on the final matrix.
Machines
Jobs 0 1 2 3 4
1 X 1 X 0 X
2 5 7 6 9 11
3 X 2 X X 4
4 X 1 X X 0
Based on the above matrix, the optimal assignment of jobs to machines is:
Job 1 -> Machine 1
Job 2 -> Machine 2
Job 3 -> Machine 4
Job 4 -> Machine 3
Therefore, no job is assigned to Machine 5.
The total processing time to complete the jobs is calculated by summing up the values in the assigned cells:
Total Processing Time = 1 + 7 + 6 + 4 = 18 hours.