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, , and a finite set of tasks, , where . The cost of a particular agent executing a particular task is a cost, or , function . The goal is to find the bijective mapping assigning agents to tasks such that the cost function
The cost function can also be viewed as a square real-valued matrix , where is the cost of having agent execute task , 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 http://en.wikipedia.org/wiki/Assignment_problemAssignment problem as of January 13, 2007.
|Date of creation||2013-03-22 16:33:40|
|Last modified on||2013-03-22 16:33:40|
|Last modified by||PrimeFan (13766)|
|Synonym||linear assignment problem|