IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v52y2004i6p836-855.html
   My bibliography  Save this article

Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule

Author

Listed:
  • Avishai Mandelbaum

    (Industrial Engineering and Management, Technion, Haifa 32000, Israel)

  • Alexander L. Stolyar

    (Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey 07974)

Abstract

We consider a queueing system with multitype customers and flexible (multiskilled) servers that work in parallel. If Q i is the queue length of type i customers, this queue incurs cost at the rate of C i ( Q i ), where C i (·) 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 max i C μ i ( Q i )μ 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 C i ( 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.

Suggested Citation

  • Avishai Mandelbaum & Alexander L. Stolyar, 2004. "Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule," Operations Research, INFORMS, vol. 52(6), pages 836-855, December.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:6:p:836-855
    DOI: 10.1287/opre.1040.0152
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0152
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0152?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Ety Zohar & Avishai Mandelbaum & Nahum Shimkin, 2002. "Adaptive Behavior of Impatient Customers in Tele-Queues: Theory and Empirical Support," Management Science, INFORMS, vol. 48(4), pages 566-583, April.
    2. Ward Whitt, 1999. "Improving Service by Informing Customers About Anticipated Delays," Management Science, INFORMS, vol. 45(2), pages 192-207, February.
    3. 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.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pengfei Guo & Paul Zipkin, 2007. "Analysis and Comparison of Queues with Different Levels of Delay Information," Management Science, INFORMS, vol. 53(6), pages 962-970, June.
    2. Jouini, Oualid & Dallery, Yves & Aksin, Zeynep, 2009. "Queueing models for full-flexible multi-class call centers with real-time anticipated delays," International Journal of Production Economics, Elsevier, vol. 120(2), pages 389-399, August.
    3. Oualid Jouini & Zeynep Akşin & Yves Dallery, 2011. "Call Centers with Delay Information: Models and Insights," Manufacturing & Service Operations Management, INFORMS, vol. 13(4), pages 534-548, October.
    4. Zeynep Akşin & Barış Ata & Seyed Morteza Emadi & Che-Lin Su, 2013. "Structural Estimation of Callers' Delay Sensitivity in Call Centers," Management Science, INFORMS, vol. 59(12), pages 2727-2746, December.
    5. Susan H. Xu & Long Gao & Jihong Ou, 2007. "Service Performance Analysis and Improvement for a Ticket Queue with Balking Customers," Management Science, INFORMS, vol. 53(6), pages 971-990, June.
    6. Gabriel R. Bitran & Juan-Carlos Ferrer & Paulo Rocha e Oliveira, 2008. "OM Forum--Managing Customer Experiences: Perspectives on the Temporal Aspects of Service Encounters," Manufacturing & Service Operations Management, INFORMS, vol. 10(1), pages 61-83, July.
    7. Z. Justin Ren & Yong-Pin Zhou, 2008. "Call Center Outsourcing: Coordinating Staffing Level and Service Quality," Management Science, INFORMS, vol. 54(2), pages 369-383, February.
    8. Zhang, Zhe George & Yin, Xiaoling, 2021. "Information and pricing effects in two-tier public service systems," International Journal of Production Economics, Elsevier, vol. 231(C).
    9. Mor Armony & Nahum Shimkin & Ward Whitt, 2009. "The Impact of Delay Announcements in Many-Server Queues with Abandonment," Operations Research, INFORMS, vol. 57(1), pages 66-81, February.
    10. Ward Whitt, 2005. "Engineering Solution of a Basic Call-Center Model," Management Science, INFORMS, vol. 51(2), pages 221-235, February.
    11. José Niño-Mora, 2006. "Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 50-84, February.
    12. De Munck, Thomas & Chevalier, Philippe & Tancrez, Jean-Sébastien, 2023. "Managing priorities on on-demand service platforms with waiting time differentiation," International Journal of Production Economics, Elsevier, vol. 266(C).
    13. Rouba Ibrahim & Mor Armony & Achal Bassamboo, 2017. "Does the Past Predict the Future? The Case of Delay Announcements in Service Systems," Management Science, INFORMS, vol. 63(6), pages 1762-1780, June.
    14. Rouba Ibrahim & Ward Whitt, 2011. "Wait-Time Predictors for Customer Service Systems with Time-Varying Demand and Capacity," Operations Research, INFORMS, vol. 59(5), pages 1106-1118, October.
    15. Qiuping Yu & Gad Allon & Achal Bassamboo & Seyed Iravani, 2018. "Managing Customer Expectations and Priorities in Service Systems," Management Science, INFORMS, vol. 64(8), pages 3942-3970, August.
    16. Esther Frostig & Gideon Weiss, 2016. "Four proofs of Gittins’ multiarmed bandit theorem," Annals of Operations Research, Springer, vol. 241(1), pages 127-165, June.
    17. Pengfei Guo & Zhe George Zhang, 2013. "Strategic Queueing Behavior and Its Impact on System Performance in Service Systems with the Congestion-Based Staffing Policy," Manufacturing & Service Operations Management, INFORMS, vol. 15(1), pages 118-131, September.
    18. Pengfei Guo & Refael Hassin, 2011. "Strategic Behavior and Social Optimization in Markovian Vacation Queues," Operations Research, INFORMS, vol. 59(4), pages 986-997, August.
    19. Qiuping Yu & Gad Allon & Achal Bassamboo, 2017. "How Do Delay Announcements Shape Customer Behavior? An Empirical Study," Management Science, INFORMS, vol. 63(1), pages 1-20, January.
    20. Marcos Singer & Patricio Donoso & Alan Scheller-Wolf, 2008. "Una Introducción A La Teoría De Colas Aplicada A La Gestión De Servicios," Abante, Escuela de Administracion. Pontificia Universidad Católica de Chile., vol. 11(2), pages 93-120.

    Corrections

    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:oropre:v:52:y:2004:i:6:p:836-855. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.