Minimax resource allocation problems with resource-substitutions represented by graphs.

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. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)