Structural insights about avoiding transfers in the patient-to-room assignment problem.

Assigning patients to rooms is a fundamental task in hospitals and, especially, within wards. For this so-called patient-to-room assignment problem (PRA) many heuristics have been proposed with a large variety of different practical constraints. However, a thorough investigation of the problem's structure itself has been neglected so far. In this paper, we present insights about the basic, underlying combinatorial problem of PRA with a focus on minimizing the number of patient transfers which occur if patients have to change rooms during their stay. Particularly, we prove that in the case of double bedrooms, although minimizing the total number of transfers is NP -complete, each patient has to be transferred at most once, and provide upper bounds on the minimum total number of transfers. [ABSTRACT FROM AUTHOR]