MINIMAX RESOURCE-ALLOCATION PROBLEMS WITH RESOURCE-SUBSTITUTIONS REPRESENTED BY GRAPHS

Citation
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
Journal title
ISSN journal
0030364X
Volume
41
Issue
5
Year of publication
1993
Pages
959 - 971
Database
ISI
SICI code
0030-364X(1993)41:5<959:MRPWRR>2.0.ZU;2-H
Abstract
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.