Rs. Klein et al., MINIMAX RESOURCE-ALLOCATION PROBLEMS WITH RESOURCE-SUBSTITUTIONS REPRESENTED BY GRAPHS, Operations research, 41(5), 1993, pp. 959-971
Citations number
31
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Resource allocation problems focus on the allocation of limited resour
ces among competing activities. We examine such problems when certain
substitutions among resources are possible. The substitutional relatio
ns can be represented by a graph comprised of multiple components. In
each component, the nodes correspond to resources and the ares corresp
ond to feasible substitutions. The objective is of the minimax form, w
here each term is a continuous, strictly decreasing function of a sing
le activity level. The objective is to minimize the largest term, subj
ect to a limited supply of multiple resources. Potential applications
to such problems are found, for example, in the manufacture of high te
ch products. We develop an efficient algorithm to solve such problems.
At each iteration, a relaxed minimax problem is solved. A max-flow al
gorithm is then applied to determine whether the solution of the relax
ed problem is feasible for the original problem. If the solution is in
feasible, a tighter relaxed problem is formulated and resolved. The al
gorithm is also extended to find the lexicographic minimax solution. C
omputational results are presented.