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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Glazebrook, K. D. Articles by Niño-Mora, J. Search for Related Content

Parallel Scheduling of Multiclass M/M/m Queues: Approximate and Heavy-Traffic Optimization of Achievable Performance

Department of Statistics, Newcastle University, Newcastle upon Tyne, NE1 7RU, UK
Department of Economics and Business, Universitat Pompeu Fabra, E-08005, Barcelona, Spain
kevin.glazebrook{at}newcastle.ac.uk
jose.nino-mora{at}econ.upf.es

We address the problem of scheduling a multiclass M/M/mqueue with Bernoulli feedback on mparallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity; and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical cµ rule. Our analysis is based on comparing the expected cost of Klimov's rule to the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set of work decomposition lawsfor the parallel-server system. We further report on the results of a computational study on the quality of the cµ rule for parallel scheduling.

Subject classifications: Queues/optimization: multiclass queues, parallel servers; Dynamic programming: performance guarantees for heuristic policies.
History: Received December 1996; revision received January 1999; revision received November 1999; accepted April 2000.

This article has been cited by other articles:

				K. D. Glazebrook, C. Kirkbride, and J. Ouenniche Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations Operations Research, July 1, 2009; 57(4): 975 - 989. [Abstract] [PDF]

				J. Nino-Mora Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues Mathematics of Operations Research, February 1, 2006; 31(1): 50 - 84. [Abstract] [PDF]

				A. Mandelbaum and A. L. Stolyar Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized c{micro}-Rule Operations Research, November 1, 2004; 52(6): 836 - 855. [Abstract] [PDF]

				R. T. Dunn and K. D. Glazebrook Discounted Multiarmed Bandit Problems on a Collection of Machines with Varying Speeds Mathematics of Operations Research, May 1, 2004; 29(2): 266 - 279. [Abstract] [PDF]