Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling

Cheng Guo (), Merve Bodur (), Dionne M. Aleman () and David R. Urbach ()
Additional contact information
Cheng Guo: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Dionne M. Aleman: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada; Institute of Health Policy, Management and Evaluation, University of Toronto, Toronto, Ontario M5S 3E3, Canada; Techna Institute at University Health Network, Toronto, Ontario M5G 1P5, Canada
David R. Urbach: Department of Surgery, University of Toronto, Toronto, Ontario M5S 3E3, Canada; Department of Surgery, Women’s College Hospital, Toronto, Ontario M5S 1B2, Canada

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1551-1569

Abstract: The distributed operating room (OR) scheduling problem aims to find an assignment of surgeries to ORs across collaborating hospitals that share their waiting lists and ORs. We propose a stochastic extension of this problem where surgery durations are considered to be uncertain. In order to obtain solutions for the challenging stochastic model, we use sample average approximation and develop two enhanced decomposition frameworks that use logic-based Benders (LBBD) optimality cuts and binary decision diagram based Benders cuts. Specifically, to the best of our knowledge, deriving LBBD optimality cuts in a stochastic programming context is new to the literature. Our computational experiments on a hospital data set illustrate that the stochastic formulation generates robust schedules and that our algorithms improve the computational efficiency. Summary of Contribution: We propose a new model for an important problem in healthcare scheduling, namely, stochastic distributed operating room scheduling, which is inspired by a current practice in Toronto, Ontario, Canada. We develop two decomposition methods that are computationally faster than solving the model directly via a state-of-the-art solver. We present both some theoretical results for our algorithms and numerical results for the evaluation of the model and algorithms. Compared with its deterministic counterpart in the literature, our model shows improvement in relevant evaluation metrics for the underlying scheduling problem. In addition, our algorithms exploit the structure of the model and improve its solvability. Those algorithms also have the potential to be used to tackle other planning and scheduling problems with a similar structure.

Keywords: distributed operating room scheduling; stochastic integer programming; logic-based Benders decomposition; binary decision diagram (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1036 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1551-1569

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().