Assignment Problem
The assignment problem is a special case of transportation problem.
Suppose there are $n$ jobs to be performed and $n$ persons are available for these jobs. Assume that each person can do each job at a time, though with varying degree of efficiency.
Let $c_{ij}$ be the cost if the $i^{th}$ person is assigned the $j^{th}$ job. Then the problem is to find an assignment so that the total cost of performing all jobs is minimum. (i.e., which job should be assigned to which person with minimum cost). Such problem is called an Assignment Problem (AP).
The tabular form of the assignment problem is as follows
| Persons \ Jobs | $1$ | $2$ | $\cdots$ | $j$ | $\cdots$ | $n$ |
|---|---|---|---|---|---|---|
| Persons/ Jobs | $1$ | $2$ | $\cdots$ | $j$ | $\cdots$ | $n$ |
| $1$ | $c_{11}$ | $c_{12}$ | $\cdots$ | $c_{1j}$ | $\cdots$ | $c_{1n}$ |
| $2$ | $c_{21}$ | $c_{22}$ | $\cdots$ | $c_{2j}$ | $\cdots$ | $c_{2n}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $i$ | $c_{i1}$ | $c_{i2}$ | $\cdots$ | $c_{ij}$ | $\cdots$ | $c_{in}$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $n$ | $c_{n1}$ | $c_{n2}$ | $\cdots$ | $c_{nj}$ | $\cdots$ | $c_{nn}$ |
The above table is called the $n\times n$ cost-matrix, where $c_{ij}$ are real numbers.
Thus the objective in the Assignment Problem is to assign a number of jobs to the equal number of persons at a minimum cost or maximum profit. e.g. assigning men to offices, classes to rooms, drivers to trucks, problems to research teams etc.
Mathematical Formulation of AP
Mathematically, the AP can be stated as $$ \begin{equation}\label{eq2.4} \min z = \sum_{i=1}^n\sum_{j=1}^n x_{ij} c_{ij}. \end{equation} $$ subject to $$ \begin{equation}\label{eq2.5} \sum_{j=1}^n x_{ij} =1,; \text{ for } i=1,2,\ldots, n \end{equation} $$
$$ \begin{equation}\label{eq2.6} \sum_{i=1}^n x_{ij} =1,; \text{ for } j=1,2,\ldots,n \end{equation} $$ where $$ \begin{equation*} x_{ij}=\left{ \begin{array}{ll} 1, & \hbox{if $i^{th}$ person is assigned $j^{th}$ job;} \ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$ Constraint \eqref{eq2.5} indicate that one job is done by $i^{th}$ person $i=1,2,\ldots, n$ and constraint \eqref{eq2.6} indicate that one person should be assigned $j^{th}$ job $j=1,2,\ldots, n$.
It may be observed from the above formulation that AP is a special type of Linear programming problem.
Unbalanced Assignment Problem
If the cost matrix of an assignment problem is not a square matrix, the assignment problem is called an Unbalanced Assignment Problem. In such a case, add dummy row or dummy column with zero cost in the cost matrix so as to form a square matrix. Then apply the usual assignment method to find the optimal solution.
Maximal Assignment Problem
Sometimes, the assignment problem deals with the maximization of an objective function instead of minimization.. For example, it may be required to assign persons to jobs in such a way that the expected profit is maximum. In such a case, first convert the problem of maximization to minimization and apply the usual procedure of assignment.
The assignment problem of maximization type can be converted to minimization type by subtracting all the elements of the given profit matrix from the largest element.
Restrictions on Assignment
Sometimes due to technical or other difficulties do not permit the assignment of a particular facility to a particular job. In such a situation, the difficulty can be overcome by assigning a very high cost (say, infinity i.e. $\infty$) to the corresponding cell.
Because of assigning an infinite penalty to such a cell the activity will be automatically excluded from the optimal solution. Then apply the usual procedure to find the optimal assignment.
