Heavy-Traffic Revenue Maximization in Parallel Multiclass Queues

Motivated by revenue maximization in server farms with admission control, we investigate optimal scheduling in parallel processor-sharing queues. Incoming customers are distinguished in multiple classes and we define revenue as a weighted sum of class throughputs. Under these assumptions, we describe a heavy-traffic limit for the revenue maximization problem and study the asymptotic properties of the optimization model as the number of clients increases. Our main result is a simple heuristic that is able to provide tight guarantees on the optimality gap of its solutions. In the general case with M queues and R classes, we prove that our heuristic is (1 + 1 M−1)-competitive in heavy-traffic. Experimental results indicate that the proposed heuristic is remarkably accurate, despite its negligible computational costs, both in random instances and using service rates of a web application measured on multiple cloud deployments.1