IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v325y2025i1p20-37.html

Patient-to-room assignment with single-rooms entitlements: Combinatorial insights and integer programming formulations

Author

Listed:
  • Brandt, Tabea
  • Büsing, Christina
  • Engelhardt, Felix

Abstract

Patient-to-room assignment (PRA) is a scheduling problem in decision support for hospitals. It consists of assigning patients to rooms during their stay at a hospital according to certain conditions and objectives, e.g., ensuring gender separated rooms, avoiding transfers and respecting single-room requests. This work presents combinatorial insights about the feasibility of PRA and about how (many) single-room requests can be respected. We further compare different integer programming (IP) formulations for PRA as well as the influence of different objectives on the runtime using real-world data. Based on these results, we develop a fast IP-based solution approach, which obtains high quality solutions. In contrast to previous IP-formulations, the results of our computational study indicate that large, real-world instances can be solved to a high degree of optimality within (fractions of) seconds. We support this result by a computational study using a large set of realistic but randomly generated instances with 50% to 95% capacity utilisation.

Suggested Citation

  • Brandt, Tabea & Büsing, Christina & Engelhardt, Felix, 2025. "Patient-to-room assignment with single-rooms entitlements: Combinatorial insights and integer programming formulations," European Journal of Operational Research, Elsevier, vol. 325(1), pages 20-37.
    • Handle: RePEc:eee:ejores:v:325:y:2025:i:1:p:20-37
    DOI: 10.1016/j.ejor.2025.02.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725001389
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.02.018?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Nicole Blay & Michael A Roche & Christine Duffield & Robyn Gallagher, 2017. "Intrahospital transfers and the impact on nursing workload," Journal of Clinical Nursing, John Wiley & Sons, vol. 26(23-24), pages 4822-4829, December.
    2. Nicole Blay & Michael Roche & Christine Duffield & Xiaoyue Xu, 2017. "Intrahospital transfers and adverse patient outcomes: An analysis of administrative health data," Journal of Clinical Nursing, John Wiley & Sons, vol. 26(23-24), pages 4927-4935, December.
    3. Wim Vancroonenburg & Patrick Causmaecker & Greet Vanden Berghe, 2016. "A study of decision support models for online patient-to-room assignment planning," Annals of Operations Research, Springer, vol. 239(1), pages 253-271, April.
    4. Annette M. C. Ficker & Frits C. R. Spieksma & Gerhard J. Woeginger, 2021. "The transportation problem with conflicts," Annals of Operations Research, Springer, vol. 298(1), pages 207-227, March.
    5. Fabian Schäfer & Manuel Walther & Dominik G. Grimm & Alexander Hübner, 2023. "Combining machine learning and optimization for the operational patient-bed assignment problem," Health Care Management Science, Springer, vol. 26(4), pages 785-806, December.
    6. Bastos, Leonardo S.L. & Marchesi, Janaina F. & Hamacher, Silvio & Fleck, Julia L., 2019. "A mixed integer programming approach to the patient admission scheduling problem," European Journal of Operational Research, Elsevier, vol. 273(3), pages 831-840.
    7. Guido, Rosita & Groccia, Maria Carmela & Conforti, Domenico, 2018. "An efficient matheuristic for offline patient-to-bed assignment problems," European Journal of Operational Research, Elsevier, vol. 268(2), pages 486-503.
    8. Bex George Thomas & Srinivas Bollapragada & Kunter Akbay & David Toledano & Peter Katlic & Onur Dulgeroglu & Dan Yang, 2013. "Automated Bed Assignments in a Complex and Dynamic Hospital Environment," Interfaces, INFORMS, vol. 43(5), pages 435-448, October.
    9. Hantel, Saskia & Benkenstein, Martin, 2019. "Roommates in Hospitals - A New and Relevant Dimension of Health Care Quality Models," SMR - Journal of Service Management Research, Nomos Verlagsgesellschaft mbH & Co. KG, vol. 3(2), pages 82-90.
    10. Fabian Schäfer & Manuel Walther & Alexander Hübner & Heinrich Kuhn, 2019. "Operational patient-bed assignment problem in large hospital settings including overflow and uncertainty management," Flexible Services and Manufacturing Journal, Springer, vol. 31(4), pages 1012-1041, December.
    11. Liu, Haichao & Wang, Yang & Hao, Jin-Kao, 2024. "Solving the patient admission scheduling problem using constraint aggregation," European Journal of Operational Research, Elsevier, vol. 316(1), pages 85-99.
    12. Range, Troels Martin & Lusby, Richard Martin & Larsen, Jesper, 2014. "A column generation approach for solving the patient admission scheduling problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 252-264.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fabian Schäfer & Manuel Walther & Dominik G. Grimm & Alexander Hübner, 2023. "Combining machine learning and optimization for the operational patient-bed assignment problem," Health Care Management Science, Springer, vol. 26(4), pages 785-806, December.
    2. Aleida Braaksma & Martin S. Copenhaver & Ana C. Zenteno & Elizabeth Ugarph & Retsef Levi & Bethany J. Daily & Benjamin Orcutt & Kathryn M. Turcotte & Peter F. Dunn, 2023. "Evaluation and implementation of a Just-In-Time bed-assignment strategy to reduce wait times for surgical inpatients," Health Care Management Science, Springer, vol. 26(3), pages 501-515, September.
    3. Liu, Haichao & Wang, Yang & Hao, Jin-Kao, 2024. "Solving the patient admission scheduling problem using constraint aggregation," European Journal of Operational Research, Elsevier, vol. 316(1), pages 85-99.
    4. Guido, Rosita & Groccia, Maria Carmela & Conforti, Domenico, 2018. "An efficient matheuristic for offline patient-to-bed assignment problems," European Journal of Operational Research, Elsevier, vol. 268(2), pages 486-503.
    5. Dimitris Bertsimas & Jean Pauphilet, 2024. "Hospital-Wide Inpatient Flow Optimization," Management Science, INFORMS, vol. 70(7), pages 4893-4911, July.
    6. Chengliang Wang & Feifei Yang & Quan-Lin Li, 2023. "Optimal Decision of Dynamic Bed Allocation and Patient Admission with Buffer Wards during an Epidemic," Mathematics, MDPI, vol. 11(3), pages 1-23, January.
    7. Fabian Schäfer & Manuel Walther & Alexander Hübner & Heinrich Kuhn, 2019. "Operational patient-bed assignment problem in large hospital settings including overflow and uncertainty management," Flexible Services and Manufacturing Journal, Springer, vol. 31(4), pages 1012-1041, December.
    8. Małgorzata M. O’Reilly & Sebastian Krasnicki & James Montgomery & Mojtaba Heydar & Richard Turner & Pieter Dam & Peter Maree, 2025. "Markov decision process and approximate dynamic programming for a patient assignment scheduling problem," Annals of Operations Research, Springer, vol. 347(3), pages 1493-1531, April.
    9. Kaining Shao & Wenjuan Fan & Zishu Yang & Shanlin Yang & Panos M. Pardalos, 2022. "A column generation approach for patient scheduling with setup time and deteriorating treatment duration," Operational Research, Springer, vol. 22(3), pages 2555-2586, July.
    10. Zhaohui Li & Haiyue Yu & Zhaowei Zhou, 2024. "Scheduling of elective operations with coordinated utilization of hospital beds and operating rooms," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-29, July.
    11. Sara Frimodig & Per Enqvist & Jan Kronqvist & Carole Mercier & Geert De Kerf, 2026. "Radiation therapy patient scheduling using a column generation approach: an algorithmic framework and a single-institution study," Annals of Operations Research, Springer, vol. 359(3), pages 2869-2915, April.
    12. Nicolas Gillet & Tiphaine Huyghebaert-Zouaghi & Christian Réveillère & Philippe Colombat & Evelyne Fouquereau, 2020. "The effects of job demands on nurses' burnout and presenteeism through sleep quality and relaxation," Journal of Clinical Nursing, John Wiley & Sons, vol. 29(3-4), pages 583-592, February.
    13. Namakshenas, Mohammad & Mazdeh, Mohammad Mahdavi & Braaksma, Aleida & Heydari, Mehdi, 2023. "Appointment scheduling for medical diagnostic centers considering time-sensitive pharmaceuticals: A dynamic robust optimization approach," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1018-1031.
    14. Balew Ayalew Kassie & Geletaw Sahle Tegenaw, 2023. "Developing a patient flow visualization and prediction model using aggregated data for a healthcare network cluster in Southwest Ethiopia," PLOS Digital Health, Public Library of Science, vol. 2(11), pages 1-15, November.
    15. Chawis Boonmee & Kosit Akarawongsapat & Warisa Wisittipanich & Wichai Chattinnawat & Krit Khwanngern, 2024. "Differential evolution for cleft lip and/or cleft palate patient treatment scheduling problems: a northern Thailand hospital case study," Annals of Operations Research, Springer, vol. 335(1), pages 563-595, April.
    16. Wiejak-Roy, Grazyna & Roy, Jaideep & Smith, Andrew, D.A.C., 2025. "Violation of land use regulations for allotment gardens: The case of Warsaw, Poland," Land Use Policy, Elsevier, vol. 158(C).
    17. Alves de Queiroz, Thiago & Iori, Manuel & Kramer, Arthur & Kuo, Yong-Hong, 2023. "Dynamic scheduling of patients in emergency departments," European Journal of Operational Research, Elsevier, vol. 310(1), pages 100-116.
    18. Emil Karlsson & Elina Rönnberg & Andreas Stenberg & Hannes Uppman, 2021. "A matheuristic approach to large-scale avionic scheduling," Annals of Operations Research, Springer, vol. 302(2), pages 425-459, July.
    19. Bouarab, Hocine & El Hallaoui, Issmail & Metrane, Abdelmoutalib & Soumis, François, 2017. "Dynamic constraint and variable aggregation in column generation," European Journal of Operational Research, Elsevier, vol. 262(3), pages 835-850.
    20. Nikzad, Erfaneh & Bashiri, Mahdi & Abbasi, Babak, 2021. "A matheuristic algorithm for stochastic home health care planning," European Journal of Operational Research, Elsevier, vol. 288(3), pages 753-774.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:325:y:2025:i:1:p:20-37. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.