Patient-to-room assignment with single-rooms entitlements: Combinatorial insights and integer programming formulations
研究了医院病人房间分配问题，提出组合可行性条件与单人房请求满足数计算方法，基于整数规划开发快速求解方法，能在秒级内求解大规模实例。
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 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 utilization. • Insights about real-life patient-to-room assignment (PRA) in German hospitals. • Hands-on formula for checking an instance’s feasibility. • Efficient computation of the number of fulfillable single-room requests. • Exact solution approach for PRA evaluated on real-life data. • Efficient BIP-based heuristic obtains high quality solution for dynamic PRA.