Minimax Resource Allocation Problems with Resource-Substitutions Represented by Graphs

Rachelle S. Klein, Hanan Luss and Uriel G. Rothblum
Additional contact information
Rachelle S. Klein: AT&T Bell Laboratories, Holmdel, New Jersey
Hanan Luss: AT&T Bell Laboratories, Holmdel, New Jersey
Uriel G. Rothblum: Technion-Israel Institute of Technology, Haifa, Israel

Operations Research, 1993, vol. 41, issue 5, 959-971

Abstract: Resource allocation problems focus on the allocation of limited resources among competing activities. We examine such problems when certain substitutions among resources are possible. The substitutional relations can be represented by a graph comprised of multiple components. In each component, the nodes correspond to resources and the arcs correspond to feasible substitutions. The objective is of the minimax form, where each term is a continuous, strictly decreasing function of a single activity level. The objective is to minimize the largest term, subject to a limited supply of multiple resources. Potential applications to such problems are found, for example, in the manufacture of high tech products. We develop an efficient algorithm to solve such problems. At each iteration, a relaxed minimax problem is solved. A max-flow algorithm is then applied to determine whether the solution of the relaxed problem is feasible for the original problem. If the solution is infeasible, a tighter relaxed problem is formulated and resolved. The algorithm is also extended to find the lexicographic minimax solution. Computational results are presented.

Keywords: production/scheduling; applications: allocation of manufacturing resources; programming; linear and nonlinear; algorithms: minimax algorithm for substitutable resources (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.5.959 (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:oropre:v:41:y:1993:i:5:p:959-971

Access Statistics for this article

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