Solving the Rectangular assignment problem and applicationsReportar como inadecuado

Solving the Rectangular assignment problem and applications - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Annals of Operations Research

, Volume 181, Issue 1, pp 443–462

First Online: 05 June 2010


The rectangular assignment problem is a generalization of the linear assignment problem LAP: one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.

We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.

KeywordsLinear assignment k-Cardinality linear assignment Linear assignment problem with outsourcing Machine replacement  Download to read the full article text

Autor: J. Bijsterbosch - A. Volgenant


Documentos relacionados