×

Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling. (English) Zbl 1394.90301

Summary: Efficient outpatient scheduling is becoming increasingly important for the overall cost effectiveness and treatment efficiency of a hospital. We consider a class of multi-mode appointment scheduling problems, with variable resource availability and resource setup times. These problems are frequently found in hospital outpatient clinics, and they are typically hard to solve. We present an exact method based on a recursive logic-based Benders’ decomposition, where each subproblem is formulated as an integer linear program. We show how such a decomposition can be designed to fully exploit the daily structure of these problems, while at the same time addressing the symmetry issues that arise from having many appointments with similar resource and time requirements. Novel valid inequalities are also added to strengthen each master problem. We demonstrate the efficiency of the overall approach through a case study from a gastroenterology clinic at the University Hospital of Northern Norway, using real life data. The computational results show that the recursive, three-level, decomposition solves the most complex real life test instances to optimality in less than 5 minutes. The method drastically outperforms the corresponding two-level decomposition, which fails to solve all but one of these test instances within the one hour time limit.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C11 Mixed integer programming
90C10 Integer programming
90B90 Case-oriented studies in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batun, S.; Begen, M. A., Optimization in healthcare delivery modeling: Methods and applications, Handbook of healthcare operations management, 75-119 (2013), Springer
[2] Beck, J. C., Checking-up on branch-and-check, Principles and practice of constraint programming-cp 2010, 84-98 (2010), Springer
[3] Benini, L.; Lombardi, M.; Mantovani, M.; Milano, M.; Ruggiero, M., Multi-stage benders decomposition for optimizing multicore architectures, (Perron, M.; Trick, M., Fifth international conference on integration of ai and or techniques in constraint programming for combinatorial oprimization problems (2008)), 36-50 · Zbl 1142.68506
[4] Bulgarini, N.; Di Lorenzo, D.; Lori, A.; Matarrese, D.; Schoen, F., Operating room joint planning and scheduling, Proceedings of the international conference on health care systems engineering, 127-138 (2014), Springer
[5] 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)
[6] Cardoen, B.; Demeulemeester, E.; Beliën, J., Operating room planning and scheduling: A literature review, European Journal of Operational Research, 201, 3, 921-932 (2010) · Zbl 1175.90160
[7] Castro, P. M.; Marques, I., Operating room scheduling with generalized disjunctive programming, Computers & Operations Research, 64, 262-273 (2015) · Zbl 1349.90324
[8] Cayirli, T.; Veral, E., Outpatient scheduling in health care: A review of literature, Production and Operations Management, 12, 4, 519-549 (2003)
[9] Charnetski, J., Scheduling operating room surgical procedures with early and late completion penalty costs, Journal of Operations Management, 5, 1, 91-102 (1984)
[10] Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, 756-766 (2006) · Zbl 1167.90601
[11] Demeulemeester, E.; Beliën, J.; Cardoen, B.; Samudra, M., Operating room planning and scheduling, Handbook of healthcare operations management book section 5. Handbook of healthcare operations management book section 5, International Series in Operations Research & Management Science, vol.184, 121-152 (2013), Springer: Springer New York
[12] Doulabi, S. H.H.; Rousseau, L.-M.; Pesant, G., A constraint programming-based column generation approach for operating room planning and scheduling, Integration of ai and or techniques in constraint programming, 455-463 (2014), Springer · Zbl 06298810
[13] Fazel-Zarandi, M.; Beck, J., Using logic-based benders decomposition to solve the capacity and distance constrained plant location problem, INFORMS Journal on Computing, 24, 399-415 (2012) · Zbl 1462.90065
[14] Fazel-Zarandi, M. M.; Berman, O.; Beck, J. C., Solving a stochastic facility location/fleet management problem with logic-based benders’ decomposition, IIE Transactions, 45, 8, 896-911 (2013)
[15] Fei, H.; Meskens, N.; Chu, C., A planning and scheduling problem for an operating theatre using an open scheduling strategy, Computers & Industrial Engineering, 58, 2, 221-230 (2010)
[16] Froehle, C. M.; Magazine, M. J., Improving scheduling and flow in complex outpatient clinics, Handbook of healthcare operations management, 229-250 (2013), Springer
[17] Guerriero, F.; Guido, R., Operational research in the management of the operating theatre: a survey, Health Care Management Science, 14, 1, 89-114 (2011)
[18] Gupta, D.; Denton, B., Appointment scheduling in health care: Challenges and opportunities, IIE Transactions, 40, 9, 800-819 (2008)
[19] Hooker, J. N., Logic-based methods for optimization (2000), Wiley
[20] Hooker, J. N., Planning and scheduling by logic-based benders decomposition, Operations Research, 55, 3, 588-602 (2007) · Zbl 1167.90512
[21] Hooker, J. N.; Ottosson, G., Logic-based benders decomposition, Mathematical Programming, 96, 1, 33-60 (2003) · Zbl 1023.90082
[22] Hulshof, P. J.H.; Kortbeek, N.; Boucherie, R. J.; Hans, E. W.; Bakker, P. J.M., Taxonomic classification of planning decisions in health care: A structured review of the state of the art in or/ms, Health Systems, 1, 2, 129-175 (2012)
[23] Jain, V.; Grossmann, I., Algorithms for hybrid MILP/CP models for a class of optimization problems, INFORMS Journal on Computing, 13, 258-276 (2001) · Zbl 1238.90106
[24] Jebali, A.; Hadj Alouane, A. B.; Ladet, P., Operating rooms scheduling, International Journal of Production Economics Control and Management of Productive Systems, 99, 1-2, 52-62 (2006)
[25] Lamorgese, L.; Mannino, C., An exact decomposition approach for the real-time train dispatching problem, Operations Research, 63, 1, 48-64 (2015) · Zbl 1327.90352
[26] Lombardi, M.; Milano, M., Optimal methods for resource allocation and scheduling: a cross-disciplinary survey, Constraints, 17, 1, 51-85 (2012)
[27] Marques, I.; Captivo, M. E.; Pato, M. V., An integer programming approach to elective surgery scheduling, OR spectrum, 34, 2, 407-427 (2012) · Zbl 1239.90065
[28] Marques, I.; Captivo, M. E.; Pato, M. V., A bicriteria heuristic for an elective surgery scheduling problem, Health care management science, 18, 3, 251-266 (2015)
[29] Marques, I.; Captivo, M. E.; Vaz Pato, M., Scheduling elective surgeries in a portuguese hospital using a genetic heuristic, Operations Research for Health Care, 3, 2, 59-72 (2014)
[30] May, J. H.; Spangler, W. E.; Strum, D. P.; Vargas, L. G., The surgical scheduling problem: Current research and future opportunities, Production and Operations Management, 20, 3, 392-405 (2011)
[31] Molina-Pariente, J. M.; Fernandez-Viagas, V.; Framinan, J. M., Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations, Computers & Industrial Engineering, 82, 8-20 (2015)
[32] Neumann, K.; Schwindt, C.; Zimmermann, J., Project Scheduling with Time Windows and Scarce Resources (2003), Springer-Verlag: Springer-Verlag New York · Zbl 1059.90001
[33] Pham, D.-N.; Klinkert, A., Surgical case scheduling as a generalized job shop scheduling problem, European Journal of Operational Research, 185, 3, 1011-1025 (2008) · Zbl 1146.90420
[34] Pisinger, D.; Sigurd, M., Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem, INFORMS Journal on Computing, 19, 1, 36-51 (2009) · Zbl 1241.90118
[35] Raidl, G. R.; Baumhauer, T.; Hu, B., Speeding up logic-based benders’ decomposition by a metaheuristic for a bi-level capacitated vehicle routing problem, Hybrid metaheuristics, 183-197 (2014), Springer
[36] Rasmussen, R.; Trick, M., A benders approach for the constrained minimum break problem, European Journal of Operational Research, 177, 1, 198-213 (2007) · Zbl 1102.90026
[37] Riise, A.; Burke, E. K., Local search for the surgery admission planning problem, Journal of Heuristics, 17, 4, 389-414 (2011)
[38] Roland, B.; Di Martinelly, C.; Riane, F., Operating theatre optimization: A resource-constrained based solving approach, Proceedings of the 2006 international conference on service systems and service management, vol.1, 443-448 (2006)
[39] Sabzehparvar, M.; Seyed-Hosseini, S. M., A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags, The Journal of Supercomputing, 44, 3, 257-273 (2008) · Zbl 1187.90143
[40] Serrano, C.; Jiménez, A.; Amaya, C.; Velasco, N., Optimization model to minimize the makespan in a hospital’s gastroenterology service (2009), Universidad de los Andes
[41] Vijayakumar, B.; Parikh, P. J.; Scott, R.; Barnes, A.; Gallimore, J., A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital, European Journal of Operational Research, 224, 3, 583-591 (2013) · Zbl 1292.90126
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.