Optimal allocation of multiple class resources in computer systems

Publisher Website
Google Scholar
Abstract
A class-constrained resource allocation problem is considered. In this problem, a set of M heterogeneous resources is to be allocated optimally among a set of L users belonging to K user classes. A set of class allocation constraints, which limit the number of users of a given class that could be allocated to a given resource, is imposed. An algorithm with worst case time complexity O(M (LM + M2 + LK)) is presented along with a proof of its correctness. This problem arises in many areas of resource management in computer systems, such as load balancing in distributed systems, transaction processing in distributed database systems, and session allocation in time-shared computer systems. We illustrate the behavior of this algorithm with an example where file servers are to be allocated to workstations of multiple classes.