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

Reformulation, linearization, and decomposition techniques for balanced distributed operating room scheduling

Author

Listed:
  • Roshanaei, Vahid
  • Luong, Curtiss
  • Aleman, Dionne M.
  • Urbach, David R.

Abstract

We study the balanced distributed operating room (OR) scheduling (BDORS) problem as a location-allocation model, encompassing two levels of balancing decisions: (i) daily macro imbalance among collaborating hospitals in terms of the number of allocated ORs and (ii) daily micro imbalance among open ORs in each hospital in terms of the total caseload assigned. BDORS is formulated as a novel mixed-integer nonlinear programming (MINLP) in which the macro and micro imbalance are penalized using absolute value and quadratic functions. We develop various reformulation-linearization techniques (RLTs) for the MINLP models, leading to three mathematical modelling variants: (i) a mixed-integer quadratically constrained program (MIQCP) and (ii) two mixed-integer programs (MIPs) for the absolute value penalty function and an MIQCP for the quadratic penalty function. Two novel exact techniques based on reformulation-decomposition techniques (RDTs) are developed to solve these models: a uni- and a bi-level logic-based Benders decomposition (LBBD). We motivate the LBBD methods with an application to BDORS in the University Health Network (UHN), consisting of three collaborating hospitals: Toronto General Hospital, Toronto Western Hospital, and Princess Margaret Cancer Centre in Toronto, Ontario, Canada. The uni-level LBBD method decomposes the model into a surgical suite location, OR allocation, and macro balancing master problem (MP) and micro OR balancing sub-problems (SPs) for each hospital-day. The bi-level approach uses a relaxed MP, consisting of a surgical suite location and relaxed allocation/macro balancing MP and two optimization SPs. The primary SP is formulated as a bin-packing problem to allocate patients to open operating rooms to minimize the number of ORs, while the secondary SP is the uni-level micro balancing SP. Using UHN datasets consisting of two datasets, hard MP/easy SPs and easy MP/hard SPs, we show that both LBBD approaches and both MIP models solved via Gurobi converge to ≈ 2% and ≈ 1–2% optimality gaps, on average, respectively, within 30 minutes runtime, whereas the MIQCP solved via Gurobi could not solve any instance of the UHN datasets given the same runtime. The uni- and bi-level LBBD approaches solved all instances of hard MP/easy SPs dataset to ≈ 11% and ≈ 2% optimality gaps, on average, respectively, within 30 minutes runtime, whereas MIQCP solved via Gurobi could not solve any of these instances. Additionally, we show that convergence of each LBBD varies depending on where in the decomposition the actual computational complexity lies.

Suggested Citation

  • Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David R., 2020. "Reformulation, linearization, and decomposition techniques for balanced distributed operating room scheduling," Omega, Elsevier, vol. 93(C).
    • Handle: RePEc:eee:jomega:v:93:y:2020:i:c:s0305048317309015
    DOI: 10.1016/j.omega.2019.03.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048317309015
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2019.03.001?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. Vahid Roshanaei & Curtiss Luong & Dionne M. Aleman & David R. Urbach, 2017. "Collaborative Operating Room Planning and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 558-580, August.
    2. 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.
    3. H. Fei & C. Chu & N. Meskens, 2009. "Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria," Annals of Operations Research, Springer, vol. 166(1), pages 91-108, February.
    4. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    5. Naderi, Bahman & Ruiz, Rubén, 2014. "A scatter search algorithm for the distributed permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 323-334.
    6. Vijayakumar, Bharathwaj & Parikh, Pratik J. & Scott, Rosalyn & Barnes, April & Gallimore, Jennie, 2013. "A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital," European Journal of Operational Research, Elsevier, vol. 224(3), pages 583-591.
    7. Elena Tànfani & Angela Testi, 2010. "A pre-assignment heuristic algorithm for the Master Surgical Schedule Problem (MSSP)," Annals of Operations Research, Springer, vol. 178(1), pages 105-119, July.
    8. Bernard Gendron & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2014. "Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 645-657, November.
    9. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    10. Ivo Adan & Jos Bekkers & Nico Dellaert & Jan Vissers & Xiaoting Yu, 2009. "Patient mix optimisation and stochastic resource requirements: A case study in cardiothoracic surgery planning," Health Care Management Science, Springer, vol. 12(2), pages 129-141, June.
    11. Pablo Santibáñez & Mehmet Begen & Derek Atkins, 2007. "Surgical block scheduling in a system of hospitals: an application to resource and wait list management in a British Columbia health authority," Health Care Management Science, Springer, vol. 10(3), pages 269-282, September.
    12. Pham, Dinh-Nguyen & Klinkert, Andreas, 2008. "Surgical case scheduling as a generalized job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1011-1025, March.
    13. 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.
    14. Hooker, J.N., 1994. "Logic-Based Methods for Optimization: A Tutorial," GSIA Working Papers 1994-05, Carnegie Mellon University, Tepper School of Business.
    15. Wheatley, David & Gzara, Fatma & Jewkes, Elizabeth, 2015. "Logic-based Benders decomposition for an inventory-location problem with service constraints," Omega, Elsevier, vol. 55(C), pages 10-23.
    16. Tony T. Tran & Arthur Araujo & J. Christopher Beck, 2016. "Decomposition Methods for the Parallel Machine Scheduling Problem with Setups," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 83-95, February.
    17. Inês Marques & M. Captivo & Margarida Vaz Pato, 2015. "A bicriteria heuristic for an elective surgery scheduling problem," Health Care Management Science, Springer, vol. 18(3), pages 251-266, September.
    18. Seyed Hossein Hashemi Doulabi & Louis-Martin Rousseau & Gilles Pesant, 2016. "A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 432-448, August.
    19. Marcon, Eric & Kharraja, Said & Simonnet, Gerard, 2003. "The operating theatre planning by the follow-up of the risk of no realization," International Journal of Production Economics, Elsevier, vol. 85(1), pages 83-90, July.
    20. Riise, Atle & Mannino, Carlo & Lamorgese, Leonardo, 2016. "Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling," European Journal of Operational Research, Elsevier, vol. 255(3), pages 719-728.
    21. 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.
    22. 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.
    23. Jebali, AIda & Hadj Alouane, Atidel B. & Ladet, Pierre, 2006. "Operating rooms scheduling," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 52-62, February.
    24. Galvao, Roberto D. & Acosta Espejo, Luis Gonzalo & Boffey, Brian & Yates, Derek, 2006. "Load balancing and capacity constraints in a hierarchical location model," European Journal of Operational Research, Elsevier, vol. 172(2), pages 631-646, July.
    25. 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.
    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. Roshanaei, Vahid & Naderi, Bahman, 2021. "Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut," European Journal of Operational Research, Elsevier, vol. 293(1), pages 65-78.
    2. Shao, Kaining & Fan, Wenjuan & Lan, Shaowen & Kong, Min & Yang, Shanlin, 2023. "A column generation-based heuristic for brachytherapy patient scheduling with multiple treatment sessions considering radioactive source decay and time constraints," Omega, Elsevier, vol. 118(C).
    3. Li, Yantong & Côté, Jean-François & Coelho, Leandro C. & Zhang, Chuang & Zhang, Shuai, 2023. "Order assignment and scheduling under processing and distribution time uncertainty," European Journal of Operational Research, Elsevier, vol. 305(1), pages 148-163.
    4. Shahbazbegian, Vahid & Shafie-khah, Miadreza & Laaksonen, Hannu & Strbac, Goran & Ameli, Hossein, 2023. "Resilience-oriented operation of microgrids in the presence of power-to-hydrogen systems," Applied Energy, Elsevier, vol. 348(C).
    5. Hassan Zohali & Bahman Naderi & Vahid Roshanaei, 2022. "Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 315-332, January.

    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. Roshanaei, Vahid & Naderi, Bahman, 2021. "Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut," European Journal of Operational Research, Elsevier, vol. 293(1), pages 65-78.
    2. Roshanaei, Vahid & Booth, Kyle E.C. & Aleman, Dionne M. & Urbach, David R. & Beck, J. Christopher, 2020. "Branch-and-check methods for multi-level operating room planning and scheduling," International Journal of Production Economics, Elsevier, vol. 220(C).
    3. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    4. Vahid Roshanaei & Curtiss Luong & Dionne M. Aleman & David R. Urbach, 2017. "Collaborative Operating Room Planning and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 558-580, August.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Babak Akbarzadeh & Ghasem Moslehi & Mohammad Reisi-Nafchi & Broos Maenhout, 2020. "A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering," Journal of Scheduling, Springer, vol. 23(2), pages 265-288, April.
    10. 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).
    11. Bahman Naderi & Vahid Roshanaei & Mehmet A. Begen & Dionne M. Aleman & David R. Urbach, 2021. "Increased Surgical Capacity without Additional Resources: Generalized Operating Room Planning and Scheduling," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2608-2635, August.
    12. Silva, Thiago A.O. & de Souza, Mauricio C. & Saldanha, Rodney R. & Burke, Edmund K., 2015. "Surgical scheduling with simultaneous employment of specialised human resources," European Journal of Operational Research, Elsevier, vol. 245(3), pages 719-730.
    13. Riise, Atle & Mannino, Carlo & Lamorgese, Leonardo, 2016. "Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling," European Journal of Operational Research, Elsevier, vol. 255(3), pages 719-728.
    14. Akbarzadeh, Babak & Moslehi, Ghasem & Reisi-Nafchi, Mohammad & Maenhout, Broos, 2019. "The re-planning and scheduling of surgical cases in the operating room department after block release time with resource rescheduling," European Journal of Operational Research, Elsevier, vol. 278(2), pages 596-614.
    15. 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.
    16. 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.
    17. Zhang, Yu & Wang, Yu & Tang, Jiafu & Lim, Andrew, 2020. "Mitigating overtime risk in tactical surgical scheduling," Omega, Elsevier, vol. 93(C).
    18. Javiera Barrera & Rodrigo A. Carrasco & Susana Mondschein & Gianpiero Canessa & David Rojas-Zalazar, 2020. "Operating room scheduling under waiting time constraints: the Chilean GES plan," Annals of Operations Research, Springer, vol. 286(1), pages 501-527, March.
    19. Shuwan Zhu & Wenjuan Fan & Tongzhu Liu & Shanlin Yang & Panos M. Pardalos, 2020. "Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs," Journal of Combinatorial Optimization, Springer, vol. 39(1), pages 185-215, January.
    20. Marques, Inês & Captivo, M. Eugénia, 2017. "Different stakeholders’ perspectives for a surgical case assignment problem: Deterministic and robust approaches," European Journal of Operational Research, Elsevier, vol. 261(1), pages 260-278.

    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:93:y:2020:i:c:s0305048317309015. 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.