×

Surgery sequencing to minimize the expected maximum waiting time of emergent patients. (English) Zbl 1430.90304

Summary: This paper investigates the problem of surgery sequencing under uncertain surgery durations, with the objective of minimizing the expected maximum waiting time that emergent patients may endure before an operating room becomes available. Given the sets of surgeries assigned to each operating room as well as the distribution of each surgery’s duration, we aim to find the room sequences that minimize the expected largest interval between consecutive completion times. To solve the resulting stochastic optimization problem called the stochastic break-in moment problem (SBIM), we implement a new MILP based on sample average approximation. An algorithm that more intelligently segments the search further improves performance. We also create a variance-based heuristic and adapt a variety of local search methods to the SBIM case. Numerical experiments based on a surgery scheduling benchmark set show that stochastic solution methods outperform their deterministic counterparts, and highlight the value of the stochastic solution.

MSC:

90B36 Stochastic scheduling theory in operations research
90C15 Stochastic programming
90B35 Deterministic scheduling theory in operations research

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addis, B.; Carello, G.; Grosso, A.; Tànfani, E., Operating room scheduling and rescheduling: A rolling horizon approach, Flexible Services and Manufacturing Journal, 28, 1-2, 206-232 (2016)
[2] Birge, J. R.; Louveaux, F., Introduction to stochastic programming (2011), Springer · Zbl 1223.90001
[3] Brucker, P., Scheduling algorithms (2007), Springer-Verlag · Zbl 1126.90001
[4] Cardoen, B.; Demeulemeester, E.; Beliën, J., Optimizing a multiple objective surgical case sequencing problem, International Journal of Production Economics, 119, 2, 354-366 (2009)
[5] Cardoen, B.; Demeulemeester, E.; Belien, J., Operating room planning and scheduling: A literature review, European Journal of Operational Research, 201, 3, 921-932 (2010) · Zbl 1175.90160
[6] Cardoen, B.; Demeulemeester, E.; van der Hoeven, J., On the use of planning models in the operating theatre: Results of a survey in Flanders, International Journal of Health Planning and Management, 25, 400-414 (2010)
[7] Ceschia, S.; Schaerf, A., Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays, Journal of Scheduling, 19, 4, 377-389 (2016) · Zbl 1347.90036
[8] Denton, B.; Viapiano, J.; Vogl, A., Optimising sequencing under uncertainty, Health Care Management Science, 10, 1, 13-24 (2007)
[9] Eitel, D.; Travers, D. A.; Rosenau, A. M.; Gilboy, N.; Wuerz, R. C., The emergency severity index triage algorithm version 2 is reliable and valid, Academic Emergency Medicine, 10, 10, 1070-1080 (2003)
[10] Ferrand, Y.; Magazine, M.; Rao, U., Comparing two operating-room-allocation policies for elective and emergency surgeries, Proceedings of the 2010 winter simulation conference, 2364-2374 (2010)
[11] Ferrand, Y. B.; Magazine, M. J.; Rao, U. S., Partially flexible operating rooms for elective and emergency surgeries, Decision Sciences, 45, 5, 819-847 (2014)
[12] Fleet, R.; Poitras, J., Have we killed the golden hour of trauma?, Annals of Emergency Medicine, 57, 1, 73-74 (2011)
[13] Gartner, D.; Kolisch, R., Scheduling the hospital-wide flow of elective patients, European Journal of Operational Research, 233, 3, 689-699 (2014) · Zbl 1339.90134
[14] Glouberman, S.; Mintzberg, H., Managing the care of health and the cure of disease - Part I: Differentiation, Health Care Management Review, 26, 56-69;discussion 87 (2001)
[15] Glover, F., Tabu Search - Part I, ORSA Journal on Computing, 2 1, 3, 4-32 (1989)
[16] Guerriero, F.; Guido, R., Operational research in the management of the operating theatre: A survey, Health Care Management Science, 14, 1, 89-114 (2011)
[17] Gurobi Optimization, Inc. (2018) Gurobi optimizer reference manual. Available at: http://www.gurobi.com/; Gurobi Optimization, Inc. (2018) Gurobi optimizer reference manual. Available at: http://www.gurobi.com/
[18] Haraden, C.; Resar, R., Patient flow in hospitals: Understanding and controlling it better, Frontiers of Health Services Management, 20, 3-15 (2004)
[19] Jebali, A.; Diabat, A., A stochastic model for operating room planning under capacity constraints, International Journal of Production Research, 53, 24, 7252-7270 (2015)
[20] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[21] Kleywegt, A. J.; Shapiro, A.; Homem-de Mello, T., Sample average approximation method for stochastic discrete optimization, SIAM Journal on Optimization, 12, 2, 479-502 (2002) · Zbl 0991.90090
[22] Lamiri, M.; Xie, X.; Dolgui, A.; Grimaud, F., A stochastic model for operating room planning with elective and emergency demand for surgery, European Journal of Operational Research, 185, 3, 1026-1037 (2008) · Zbl 1175.90446
[23] Landa, P.; Aringhieri, R.; Soriano, P.; Tànfani, E.; Testi, A., A hybrid optimization algorithm for surgeries scheduling, Operations Research for Health Care, 8, 103-114 (2016)
[24] Latorre-Núñez, G.; Lüer-Villagra, A.; Marianov, V.; Obreque, C.; Ramis, F.; Neriz, L., Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries, Computers and Industrial Engineering, 97, 248-257 (2016)
[25] Leeftink, G.; Hans, E. W., Case mix classification and a benchmark set for surgery scheduling, Journal of Scheduling, 21, 1, 17-33 (2018) · Zbl 06974913
[26] Min, D.; Yih, Y., Scheduling elective surgery under uncertainty and downstream capacity constraints, European Journal of Operational Research, 206, 3, 642-652 (2010) · Zbl 1188.90158
[27] Newgard, C. D.; Schmicker, R. H.; Hedges, J. R.; Trickett, J. P.; Davis, D. P.; Bulger, E. M., Emergency medical services intervals and survival in trauma: Assessment of the “Golden Hour” in a North American prospective cohort, Annals of Emergency Medicine, 55, 3, 235-246 (2010)
[28] Rachuba, S.; Werners, B., A fuzzy multi-criteria approach for robust operating room schedules, Annals of Operations Research, 251, 1-2, 325-350 (2017) · Zbl 1370.90125
[29] Spangler, W. E.; Strum, D. P.; Vargas, L. G.; May, J. H., Estimating procedure times for surgeries by determining location parameters for the lognormal model, Health Care Management Science, 7, 2, 97-104 (2004)
[30] Stepaniak, P. S.; Heij, C.; De Vries, G., Modeling and prediction of surgical procedure times, Statistica Neerlandica, 64, 1, 1-18 (2010)
[31] Strum, D. P.; May, J.; Vargas, L. G., Modeling the uncertainty of surgical procedure times, Anesthesiology, 92, 4, 1160-1167 (2000)
[32] van Essen, J. T.; Hans, E. W.; Hurink, J. L.; Oversberg, A., Minimizing the waiting time for emergency surgery, Operations Research for Health Care, 1, 2-3, 34-44 (2012)
[33] van Riet, C.; Demeulemeester, E., Trade-offs in operating room planning for electives and emergencies: A review, Operations Research for Health Care, 7, 52-69 (2015)
[34] Wullink, G.; van Houdenhoven, M.; Hans, E. W.; van Oostrum, J. M.; van Der Lans, M.; Kazemier, G., Closing emergency operating rooms improves efficiency, Journal of Medical Systems, 31, 6, 543-546 (2007)
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.