Methods for solving selected variants of the assignment problem

The assignment problem deals with the optimization of resource allocation, where it is necessary to assign agents (e.g. employees, machines, vehicles) to tasks or objects (e.g. orders, production operations, locations) in such a way as to minimize the total cost or maximize the profit. The problem has many different variants. The basic one is the linear assignment problem, where the number of agents and tasks is the same and the cost function is linear. In the rectangular assignment problem, the number of agents and tasks varies. In the generalized assignment problem, agents can perform more than one task. Another generalization is, for example, the quadratic assignment problem, where the costs are quadratic. Applications of this problem are very diverse - from production planning, transportation and logistics optimization to shift management and equipment deployment. Various methods are used, from exact to heuristic and metaheuristic methods.