Assignment Problem

Assignment Problem

The assignment problem is used to allocation a number of persons to a number of jobs so that the total time of completion is minimized.

We can clarify the assignment problem as follows:
Given n facilities, n jobs and the effectiveness of each facility to each job, here the problem is to assign each facility to one and only one job so that the measure of effectiveness if optimized. Here the optimization means Maximized or Minimized. There are many management problems has a assignment problem structure. For example, the head of the department may have 6 people available for assignment and 6 jobs to fill. Here the head may like to know which job should be assigned to which person so that all tasks can be accomplished in the shortest time possible. Another example, a container company may have an empty container in each of the location 1, 2, 3, 4, 5 and requires an empty container in each of the locations 6, 7, 8, 9, 10. It would like to ascertain the assignments of containers to various locations so as to minimize the total distance. The third example here is, a marketing set up by making an estimate of sales performance for different salesmen as well as for different cities one could assign a particular salesman to a particular city with a view to maximize the overall sales.
Note: with n facilities and n jobs there are n! possible assignments. The simplest way to find an optimum assignment is to write all the n! possible arrangements, evaluate their total cost and select the assignment with minimum cost. Bust this method leads to a calculation problem of formidable size even when the value of n is moderate. For n = 10 the possible number of arrangements is 3268800.

The assignment problem is said to be balanced if it has equal number of person and jobs to be assigned. If the number of persons (jobs) is different from the number of jobs (persons) then the problem is said to be unbalanced. An unbalanced assignment problem can be solved by converting into a balanced assignment problem. The conversion is done by introducing dummy person or a dummy job with zero cost. Because of the special structure of the assignment problem, it is solved by using a special method known as Hungarian Method.
Cost Table: The completion time or cost corresponding to every assignment is written down in a table form if referred as a cost table.
Hungarian Method: is a technique for solving the assignment problems.
Assignment Problem: is a special kind of linear programming problem where the objective is to minimize the assignment cost or time.
Balanced Assignment Problem: is an assignment problem where the number of persons equal to the number of jobs.
Unbalanced Assignment Problem: is an assignment problem where the number of jobs is not equal to the number of persons.
Infeasible Assignment Problem: is an assignment problem where a particular person is unable to perform a particular job or certain job cannot be done by certain machines.


Assignment Problem Structure and Solution:
The structure of the Assignment problem is similar to a transportation problem, it is as follows:

The element cij represents the measure of effectiveness when ith person is assigned jth job. Assume that the overall measure of effectiveness is to be minimized. The element xij represents the number of ith assigned persons to the jth job. Since ith person can be assigned only one job and jth job can be assigned to only one person. Th objective function is formulated as
Minimize c11x11 + c12x12 + ……….. + cnnxnn
xij ? 0
The assignment problem is actually a special case of the transportation problem where m = n and ai = bj = 1. However, it may be easily noted that any basic feasible solution of an assignment problem contains (2n – 1) variables of which (n – 1) variables are zero. Because of this high degree of degeneracy the usual computation techniques of a transportation problem become very inefficient. So, a separate computation technique is necessary for the assignment problem.
The solution of the assignment problem is based on the following results:
“If a constant is added to every element of a row/column of the cost matrix of an assignment problem, the resulting assignment problem has the same optimum solution as the original assignment problem and vice versa”. This result may be used in two different methods to solve the assignment problem. If in an assignment problem some cost elements cij are negative, we may have to convert them into an equivalent assignment problem where all the cost elements are non-negative by adding a suitable large constant to the cost elements of the row or column, and then we look for a feasible solution which has zero assignment cost after adding suitable constants to the cost elements of the various rows and columns. Since it has been assumed that all the cost elements are non-negative, this assignment must be optimum. On the basis of this principle a computational technique known as Hungarian Method is developed. The Hungarian Method is discussed as follows:
Hungarian Method:
The Hungarian method is discussed in the form of a series of computational steps as follows, when the objective function is that of minimization type.
Step 1:
From the given problem, find out the cost table. Note that if the number of origins is not equal to the number of destinations then a dummy origin or destination must be added.
Step 2:
In each row of the table find out the smallest cost element, subtract this smallest cost element from each element in that row. So, that there will be at least one zero in each row of the new table. This new table is known as First Reduced Cost Table (FRCT).
Step 3:
In each column of the table find out the smallest cost element, subtract this smallest cost element from each element in that column. As a result of this, each row and column has at least one zero element. This new table is known as Second Reduced Cost Table (SRCT).
Step 4:
Now determine an assignment as follows:
1. For each row or column with a single zero element cell that has not be assigned or eliminated, box that zero element as an assigned cell.
2. For every zero that becomes assigned, cross out all other zeros in the same row and for column.
3. If for a row and for a column there are two or more zero and one can’t be chosen by inspection, choose the assigned zero cell arbitrarily.
4. The above procedures may be repeated until every zero element cell is either assigned (boxed) or crossed out.
Step 5:
An optimum assignment is found, if the number of assigned cells is equal to the number of rows (and columns). In case we had chosen a zero cell arbitrarily, there may be an alternate optimum. If no optimum solution is found, i.e. some rows or columns without an assignment then go to Step 6.
Step 6:
Draw a set of lines equal to the number of assignments which has been made in Step 4, covering all the zeros in the following manner:
1. Mark check (?) to those rows where no assignment has been made.
2. Examine the checked (?) rows. If any zero element cell occurs in those rows, check (?) the respective columns that contains those zeros.
3. Examine the checked (?) columns. If any assigned zero element occurs in those columns, check (?) the respective rows that contain those assigned zeros.
4. The process may be repeated until now more rows or column can be checked.
5. Draw lines through all unchecked rows and through all checked columns.
Step 7:
Examine those elements that are not covered by a line. Choose the smallest of these elements and subtract this smallest from all the elements that do not have a line through them. Add this smallest element to every element that lies at the intersection of two lines. Then the resulting matrix is a new revised cost table.