Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13795
Title: Asymptotic optimality of balanced routing
Authors: Chen, H
Ye, HQ 
Keywords: Asymptotic optimality
Balanced routing
Diffusion limit
Fluid limit
Join-the-shortest-queue
Issue Date: 2012
Publisher: Institute for Operations Research and the Management Sciences
Source: Operations research, 2012, v. 60, no. 1, p. 163-179 How to cite?
Journal: Operations research 
Abstract: Consider a system with K parallel servers, each with its own waiting room. Upon arrival, a job is routed to the queue of one of the servers. Finding a routing policy that minimizes the total workload in the system is a known difficult problem in general. Even if the optimal policy is identified, the policy would require the full queue length information at the arrival of each job; for example, the join-the-shortest-queue policy (which is known to be optimal for identical servers with exponentially distributed service times) would require comparing the queue lengths of all the servers. In this paper, we consider a balanced routing policy that examines only a subset of c servers, with 1 ≤ c ≤ K: specifically, upon the arrival of a job, choose a subset of c servers with a probability proportional to their service rates, and then route the job to the one with the shortest queue among the c chosen servers. Under such a balanced policy, we derive the diffusion limits of the queue length processes and the workload processes. We note that the diffusion limits are the same for these processes regardless the choice of c, as long as c ≥ 2. We further show that the proposed balanced routing policy for any fixed c ≥ 2 is asymptotically optimal in the sense that it minimizes the workload over all time in the diffusion limit. In addition, the policy helps to distribute work among all the servers evenly.
URI: http://hdl.handle.net/10397/13795
ISSN: 0030-364x
EISSN: 1526-5463
DOI: 10.1287/opre.1110.0998
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

1
Last Week
0
Last month
0
Citations as of Aug 7, 2017

Page view(s)

42
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.