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 to minimize the total processing time, we can use the Hungarian Algorithm or the Matrix Reduction method.
First, let's apply the Matrix Reduction method:
Step 1: Subtract the minimum value of each row from all elements of that row.
Machines/Jobs A B C D E
1 1 0 3 -1 4
2 -2 0 -1 2 4
3 2 1 0 -1 3
4 2 1 0 -1 0
Step 2: Subtract the minimum value of each column from all elements of that column.
Machines/Jobs A B C D E
1 3 0 3 -3 4
2 -4 0 -1 1 0
3 0 1 0 0 2
4 0 1 0 0 -3
Step 3: Assign jobs to machines based on the zeros in the reduced matrix. Start with the row or column with the least number of zeros.
Assign job A to machine 3: (3, 1)
Assign job B to machine 2: (2, 2)
Assign job C to machine 1: (1, 3)
Assign job D to machine 3: (3, 4)
No zero left for job E, so it is unassigned.
The optimal assignment of jobs to machines is:
Job A assigned to Machine 3
Job B assigned to Machine 2
Job C assigned to Machine 1
Job D assigned to Machine 3
Job E is unassigned.
To find the total processing time, sum the values of the assigned jobs:
Processing time = 4 + 12 + 6 + 1 = 23 hours.