Posted On :

The Hungarian Algorithm is applicable only for minimization models.

The Hungarian Algorithm is applicable only for minimization models. In case the problem is not in minimization form, convert the

1. Identify the largest number in the entire matrix / table.

2. Subtract all the entries from the highest number and write down the new reduced table.

Also, on occasion, the number of assignees to be assigned to perform tasks will not be equal; that is, the number of rows will not equal to the number of columns. This kind of assignment models are known as unbalanced assignment problems. To apply the Hungarian Algorithm, you have to convert the problem into a balanced assignment problem.

An Assignment problem is known as balanced one, if the number of rows equals to the number of columns. In case, if the given problem is unbalanced one, you have to add appropriate number of rows or columns with zero as assignment cost [dummy row or dummy column] and make the problem as balanced assignment model.

Then the Hungarian method is applied to this modified table, which is given in the following steps. If the given problem is a balanced model, you can skip this initiation process.

Subtract the smallest number in each row from every number in the row; this is known as row reduction. Enter the results in a new table.

Subtract the smallest number in each column of the new table obtained in Step-1 from every number in the respective column; this is known as column reduction. Enter the results in the new table.

Check whether an optimal set of assignments can be made. This is done in the following procedure;

1. Draw minimum number of straight lines to cover all the zeros in the table obtained after column reduction.

4. In the rest of columns / row, find a row or column that contains maximum number of zeros and draw the next line [in case a zero is already covered by a straight line, do not count while drawing the new line].

6. If the minimum of number of straight lines equal to number of rows, an optimal set of assignment is possible; otherwise, go to the Step-4.

If the number of straight lines is not equal to the number of rows, then do the following operations in the table, which is just now covered by straight lines.

1. Subtract the smallest uncovered number [not covered by any straight lines] from every uncovered number in the table.

If the number of straight lines is equal to the number of rows / columns, then it is an indication of optimum solution can be arrived by using the zero elements.

1. Make the assignments one at a time in positions that have zero elements.

This procedure will provide the complete set of assignments and an optimum solution for the problem.

Find the assignment of operator to appropriate job with lowest possible time to complete the jobs.

Since the given problem is a minimization model and balanced one, we apply the Hungarian algorithm straight away on the given table.

Subtract the minimum value
in each row from all other respective row values:

Subtract the minimum value
in each column from all other respective column values:

Check whether an optimal set of assignments can be made. Draw minimal number straight lines to cover all the zeros.

1. The maximum number of zeros is found in row-3 and column-5 [Three zeros each]; the first line is drawn arbitrarily at row-3

Since the number of straight lines is not equal to the number of rows, then we do the following operations in the table, which is just now covered by straight lines.

1. Subtract the smallest uncovered number [not covered by any straight lines] from every uncovered number in the table; in the above table, the smallest uncovered number is one.

The first line is drawn at Row-4, which is having 4 zeros; then the second line is drawn at Column-4, which is having 3 zeros; the third line is drawn at column-1, which is having 2 zeros; the next line is drawn at row-3 and the last line is drawn at column-5

We now proceed to make optimum allocation with available zero entries; in the new matrix, jot down all the zeros in their respective positions.

1. Search row wise for a unique zero; if one such zero is found mark it and strike the respective column [zeros]

The first unique zero is found in Row-2 and it is marked; then the column-1 is strike out; the next unique zero is found in row-5 and the same process is repeated. Third unique zero was found again in the row search at row-1; fourth unique zero was found at row-3 and finally the last unique zero was found in row-4.

Now this is an indication of optimum allocation has been made. The respective zero allocation positions are considered as optimum allocation for the given problem.

Tags : Operations Management - Transportation / Assignment & Inventory Management

Last 30 days 1092 views