Algorithms for the Multi-Resource Generalized Assignment Problem
研究多资源广义指派问题，即任务分配给多个代理时每个代理消耗多种资源。提出了松弛方法、问题缩减规则、启发式算法和分支定界算法，并通过计算实验验证其有效性。
The multi-resource generalized assignment problem is encountered when a set of tasks have to be assigned to a set of agents in a way that permits assignment of multiple tasks to an agent subject to the availability of a set of multiple resources consumed by that agent. This problem differs from the generalized assignment problem in that an agent consumes not just one but a variety of resources in performing the tasks assigned to him. This paper develops effective solution procedures for the multi-resource generalized assignment problem. Various relaxations of the problem are studied and theoretical relations among these relaxations are pointed out. Rules for reducing problem size are discussed and are shown to be effective through computational experiments. Heuristic solution procedures and an efficient branch and bound procedure are developed. Results of computational experiments testing these procedures are reported.