Answer to Question #109041 in Operations Research for Gnanamani CT

Question

Execute the Job Assignment Problem and prove the solution

Answer 1

The Hungarian method of assignment provides us with an efficient means of finding the optimal solution. The Hungarian method is based upon the following principles:

(i)     If a constant is added to every element of a row and/or column of the cost matrix of an assignment problem the resulting assignment problem has the same optimum solution as the original problem or vice versa.

(ii)   The solution having zero total cost is considered as optimum solution.        

Hungarian method of assignment problem (minimization case) can be summarized in the following steps:

Step I:  Subtract the minimum cost of each row of the cost (effectiveness) matrix from all the elements of the respective row so as to get first reduced matrix.

Step II:   Similarly subtract the minimum cost of each column of the cost matrix from all the elements of the respective column of the first reduced matrix. This is first modified matrix.

Step III:   Starting with row 1 of the first modified matrix, examine the rows one by one until a row containing exactly single zero elements is found. Make any assignment by making that zero in or enclose the zero inside a. Then cross (X) all other zeros in the column in which the assignment was made. This eliminates the possibility of making further assignments in that column.

Step IV: When the set of rows have been completely examined, an identical procedure is applied successively to columns that is examine columns one by one until a column containing exactly single zero element is found. Then make an experimental assignment in that position and cross other zeros in the row in which the assignment has been made.

Step V: Continue these successive operations on rows and columns until all zeros have been either assigned or crossed out and there is exactly one assignment in each row and in each column. In such case optimal assignment for the given problem is obtained.

Step VI: There may be some rows (or columns) without assignment i.e. the total number of marked zeros is less than the order of the matrix. In such case proceed to step VII.

Step VII: Draw the least possible number of horizontal and vertical lines to cover all zeros of the starting table. This can be done as follows:

1.      Mark (√) in the rows in which assignments has not been made.

2.      Mark column with (√) which have zeros in the marked rows.

3.      Mark rows with (√) which contains assignment in the marked column.

4.      Repeat 2 and 3 until the chain of marking is completed.

5.      Draw straight lines through marked columns.

6.      Draw straight lines through unmarked rows.

By this way we draw the minimum number of horizontal and vertical lines necessary to cover all zeros at least once. It should, however, be observed that in all n x n matrices less than n lines will cover the zeros only when there is no solution among them. Conversely, if the minimum number of lines is n, there is a solution.

Step VIII: In this step, we

1.    � Select the smallest element, say X, among all the not covered by any of the lines of the table; and

2.    Subtract this value X from all of the elements in the matrix not covered by lines and add X to all those elements that lie at the intersection of the horizontal and vertical lines, thus obtaining the second modified cost matrix.

Step IX: Repeat Steps IV, V and VI until we get the number of lines equal to the order of matrix I, till an optimum solution is attained.

Step X: We now have exactly one encircled zero in each row and each column of the cost matrix. The assignment schedule corresponding to these zeros is the optimum assignment. The above technique is explained by taking the following examples

(This is Excerpts from the printed work used R. Malhotra & D. K. Jain)