IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i3p918-937.html
   My bibliography  Save this article

A Sequential Follower Refinement Algorithm for Robust Surgery Scheduling

Author

Listed:
  • Ankit Bansal

    (Department of Systems Science and Industrial Engineering, State University of New York, Binghamton, New York 13902)

  • Jean-Philippe Richard

    (Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455)

  • Bjorn P. Berg

    (Division of Health Policy and Management, School of Public Health, University of Minnesota, Minneapolis, Minnesota 55455)

  • Yu-Li Huang

    (Robert D. and Patricia E. Kern Center for the Science of Healthcare Delivery, Mayo Clinic, Rochester, Minnesota 55905)

Abstract

An algorithm for the two-stage robust optimization surgery-to-operating room allocation problem is presented. The second-stage problem is an integer linear program whose convex hull is approximated using three types of specialized valid inequalities and Chvátal-Gomory cuts. The resulting linear relaxation of the second-stage problem is then dualized and integrated into the first-stage problem. The resulting mixed integer linear program, which is an approximation of the original problem, is then solved using a commercial solver. If the solution of this model is not optimal for the second-stage problem, valid inequalities for the second-stage problem are generated, yielding a type of column-generation based approach that we refer to as the sequential follower refinement ( SFR ) algorithm. Data from an academic medical center are used to compare the computational performance of SFR with the constraint and column generation ( C&CG ) algorithm, which is the only exact approach that has been specifically applied for this problem in the literature. An extensive numerical study of SFR and its computational characteristics is presented that shows that SFR yields better-quality solutions compared with C&CG , even as the termination criterion of SFR is met much sooner, especially for problems involving higher number of surgeries.

Suggested Citation

  • Ankit Bansal & Jean-Philippe Richard & Bjorn P. Berg & Yu-Li Huang, 2024. "A Sequential Follower Refinement Algorithm for Robust Surgery Scheduling," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 918-937, May.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:918-937
    DOI: 10.1287/ijoc.2022.0191
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0191
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0191?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. Nan Liu & Van‐Anh Truong & Xinshang Wang & Brett R. Anderson, 2019. "Integrated Scheduling and Capacity Planning with Considerations for Patients’ Length‐of‐Stays," Production and Operations Management, Production and Operations Management Society, vol. 28(7), pages 1735-1756, July.
    2. Amir Ardestani-Jaafari & Erick Delage, 2021. "Linearized Robust Counterparts of Two-Stage Robust Optimization Problems with Applications in Operations Management," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1138-1161, July.
    3. Fügener, Andreas & Hans, Erwin W. & Kolisch, Rainer & Kortbeek, Nikky & Vanberkel, Peter T., 2014. "Master surgery scheduling with consideration of multiple downstream units," European Journal of Operational Research, Elsevier, vol. 239(1), pages 227-236.
    4. Shanshan Wang & Jinlin Li & Sanjay Mehrotra, 2021. "Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1661-1677, October.
    5. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.
    6. Sagnol, Guillaume & Barner, Christoph & Borndörfer, Ralf & Grima, Mickaël & Seeling, Matthes & Spies, Claudia & Wernecke, Klaus, 2018. "Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations," European Journal of Operational Research, Elsevier, vol. 271(2), pages 420-435.
    7. 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.
    8. Maya Bam & Brian T. Denton & Mark P. Van Oyen & Mark E. Cowen, 2017. "Surgery scheduling with recovery resources," IISE Transactions, Taylor & Francis Journals, vol. 49(10), pages 942-955, October.
    9. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    10. 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.
    11. 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.
    12. Vandenberghe, Mathieu & De Vuyst, Stijn & Aghezzaf, El-Houssaine & Bruneel, Herwig, 2019. "Surgery sequencing to minimize the expected maximum waiting time of emergent patients," European Journal of Operational Research, Elsevier, vol. 275(3), pages 971-982.
    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. Neyshabouri, Saba & Berg, Bjorn P., 2017. "Two-stage robust optimization approach to elective surgery and downstream capacity planning," European Journal of Operational Research, Elsevier, vol. 260(1), pages 21-40.
    15. 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.
    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.
    17. Yan Deng & Siqian Shen & Brian Denton, 2019. "Chance-Constrained Surgery Planning Under Conditions of Limited and Ambiguous Data," INFORMS Journal on Computing, INFORMS, vol. 31(3), pages 559-575, July.
    18. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2019. "A distributionally robust optimization approach for surgery block allocation," European Journal of Operational Research, Elsevier, vol. 273(2), pages 740-753.
    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. 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. Aisha Tayyab & Saif Ullah & Mohammed Fazle Baki, 2023. "An Outer Approximation Method for Scheduling Elective Surgeries with Sequence Dependent Setup Times to Multiple Operating Rooms," Mathematics, MDPI, vol. 11(11), pages 1-15, May.
    3. 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.
    4. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2019. "A distributionally robust optimization approach for surgery block allocation," European Journal of Operational Research, Elsevier, vol. 273(2), pages 740-753.
    5. 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.
    6. Wang, Yu & Zhang, Yu & Tang, Jiafu, 2024. "Wasserstein distributionally robust surgery scheduling with elective and emergency patients," European Journal of Operational Research, Elsevier, vol. 314(2), pages 509-522.
    7. Silva, Thiago A.O. & de Souza, Mauricio C., 2020. "Surgical scheduling under uncertainty by approximate dynamic programming," Omega, Elsevier, vol. 95(C).
    8. Santos, Daniel & Marques, Inês, 2022. "Designing master surgery schedules with downstream unit integration via stochastic programming," European Journal of Operational Research, Elsevier, vol. 299(3), pages 834-852.
    9. Jian-Jun Wang & Zongli Dai & Ai-Chih Chang & Jim Junmin Shi, 2022. "Surgical scheduling by Fuzzy model considering inpatient beds shortage under uncertain surgery durations," Annals of Operations Research, Springer, vol. 315(1), pages 463-505, August.
    10. van den Broek d’Obrenan, Anne & Ridder, Ad & Roubos, Dennis & Stougie, Leen, 2020. "Minimizing bed occupancy variance by scheduling patients under uncertainty," European Journal of Operational Research, Elsevier, vol. 286(1), pages 336-349.
    11. Hossein Hashemi Doulabi & Soheyl Khalilpourazari, 2023. "Stochastic weekly operating room planning with an exponential number of scenarios," Annals of Operations Research, Springer, vol. 328(1), pages 643-664, September.
    12. 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.
    13. 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.
    14. Yuan Shi & Saied Mahdian & Jose Blanchet & Peter Glynn & Andrew Y. Shin & David Scheinker, 2023. "Surgical scheduling via optimization and machine learning with long-tailed data," Health Care Management Science, Springer, vol. 26(4), pages 692-718, December.
    15. 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.
    16. Neyshabouri, Saba & Berg, Bjorn P., 2017. "Two-stage robust optimization approach to elective surgery and downstream capacity planning," European Journal of Operational Research, Elsevier, vol. 260(1), pages 21-40.
    17. Lu, Mengshi & Nakao, Hideaki & Shen, Siqian & Zhao, Lin, 2021. "Non-profit resource allocation and service scheduling with cross-subsidization and uncertain resource consumptions," Omega, Elsevier, vol. 99(C).
    18. Zhang, Jian & Dridi, Mahjoub & El Moudni, Abdellah, 2020. "Column-generation-based heuristic approaches to stochastic surgery scheduling with downstream capacity constraints," International Journal of Production Economics, Elsevier, vol. 229(C).
    19. Cheng Guo & Merve Bodur & Dionne M. Aleman & David R. Urbach, 2021. "Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1551-1569, October.
    20. Zhang, Jian & Dridi, Mahjoub & El Moudni, Abdellah, 2019. "A two-level optimization model for elective surgery scheduling with downstream capacity constraints," European Journal of Operational Research, Elsevier, vol. 276(2), pages 602-613.

    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:orijoc:v:36:y:2024:i:3:p:918-937. 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.