A greedy-tabu approach to the patient bed assignment problem in the Hospital Universitario San Ignacio

Abstract: Patient Bed Assignment (PBA) consists of assigning patients to hospital beds according to specific requirements such as patient diagnosis, equipment requirements, age and gender policies, among others. We worked in conjunction with the Hospital Universitario San Ignacio (HUSI) with the goal of designing an application to support decision-making during the bed assignment process. We introduced a mathematical model for the PBA. We used Analytic Hierarchy Process (AHP) to determine the weights attributed to each part of the objective function. Due to the long execution time required, we used a Greedy Algorithm and Tabu Search (TS) to optimize the match between the patient’s requirements and the characteristics of the assigned bed. To test the algorithms, we created 15 test instances of various sizes. The results showed that the gap between the value of the objective function resulting from using the Greedy/TS in comparison with the optimal solution is on average 6.2%. Also, the TS takes 84% less time than the MILP for medium and large instances. We collected data from real life instances and compared the actual method with the designed metaheuristic. On average, the value of the objective function resulting from using the proposed Greedy/Tabu algorithm is 8.6% higher.

How to cite this paper

 Arguello-Monroya, A., Castellanos-Ramírez, V., González-Neira, E., Otero-Caicedo, R & Delgadillo-Sánchez, V. (2021). A greedy-tabu approach to the patient bed assignment problem in the Hospital Universitario San Ignacio.Decision Science Letters , 10(1), 21-38.

Refrences

Almomani, R., Al-Ghdabi, R., & Banyhamdan, K. (2020). Patients’ satisfaction of health service quality in public hospitals: A PubHosQual analysis. Management Science Letters, 10(8), 1803-1812.
Alshamrani, A., & Bahattab, A. (2015). A comparison between three SDLC models waterfall model, spiral model, and Incremental/Iterative model. International Journal of Computer Science Issues, 12(1), 106.
Bilgin, B., Demeester, P., Misir, M., Vancroonenburg, W., & Vanden Berghe, G. (2012). One hyper-heuristic approach to two timetabling problems in health care. Journal of Heuristics, 18, 401-434.
Bolaji, A. L. aro, Bamigbola, A. F., & Shola, P. B. (2018). Late acceptance hill climbing algorithm for solving patient admission scheduling problem. Knowledge-Based Systems, 145, 1–14. https://doi.org/10.1016/j.knosys.2018.01.017
Ceschia, S., & Schaerf, A. (2011). Local search and lower bounds for the patient admission scheduling problem. Computers and Operations Research, 38(10), 1452–1463. https://doi.org/10.1016/j.cor.2011.01.007
Ceschia, S., & Schaerf, A. (2012). Modeling and solving the dynamic patient admission scheduling problem under uncertainty. Artificial Intelligence in Medicine, 56(3), 199–205. https://doi.org/10.1016/j.artmed.2012.09.001
Ceschia, S., & Schaerf, A. (2016). Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays. Journal of Scheduling, 19(4), 377–389. https://doi.org/10.1007/s10951-014-0407-8
Cote, M. J. (2000). Understanding patient flow. Decision Line, 31, 8-13.
Demeester, P., Souffriau, W., De Causmaecker, P., & Vanden Berghe, G. (2010). A hybrid tabu search algorithm for automatically assigning patients to beds. Artificial Intelligence in Medicine, 48(1), 61–70.
Gendreau, M., & Potvin, J.-Y. (2010). Tabu Search. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of Metaheuristics (Vol. 146, pp. 41–59). Boston, MA: Springer US. https://doi.org/10.1007/978-1-4419-1665-5_2
Glover, F. (1989). Tabu Search - Part I. ORSA Journal on Computing, 21(3), 4–32. https://doi.org/10.1287/ijoc.2.1.4
Guido, R., Groccia, M. C., & Conforti, D. (2018). An efficient matheuristic for offline patient-to-bed assignment problems. European Journal of Operational Research, 268(2), 486–503. https://doi.org/10.1016/j.ejor.2018.02.007
Hulshof, P. J. H., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. M. (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.
International Standardization Organization ISO. (2018). La familia de normas ISO/IEC 25000. La Familia de Normas ISO/IEC 25000. http://iso25000.com/index.php/normas-iso-25000
Kloehn, P. (2004). Demystifying patient throughput to optimize revenue and patient satisfaction. Hales Corner, WI.
Liu, S., Zhao, Q., & Wen, M. (2013). Assessing the impact of hydroelectric project construction on the ecological integrity of the Nuozhadu Nature Reserve. Stochastic Environmental Research and Risk Assessment, 27, 1709–1718.
Lou, Y., Chen, J., Zhang, L., & Hao, D. (2019). A Survey on Regression. Advances in Computers (1st ed., Vol. 113). Elsevier. https://doi.org/10.1016/bs.adcom.2018.10.001
Lusby, R. M., Schwierz, M., Range, T. M., & Larsen, J. (2016). An adaptive large neighborhood search procedure applied to the dynamic patient admission scheduling problem. Artificial Intelligence in Medicine, 74, 21–31. https://doi.org/10.1016/j.artmed.2016.10.002
Range, T. M., Lusby, R. M., & Larsen, J. (2014). A column generation approach for solving the patient admission scheduling problem. European Journal of Operational Research, 235(1), 252–264. https://doi.org/10.1016/j.ejor.2013.10.050
Romero-Conrado, A. R., Castro-Bolaño, L. J., Montoya-Torres, J. R., & Jiménez Barros, M. Á. (2017). Operations research as a decision-making tool in the health sector: A state of the art. Dyna, 84(201), 129.
Saaty, T. L. (2008). Decision making with the analytic hierarchy process. International Journal of Services Sciences, 1(1), 83-98.
Thomas, B. G., Bollapragada, S., Akbay, K., Toledano, D., Katlic, P., Dulgeroglu, O., & Yang, D. (2013). Automated bed assignments in a complex and dynamic hospital environment. Interfaces, 43(5), 435–448.
Turhan, A. M., & Bilgen, B. (2017). Mixed integer programming based heuristics for the Patient Admission Scheduling problem. Computers and Operations Research, 80, 38–49. https://doi.org/10.1016/j.cor.2016.11.016
Vancroonenburg, W., Goossens, D., & Spieksma, F. (2011). On the complexity of the patient assignment problem. Tech. rep., Tech. rep.
Vancroonenburg, W., Causmaecker, P. De, Spieksma, F., & Vanden Berghe, G. (2013). Scheduling elective patient admissions considering room assignment and operating theatre capacity constraints. Lecture Notes in Management Science. 5th International Conference on Applied Operational Research, Proceedings, 5, 153–158.
Vancroonenburg, W., De Causmaecker, P., & Vanden Berghe, G. (2013). A study of decision support models for online patient-to-room assignment planning. Annals of Operations Research, 239(1), 253–271.