Heavy-traffic revenue maximization in parallel multiclass queues

Motivated by revenue maximization in server farms with admission control, we investigate the 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 MM queues and RR classes, we prove that our heuristic is (1+1M−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.