A min-max-sum resource allocation problem and its applications
成果类型：
Article
署名作者：
Karabati, S; Kouvelis, P; Yu, G
署名单位：
Koc University; Washington University (WUSTL); University of Texas System; University of Texas Austin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.6.913.10023
发表日期：
2001
页码：
913-922
关键词：
摘要：
In this paper we consider a class of discrete resource-allocation problems with a min-max-sum objective function. We first provide several examples of practical applications of this problem. We then develop a branch-and-bound procedure for solving the general case of this computationally intractable problem. The proposed solution procedure employs a surrogate relaxation technique to obtain lower and upper bounds on the optimal objective function value of the problem. To obtain the multipliers of the surrogate relaxation, two alternative approaches are discussed. We also discuss a simple approximation algorithm with a tight bound. Our computational results support the effectiveness of the branch-and-bound procedure for fairly large-size problems.