Unbalanced Assignment Problem

Unbalanced Assignment Problem
In the previous section we assumed that the number of persons to be assigned equal to the number of jobs. Such kind of assignment problem is called as balanced assignment problem. If the number of person is different from the number of jobs then the assignment problem is called as unbalanced assignment problem.
If the number of jobs is less than the number of persons, some of them can’t be assigned any job, so that we have to introduce one or more dummy jobs of zero duration to convert the unbalanced assignment problem to the balanced assignment problem. This balanced assignment problem can be solved by using the Hungarian Method as discussed in the previous section. The persons to whom the dummy jobs are assigned are left out of assignment.
Similarly, if the number of persons is less than number of jobs then we have introduce one or more dummy persons with zero duration to modify the unbalanced into balanced and then the problem is solved by using the Hungarian Method. Here the jobs assigned to the dummy persons are left out.
Example: Solve the following unbalanced assignment problem of minimizing the total time for performing all the jobs.

Solution
In this problem, the number of jobs is less than the number of workers so we have to introduce a dummy job with zero duration.
The revised assignment problem is as follows:

Now the problem becomes balanced one since the number of workers is equal to the number jobs. So that the problem can be solved using Hungarian Method.
Step 1: The cost Table

Step 2: Find the (FRCT)

Step 3: Find the (SRCT)

Step 4: Determine an Assignment
By using the Hungarian method, the assignment is made as follows:



Step 5:
The solution obtained in Step 4 is not optimal. Because we were able to make five assignments when six were required.
Step 6:
Cover all the zeros of the table shown in the Step 4 with five lines (since already we made five assignments).
Check row E since it has no assignment. Note that row B has a zero in column 6, therefore check column 6. Then we check row C since it has a zero in column 6. Note that no other rows and columns are checked. Now we may draw five lines through unchecked rows (row A, B, D and F) and the checked column (column 6). This is shown in the table given below:

Step 7:
Develop the new revised table.
Examine those elements that are not covered by a line in the table given in Step 6. Take the smallest element, in this case the smallest element is 1. Subtract this smallest element from the uncovered cells and add 1 to elements (A6, B6, D6 and F6) that lie at the intersection of two lines.
Finally, we get the new revised cost table, which is shown below:


Step 8:
Now, we go to Step 4 and repeat the procedure until we arrive at an optimal solution (assignment).
Step 9: Determine an assignment