## You are here

Homeassignment problem

## Primary tabs

# assignment problem

The assignment problem is a kind of optimization problem in which the goal is to reduce the total cost of a number of tasks by choosing a particular assignment of those tasks to a number of agents, or task executors. One example might be an algorithm for assigning pieces of work to individual processors of different capacities in a multiprocessor computer. A more real-world example might be Amazon deciding, given a finite number of airplanes, which distribution center should be used, with its fleet, to service a particular set of delivery requests in order to minimize the usage of fuel.

Mathematically, the assignment problem starts with a finite set of agents, $A$, and a finite set of tasks, $T$, where $\lvert A\rvert=\lvert T\rvert$. The cost of a particular agent executing a particular task is a cost, or weight, function $C:A\times T\to\mathbb{R}$. The goal is to find the bijective mapping $f:A\to T$ assigning agents to tasks such that the cost function

$\sum_{{a\in A}}C(a,f(a))$ |

is minimized.

The cost function can also be viewed as a square real-valued matrix $C$, where $C_{{i,j}}$ is the cost of having agent $i$ execute task $t$, so that the objective function can be written as

$\sum_{{a\in A}}C_{{a,f(a)}}$ |

The problem is “linear” because the cost function to be optimized as well as all the constraints contain only linear terms.

This entry was adapted from the Wikipedia article Assignment problem as of January 13, 2007.

## Mathematics Subject Classification

90C27*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections