A Benders Decomposition Algorithm for Integrated Operating Room Planning and Scheduling Problem by Considering Multiple Shifts and Preparation Time

Document Type : Research Paper

Authors

1 Phd student of Systems Optimization, Industrial Engineering Group, Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

2 . Assistant Professor, Social Economic Systems Group, Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

Abstract

The integrated operating room planning and scheduling problem is one of the most important optimization problems in the field of health, which has recently attracted the attention of hospital managers. In this article, a planning and scheduling model is proposed with the aim of increasing revenue and reducing current costs of the operating room and considering human resources including surgeons and nurses and available time for surgeons. In this model, for the optimal use of the capacity of the operating room, it is possible to plan during several shifts, and the costs of surgery and staffs are included in each shift. Also, due to the variety of surgeries and the need to prepare the operating room, the preparation time of the operating room is also considered for more accurate planning. Due to the complicating variables, the model has been solved by Benders decomposition algorithm and with GAMS software for different sizes. Considering multiple shifts has made it to plan for a high number of surgeries. On the one hand, because of planning in several shifts, the results show that the amount of the objective function has been improved by using the Benders decomposition compared to the GAMS software for larger size problems and has led to an optimal solution with more income and more efficient planning of the operating room. On the other hand, the solution time is reduced by this algorithm.

Keywords

Main Subjects

References

  •  

    • Doulabi, S., L.-M. Rousseau, and G. Pesant, A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling. INFORMS Journal on Computing, 2016. 28: p. 432-448. https://doi.org/10.1287/ijoc.2015.0686
    • Molina-Pariente, J.M., V. Fernandez-Viagas, and J. Framinan, Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations. Computers & Industrial Engineering, 2015. 82: p. 8-20. https://doi.org/10.1016/j.cie.2015.01.006
    • Latorre-Núñez, G., et al., Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries. Computers & Industrial Engineering, 2016. 97. https://doi.org/10.1016/j.cie.2016.05.016
    • Guerriero, F. and R. Guido, Operational research in the management of the operating theatre: A survey. Health care management science, 2011. 14: p. 89-114. https://doi.org/10.1007/s10729-010-9143-6
    • Gabel, R.A., Operating Room Management. 1999: Elsevier - Health Sciences Division.
    • Cardoen, B., E. Demeulemeester, and J. Beliën, Operating room planning and scheduling: A literature review. European Journal of Operational Research, 2010. 201(3): p. 921-932. https://doi.org/10.1016/j.ejor.2009.04.011
    • Blake, J., F. Dexter, and J. Donald, Operating Room Managers??? Use of Integer Programming for Assigning Block Time to Surgical Groups: A Case Study. Anesthesia and analgesia, 2002. 94: p. 143-8, table of contents. https://doi.org/10.1097/00000539-200201000-00027
    • Fei, H., N. Meskens, and C. Chu, A planning and scheduling problem for an operating theatre using an open scheduling strategy. Computers & Industrial Engineering, 2010. 58(2): p. 221-230. https://doi.org/10.1016/j.cie.2009.02.012
    • Younespour, M., et al., Using mixed integer programming and constraint programming for operating rooms scheduling with modified block strategy. Operations Research for Health Care, 2019. 23. https://doi.org/10.1016/j.orhc.2019.100220
    • Bargetto, R., T. Garaix, and X. Xie, A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints. Computers & Operations Research, 2023. 152: p. 106136. https://doi.org/10.1016/j.cor.2022.106136
    • Roland, B., C.d. Martinelly, and F. Riane. Operating Theatre Optimization : A Resource-Constrained Based Solving Approach. in 2006 International Conference on Service Systems and Service Management. 2006. https://doi.org/10.1109/ICSSSM.2006.320503
    • Roland, B., et al., Scheduling an operating theatre under human resource constraints. Computers & Industrial Engineering, 2010. 58: p. 212-220. https://doi.org/10.1016/j.cie.2009.01.005
    • Marques, I., M.E. Captivo, and M. Vaz Pato, An integer programming approach to elective surgery scheduling. OR Spectrum, 2012. 34(2): p. 407-427. https://doi.org/10.1007/s00291-011-0279-7
    • Marques, I., M.E. Captivo, and M. Vaz Pato, Scheduling elective surgeries in a Portuguese hospital using a genetic heuristic. Operations Research for Health Care, 2014. 3(2): p. 59-72. ttps://doi.org/10.1016/j.orhc.2013.12.001
    • Guido, R. and D. Conforti, A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem. Computers & Operations Research, 2017. 87: p. 270-282. https://doi.org/10.1016/j.cor.2016.11.009
    • Akbarzadeh, B., et al., A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering. Journal of Scheduling, 2020. 23(2): p. 265-288. https://doi.org/10.1007/s10951-020-00639-6
    • Breuer, D.J., et al., Robust combined operating room planning and personnel scheduling under uncertainty. Operations Research for Health Care, 2020. 27: p. 100276. https://doi.org/10.1016/j.orhc.2020.100276
    • Mancilla, C. and R.H. Storer, Stochastic sequencing and scheduling of an operating room. Theses and Dissertations, Lehigh University, Department of Industrial and Systems Engineering (November 14, 2009), 2009.
    • Roshanaei, V., et al., Collaborative operating room planning and scheduling. INFORMS Journal on Computing, 2017. 29(3): p. 558-580. https://doi.org/10.1287/ijoc.2017.0745
    • Kamran, M.A., B. Karimi, and N. Dellaert, Uncertainty in advance scheduling problem in operating room planning. Computers & Industrial Engineering, 2018. 126: p. 252-268. https://doi.org/10.1016/j.cie.2018.09.030
    • Kamran, M.A., B. Karimi, and N. Dellaert, A column-generation-heuristic-based benders’ decomposition for solving adaptive allocation scheduling of patients in operating rooms. Computers & Industrial Engineering, 2020. 148: p. 106698. https://doi.org/10.1016/j.cie.2020.106698
    • Ghandehari, N. and K. Kianfar, Mixed-integer linear programming, constraint programming and column generation approaches for operating room planning under block strategy. Applied Mathematical Modelling, 2022. 105: p. 438-453. https://doi.org/10.1016/j.apm.2022.01.001
    • Gür, Ş., et al., Operating room scheduling with surgical team: a new approach with constraint programming and goal programming. Central European Journal of Operations Research, 2023. 31(4): p. 1061-1085. https://doi.org/10.1007/s10100-022-00835-z
    • Tayyab, A., S. Ullah, and M.F. Baki, An outer approximation method for scheduling elective surgeries with sequence dependent setup times to multiple operating rooms. Mathematics, 2023. 11(11): p. 2441. https://doi.org/10.3390/math11112441
    • Karimi, N. and H. Davoudpour, A Benders decomposition algorithm for multi-factory scheduling problem with batch delivery. Scientia Iranica, 2017. 24(2): p. 823-833 https://doi.org/10.24200/sci.2017.4064
Journal of Industrial Engineering Research in Production Systems
Volume 12, Issue 24
September 2024
Pages 49-61

Files

Share

How to cite

Statistics