USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Unbalanced Assignments

For unbalanced or non-standard assignment problem no. of rows ≠ no. of columns in the assignment cost matrix i.e., we deal with a rectangular cost matrix. To find an assignment for this

type of problem, we have to first convert this unbalanced problem into a balanced problem by adding dummy rows or columns with zero costs so that the defective function will be unaltered. For machine-job problem, if no. of machines (say, m) > no. of jobs (say, n), then create m-n dummy jobs and the processing cost of dummy jobs as zero. When a dummy job gets assigned to a machine, that machine stays idle. Similarly the other case i.e., n > m, is handled.


Example 4. Find an optimal solution to an assignment problem with the following cost matrix :

Solution. The above problem is unbalanced. We have to create a dummy machine M6 with zero processing time to make the problem as balanced assignment problem. Therefore we obtain the following :

Let us bring zeros column wise by subtracting the respective m1mma elements from each column respectively and the cost matrix, thus obtained, is as follows :

Let us cover all the zeros by minimum number of horizontal and vertical lines and is given below :

Now the number of lines ≠order of the matrix. The minimum uncovered element by the lines is 1. Using Step-d of the Hungarian algorithm and covering all the zeros by minimum no. of lines we obtain as follows :

Now the number of lines = order of the matrix and we have to select 6 zeros such that they cover all the rows and columns. This is done in the following :

Therefore, the optimal assignment is

J l->M2, J2->M6, J3->M 1, J4->M3, J5->M5, 16->M4 and the minimum cost= $ (5 + 0

+ 6 -r 15 + 6 + 5) = $ 37.


In the above, the job J2 will not get processed since the machine M6 is dummy.