×

Collaborative operating room planning and scheduling. (English) Zbl 1386.90062

Summary: Operating rooms (ORs) play a substantial role in hospital profitability, and their optimal utilization is conducive to containing the cost of surgical service delivery, shortening surgical patient wait times, and increasing patient admissions. We extend the OR planning and scheduling problem from a single independent hospital to a coalition of multiple hospitals in a strategic network, where a pool of patients, surgeons, and ORs are collaboratively planned. To solve the resulting mixed-integer dual resource constrained model, we develop a novel logic-based Benders’ decomposition approach that employs an allocation master problem, sequencing sub-problems for each hospital-day, and novel multistrategy Benders’ feasibility and optimality cuts. We investigate various patient-to-surgeon allocation flexibilities, as well as the impact of surgeon schedule tightness. Using real data obtained from the General Surgery Departments of the University Health Network (UHN) hospitals, consisting of Toronto General Hospital, Toronto Western Hospital, and Princess Margret Cancer Centre in Toronto, Ontario, Canada (who already engage in some collaborative resource sharing), we find that on average, collaborative OR scheduling with traditional patient-to-surgeon allocation flexibility results in 6% cost-savings, while flexible patient-to-surgeon allocation flexibility increases cost-savings to 40%, and surgeon schedule tightness can impact costs by 15%. The collective impact of our collaboration and patient flexibility results in between 45% and 63% savings per surgery. We also use a game theoretic approach to fairly redistribute the payoff acquired from a coalition of hospitals and to empirically show coalitional stability among hospitals.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
91A12 Cooperative games
Full Text: DOI

References:

[1] Agee MD, Zane G (2013) Lessons from game theory about healthcare system price inflation. Appl. Health Econom. Health Policy 11(1):45-51.Crossref, Google Scholar · doi:10.1007/s40258-012-0003-z
[2] Batun S, Denton BT, Huschka TR, Schaefer AJ (2011) Operating room pooling and parallel surgery processing under uncertainty. INFORMS J. Comput. 23(2):220-237.Link, Google Scholar · Zbl 1243.90102
[3] Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238-252.Crossref, Google Scholar · Zbl 0109.38302 · doi:10.1007/BF01386316
[4] Cardoen B, Demeulemeester E, Belien J (2010) Operating room planning and scheduling: A literature review. Eur. J. Oper. Res. 201(3):921-932.Crossref, Google Scholar · Zbl 1175.90160 · doi:10.1016/j.ejor.2009.04.011
[5] Chan TCY, Demirtas D, Kwon RH (2016) Optimizing the deployment of public access defibrillators. Management Sci. 62(12):3617-3635.Link, Google Scholar
[6] Chaudhry IA, Drake PR (2009) Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms. Internat. J. Adv. Manufacturing Tech. 42(5-6):581-594.Crossref, Google Scholar · doi:10.1007/s00170-008-1617-z
[7] Chu Y, Xia Q (2004) Generating Benders cuts for a general class of integer programming problems. Régin J-C, Rueher M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 3011 (Springer, Berlin), 127-141.Crossref, Google Scholar · Zbl 1094.90578 · doi:10.1007/978-3-540-24664-0_9
[8] Clinical Advisory Board (2001) Surgical services reform: Executive briefing for clinical leaders. Technical report, Advisory Board Company, Washington, DC.Google Scholar
[9] Day R, Garfinkel R, Thompson S (2012) Integrated block sharing: A win-win strategy for hospitals and surgeons. Manufacturing Service Oper. Management 14(4):567-583.Link, Google Scholar
[10] Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4, Pt. 1):802-816.Link, Google Scholar · Zbl 1228.90065
[11] ElMaraghy H, Patel V, Abdallah IB (1999) Genetic algorithm based approach for scheduling of dual-resource constrained manufacturing systems. CIRP Ann.—Manufacturing Tech. 48(1):369-372.Crossref, Google Scholar · doi:10.1016/S0007-8506(07)63204-1
[12] ElMaraghy H, Patel V, Abdallah IB (2000) Scheduling of manufacturing systems under dual-resource constraints using genetic algorithms. J. Manufacturing Systems 19(3):186-201.Crossref, Google Scholar · doi:10.1016/S0278-6125(00)80011-4
[13] Fazel-Zarandi MM, Beck JC (2012) Using logic-based Benders decomposition to solve the capacity- and distance-constrained plant location problem. INFORMS J. Comput. 24(3):387-398.Link, Google Scholar · Zbl 1462.90065
[14] Fei H, Chu C, Meskens N (2009) Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria. Ann. Oper. Res. 166(1):91-108.Crossref, Google Scholar · Zbl 1163.90487 · doi:10.1007/s10479-008-0413-3
[15] Fei H, Meskens N, Chu C (2010) A planning and scheduling problem for an operating theatre using an open scheduling strategy. Comput. Indust. Engrg. 58(2):221-230.Crossref, Google Scholar · doi:10.1016/j.cie.2009.02.012
[16] Fei H, Chu C, Meskens N, Artiba A (2008) Solving surgical cases assignment problem by a branch-and-price approach. Internat. J. Production Econom. 112(1):96-108.Crossref, Google Scholar · doi:10.1016/j.ijpe.2006.08.030
[17] Guerriero F, Guido R (2011) Operational research in the management of the operating theatre: A survey. Health Care Management Sci. 14(1):89-114.Crossref, Google Scholar · doi:10.1007/s10729-010-9143-6
[18] Guinet A, Chaabane S (2003) Operating theatre planning. Internat. J. Production Econom. 85(1):69-81.Crossref, Google Scholar · doi:10.1016/S0925-5273(03)00087-2
[19] Harjunkoski I, Grossmann IE (2002) Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods. Comput. Chemical Engrg. 26(11):1533-1552.Crossref, Google Scholar · doi:10.1016/S0098-1354(02)00100-X
[20] Hashemi Doulabi SH, Rousseau L-M, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28(3):432-448.Link, Google Scholar · Zbl 1348.90271
[21] Health Care Financial Management Association (2005) Achieving operating room efficiency through process integration. Technical report, Health Care Financial Management Association, Westchester, IL.Google Scholar
[22] Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588-602.Link, Google Scholar · Zbl 1167.90512
[23] Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33-60.Crossref, Google Scholar · Zbl 1023.90082 · doi:10.1007/s10107-003-0375-9
[24] Jebali A, Alouane ABH, Ladet P (2006) Operating rooms scheduling. Internat. J. Production Econom. 99(1-2):52-62.Crossref, Google Scholar · doi:10.1016/j.ijpe.2004.12.006
[25] Lei D, Guo X (2014) Variable neighbourhood search for dual-resource constrained flexible job shop scheduling. Internat. J. Production Res. 52(9):2519-2529.Crossref, Google Scholar · doi:10.1080/00207543.2013.849822
[26] Leng M, Parlar M (2009) Allocation of cost savings in a three-level supply chain with demand information sharing: A cooperative-game approach. Ann. Oper. Res. 57(1):200-213.Link, Google Scholar · Zbl 1181.90015
[27] Marques I, Captivo ME, Margarida VP (2012) An integer programming approach to elective surgery scheduling. OR Spectrum 34(2):407-427.Crossref, Google Scholar · Zbl 1239.90065 · doi:10.1007/s00291-011-0279-7
[28] Naderi B, Azab A (2014) Modeling and heuristics for scheduling of distributed job shops. Expert Systems Appl. 41(17):7754-7763.Crossref, Google Scholar · doi:10.1016/j.eswa.2014.06.023
[29] Naderi B, Ruiz R (2010) The distributed permutation flowshop scheduling problem. Comput. Oper. Res. 37(4):754-768.Crossref, Google Scholar · Zbl 1176.90237 · doi:10.1016/j.cor.2009.06.019
[30] Naderi B, Ruiz R (2014) A scatter search algorithm for the distributed permutation flowshop scheduling problem. Eur. J. Oper. Res. 239(2):323-334.Crossref, Google Scholar · Zbl 1339.90145 · doi:10.1016/j.ejor.2014.05.024
[31] Nelsen RB (2006) An Introduction to Copulas, Springer Series in Statistics (Springer, New York).Google Scholar · Zbl 1152.62030
[32] Neumann JV, Morgenstern O (1944) An Introduction to Copulas, Springer Series in Statistics (Princeton University Press, Princeton, NJ).Google Scholar · Zbl 0063.05930
[33] Pham DN, Klinkert A (2008) Surgical case scheduling as a generalized job shop scheduling problem. Eur. J. Oper. Res. 185(3):1011-1025.Crossref, Google Scholar · Zbl 1146.90420 · doi:10.1016/j.ejor.2006.03.059
[34] Roland B, Di Martinelly C, Riane F, Pochet Y (2010) Scheduling an operating theatre under human resource constraints. Comput. Indust. Engrg. 58(2):212-220.Crossref, Google Scholar · doi:10.1016/j.cie.2009.01.005
[35] Roshanaei V, Luong C, Aleman D, Urbach D (2017) Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling. Eur. J. Oper. Res. 257(2):439-455.Crossref, Google Scholar · Zbl 1394.90302 · doi:10.1016/j.ejor.2016.08.024
[36] Ruiz-Torres AJ, Centeno G (2007) Scheduling with flexible resources in parallel workcenters to minimize maximum completion time. Comput. Oper. Res. 34(1):48-69.Crossref, Google Scholar · Zbl 1102.90027 · doi:10.1016/j.cor.2005.02.042
[37] Samudra M, Van Riet C, Demeulemeester E, Cardoen B, Vansteenkiste N, Rademakers FE (2016) Scheduling operating rooms: Achievements, challenges and pitfalls. J. Scheduling 19(5):493-525.Crossref, Google Scholar · Zbl 1353.90067 · doi:10.1007/s10951-016-0489-6
[38] Santibanez P, Begen M, Atkins D (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 Sci. 10(3):269-282.Crossref, Google Scholar · doi:10.1007/s10729-007-9019-6
[39] Shapley LS (1953) A value for n-person games. Ann. Math. Stud. 28(2):307-317.Google Scholar · Zbl 0050.14404
[40] Shapley LS (1971) Cores of convex games. Internat. J. Game Theory 1(1):11-26.Crossref, Google Scholar · Zbl 0222.90054 · doi:10.1007/BF01753431
[41] Sheater SJ, Jones MC (1991) A reliable data-based bandwidth selection method for kernel density estimation. J. Roy. Statist. Soc. Res. 53(3):683-690.Google Scholar · Zbl 0800.62219
[42] Tran TT, Beck JC (2012) Logic-based Benders decomposition for alternative resource scheduling with sequence dependent setups. De Raedt L, Dubois D, Bessiere C, eds. ECAI’12 Proc. 20th Eur. Conf. Artificial Intelligence (IOS Press, Amsterdam), 774-779.Google Scholar · Zbl 1327.90075
[43] Tran TT, Araujo A, Beck JC (2016) Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28(1):83-95.Link, Google Scholar · Zbl 1338.90184
[44] Vijayakumar B, Parikh PJ, Scott R, Barnes A, Gallimore J (2013) A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital. Eur. J. Oper. Res. 224(3):583-591.Crossref, Google Scholar · Zbl 1292.90126 · doi:10.1016/j.ejor.2012.09.010
[45] Wand MP, Jones MC (1995) Kernel Smoothing (Chaplan & Hall/CRC, Boca Raton, FL).Crossref, Google Scholar · doi:10.1007/978-1-4899-4493-1
[46] Wang S, Roshanaei V, Aleman D, Urbach D (2016) A discrete event simulation evaluation of distributed operating room scheduling. IIE Trans. Healthcare Systems Engrg. 6(4):236-245.Crossref, Google Scholar · doi:10.1080/19488300.2016.1226994
[47] Westhoff WW, Cohen CF, Cooper EE, Corvin J, McDermott RJ (2012) Cooperation or competition: Does game theory have relevance for public health? Amer. J. Health Ed. 43(3):175-183.Crossref, Google Scholar · doi:10.1080/19325037.2012.10872089
[48] Xu J, Xu X, Xie SQ (2011) Recent developments in dual resource constrained (DRC) system research. Eur. J. Oper. Res. 215(2):309-318.Crossref, Google Scholar · doi:10.1016/j.ejor.2011.03.004
[49] Young HP (1985) Monotonic solutions of cooperative games. Internat. J. Game Theory 14(2):65-72.Crossref, · Zbl 0569.90106 · doi:10.1007/BF01769885
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.