IDEAS home Printed from
   My bibliography  Save this article

Developing Effective Service Policies for Multiclass Queues with Abandonment: Asymptotic Optimality and Approximate Policy Improvement


  • Terry James

    () (STOR-i Doctoral Training Centre, Fylde College, Lancaster University, Lancaster, LA1 4YF, United Kingdom)

  • Kevin Glazebrook

    () (Department of Management Science, Lancaster University, Lancaster, LA1 4YF, United Kingdom)

  • Kyle Lin

    () (Operations Research Department, Naval Postgraduate School, Monterey, California 93943)


We study a single server queuing model with multiple classes and impatient customers. The goal is to determine a service policy to maximize the long-run reward rate earned from serving customers net of holding costs and penalties respectively due to customers waiting for and leaving before receiving service. We first show that it is without loss of generality to study a pure-reward model. Since standard methods can usually only compute the optimal policy for problems with up to three customer classes, our focus is to develop a suite of heuristic approaches, with a preference for operationally simple policies with good reward characteristics. One such heuristic is the Rμθ rule—a priority policy that ranks all customer classes based on the product of reward R , service rate μ , and abandonment rate θ . We show that the Rμθ rule is asymptotically optimal as customer abandonment rates approach zero and often performs well in cases where the simpler Rμ rule performs poorly. The paper also develops an approximate policy improvement method that uses simulation and interpolation to estimate the bias function for use in a dynamic programming recursion. For systems with two or three customer classes, our numerical study indicates that the best of our simple priority policies is near optimal in most cases; when it is not, the approximate policy improvement method invariably tightens up the gap substantially. For systems with five customer classes, our heuristics typically achieve within 4% of an upper bound for the optimal value, which is computed via a linear program that relies on a relaxation of the original system. The computational requirement of the approximate policy improvement method grows rapidly when the number of customer classes or the traffic intensity increases.

Suggested Citation

  • Terry James & Kevin Glazebrook & Kyle Lin, 2016. "Developing Effective Service Policies for Multiclass Queues with Abandonment: Asymptotic Optimality and Approximate Policy Improvement," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 251-264, May.
  • Handle: RePEc:inm:orijoc:v:28:y:2016:i:2:p:251-264
    DOI: 10.1287/ijoc.2015.0675

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. repec:wly:navres:v:56:y:2009:i:2:p:113-126 is not listed on IDEAS
    2. Kevin D. Glazebrook & José Niño-Mora, 2001. "Parallel Scheduling of Multiclass M/M/m Queues: Approximate and Heavy-Traffic Optimization of Achievable Performance," Operations Research, INFORMS, vol. 49(4), pages 609-623, August.
    3. repec:wly:navres:v:55:y:2008:i:2:p:142-155 is not listed on IDEAS
    4. repec:wly:navres:v:53:y:2006:i:6:p:588-599 is not listed on IDEAS
    5. Oualid Jouini & Auke Pot & Ger Koole & Yves Dallery, 2010. "Online Scheduling Policies for Multiclass Call Centers with Impatient Customers," Post-Print hal-00565528, HAL.
    6. repec:wly:navres:v:57:y:2010:i:3:p:225-236 is not listed on IDEAS
    7. Jouini, Oualid & Pot, Auke & Koole, Ger & Dallery, Yves, 2010. "Online scheduling policies for multiclass call centers with impatient customers," European Journal of Operational Research, Elsevier, vol. 207(1), pages 258-268, November.
    Full references (including those not matched with items on IDEAS)


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:28:y:2016:i:2:p:251-264. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.