MAX-MIN MATCHING PROBLEMS WITH MULTIPLE ASSIGNMENTS

In job assignment and matching problems, we may sometimes need to assi gn several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples in clude the assignment of courses to faculty, consultants to projects, e tc. In terms of objectives, we may wish to maximize profits or minimiz e costs, or maximize the minimal value (max-min criterion) of an attri bute 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 o n the number of assignments. In this paper, we present a method, refer red to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.