IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v52y2004i6p836-855.html

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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. 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).
    7. 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.
    8. 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.
    9. Naumov, Sergey & Oliva, Rogelio, 2025. "Structural feedback and behavioral decision making in queuing systems: A hybrid simulation framework," European Journal of Operational Research, Elsevier, vol. 324(3), pages 855-870.
    10. 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.
    11. Ward Whitt, 2005. "Engineering Solution of a Basic Call-Center Model," Management Science, INFORMS, vol. 51(2), pages 221-235, February.
    12. 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.
    13. 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).
    14. Elvin Coban & Aliza Heching & Alan Scheller‐Wolf, 2019. "Service Center Staffing with Cross‐Trained Agents and Heterogeneous Customers," Production and Operations Management, Production and Operations Management Society, vol. 28(4), pages 788-809, April.
    15. 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.
    16. Zeynep Akşin & Baris Ata & Seyed Morteza Emadi & Che-Lin Su, 2017. "Impact of Delay Announcements in Call Centers: An Empirical Approach," Operations Research, INFORMS, vol. 65(1), pages 242-265, February.
    17. 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.
    18. 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.
    19. Jamol Pender & Richard Rand & Elizabeth Wesson, 2020. "A Stochastic Analysis of Queues with Customer Choice and Delayed Information," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1104-1126, August.
    20. Noa Zychlinski & Avishai Mandelbaum & Petar Momčilović & Izack Cohen, 2020. "Bed Blocking in Hospitals Due to Scarce Capacity in Geriatric Institutions—Cost Minimization via Fluid Models," Manufacturing & Service Operations Management, INFORMS, vol. 22(2), pages 396-411, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.