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.
First, subtract the minimum value in each row from all the elements in that row to create a matrix of reduced values:
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
Next, subtract the minimum value in each column from all the elements in that column to create a matrix of reduced values:
Machines
Jobs A B C D E
1 0 0 5 1 4
2 6 9 8 12 13
3 0 0 0 0 4
4 4 3 2 7 1
Now, we can start assigning jobs to machines. Start with the row that has the fewest zeros (in this case, row 3). Assign the job with the smallest value (1) to the machine with the smallest value (A). This results in the following assignment:
Machines
Jobs A B C D E
1 0 0 5 1 4
2 6 9 8 12 13
3 0 0 0 X 4
4 4 3 2 7 1
Next, cross out all the values in column D and row 3, as a job has been assigned to machine D:
Machines
Jobs A B C D E
1 0 0 5 X 4
2 6 9 8 X 13
3 X X X X X
4 4 3 2 X 1
Repeat this process with the remaining rows and columns. Assign job 2 to machine B, job 4 to machine E, and job 1 to machine C:
Machines
Jobs A B C D E
1 0 0 X X 4
2 6 X X X 13
3 X X X X X
4 4 3 X X X
Finally, assign job 3 to machine A:
Machines
Jobs A B C D E
1 X 0 X X 4
2 6 X X X 13
3 0 X X X X
4 4 3 X X X
Now, we can see that no job is assigned to machine C.
To find the total processing time, sum up the values in the assigned cells:
Total processing time = 0 + 0 + 4 + 6 + 13 + 0 + 4 + 3 = 30
Therefore, the optimum assignment of jobs to machines to minimize the total processing time is:
Job 1 to Machine D
Job 2 to Machine B
Job 3 to Machine A
Job 4 to Machine E
The total processing time to complete the jobs is 30 hours.