Abstract
The present paper studies patient-to-room assignment planning in a dynamic context. To this end, an extension of the patient assignment (PA) problem formulation is proposed, for which two online ILP-models are developed. The first model targets the optimal assignment for newly arrived patients, whereas the second also considers future, but planned, arrivals. Both models are compared on an existing set of benchmark instances from the PA planning problem, which serves as the basic problem setting. These instances are then extended with additional parameters to study the effect of uncertainty on the patients’ length of stay, as well as the effect of the percentage of emergency patients. The results show that the second model provides better results under all conditions, while still being computationally tractable. Moreover, the results show that pro-actively transferring patients from one room to another is not necessarily beneficial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Also denoted as a block scheduling strategy.
Note that the notion of a maximal clique differs from a maximum clique. A maximum clique is the largest cardinality clique that can be found in a graph.
References
Beliën, J., & Demeulemeester, E. (2007). Building cyclic master surgery schedules with leveled resulting bed occupancy. European Journal of Operational Research, 176(2), 1185–1204. doi:10.1016/j.ejor.2005.06.063.
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(3), 401–434. doi:10.1007/s10732-011-9192-0.
Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7, 441–499. doi:10.1023/B:JOSH.0000046076.75950.0b.
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. doi:10.1016/j.ejor.2009.04.011.
Ceschia, S., & Schaerf, A. (2011). Local search and lower bounds for the patient admission scheduling problem. Computers & Operations Research, 38(10), 1452–1463. doi: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. doi:10.1016/j.artmed.2012.09.001.
Demeester, P. (2012). Patient admission scheduling problem website. Online, http://allserv.kahosl.be/~peter/pas/.
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. doi:10.1016/j.artmed.2009.09.001.
Fei, H., Chu, C., & Meskens, N. (2008). Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria. Annals of Operations Research, 166(1), 91–108. doi:10.1007/s10479-008-0413-3.
Guinet, A., & Chaabane, S. (2003). Operating theatre planning. International Journal of Production Economics, 85(1), 69–81. doi:10.1016/S0925-5273(03)00087-2.
IBM ILOG (2012). Ibm ilog cplex optimization studio information center. Online, http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp.
Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: a survey. Naval Research Logistics, 54(5), 530–543. doi:10.1002/nav.20231.
Krishnamoorthy, M., Ernst, A., & Baatar, D. (2012). Algorithms for large scale shift minimisation personnel task scheduling problems. European Journal of Operational Research, 219(1), 34–48. http://www.sciencedirect.com/science/article/pii/S0377221711010435. doi:10.1016/j.ejor.2011.11.034.
R Core Team (2012). A language and environment for statistical computing. Vienna: R Foundation for Statistical Computing. http://www.R-project.org/, ISBN 3-900051-07-0.
Rais, A., & Viana, A. (2011). Operations research in healthcare: a survey. International Transactions in Operational Research, 18(1), 1–31. doi:10.1111/j.1475-3995.2010.00767.x.
Riise, A., & Burke, E. K. (2010). Local search for the surgery admission planning problem. Journal of Heuristics, 17(4), 389–414. doi:10.1007/s10732-010-9139-x.
Vancroonenburg, W., Goossens, D., & Spieksma, F. C. R. (2011). On the complexity of the patient assignment problem (Tech. rep.). KAHO Sint-Lieven, Gebroeders De Smetstraat 1, Gent, Belgium. URL http://allserv.kahosl.be/~wimvc/pas-complexity-techreport.pdf
Acknowledgements
We would like to thank Sara Ceschia and Andrea Schaerf from the University of Udine for the many fruitful discussions on the specific subject of this study. This research is funded by a Ph.D. grant of the Agency for Innovation by Science and Technology (IWT).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vancroonenburg, W., De Causmaecker, P. & Vanden Berghe, G. A study of decision support models for online patient-to-room assignment planning. Ann Oper Res 239, 253–271 (2016). https://doi.org/10.1007/s10479-013-1478-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-013-1478-1