IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v106y2022ics0305048321001328.html
   My bibliography  Save this article

Sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals

Author

Listed:
  • Wu, Xueqi
  • Zhou, Shenghai

Abstract

In this paper, we consider the problem of sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals. The objective is to minimize the weighted sum of server staffing cost and total expected cost of customer waiting, server idleness and overtime. To solve the problem, we first formulate it as a two-stage integer program, where the second stage involves multiple stochastic linear programs. Based on this, we then derive a deterministic mixed-integer linear program for the problem via sample average approximation and further strengthen the formulation by exploiting problem properties. Due to the high complexity of the problem, we also propose an efficient integer L-shaped based heuristic, which is further enhanced by variable neighborhood descent. Our computational experiments show that the proposed integer L-shaped heuristic dominates the strengthened deterministic program and integer L-shaped method especially for large-scale problems, while the incorporation of variable neighborhood descent can significantly improve the performance of the heuristic. Our computational results also reveal that variations in service durations and fluctuations as well as customer unpunctual times have significant impacts on the system performance, while optimizing appointment sequencing decision can help reduce operational cost.

Suggested Citation

  • Wu, Xueqi & Zhou, Shenghai, 2022. "Sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals," Omega, Elsevier, vol. 106(C).
    • Handle: RePEc:eee:jomega:v:106:y:2022:i:c:s0305048321001328
    DOI: 10.1016/j.omega.2021.102523
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048321001328
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2021.102523?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Qingxia Kong & Chung-Yee Lee & Chung-Piaw Teo & Zhichao Zheng, 2013. "Scheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones," Operations Research, INFORMS, vol. 61(3), pages 711-726, June.
    2. Alexopoulos, Christos & Goldsman, David & Fontanesi, John & Kopald, David & Wilson, James R., 2008. "Modeling patient arrivals in community clinics," Omega, Elsevier, vol. 36(1), pages 33-43, February.
    3. Ahmadi-Javid, Amir & Jalali, Zahra & Klassen, Kenneth J, 2017. "Outpatient appointment systems in healthcare: A review of optimization studies," European Journal of Operational Research, Elsevier, vol. 258(1), pages 3-34.
    4. Laura McLay & Sheldon Jacobson & Alexander Nikolaev, 2009. "A sequential stochastic passenger screening problem for aviation security," IISE Transactions, Taylor & Francis Journals, vol. 41(6), pages 575-591.
    5. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    6. Rachel R. Chen & Lawrence W. Robinson, 2014. "Sequencing and Scheduling Appointments with Potential Call-In Patients," Production and Operations Management, Production and Operations Management Society, vol. 23(9), pages 1522-1538, September.
    7. Kong, Qingxia & Lee, Chung-Yee & Teo, Chung-Piaw & Zheng, Zhichao, 2016. "Appointment sequencing: Why the Smallest-Variance-First rule may not be optimal," European Journal of Operational Research, Elsevier, vol. 255(3), pages 809-821.
    8. Wyean Chan & Ger Koole & Pierre L'Ecuyer, 2014. "Dynamic Call Center Routing Policies Using Call Waiting and Agent Idle Times," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 544-560, October.
    9. Michele Samorani & Subhamoy Ganguly, 2016. "Optimal Sequencing of Unpunctual Patients in High-Service-Level Clinics," Production and Operations Management, Production and Operations Management Society, vol. 25(2), pages 330-346, February.
    10. Zheng Zhang & Xiaolan Xie, 2015. "Simulation-based optimization for surgery appointment scheduling of multiple operating rooms," IISE Transactions, Taylor & Francis Journals, vol. 47(9), pages 998-1012, September.
    11. Sharan Srinivas & A. Ravi Ravindran, 2020. "Designing schedule configuration of a hybrid appointment system for a two-stage outpatient clinic with multiple servers," Health Care Management Science, Springer, vol. 23(3), pages 360-386, September.
    12. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    13. Zhou, Shenghai & Li, Debiao & Yin, Yong, 2021. "Coordinated appointment scheduling with multiple providers and patient-and-physician matching cost in specialty care," Omega, Elsevier, vol. 101(C).
    14. Tugba Cayirli & Kum Khiong Yang & Ser Aik Quek, 2012. "A Universal Appointment Rule in the Presence of No‐Shows and Walk‐Ins," Production and Operations Management, Production and Operations Management Society, vol. 21(4), pages 682-697, July.
    15. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2014. "Sequencing Appointments for Service Systems Using Inventory Approximations," Manufacturing & Service Operations Management, INFORMS, vol. 16(2), pages 251-262, May.
    16. Sabine Sickinger & Rainer Kolisch, 2009. "The performance of a generalized Bailey–Welch rule for outpatient appointment scheduling under inpatient and emergency demand," Health Care Management Science, Springer, vol. 12(4), pages 408-419, December.
    17. Hyun-Jung Alvarez-Oh & Hari Balasubramanian & Ekin Koker & Ana Muriel, 2018. "Stochastic Appointment Scheduling in a Team Primary Care Practice with Two Flexible Nurses and Two Dedicated Providers," Service Science, INFORMS, vol. 10(3), pages 241-260, September.
    18. Wu, Xueqi & Che, Ada, 2020. "Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search," Omega, Elsevier, vol. 94(C).
    19. Brian Denton & James Viapiano & Andrea Vogl, 2007. "Optimization of surgery sequencing and scheduling decisions under uncertainty," Health Care Management Science, Springer, vol. 10(1), pages 13-24, February.
    20. Xuanming Su & Stefanos A. Zenios, 2005. "Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model," Operations Research, INFORMS, vol. 53(3), pages 443-455, June.
    21. Jiang, Bowen & Tang, Jiafu & Yan, Chongjun, 2019. "A stochastic programming model for outpatient appointment scheduling considering unpunctuality," Omega, Elsevier, vol. 82(C), pages 70-82.
    22. Soltani, Mohamad & Samorani, Michele & Kolfal, Bora, 2019. "Appointment scheduling with multiple providers and stochastic service times," European Journal of Operational Research, Elsevier, vol. 277(2), pages 667-683.
    23. Camilo Mancilla & Robert Storer, 2012. "A sample average approximation approach to stochastic appointment sequencing and scheduling," IISE Transactions, Taylor & Francis Journals, vol. 44(8), pages 655-670.
    24. Deceuninck, Matthias & Fiems, Dieter & De Vuyst, Stijn, 2018. "Outpatient scheduling with unpunctual patients and no-shows," European Journal of Operational Research, Elsevier, vol. 265(1), pages 195-207.
    25. Christos Zacharias & Michael Pinedo, 2017. "Managing Customer Arrivals in Service Systems with Multiple Identical Servers," Manufacturing & Service Operations Management, INFORMS, vol. 19(4), pages 639-656, October.
    26. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2015. "Appointment Scheduling with Limited Distributional Information," Management Science, INFORMS, vol. 61(2), pages 316-334, February.
    27. Han Zhu & Youhua (Frank) Chen & Eman Leung & Xing Liu, 2018. "Outpatient appointment scheduling with unpunctual patients," International Journal of Production Research, Taylor & Francis Journals, vol. 56(5), pages 1982-2002, March.
    28. Ruiwei Jiang & Siqian Shen & Yiling Zhang, 2017. "Integer Programming Approaches for Appointment Scheduling with Random No-Shows and Service Durations," Operations Research, INFORMS, vol. 65(6), pages 1638-1656, December.
    29. Refael Hassin & Sharon Mendel, 2008. "Scheduling Arrivals to Queues: A Single-Server Model with No-Shows," Management Science, INFORMS, vol. 54(3), pages 565-572, March.
    30. Kenneth J. Klassen & Reena Yoogalingam, 2019. "Appointment scheduling in multi-stage outpatient clinics," Health Care Management Science, Springer, vol. 22(2), pages 229-244, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Meersman, Tine & Maenhout, Broos & Van Herck, Koen, 2023. "A nested Benders decomposition-based algorithm to solve the three-stage stochastic optimisation problem modeling population-based breast cancer screening," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1273-1293.
    2. Çelik, Batuhan & Gul, Serhat & Çelik, Melih, 2023. "A stochastic programming approach to surgery scheduling under parallel processing principle," Omega, Elsevier, vol. 115(C).

    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. Zhou, Shenghai & Li, Debiao & Yin, Yong, 2021. "Coordinated appointment scheduling with multiple providers and patient-and-physician matching cost in specialty care," Omega, Elsevier, vol. 101(C).
    2. Karmel S. Shehadeh & Amy E. M. Cohn & Ruiwei Jiang, 2021. "Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(1), pages 89-111, February.
    3. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    4. Oualid Jouini & Saif Benjaafar & Bingnan Lu & Siqiao Li & Benjamin Legros, 2022. "Appointment-driven queueing systems with non-punctual customers," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 1-56, June.
    5. Shenghai Zhou & Yichuan Ding & Woonghee Tim Huh & Guohua Wan, 2021. "Constant Job‐Allowance Policies for Appointment Scheduling: Performance Bounds and Numerical Analysis," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2211-2231, July.
    6. Jiang, Bowen & Tang, Jiafu & Yan, Chongjun, 2019. "A stochastic programming model for outpatient appointment scheduling considering unpunctuality," Omega, Elsevier, vol. 82(C), pages 70-82.
    7. Christos Zacharias & Tallys Yunes, 2020. "Multimodularity in the Stochastic Appointment Scheduling Problem with Discrete Arrival Epochs," Management Science, INFORMS, vol. 66(2), pages 744-763, February.
    8. Alex Kuiper & Robert H. Lee, 2022. "Appointment Scheduling for Multiple Servers," Management Science, INFORMS, vol. 68(10), pages 7422-7440, October.
    9. Avishai Mandelbaum & Petar Momčilović & Nikolaos Trichakis & Sarah Kadish & Ryan Leib & Craig A. Bunnell, 2020. "Data-Driven Appointment-Scheduling Under Uncertainty: The Case of an Infusion Unit in a Cancer Center," Management Science, INFORMS, vol. 66(1), pages 243-270, January.
    10. Pan, Xingwei & Geng, Na & Xie, Xiaolan, 2021. "Appointment scheduling and real-time sequencing strategies for patient unpunctuality," European Journal of Operational Research, Elsevier, vol. 295(1), pages 246-260.
    11. Kuiper, Alex & de Mast, Jeroen & Mandjes, Michel, 2021. "The problem of appointment scheduling in outpatient clinics: A multiple case study of clinical practice," Omega, Elsevier, vol. 98(C).
    12. Ahmadi-Javid, Amir & Jalali, Zahra & Klassen, Kenneth J, 2017. "Outpatient appointment systems in healthcare: A review of optimization studies," European Journal of Operational Research, Elsevier, vol. 258(1), pages 3-34.
    13. Ruiwei Jiang & Siqian Shen & Yiling Zhang, 2017. "Integer Programming Approaches for Appointment Scheduling with Random No-Shows and Service Durations," Operations Research, INFORMS, vol. 65(6), pages 1638-1656, December.
    14. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    15. Shehadeh, Karmel S. & Cohn, Amy E.M. & Jiang, Ruiwei, 2020. "A distributionally robust optimization approach for outpatient colonoscopy scheduling," European Journal of Operational Research, Elsevier, vol. 283(2), pages 549-561.
    16. Shuwan Zhu & Wenjuan Fan & Shanlin Yang & Jun Pei & Panos M. Pardalos, 2019. "Operating room planning and surgical case scheduling: a review of literature," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 757-805, April.
    17. Shan Wang & Nan Liu & Guohua Wan, 2020. "Managing Appointment-Based Services in the Presence of Walk-in Customers," Management Science, INFORMS, vol. 66(2), pages 667-686, February.
    18. Shen, Zuo-Jun Max & Xie, Jingui & Zheng, Zhichao & Zhou, Han, 2023. "Dynamic scheduling with uncertain job types," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1047-1060.
    19. Esmaeil Keyvanshokooh & Pooyan Kazemian & Mohammad Fattahi & Mark P. Van Oyen, 2022. "Coordinated and Priority‐Based Surgical Care: An Integrated Distributionally Robust Stochastic Optimization Approach," Production and Operations Management, Production and Operations Management Society, vol. 31(4), pages 1510-1535, April.
    20. Creemers, Stefan & Lambrecht, Marc R. & Beliën, Jeroen & Van den Broeke, Maud, 2021. "Evaluation of appointment scheduling rules: A multi-performance measurement approach," Omega, Elsevier, vol. 100(C).

    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:eee:jomega:v:106:y:2022:i:c:s0305048321001328. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.