While many heuristics have been proposed for the problem of patient-to-room assignment (PRA) with a large variety of different practical constraints, a thorough investigation of the problem’s structure itself has been neglected so far. Therefore, in this paper, we present insights about the basic, underlying combinatorial problem of PRA. At first we consider the problem with patient-room assignment restrictions, where not every patient can be assigned to any room. In this case, the problem is strongly N P-complete even if all rooms are double bedrooms. This also settles an open question concerning the red-blue transportation problem. Afterwards, we study the problem without such restrictions and focus on minimizing the number of patients who have to change rooms during their stay. Particularly, we prove that in the case of double bedrooms, each patient has to be transfered at most once.
Article
View One transfer per patient suffices: Structural insights about patient-to-room assignment