Optimum Allocation of Servers to Two Types of Competing Customers

We consider the problem of optimal dynamic allocation of a limited number of processors to service the demands from different types of users. The types are differentiated by the rates at which they enter requests for service and the mean length of time they occupy a single processor. The decision to accept or reject a request for service may be based on the number of processors occupied by each type. Throughput, or utilization of processors, weighted differently for each type may be used as a performance measure. While the optimum allocation question is formulated for any finite number of customer types, our solution is limited to the case of two competing customer classes. For two types of users we show that among a large class of policies, the optimum is the easily implemented policy of restricting the maximum number of processors that one of the two types can occupy at any time. The requests from the other type are always honored as long as a processor is available for service. It is intuitively reasonable that, despite the complex interactivity permitted in some policies and the multidimensional characterization of a customer type, one of the customer types should have a relative advantage and be permitted open access while a hard limitation is enforced on the competition. The crux of the proof involves a policy space perturbation argument relying on the structure of the equilibrium density.