- Title:
- Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance
- Authors:
- Kevin D. Glazebrook and José Niño-Mora
- Date:
- February 1997 (Revised: October 1999)
- 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:
- Multiclass queueing network, suboptimality bound, heavy-traffic optimality, parallel scheduling, achievable performance region, priority index rule, work decomposition laws
- JEL codes:
- C60, C61
- Area of Research:
- Operations Management
- Published in:
- Operations Research, (forthcoming)