USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Hungarian Algorithm

 

This is an efficient algorithm for solving the assignment problem developed by the Hungarian Mathematician Konig. Here the optimal assignment is not affected if a constant is added or subtracted from any row or column of the balanced assignment cost matrix. The algorithm can be started as follows :

 

(a)   Bring at least one zero to each row and column of the cost matrix by subtracting the minimum of the row and column respectively.

 

(b)   Cover all the zeros in cost matrix by minimum number of horizontal and vertical lines.

 

(c)   If number of lines = order of the matrix, then select the zeros as many as the order of the matrix in such a way that they cover all the rows and columns.

 

( Here An * n means nth order matrix)

 

(d)   If number of lines :;: order of the matrix, then perform the following and create a new matrix:

 

(i)              Select the minimum element from the uncovered elements of the cost matrix by the lines.

(ii)            Subtract the uncovered elements from the minimum element.

(iii)          Add the minimum element to the junction (i.e., crossing of the lines) elements.

(iv)          Other elements on the lines remain unaltered.

(v)            Go to Step (b).

 

Example 2. A construction company has four engineers for designing. The general manager is facing the problem of assigning four designing projects to these engineers. It is also found that Engineer 2 is not competent to design project 4. Given the time estimate required by each engineer to design a given project, find an assignment which minimizes the total time.

Solution. Let us first bring zeros row wise by subtracting the respective minima from all the row elements respectively.

Let us bring zero columns wise by subtracting the respective m1mma from all the column elements respectively. Here the above operations is to be performed only on first colunm, since at least one zero has appeared in the remaining columns.

 

(This completes Step-a)

Now (Step-b) all the zeros are to be covered by minimum number of horizontal and vertical lines which is shown below. It is also to be noted that this covering is not unique.

It is seen that no. of lines = 4 = order of the matrix. Therefore by Step-c, we can go for assignment i.e., we have to select 4 zeros such that they cover all the rows and columns which is shown below :

Therefore the optimal assignment is

E 1 -> Pl, E 2 -> 3, E3-> 2, E4 -> 4

 

and the minimum total time required = 6 + 4 + 3 + 2 = 15 units.

 

Example 3. Solve the following job machine assignment problem. Cost data are given below :

Solution. Let us first bring zeros first row wise and then column wise by subtracting the respective minima elements from each row and each column respectively and the cost matrix, thus obtained, is as follows :

By Step-b, all the zeros are covered by minimum number of horizontal and vertical lines which is shown below :

Here no. of lines ≠ order of the matrix. Hence we have to apply Step-d. The minimum uncovered element is 1. By applying Step-d we obtain the following matrix :

Now, by Step-b , we cover all the zeros by minimum number of horizontal and vertical straight lines.

Now the no. of lines = order of the matrix. So we can go for assignment by Step-c. The assignment is shown below :

The optimal assignment is A-> 4, B->3, C->5, D->2, E->4, F->6. An alternative assignment is also obtained as A->4. B->3, C->5 , D->2, E->1, F->6. For both the assignments, the minimum cost is 2 1 + 22 + 27 + 30 + 2 0 + 2 1 i.e., $ 141.