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 |A|=|T|. The cost of a particular agent executing a particular task is a cost, or , functionMathworldPlanetmath C:A×T. The goal is to find the bijective mapping f:AT assigning agents to tasks such that the cost function


is minimized.

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


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 problem as of January 13, 2007.

Title assignment problem
Canonical name AssignmentProblem
Date of creation 2013-03-22 16:33:40
Last modified on 2013-03-22 16:33:40
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 8
Author PrimeFan (13766)
Entry type Definition
Classification msc 90C27
Synonym linear assignment problem