Multidimensional assignment problem: Difference between revisions

Revision as of 19:04, 8 February 2022

Revision as of 19:08, 8 February 2022

Line 1:

{{AfC submission|t||ts=20220208190437|u=COPknowledge|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

{{Short description|Generalization of linear assignment problem from two to multiple dimensions}}

{{Draft topics|computing}}

{{AfC topic|stem}}

{{AfC submission|||ts=20220208190802|u=COPknowledge|ns=118}}

{{AfC submission|t||ts=20220208190437|u=COPknowledge|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem which was introduced by Pierskalla<ref>{{cite article |last=Pierskalla |first=William P. |title=Letter to the Editor—The Multidimensional Assignment Problem | journal=Operations Research 16(2) |publisher=INFORMS |date=1968 |page=422-431 |url=https://pubsonline.informs.org/doi/abs/10.1287/opre.16.2.422}}</ref>. This problem can be seen as a generalization of the linear [[assignment problem]]. In words, the problem can be described as follows:

: An instance of the problem has a number of ''agents'' (i.e., ''cardinality'' parameter) and a number of ''job characteristics'' (i.e., ''dimensionality'' parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some ''cost''. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the ''total cost'' of assigning the agents so that the assignment of agents to each job characteristic is an [[injective function]], or [[one-to-one function]] from agents to a given job characteristic.