Kd. Glazebrook et J. Nino-mora, Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance, OPERAT RES, 49(4), 2001, pp. 609-623
We address the problem of scheduling a multiclass M/M/m queue with Bernoull
i feedback on m parallel servers to minimize time-average linear holding co
sts. We analyze the performance of a heuristic priority-index rule, which e
xtends Klimov's optimal solution to the single-server case: servers select
preemptively customers with larger Klimov indices. We present closed-form s
uboptimality 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 (i
i) the number of servers. It follows that its relative suboptimality gap va
nishes 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 rul
e 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 obta
in this relaxation, we derive and exploit a new set of work decomposition l
aws for the parallel-server system. We further report on the results of a c
omputational study on the quality of the c mu rule for parallel scheduling.