|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Assignment Problem |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Some
Special Cases
|
1. Unbalanced Assignment Problem
In the previous section, the number of persons and the number of jobs were assumed to be the same. In this section, we remove this assumption and consider a situation where the number of persons is not equal to the number of jobs. In all such cases, fictitious rows and/or columns are added in the matrix to make it a square matrix. Then, we apply the usual Hungarian Method to this resulting balanced assignment problem. We provide the following example to illustrate the solution of an unbalanced assignment problem.
Example
| Job | ||||
|---|---|---|---|---|
| Person | 1 | 2 | 3 | 4 |
| A | 20 | 25 | 22 | 28 |
| B | 15 | 18 | 23 | 17 |
| C | 19 | 17 | 21 | 24 |
Solution
Since the number of persons is less than the number of jobs, we introduce a dummy person (D) with zero values. The revised assignment problem is given below:
Table
| Job | ||||
|---|---|---|---|---|
| Person | 1 | 2 | 3 | 4 |
| A | 20 | 25 | 22 | 28 |
| B | 15 | 18 | 23 | 17 |
| C | 19 | 17 | 21 | 24 |
| D (dummy) | 0 | 0 | 0 | 0 |
Now use the Hungarian method to obtain the optimal solution yourself.
Ans. = 20 + 17 + 17 + 0 = 54.
