IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v68y2021i1p89-111.html
   My bibliography  Save this article

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

Author

Listed:
  • Karmel S. Shehadeh
  • Amy E. M. Cohn
  • Ruiwei Jiang

Abstract

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.

Suggested Citation

  • 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.
  • Handle: RePEc:wly:navres:v:68:y:2021:i:1:p:89-111
    DOI: 10.1002/nav.21933
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21933
    Download Restriction: no

    File URL: https://libkey.io/10.1002/nav.21933?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. 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.
    2. 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.
    3. Uri Gneezy & Stephan Meier & Pedro Rey-Biel, 2011. "When and Why Incentives (Don't) Work to Modify Behavior," Journal of Economic Perspectives, American Economic Association, vol. 25(4), pages 191-210, Fall.
    4. 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.
    5. 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.
    6. 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.
    7. Jose M. Molina-Pariente & Erwin W. Hans & Jose M. Framinan, 2018. "A stochastic approach for solving the operating room scheduling problem," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 224-251, June.
    8. Peter A. Salzarulo & Stephen Mahar & Sachin Modi, 2016. "Beyond Patient Classification: Using Individual Patient Characteristics in Appointment Scheduling," Production and Operations Management, Production and Operations Management Society, vol. 25(6), pages 1056-1072, June.
    9. Rohleder, Thomas R. & Klassen, Kenneth J., 2000. "Using client-variance information to improve dynamic appointment scheduling performance," Omega, Elsevier, vol. 28(3), pages 293-302, June.
    10. 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.
    11. 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.
    12. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    13. Diwakar Gupta & Wen-Ya Wang, 2012. "Patient Appointments in Ambulatory Care," International Series in Operations Research & Management Science, in: Randolph Hall (ed.), Handbook of Healthcare System Scheduling, chapter 0, pages 65-104, Springer.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    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. Wu, Xueqi & Zhou, Shenghai, 2022. "Sequencing and scheduling appointments on multiple servers with stochastic service durations and customer arrivals," Omega, Elsevier, vol. 106(C).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Seokjun Youn & H. Neil Geismar & Michael Pinedo, 2022. "Planning and scheduling in healthcare for better care coordination: Current understanding, trending topics, and future opportunities," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4407-4423, December.
    8. 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).
    9. Tugba Cayirli & Kum Khiong Yang, 2019. "Altering the Environment to Improve Appointment System Performance," Service Science, INFORMS, vol. 11(2), pages 138-154, June.
    10. 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.
    11. Miao Bai & Robert H. Storer & Gregory L. Tonkay, 2022. "Surgery Sequencing Coordination with Recovery Resource Constraints," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1207-1223, March.
    12. 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.
    13. 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.
    14. 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.
    15. Miao Bai & Bjorn Berg & Esra Sisikoglu Sir & Mustafa Y. Sir, 2023. "Partially partitioned templating strategies for outpatient specialty practices," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 301-318, January.
    16. Shehadeh, Karmel S. & Padman, Rema, 2021. "A distributionally robust optimization approach for stochastic elective surgery scheduling with limited intensive care unit capacity," European Journal of Operational Research, Elsevier, vol. 290(3), pages 901-913.
    17. Tsang, Man Yiu & Shehadeh, Karmel S., 2023. "Stochastic optimization models for a home service routing and appointment scheduling problem with random travel and service times," European Journal of Operational Research, Elsevier, vol. 307(1), pages 48-63.
    18. 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.
    19. 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).
    20. Golmohammadi, Davood & Zhao, Lingyu & Dreyfus, David, 2023. "Using machine learning techniques to reduce uncertainty for outpatient appointment scheduling practices in outpatient clinics," Omega, Elsevier, vol. 120(C).

    More about this item

    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:wly:navres:v:68:y:2021:i:1:p:89-111. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.