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

Kevin D. Glazebrook () and José Niño-Mora ()
Additional contact information
Kevin D. Glazebrook: Department of Statistics, Newcastle University, Newcastle upon Tyne, NE1 7RU, UK
José Niño-Mora: Department of Economics and Business, Universitat Pompeu Fabra, E-08005, Barcelona, Spain

Operations Research, 2001, vol. 49, issue 4, 609-623

Abstract: We address the problem of scheduling a multiclass M/M/m queue with Bernoulli feedback on m parallel 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 relative suboptimality 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(mu) 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 laws for the parallel-server system. We further report on the results of a computational study on the quality of the c(mu) rule for parallel scheduling.

Keywords: Queues/optimization: multiclass queues; parallel servers; Dynamic programming: performance guarantees for heuristic policies (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.4.609.11225 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:4:p:609-623

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().