MINIMAX RESOURCE-ALLOCATION WITH TREE STRUCTURED SUBSTITUTABLE RESOURCES

• 成果类型: Article
• 署名作者: KLEIN, RS; LUSS, H
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.2.285
• 发表日期: 1991
• 页码: 285-295
• 关键词: PRODUCTION SCHEDULING; APPLICATIONS - ALLOCATION OF MANUFACTURING RESOURCES; programming; LINEAR; algorithm; MINIMAX ALGORITHM FOR SUBSTITUTABLE RESOURCES

摘要

We 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. Our formulation of this problem involves a large number of possible resource constraints. We 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.