Hungarian Method for Balanced Assignment Problem-example

Hungarian Method for Balanced Assignment Problem-example

In this article we will study the step by step procedure to solve balanced assignment problem using Hungarian method.

Balanced Assignment Problem Example

Five jobs are to assigned to five people, each person will do one job only. The expected times (in hour) required for each person to complete each job have been estimated and are shown in the following table.

Job \ Person P1 P2 P3 P4 P5
J1 12 15 13 14 15
J2 16 18 15 14 16
J3 18 16 15 18 20
J4 15 20 18 17 19
J5 16 15 18 14 15

Use the Hungarian method to determine the optimal assignments.

Solution

In the given problem there are 5 jobs and 5 Swimmers. The problem can be formulated as $5\times 5$ assignment problem with $c_{ij}$ = expected time (in hours) required for $j^{th}$ person to complete $i^{th}$ job

Let

$$ \begin{equation*} x_{ij}=\left\{ \begin{array}{ll} 1, & \hbox{if $j^{th}$ Job is assigned to $i^{th}$ Person;} \\ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$

The expected times (in hour) required for each person to complete each job have been estimated and are shown in the following table:

Job \ Person P1 P2 P3 P4 P5
J1 12 15 13 14 15
J2 16 18 15 14 16
J3 18 16 15 18 20
J4 15 20 18 17 19
J5 16 15 18 14 15

Step 1

In first row smallest is 12, second row is 14, third row is 15, fourth row is 15 and fifth row is 14.

Subtract the minimum of each row of the above cost matrix, from all the elements of respective rows. The modified matrix is as follows:

Assignment Problem
Assignment Problem

Step 2

In first column smallest is 0, second column is 1, third column is 0, fourth column is 0 and fifth column is 1.

Subtract the minimum of each column of the modified matrix, from all the elements of respective columns. The modified matrix is as follows:

Assignment Problem
Assignment Problem

Step 3

Draw the minimum number of horizontal and vertical line to cover all the zeros in the modified matrix.

Assignment Problem
Assignment Problem

The minimum number of lines = 4, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.

Step 4

The smallest element in the matrix, not covered by the lines is 1. Subtract 1 from all the uncovered elements and add 1 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

Assignment Problem
Assignment Problem

Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.

Assignment Problem
Assignment Problem

Step 5

The minimum number of lines = 5, which is equal to the order of assignment problem (i.e. 5). Hence the optimal assignment using Hungarian method is possible.

Step 6

Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.

Step 7

Repeating Step 6 successively we have

Assignment Problem
Assignment Problem

Step 8

From the above table it is clear that in each row and in each column exactly one marked $\square$ zero is obtained. The optimal assignment is

Person 1 $\to$ Job 4

Person 2 $\to$ Job 3

Person 3 $\to$ Job 1

Person 4 $\to$ Job 2

Person 5 $\to$ Job 5

The expected time for five persons to complete five jobs is as follows:

Person Job Expected Time (in Hours)
Person 1 Job 4 15
Person 2 Job 3 16
Person 3 Job 1 13
Person 4 Job 2 14
Person 5 Job 5 15

Thus the optimal (minimum) expected time for five persons to complete all the five jobs is

Minimum total expected time= 15+16+13+14+15 =73 hours.

Endnote

In this tutorial, you learned about step by step solution of balanced assignment problem using Hungarian Algorithm.

To learn more about Assignment problems please refer to the following tutorials:

Assignment Problems

Read step by step solution

Let me know in the comments if you have any questions on Hungarian Algorithm to solve Assignment problems and your thought on this article.

Leave a Comment