IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v286y2020i1p49-62.html
   My bibliography  Save this article

Next-day operating room scheduling with uncertain surgery durations: Exact analysis and heuristics

Author

Listed:
  • Khaniyev, Taghi
  • Kayış, Enis
  • Güllü, Refik

Abstract

Operating rooms are units of particular interest in hospitals as they constitute more than 40% of total expenses and revenues. Managing operating rooms is challenging due to conflicting priorities and preferences of various stakeholders and the inherent uncertainty of surgery durations. In this study, we consider the next-day scheduling problem of a hospital operating room. Given the list and the sequence of non-identical surgeries to be performed in the next day, one needs to determine the scheduled durations of surgeries where the actual duration of each surgery is uncertain. Our objective is to minimize the weighted sum of expected patient waiting times, room idle time and overtime. First, we provide a reformulation of the objective function in terms of auxiliary functions with a recursive pattern that enables exact analysis of the optimal surgery durations at the expense of high CPU time. Next, we develop and analyze simple-to-use and close-to-optimal scheduling heuristics motivated by practice, for the OR managers to deploy in the field. Our proposed hybrid heuristic attains 1.22% average performance gap and worst average optimality gap of 2.77%. Our solution is easy to implement as it does not require any advanced optimization tool, which is the reality of many operating room environments.

Suggested Citation

  • Khaniyev, Taghi & Kayış, Enis & Güllü, Refik, 2020. "Next-day operating room scheduling with uncertain surgery durations: Exact analysis and heuristics," European Journal of Operational Research, Elsevier, vol. 286(1), pages 49-62.
  • Handle: RePEc:eee:ejores:v:286:y:2020:i:1:p:49-62
    DOI: 10.1016/j.ejor.2020.03.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720302162
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.03.002?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. Mehmet A. Begen & Maurice Queyranne, 2011. "Appointment Scheduling with Discrete Random Durations," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 240-257, May.
    2. Lamiri, Mehdi & Xie, Xiaolan & Dolgui, Alexandre & Grimaud, Frederic, 2008. "A stochastic model for operating room planning with elective and emergency demand for surgery," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1026-1037, March.
    3. Enis Kayış & Taghi Khaniyev & Jaap Suermondt & Karl Sylvester, 2015. "A robust estimation model for surgery durations with temporal, operational, and surgery team effects," Health Care Management Science, Springer, vol. 18(3), pages 222-233, September.
    4. Serhat Gul & Brian T. Denton & John W. Fowler, 2015. "A Progressive Hedging Approach for Surgery Planning Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 755-772, November.
    5. Sakine Batun & Brian T. Denton & Todd R. Huschka & Andrew J. Schaefer, 2011. "Operating Room Pooling and Parallel Surgery Processing Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 220-237, May.
    6. Yigal Gerchak & Diwakar Gupta & Mordechai Henig, 1996. "Reservation Planning for Elective Surgery Under Uncertain Demand for Emergency Surgery," Management Science, INFORMS, vol. 42(3), pages 321-334, March.
    7. Kim, Seung-Chul & Horowitz, Ira, 2002. "Scheduling hospital services: the efficacy of elective-surgery quotas," Omega, Elsevier, vol. 30(5), pages 335-346, October.
    8. Dongdong Ge & Guohua Wan & Zizhuo Wang & Jiawei Zhang, 2014. "A Note on Appointment Scheduling with Piecewise Linear Cost Functions," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1244-1251, November.
    9. Wang, P. Patrick, 1999. "Sequencing and scheduling N customers for a stochastic server," European Journal of Operational Research, Elsevier, vol. 119(3), pages 729-738, December.
    10. Cardoen, Brecht & Demeulemeester, Erik & Beliën, Jeroen, 2009. "Optimizing a multiple objective surgical case sequencing problem," International Journal of Production Economics, Elsevier, vol. 119(2), pages 354-366, June.
    11. Mehmet A. Begen & Retsef Levi & Maurice Queyranne, 2012. "Technical Note---A Sampling-Based Approach to Appointment Scheduling," Operations Research, INFORMS, vol. 60(3), pages 675-681, June.
    12. 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.
    13. Cardoen, Brecht & Demeulemeester, Erik & Beliën, Jeroen, 2010. "Operating room planning and scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 201(3), pages 921-932, March.
    14. P. Patrick Wang, 1993. "Static and dynamic scheduling of customer arrivals to a single‐server system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 345-360, April.
    15. Jianzhe Luo & Vidyadhar G. Kulkarni & Serhan Ziya, 2012. "Appointment Scheduling Under Patient No-Shows and Service Interruptions," Manufacturing & Service Operations Management, INFORMS, vol. 14(4), pages 670-684, October.
    16. Min, Daiki & Yih, Yuehwern, 2010. "Scheduling elective surgery under uncertainty and downstream capacity constraints," European Journal of Operational Research, Elsevier, vol. 206(3), pages 642-652, November.
    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. Sean Harris & David Claudio, 2022. "Current Trends in Operating Room Scheduling 2015 to 2020: a Literature Review," SN Operations Research Forum, Springer, vol. 3(1), pages 1-42, March.
    2. Tsai, Shing Chih & Yeh, Yingchieh & Kuo, Chen Yun, 2021. "Efficient optimization algorithms for surgical scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 579-593.
    3. Yanbo Ma & Kaiyue Liu & Zheng Li & Xiang Chen, 2022. "Robust Operating Room Scheduling Model with Violation Probability Consideration under Uncertain Surgery Duration," IJERPH, MDPI, vol. 19(20), pages 1-20, October.
    4. Çelik, Batuhan & Gul, Serhat & Çelik, Melih, 2023. "A stochastic programming approach to surgery scheduling under parallel processing principle," Omega, Elsevier, vol. 115(C).
    5. Şeyda Gür & Mehmet Pınarbaşı & Hacı Mehmet Alakaş & Tamer Eren, 2023. "Operating room scheduling with surgical team: a new approach with constraint programming and goal programming," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(4), pages 1061-1085, December.
    6. Shing Chih Tsai & Wu Hung Lin & Chia Cheng Wu & Shao Jen Weng & Ching Fen Tang, 2022. "Decision support algorithms for optimizing surgery start times considering the performance variation," Health Care Management Science, Springer, vol. 25(2), pages 208-221, June.

    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. Zhang, Yu & Wang, Yu & Tang, Jiafu & Lim, Andrew, 2020. "Mitigating overtime risk in tactical surgical scheduling," Omega, Elsevier, vol. 93(C).
    2. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2019. "Dynamic job assignment: A column generation approach with an application to surgery allocation," European Journal of Operational Research, Elsevier, vol. 272(1), pages 78-93.
    3. Michael Samudra & Carla Van Riet & Erik Demeulemeester & Brecht Cardoen & Nancy Vansteenkiste & Frank E. Rademakers, 2016. "Scheduling operating rooms: achievements, challenges and pitfalls," Journal of Scheduling, Springer, vol. 19(5), pages 493-525, October.
    4. Silva, Thiago A.O. & de Souza, Mauricio C., 2020. "Surgical scheduling under uncertainty by approximate dynamic programming," Omega, Elsevier, vol. 95(C).
    5. 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.
    6. 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.
    7. 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.
    8. Francesca Guerriero & Rosita Guido, 2011. "Operational research in the management of the operating theatre: a survey," Health Care Management Science, Springer, vol. 14(1), pages 89-114, March.
    9. 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.
    10. Sauré, Antoine & Patrick, Jonathan & Tyldesley, Scott & Puterman, Martin L., 2012. "Dynamic multi-appointment patient scheduling for radiation therapy," European Journal of Operational Research, Elsevier, vol. 223(2), pages 573-584.
    11. Gartner, Daniel & Kolisch, Rainer, 2014. "Scheduling the hospital-wide flow of elective patients," European Journal of Operational Research, Elsevier, vol. 233(3), pages 689-699.
    12. Gökalp, E. & Gülpınar, N. & Doan, X.V., 2023. "Dynamic surgery management under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(2), pages 832-844.
    13. Eun, Joonyup & Kim, Sang-Phil & Yih, Yuehwern & Tiwari, Vikram, 2019. "Scheduling elective surgery patients considering time-dependent health urgency: Modeling and solution approaches," Omega, Elsevier, vol. 86(C), pages 137-153.
    14. Anders Reenberg Andersen & Thomas Jacob Riis Stidsen & Line Blander Reinhardt, 2020. "Simulation-Based Rolling Horizon Scheduling for Operating Theatres," SN Operations Research Forum, Springer, vol. 1(2), pages 1-26, June.
    15. Mahdi Noorizadegan & Abbas Seifi, 2018. "An efficient computational method for large scale surgery scheduling problems with chance constraints," Computational Optimization and Applications, Springer, vol. 69(2), pages 535-561, March.
    16. 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.
    17. Yao Xiao & Reena Yoogalingam, 2021. "Reserved capacity policies for operating room scheduling," Operations Management Research, Springer, vol. 14(1), pages 107-122, June.
    18. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2016. "Dynamic job assignment: A column generation approach with an application to surgery allocation," Discussion Papers on Economics 4/2016, University of Southern Denmark, Department of Economics.
    19. Serhat Gul & Brian T. Denton & John W. Fowler, 2015. "A Progressive Hedging Approach for Surgery Planning Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 755-772, November.
    20. 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.

    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:ejores:v:286:y:2020:i:1:p:49-62. 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/locate/eor .

    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.