Minimax resource allocation with tree structured substitutable resources

The authors examine an allocation problem in which limited resources are allocated among competing activities. Certain substitutions among resources are possible. The substitutional relations are formulated using tree structures, where a node (resource) can substitute for all its descendants. Potential applications with such resources are found, for example, in the manufacturing of high technology products. The objective is to minimize the maximum weighted relative deviation of the activity levels from given demands. The present formulation of this problem involves a large number of possible resource constraints. The authors develop an efficient minimax algorithm that is based on an iterative solution of relaxed problems, where each such problem considers at most one aggregated constraint from each tree. The algorithm is extended to minimize lexicographically the nonincreasingly sorted vector of all terms in the objective, each of which represents an activity’s deviation. Computational results show that the algorithm solves large problems using relatively small computation time.