This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Atar, R. Articles by Shwartz, A. Search for Related Content

Efficient Routing in Heavy Traffic Under Partial Sampling of Service Times

Technion–Israel Institute of Technology, Haifa 32000, Israel
Technion–Israel Institute of Technology, Haifa 32000, Israel
atar{at}ee.technion.ac.il
adam{at}ee.technion.ac.il

We consider a queue with renewal arrivals and n exponential servers in the Halfin-Whitt heavy traffic regime, where n and the arrival rate increase without bound, so that a critical loading condition holds. Server k serves at rate µ_k, and the empirical distribution of {µ_k}_{k = 1,...,n} is assumed to converge weakly. We show that very little information on the service rates is required for a routing mechanism to perform well. More precisely, we construct a routing mechanism that has access to a single sample from the service time distribution of each of n^{1/2 +} randomly selected servers ( > 0), but not to the actual values of the service rates, the performance of which is asymptotically as good as the best among mechanisms that have the complete information {µ_k}_{k = 1,...,n}.

Key Words: Halfin-Whitt regime; routing policies; service time sampling
History: Received: October 19, 2007; revision received: March 12, 2008;