Algorithms for the Multi-Resource Generalized Assignment Problem

Bezalel Gavish and Hasan Pirkul
Additional contact information
Bezalel Gavish: Owen Graduate School of Management, Vanderbilt University, Nashville, Tennessee 37203
Hasan Pirkul: College of Business, The Ohio State University, Columbus, Ohio 43210

Management Science, 1991, vol. 37, issue 6, 695-713

Abstract: The multi-resource generalized assignment problem is encountered when a set of tasks have to be assigned to a set of agents in a way that permits assignment of multiple tasks to an agent subject to the availability of a set of multiple resources consumed by that agent. This problem differs from the generalized assignment problem in that an agent consumes not just one but a variety of resources in performing the tasks assigned to him. This paper develops effective solution procedures for the multi-resource generalized assignment problem. Various relaxations of the problem are studied and theoretical relations among these relaxations are pointed out. Rules for reducing problem size are discussed and are shown to be effective through computational experiments. Heuristic solution procedures and an efficient branch and bound procedure are developed. Results of computational experiments testing these procedures are reported.

Keywords: combinatorial optimization; Lagrangian relaxation; subgradient optimization; generalized assignment problem (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.37.6.695 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:37:y:1991:i:6:p:695-713

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().