The Benefit of Introducing Variability in Single-Server Queues with Application to Quality-Based Service Domains

We propose a static service differentiation policy for a single-server queueing system serving homogeneous customers. We show that by randomly assigning customers different service grades with different service rates, the average waiting time can be reduced without affecting the mean service time. Such differentiation introduces more service time variability, but it also creates information that enables the implementation of service rate-based scheduling, which mitigates the increased variance and may even reduce the total waiting time. We provide conditions under which our static service differentiation reduces waiting, and further derive closed-form expressions for the optimal differentiation policy, which shows that both optimal service rates and allocation probabilities form geometric sequences. We illustrate our policy in the context of quality-based service domains, in which customers value service time but dislike waiting. Numerically, we find that providing differentiated service can improve system performance by 5% without any additional capacity.