Assignment Model

 Definition  

Given n facilities and n jobs and given the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job so as to optimize the given measure of effectiveness. Assignments are generally made on a one-to-one basis. Each resource or facility is to be associated with one and only job and associations ought to be made in such a way as to maximize or minimize the total effectiveness 

Mathematical representation of the assignment model 

Mathematically the assignment model can be expressed as follows.

Let xij  denote the assignment of facility i to job j such that 

Comparison to the Transportation problem

In a transportation model, sources and destinations are present; in an assignment model, there are facilities, and jobs which must be assigned to those facilities. Unlike a transportation model, in an assignment model, the number of facilities (sources) is equal to the number of jobs (destinations). 

The Hungarian method for solving assignment problems

The Hungarian method suggested by Mr Koning of Hungary is used for solving assignment problems.

This method is also called as Reduced matrix method or the Flood's technique.

The method consists of the following steps 

Step 1: Prepare a square matrix  

Check whether the given matrix Is a square matrix. ie) the number of rows = the number of columns. If not insert a dummy row or a dummy column to make it a square matrix. 

Step 2: Reduce the matrix 

Subtract the smallest element of each row from all the elements of the row.  

Examine if there is at least one zero in each column. If not subtract the minimum element of the column not containing a zero from all the elements of that column. 

Step 3: Check whether an optimal assignment can be made in the reduced matrix 

1. Search for a row with exactly 1 unmarked zero. Make an assignment to the single zero by putting a square (☐) around it and cross (X) all the other zeros in the same column. Repeat this until all rows are examined. 

2. Search for a column with exactly 1 unmarked 0. Make an assignment thereby putting a square (☐) around it and cross (X) other zeros in the same row. 

3. In case, if there is no row or column containing a single unmarked zero, mark a zero arbitrarily and cross (X) all other zeros in the rows and columns. Repeat this until there is no unmarked 0 left in the cost matrix. 

Step 4: Find the minimum number of lines crossing all zeros  

This consists of the following sub-steps. 

a) Mark ((✓) the rows that do not have assignments. 

b) Mark (✓) the columns (not already marked) that have zeros in marked rows. 

c) Mark ((✓) the rows (not already marked) that have assignments in marked columns. 

d) Repeat sub-steps b & c till no more rows or columns can be marked. 

e) Draw straight lines through unmarked rows and marked columns. 

This gives the minimum number of lines crossing all zeros. If this number is equal to the order of the                matrix, then it is an optimal solution. 

Otherwise, go to Step 5  

Step 5: Iterate towards the optimal solution  

Select the smallest unmarked element and subtract it from all the unmarked elements in the matrix.                Add this smallest element to every element that lies at the intersection of two lines. 

This gives a new cost matrix. 

 

Step 6: Finding the optimal solution. 

Repeat steps 3 through 5 until the number of lines crossing all zeros becomes equal to the order of the

               matrix. The total cost for the solution is obtained by adding the original cast in the assigned cells.

Variations of the assignment problem 

1 Non-square matrix  

If the given assignment problem is not a square matrix, then insert a dummy row or a dummy column to make it a square matrix. 

2 Maximization problem  

If the given problem is of maximization type, change it to minimization before using the Hungarian method. The maximization problem is converted to minimization by subtracting all the elements in the matrix from the largest element of the matrix. 

3 Restrictions on assignments  

Sometimes the assignment problem contains a - in a cell. That is, allocation cost may not be given because no allocation is allowed in that cell. Such problems can be solved by assigning a very heavy cost that is, Infinity (∝) 

4 Alternate optimal solution 

Sometimes it is possible to have two or more ways to strike off all zero elements in the reduced matrix. In such cases, there will be an alternate optimal solution with the same cost.