Weighted Assignment Models and Their Application

Abstract

This paper defines the components and characteristics of an important class of models called weighted assignment models and identifies these elements in a number of existing and potential applications. The weighted assignment model represents problems with the following characteristics: A set of tasks must be divided among a set of agents, and each task must be completed by only one agent. Tasks may be completed at one of several predetermined levels. When an agent completes a task at some level, a resource possessed by the agent is consumed and a system disutility is incurred. The weighted assignment model may be used to determine the best assignment of tasks to agents and the task completion levels so as to minimize total system disutility while satisfying the agent resource constraints. In the first part of the paper, a general formulation is presented, and its relationship to assignment models, transportation models, knapsack models and various fixed charge models is established. In the second part of the paper, a number of applications are described which demonstrate the usefulness of weighted assignment models. These applications include machine loading problems, personnel assignment problems and districting problems. Computational results for several of the applications are presented to document the tractability of the models.