) 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
To find the optimum assignment of jobs to machines, we can use the Hungarian algorithm. The steps to solve this problem are as follows:
Step 1: Subtract the minimum value in each row from all the elements in that row.
A B C D E
1 1 0 3 0 5
2 0 2 1 4 6
3 2 1 0 0 4
4 2 1 0 3 0
Step 2: Subtract the minimum value in each column from all the elements in that column.
A B C D E
1 1 0 3 0 5
2 0 2 1 4 6
3 2 1 0 0 4
4 0 0 0 2 0
Step 3: Draw lines through the rows and columns such that all zeros are covered and the minimum number of lines are used.
A B C D E
1 1 x 3 x 5
2 x 2 1 4 6
3 2 1 x x 4
4 0 0 0 2 0
Step 4: Find the minimum value that is not covered by any line and subtract it from all the uncovered values. Add it to the values that are covered by two lines.
A B C D E
1 0 x 2 x 4
2 x 2 1 3 6
3 1 0 x x 3
4 0 0 0 1 0
Step 5: Repeat steps 3 and 4 until there are no more zeros that are not covered by any line.
A B C D E
1 0 x 1 x 3
2 x 2 1 2 5
3 1 0 x x 2
4 0 0 0 0 0
Step 6: Assign the jobs to machines based on the assigned zeros. For example, job 1 is assigned to machine A, job 2 is assigned to machine C, job 3 is assigned to machine B, and job 4 is assigned to machine D. No job is assigned to machine E.
Therefore, the optimum assignment of jobs to machines to minimize the total processing time is as follows:
Job 1 - Machine A
Job 2 - Machine C
Job 3 - Machine B
Job 4 - Machine D
The total processing time to complete the jobs is 1 + 1 + 1 + 0 = 3 hours.