Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
Top Cited Papers
- 1 December 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 52 (6), 836-855
- https://doi.org/10.1287/opre.1040.0152
Abstract
We consider a queueing system with multitype customers and flexible (multiskilled) servers that work in parallel. If Qi is the queue length of type i customers, this queue incurs cost at the rate of Ci(Qi), where Ci(·) is increasing and convex. We analyze the system in heavy traffic (Harrison and Lopez 1999) and show that a very simple generalized cμ-rule (Van Mieghem 1995) minimizes both instantaneous and cumulative queueing costs, asymptotically, over essentially all scheduling disciplines, preemptive or non-preemptive. This rule aims at myopically maximizing the rate of decrease of the instantaneous cost at all times, which translates into the following: when becoming free, server j chooses for service a type i customer such that i ε arg maxi Cμi(Qi)μij, where μij is the average service rate of type i customers by server j. An analogous version of the generalized cμ-rule asymptotically minimizes delay costs. To this end, let the cost incurred by a type i customer be an increasing convex function Ci(D) of its sojourn time D. Then, server j always chooses for service a customer for which the value of C′i(D) μij is maximal, where D and i are the customer's sojourn time and type, respectively.Keywords
This publication has 21 references indexed in Scilit:
- Some diffusion approximations with state space collapsePublished by Springer Nature ,2005
- SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATESProbability in the Engineering and Informational Sciences, 2004
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy trafficThe Annals of Applied Probability, 2004
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policyThe Annals of Applied Probability, 2001
- Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policiesThe Annals of Applied Probability, 1998
- Dynamic control of Brownian networks: state space collapse and equivalent workload formulationsThe Annals of Applied Probability, 1997
- Dynamic Scheduling with Convex Delay Costs: The Generalized $c|mu$ RuleThe Annals of Applied Probability, 1995
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992
- A multiclass feedback queue in heavy trafficAdvances in Applied Probability, 1988
- Time-Sharing Service Systems. IITheory of Probability and Its Applications, 1979