A MULTIPLE-ASSIGNMENT PROBLEM

Abstract

A generalization of Kuhn's simple assignment problem is considered: There are m men and n tasks given with each man qualified for certain of the tasks. The output from each task is given as a concave function of the number of qualified men assigned to it. Find an assignment of men to task, perhaps more than one man to a task, so as to maximize total output. An algorithm for solving this general problem is given in which transfers like those used by Kuhn on the simple problem are selected using a node-labeling procedure on a related network. The algorithm yields for every k, 1 < k < m, an optimal assignment of the first k men only, employing a single transfer to increase k by one. Several special forms of the generalized problem are considered including a target assignment problem which A. S. Manne has formulated as a linear program.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1964
Accession Number
AD0602672

Entities

People

  • David W. Walkup
  • M. D. Maclaren

Organizations

  • Boeing

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Equations
  • Heuristic Methods
  • Inequalities
  • Integrals
  • Linear Programming
  • Mathematics
  • Probability
  • Qualifications
  • Scientific Research
  • Sequences
  • Transportation

Readers

  • Naval Personnel Management
  • Operations Research