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. 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.
    2. 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).
    3. Ward Whitt, 2005. "Engineering Solution of a Basic Call-Center Model," Management Science, INFORMS, vol. 51(2), pages 221-235, February.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    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. 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.
    13. 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.
    14. R. T. Dunn & K. D. Glazebrook, 2004. "Discounted Multiarmed Bandit Problems on a Collection of Machines with Varying Speeds," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 266-279, May.
    15. Lawrence Brown & Noah Gans & Avishai Mandelbaum & Anat Sakov & Haipeng Shen & Sergey Zeltyn & Linda Zhao & Novemer, "undated". "Statistical Analysis of a Telephone Call Center: A Queueing-Science Perspective," Center for Financial Institutions Working Papers 03-12, Wharton School Center for Financial Institutions, University of Pennsylvania.
    16. Athanasia Manou & Antonis Economou & Fikri Karaesmen, 2014. "Strategic Customers in a Transportation Station: When Is It Optimal to Wait?," Operations Research, INFORMS, vol. 62(4), pages 910-925, August.
    17. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2009. "Pointwise Stationary Fluid Models for Stochastic Processing Networks," Manufacturing & Service Operations Management, INFORMS, vol. 11(1), pages 70-89, August.
    18. Veeraruna Kavitha & Jayakrishnan Nair & Raman Kumar Sinha, 2019. "Pseudo conservation for partially fluid, partially lossy queueing systems," Annals of Operations Research, Springer, vol. 277(2), pages 255-292, June.
    19. J. E. Reed & Amy R. Ward, 2008. "Approximating the GI/GI/1+GI Queue with a Nonlinear Drift Diffusion: Hazard Rate Scaling in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 33(3), pages 606-644, August.
    20. Karen Donohue & Özalp Özer, 2020. "Behavioral Operations: Past, Present, and Future," Manufacturing & Service Operations Management, INFORMS, vol. 22(1), pages 191-202, January.

    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.