Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling

Vahid Roshanaei, Curtiss Luong, Dionne M. Aleman and David Urbach

European Journal of Operational Research, 2017, vol. 257, issue 2, 439-455

Abstract: We develop three novel logic-based Benders’ decomposition (LBBD) approaches and a cut propagation mechanism to solve large-scale location-allocation integer programs (IPs). We show that each LBBD can be implemented in four different possible ways, yielding distinct LBBD variants with completely different computational performances. LBBDs decompose the IP model into an integer location and knapsack-based allocation master problem and multiple packing IP sub-problems. We illustrate the performance of our LBBDs on the distributed operating room (OR) scheduling (DORS) problem, where patients and ORs are collaboratively scheduled across a network of hospitals, and the goal is to select patients with the highest priority scores and schedule them in the current planning horizon, while determining the number of surgical suites and operating rooms required to accommodate the schedule at minimum cost. We quantitatively demonstrate that the new Benders’ cuts, cut propagation, and implementation can individually or collectively yield a computational time impact of at least two orders of magnitude. We also demonstrate that our LBBDs are 10–100x faster than IP+Gurobi and are more successful at finding optimal solutions. Finally, we show that DORS increases the average OR utilization across the network to more than 95%.

Keywords: Distributed operating room scheduling; Logic-based Benders’ decomposition; Cut strength; Propagation; Implementation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716306609
Full text for ScienceDirect subscribers only

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:eee:ejores:v:257:y:2017:i:2:p:439-455

DOI: 10.1016/j.ejor.2016.08.024

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().