Assignment Problem
The assignment problem is a special case of transportation problem where the objective is to minimize the cost or time of completing a number of jobs by a number of persons or to maximize the profit of completing a number of jobs by a number of persons.
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$ |
|---|---|---|---|---|---|---|
| $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.
Some examples of assignment problems are assigning
- men to offices,
- classes to rooms,
- drivers to trucks,
- problems to research teams, etc.
Assumptions in Assignment Problem
- Number of jobs is equal to the number of persons or machines.
- Each person or machine is assigned only one job.
- Each person or machine is independently capable of handling any job to be done.
- Assigning criteria is clearly specified in the problem (i.e., minimizing cost or maximizing profit).
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*} $$
Equation \eqref{eq2.4} is the objective function. 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.
Variations of the Assignment Problems
Balanced Assignment Problem
If the cost matrix of an assignment problem is a square matrix, the assignment problem is called an Balanced Assignment Problem. The optimal solution of balanced assignment problem can be found using Hungarian method.
Read step by step solution for solving balanced assignment problem using Hungarian method.
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.
Read step by step solution for solving unbalanced assignment problem using Hungarian method.
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.
Read step by step solution for solving assignment problem of maximization type using Hungarian method.
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.
Read step by step solution for solving assignment problem with restrictions using Hungarian method
Endnote
In this tutorial, you learned about assignment problem, its formulation as LPP and various types of assignment problems.
To learn more about Assignment problems please refer to the following tutorials:
Let me know in the comments if you have any questions on Assignment problems and your thought on this article.
