Hungarian Method for Unbalanced Assignment Problem-examples

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

Unbalanced Assignment Problem Example 1

The coach of an age group swim team needs to assign swimmers to a 200-yard medley relay team to send to the Junior Olympics. Since most of his best swimmers are very fast in more than one stroke, it is not clear which swimmer should be assigned to each of the four strokes. The five fastest swimmers and the best time (in seconds) they have achieved in each of the strokes (for 50 yards) are

Stroke	Carl	Chris	David	Tony	Ken
Backstroke	37.7	32.9	33.8	37.0	35.4
Breaststroke	43.4	33.1	42.2	34.7	41.8
Butterfly	33.3	28.5	38.9	30.4	33.6
Freestyle	29.2	26.4	29.6	28.5	31.1

The coach wishes to determine how to assign four swimmers to the four different strokes to minimize the sum of the corresponding best times.

a. Fomulate this problem as an assignment problem.
b. Obtain an optimal solution.

Solution

In the given problem there are 4 type of strokes and 5 Swimmers. The problem can be formulated as $4\times 5$ assignment problem with $c_{ij}$ = time taken by the $j^{th}$ swimmer using $i^{th}$ type of stroke.

Let

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

The five fastest swimmers and the best time (in seconds) they have achieved in each of the strokes (for 50 yards) are

Stroke	Carl	Chris	David	Tony	Ken
Backstroke	37.7	32.9	33.8	37.0	35.4
Breaststroke	43.4	33.1	42.2	34.7	41.8
Butterfly	33.3	28.5	38.9	30.4	33.6
Freestyle	29.2	26.4	29.6	28.5	31.1

As the table is not a square matrix, add a dummy row with best times = 0.

Stroke	Carl	Chris	David	Tony	Ken
Backstroke	37.7	32.9	33.8	37.0	35.4
Breaststroke	43.4	33.1	42.2	34.7	41.8
Butterfly	33.3	28.5	38.9	30.4	33.6
Freestyle	29.2	26.4	29.6	28.5	31.1
Dummy	0	0	0	0	0

Step 1

In first row smallest is 32.9, second row is 33.1, third row is 28.5, fourth row is 26.4 and fifth row is 0.

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

Step 2

The minimum of each column of the modified matrix is 0.

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

Step 3

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

The minimum number of lines = 2, 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 0.9. Subtract 0.9 from all the uncovered elements and add 0.9 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

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

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

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

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

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.

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

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

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

Repeat the Step 6 successively we have

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

Backstroke $\to$ David

Breaststroke $\to$ Tony

Butterfly $\to$ Chris

Freestyle $\to$ Carl

Dummy $\to$ Ken

The optimal best time for each swimmer is as follows:

Stroke	Swimmer	Best Time (in sec)
Backstroke	David	33.8
Breaststroke	Tony	34.7
Butterfly	Chris	28.5
Freestyle	Carl	29.2
Dummy	Ken	0

Thus the optimal (minimum) total best time for five swimmers is

$\text{Minimum total Best time }= 33.8+34.7+28.5+29.2+0 =126.2$ seconds.

Endnote

In this tutorial, you learned about step by step procedure of Hungarian Algorithm to solve unbalanced assignment problem.

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 Unbalanced Assignment problems and your thought on this article.