A new genetic algorithm to solve integrated operating room scheduling problem with multiple objective functions

Document Type : Research Paper

Authors

Industrial Engineering Department, Faculty of Engineering, Semnan University, Semnan, Iran

Abstract

In this paper, a new genetic algorithm is presented to plan and schedule operating rooms at the operational level to minimize completion time, surgeons’ free time window, and operating rooms’ overtime, idle time, and setup time costs. The duration of surgeries is calculated according to a predetermined time plus an allowance related to the uncertainty of the surgery time. Also, the operating rooms’ setup times depend on the sequence of surgeries. The time window constraint involves resource availability such as surgeons and operating rooms. First, a mixed-integer nonlinear mathematical model is proposed to solve the problem. Thereafter, a genetic algorithm is developed to solve the problem inspired from the role model concept in sociology using simulating and differentiating procedures, namely Role Model Genetic Algorithm (RMGA). The performance of the proposed algorithm is examined by comparing it with a conventional genetic algorithm and a hybrid genetic algorithm proposed for the nearest problem in the literature to the current problem. The results shows that RMGA prepares better results.

Keywords

Main Subjects


Addis, B., Carello, G., Grosso, A., & Tànfani, E. (2016). Operating room scheduling and rescheduling: a rolling horizon approach. Flexible Services and Manufacturing Journal, 28(1-2), 206-232.
Agnetis, A., Coppi, A., Corsini, M., Dellino, G., Meloni, C., & Pranzo, M. (2014). A decomposition approach for the combined master surgical schedule and surgical case assignment problems. Health care management science, 17(1), 49-59.
Ahmadi-Javid, A., Jalali, Z., & Klassen, K. J. (2017). Outpatient appointment systems in healthcare: A review of optimization studies. European Journal of Operational Research, 258(1), 3-34.
Akbarzadeh, B., Moslehi, G., Reisi-Nafchi, M., & Maenhout, B. (2020). A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering. Journal of scheduling, 23(2), 265-288.
Ala, A., Torkayesh, S. E., Torkayesh, A. E., & Iranizad, A. (2020). A hybrid genetic algorithm for appointment scheduling in a health examination system. International Journal of Value Chain Management, 11(4), 293-310.
Aringhieri, R., Landa, P., Soriano, P., Tànfani, E., & Testi, A. (2015). A two level metaheuristic for the operating room scheduling and assignment problem. Computers & Operations Research, 54, 21-34.
Arnaout, J.-P. (2010). Heuristics for the maximization of operating rooms utilization using simulation. Simulation, 86(8-9), 573-583.
Batun, S., Denton, B. T., Huschka, T. R., & Schaefer, A. J. (2011). Operating room pooling and parallel surgery processing under uncertainty. INFORMS journal on Computing, 23(2), 220-237.
Breuer, D. J., Lahrichi, N., Clark, D. E., & Benneyan, J. C. (2020). Robust combined operating room planning and personnel scheduling under uncertainty. Operations Research for health care, 27, 100276.
Cardoen, B., Demeulemeester, E., & Beliën, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201(3), 921-932.
Ciavotta, M., Dellino, G., Meloni, C., & Pranzo, M. (2010). A rollout algorithmic approach for complex parallel machine scheduling in healthcare operations. Paper presented at the XXXVI International ORAHS Conference.
Conforti, D., Guerriero, F., & Guido, R. (2010). A multi-objective block scheduling model for the management of surgical operating rooms: New solution approaches via genetic algorithms. Paper presented at the 2010 IEEE workshop on health care management (WHCM).
Denton, B. T., Miller, A. J., Balasubramanian, H. J., & Huschka, T. R. (2010). Optimal allocation of surgery blocks to operating rooms under uncertainty. Operations research, 58(4-part-1), 802-816.
Díaz-López, D., López-Valencia, N., González-Neira, E., Barrera, D., Suárez, D., Caro-Gutiérrez, M., & Sefair, C. (2018). A simulation-optimization approach for the surgery scheduling problem: a case study considering stochastic surgical times. International Journal of Industrial Engineering Computations, 9(4), 409-422.
Dios, M., Molina-Pariente, J. M., Fernandez-Viagas, V., Andrade-Pineda, J. L., & Framinan, J. M. (2015). A decision support system for operating room scheduling. Computers & Industrial Engineering, 88, 430-443.
Doulabi, S. H. H., Rousseau, L.-M., & Pesant, G. (2014). A constraint programming-based column generation approach for operating room planning and scheduling. Paper presented at the International conference on ai and or techniques in constriant programming for combinatorial optimization problems.
Durán, G., Rey, P. A., & Wolff, P. (2017). Solving the operating room scheduling problem with prioritized lists of patients. Annals of Operations Research, 258(2), 395-414.
Fei, H., Meskens, N., & Chu, C. (2010). A planning and scheduling problem for an operating theatre using an open scheduling strategy. Computers & Industrial Engineering, 58(2), 221-230.
Gartner, D., & Padman, R. (2017). Mathematical programming and heuristics for patient scheduling in hospitals: A survey. In Handbook of research on healthcare administration and management (pp. 627-645): IGI Global.
Ghazalbash, S., Sepehri, M. M., Shadpour, P., & Atighehchian, A. (2012). Operating room scheduling in teaching hospitals. Advances in Operations Research, 2012.
Guido, R., & Conforti, D. (2017). A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem. Computers & Operations Research, 87, 270-282.
Hashemi Doulabi, S. H., Rousseau, L.-M., & Pesant, G. (2016). A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS journal on Computing, 28(3), 432-448.
Hulshof, P. J., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. (2012). 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.
Jebali, A., Alouane, A. B. H., & Ladet, P. (2006). Operating rooms scheduling. International Journal of Production Economics, 99(1-2), 52-62.
Kamran, M. A., Karimi, B., & Dellaert, N. (2020). A column-generation-heuristic-based benders’ decomposition for solving adaptive allocation scheduling of patients in operating rooms. Computers & Industrial Engineering, 148, 106698.
Landa, P., Aringhieri, R., Soriano, P., Tànfani, E., & Testi, A. (2016). A hybrid optimization algorithm for surgeries scheduling. Operations Research for health care, 8, 103-114.
Latorre-Núñez, G., Lüer-Villagra, A., Marianov, V., Obreque, C., Ramis, F., & Neriz, L. (2016). Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries. Computers & Industrial Engineering, 97, 248-257.
Lin, Y.-K., & Chou, Y.-Y. (2020). A hybrid genetic algorithm for operating room scheduling. Health care management science, 23(2), 249-263.
Marques, I., & Captivo, M. E. (2015). Bicriteria elective surgery scheduling using an evolutionary algorithm. Operations Research for health care, 7, 14-26.
Marques, I., Captivo, M. E., & Pato, M. V. (2012). An integer programming approach to elective surgery scheduling. OR spectrum, 34(2), 407-427.
Marques, I., Captivo, M. E., & Pato, M. V. (2014). Scheduling elective surgeries in a Portuguese hospital using a genetic heuristic. Operations Research for health care, 3(2), 59-72.
Marques, I., Captivo, M. E., & Pato, M. V. (2015). A bicriteria heuristic for an elective surgery scheduling problem. Health care management science, 18(3), 251-266.
Mateus, C., Marques, I., & Captivo, M. E. (2018). Local search heuristics for a surgical case assignment problem. Operations Research for health care, 17, 71-81.
Merton, R. K. (1957). The Role-Set: Problems in Sociological Theory. The British Journal of Sociology, 8, 106-120.
Molina-Pariente, J. M., Hans, E. W., & Framinan, J. M. (2018). A stochastic approach for solving the operating room scheduling problem. Flexible services and manufacturing journal, 30(1-2), 224-251.
Molina, P., Jose M, Fernandez-Viagas, V., & Framinan, J. M. (2015). Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations. Computers & Industrial Engineering, 82, 8-20.
Molina, P., Jose M, Hans, E. W., & Framinan, J. M. (2018). A stochastic approach for solving the operating room scheduling problem. Flexible Services and Manufacturing Journal, 30(1-2), 224-251.
Moosavi, A., & Ebrahimnejad, S. (2018). Scheduling of elective patients considering upstream and downstream units and emergency demand using robust optimization. Computers & Industrial Engineering, 120, 216-233.
Pham, D.-N., & Klinkert, A. (2008). Surgical case scheduling as a generalized job shop scheduling problem. European Journal of Operational Research, 185(3), 1011-1025.
Riise, A., & Burke, E. K. (2011). Local search for the surgery admission planning problem. Journal of Heuristics, 17(4), 389-414.
Riise, A., Mannino, C., & Burke, E. K. (2016). Modelling and solving generalised operational surgery scheduling problems. Computers & Operations Research, 66, 1-11.
Roland, B., Di Martinelly, C., & Riane, F. (2006). Operating theatre optimization: A resource-constrained based solving approach. Paper presented at the 2006 International conference on service systems and service management.
Roland, B., Di Martinelly, C., Riane, F., & Pochet, Y. (2010). Scheduling an operating theatre under human resource constraints. Computers & Industrial Engineering, 58(2), 212-220.
Roshanaei, V., Booth, K. E., Aleman, D. M., Urbach, D. R., & Beck, J. C. (2020). Branch-and-check methods for multi-level operating room planning and scheduling. International Journal of Production Economics, 220, 107433.
Saadouli, H., Jerbi, B., Dammak, A., Masmoudi, L., & Bouaziz, A. (2015). A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department. Computers & Industrial Engineering, 80, 72-79.
Saremi, A., Jula, P., ElMekkawy, T., & Wang, G. G. (2013). Appointment scheduling of outpatient surgical services in a multistage operating room department. International Journal of Production Economics, 141(2), 646-658.
Tan, Y., El Mekkawy, T., Peng, Q., & Oppenheimer, L. (2007). Mathematical programming for the scheduling of elective patients in the operating room department. Proceedings of the Canadian Engineering Education Association (CEEA).
Testi, A., & Tànfani, E. (2009). Tactical and operational decisions for operating room planning: Efficiency and welfare implications. Health care management science, 12(4), 363.
Testi, A., Tanfani, E., & Torre, G. (2007). A three-phase approach for operating theatre schedules. Health care management science, 10(2), 163-172.
Van Huele, C., & Vanhoucke, M. (2014). Analysis of the integration of the physician rostering problem and the surgery scheduling problem. Journal of medical systems, 38(6), 43.
Van Oostrum, J. M., Bredenhoff, E., & Hans, E. W. (2010). Suitability and managerial implications of a master surgical scheduling approach. Annals of Operations Research, 178(1), 91-104.
Vijayakumar, B., Parikh, P. J., Scott, R., Barnes, A., & Gallimore, J. (2013). A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital. European Journal of Operational Research, 224(3), 583-591.
Xiang, W., Yin, J., & Lim, G. (2015). An ant colony optimization approach for solving an operating room surgery scheduling problem. Computers & Industrial Engineering, 85, 335-345.
Zhao, Z., & Li, X. (2014). Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming. Operations Research for health care, 3(3), 160-167.
Zhu, S., Fan, W., Liu, T., Yang, S., & Pardalos, P. M. (2020). Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs. Journal of Combinatorial Optimization, 39(1), 185-215.
Zhu, S., Fan, W., Yang, S., Pei, J., & Pardalos, P. M. (2019). Operating room planning and surgical case scheduling: a review of literature. Journal of Combinatorial Optimization, 37(3), 757-805.