Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Parallel scheduling of multiclass M/M/m queues: approximate and heavy-traffic optimization of achievable performance
AU - Glazebrook, Kevin
AU - Nino-Mora, J.
N1 - RAE_import_type : Journal article RAE_uoa_type : Statistics and Operational Research
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
U2 - 10.1287/opre.49.4.609.11225
DO - 10.1287/opre.49.4.609.11225
M3 - Journal article
VL - 49
SP - 609
EP - 623
JO - Operations Research
JF - Operations Research
SN - 0030-364X
IS - 4
ER -