×

A value function-based approach for robust surgery planning. (English) Zbl 1511.90157

Summary: We present a value function-based formulation for solving a two-stage robust optimization model for surgery-to-OR allocation planning where only upper and lower bounds on surgery duration are known. We solve this formulation using a constraint and column generation algorithm and interpret it as an iterative bi-level interdiction game. We derive valid inequalities based in this interpretation and compare the computational performance of this algorithm with the only other exact solution approach in the literature using the data from an academic medical center. The value function-based formulation yields better or similar quality solutions on difficult problem instances with low or intermediate number of surgeries.

MSC:

90B35 Deterministic scheduling theory in operations research
90C17 Robustness in mathematical programming
91A80 Applications of game theory

Software:

ROME
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ardestani-Jaafari, A. & Delage, E. (2016). Linearized robust counterparts of two-stage robust optimization problems with applications in operations management. http://www.optimization-online.org/DB_FILE/2016/03/5388.pdf. · Zbl 1342.90222
[2] Bam, M.; Denton, B. T.; Van Oyen, M. P.; Cowen, M. E., Surgery scheduling with recovery resources, IISE Trans., 49, 942-955 (2017)
[3] Berg, B. P.; Denton, B. T.; Erdogan, S. A.; Rohleder, T.; Huschka, T., Optimal booking and scheduling in outpatient procedure centers, Comput. Oper. Res., 50, 24-37 (2014) · Zbl 1348.90341
[4] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Math. Program., 98, 49-71 (2003) · Zbl 1082.90067
[5] Cardoen, B.; Demeulemeester, E.; Beliën, J., Operating room planning and scheduling: a literature review, Eur. J. Oper. Res., 201, 921-932 (2010) · Zbl 1175.90160
[6] Deng, Y.; Shen, S.; Denton, B., Chance-constrained surgery planning under conditions of limited and ambiguous data, INFORMS J. Comput., 31, 559-575 (2019) · Zbl 1451.90075
[7] Denton, B. T.; Miller, A. J.; Balasubramanian, H. J.; Huschka, T. R., Optimal allocation of surgery blocks to operating rooms under uncertainty, Oper. Res., 58, 802-816 (2010) · Zbl 1228.90065
[8] Dexter, F., 2020. Bibliography of operating room management articles. https://www.franklindexter.net/bibliography_PredictingDuration.htm.
[9] Erdogan, S. A.; Denton, B., Surgery planning and scheduling, (Cochran, J.; Cox, L.; Keskinocak, P.; Kharoufeh, J.; Smith, J., Wiley Encyclopedia of Operations Research and Management Science (2011), John Wiley & Sons: John Wiley & Sons Hoboken, NJ)
[10] Ferrand, Y. B.; Magazine, M. J.; Rao, U. S., Managing operating room efficiency and responsiveness for emergency and elective surgeries-a literature survey, IIE Trans. Healthcare Syst. Eng., 4, 49-64 (2014)
[11] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., Interdiction games and monotonicity, with application to knapsack problems, INFORMS J. Comput., 31, 390-410 (2019) · Zbl 07281718
[12] Fügener, A.; Hans, E. W.; Kolisch, R.; Kortbeek, N.; Vanberkel, P. T., Master surgery scheduling with consideration of multiple downstream units, Eur. J. Oper. Res., 239, 227-236 (2014) · Zbl 1339.90132
[13] Goh, J.; Sim, M., Distributionally robust optimization and its tractable approximations, Oper. Res., 58, 902-917 (2010) · Zbl 1228.90067
[14] Guerriero, F.; Guido, R., Operational research in the management of the operating theatre: a survey, Health Care Manage. Sci., 14, 89-114 (2011)
[15] Gupta, D., Surgical suites’ operations management, Prod. Oper. Manage., 16, 689-700 (2007)
[16] Hall, M. J.; Schwartzman, A.; Zhang, J.; Liu, X., Ambulatory surgery data from hospitals and ambulatory surgery centers: United states, 2010, Nat. Health Stat. Rep., 102, 1-15 (2017)
[17] Hamid, M.; Hamid, M.; Musavi, M.; Azadeh, A., Scheduling elective patients based on sequence-dependent setup times in an open-heart surgical department using an optimization and simulation approach, Simulation, 95, 1141-1164 (2019)
[18] Hamid, M.; Nasiri, M. M.; Werner, F.; Sheikhahmadi, F.; Zhalechian, M., Operating room scheduling by considering the decision-making styles of surgical team members: a comprehensive approach, Comput. Oper. Res., 108, 166-181 (2019) · Zbl 1458.90301
[19] Kaye, D. R.; Luckenbaugh, A. N.; Oerline, M.; Hollenbeck, B. K.; Herrel, L. A.; Dimick, J. B.; Hollingsworth, J. M., Understanding the costs associated with surgical care delivery in the medicare population, Ann. Surg., 271, 23-28 (2020)
[20] Liu, N.; Truong, V.-A.; Wang, X.; Anderson, B. R., Integrated scheduling and capacity planning with considerations for patients’ length-of-stays, Prod. Oper. Manage., 28, 1735-1756 (2019)
[21] Lozano, L.; Smith, J. C., A value-function-based exact approach for the bilevel mixed-integer programming problem, Oper. Res., 65, 768-786 (2017) · Zbl 1387.90161
[22] Mannino, C.; Nilssen, E. J.; Nordlander, T. E., A pattern based, robust approach to cyclic master surgery scheduling, J. Sched., 15, 553-563 (2012)
[23] May, J. H.; Spangler, W. E.; Strum, D. P.; Vargas, L. G., The surgical scheduling problem: current research and future opportunities, Prod. Oper. Manage., 20, 392-405 (2011)
[24] May, J. H.; Strum, D. P.; Vargas, L. G., Fitting the lognormal distribution to surgical procedure times, Decis. Sci., 31, 129-148 (2000)
[25] Min, D.; Yih, Y., Scheduling elective surgery under uncertainty and downstream capacity constraints, Eur. J. Oper. Res., 206, 642-652 (2010) · Zbl 1188.90158
[26] Neyshabouri, S.; Berg, B. P., Two-stage robust optimization approach to elective surgery and downstream capacity planning, Eur. J. Oper. Res., 260, 21-40 (2017) · Zbl 1402.90059
[27] Rath, S.; Rajaram, K.; Mahajan, A., Integrated anesthesiologist and room scheduling for surgeries: methodology and application, Oper. Res., 65, 1460-1478 (2017) · Zbl 1386.90088
[28] Saadouli, H.; Jerbi, B.; Dammak, A.; Masmoudi, L.; Bouaziz, A., A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department, Comput. Ind. Eng., 80, 72-79 (2015)
[29] Shylo, O. V.; Prokopyev, O. A.; Schaefer, A. J., Stochastic operating room scheduling for high-volume specialties under block booking, INFORMS J. Comput., 25, 682-692 (2012)
[30] Tavaslíoğlu, O.; Prokopyev, O. A.; Schaefer, A. J., Solving stochastic and bilevel mixed-integer programs via a generalized value function, Oper. Res., 67, 1659-1677 (2019) · Zbl 1455.90110
[31] Wang, Y.; Zhang, Y.; Tang, J., A distributionally robust optimization approach for surgery block allocation, Eur. J. Oper. Res., 273, 740-753 (2019)
[32] Xiao, G.; van Jaarsveld, W.; Dong, M.; van de Klundert, J., Stochastic programming analysis and solutions to schedule overcrowded operating rooms in china, Comput. Oper. Res., 74, 78-91 (2016) · Zbl 1349.90449
[33] Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 457-461 (2013) · Zbl 1286.90143
[34] Zhang, Y.; Shen, S.; Erdogan, S. A., Solving 0-1 semidefinite programs for distributionally robust allocation of surgery blocks, Optim. Lett., 12, 1503-1521 (2018) · Zbl 1407.90246
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.