Abstract
In job assignment and matching problems, we may sometimes need to assign several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples include the assignment of courses to faculty, consultants to projects, etc. In terms of objectives, we may wish to maximize profits or minimize costs, or maximize the minimal value (max-min criterion) of an attribute such as the performance rating of a processor in the matching, or combine the two goals into one composite objective function entailing time-cost tradeoffs. The regular bipartite matching algorithms cannot solve the matching problem, when upper and lower bounds are imposed on the number of assignments. In this paper, we present a method, referred to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.
Similar content being viewed by others
References
Balinski, M. L.,Signature Methods for the Assignment Problem, Operations Research, Vol. 33, pp. 527–536, 1985.
Barr, R. S., Glover, F., andKlingman, D.,The Alternating Basis for Assignment Problems, Mathematical Programming, Vol. 13, pp. 1–13, 1977.
Hung, M. S., andRom, W. O.,Solving the Assignment Problem by Relaxation, Operations Research, Vol. 28, pp. 969–982, 1980.
McGinnis, F.,Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem, Operations Research, Vol. 31, pp. 277–291, 1983.
Kuhn, H. W.,The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, Vol. 2, pp. 83–97, 1955.
Lawler, E. L.,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, New York, 1976.
Garfinkel, R. S.,An Improved Algorithm for the Bottleneck Assignment Problem, Operations Research, Vol. 18, pp. 1747–1751, 1971.
Ravindran, A., andRamaswamy, V.,On the Bottleneck Assignment Problem, Journal of Optimization Theory and Applications, Vol. 21, pp. 451–458, 1979.
Baksi, H. C., Bhatia, H. L., andPuri, M. C.,Tradeoff Relations in Assignment Problems, Cahiers du CERO, Vol. 21, pp. 367–374, 1979.
Berman, O., Einav, D. andHandler, G.,The Constrained Bottleneck Problem in Networks, Operations Research, Vol. 38, pp. 178–181, 1990.
Geetha, S., andNair, K. P. K.,A Variation of the Assignment Problem, European Journal of Operational Research, Vol. 68, pp. 422–426, 1993.
Bazaraa, M. S., andJarvis, J. J.,Linear Programming and Network Flows, 2nd Edition, John Wiley and Sons, New York, New York, 1990.
Author information
Authors and Affiliations
Additional information
Communicated by C. T. Leondes
Rights and permissions
About this article
Cite this article
Dondeti, V.R., Emmons, H. Max-min matching problems with multiple assignments. J Optim Theory Appl 91, 491–511 (1996). https://doi.org/10.1007/BF02190106
Issue Date:
DOI: https://doi.org/10.1007/BF02190106