Inpatient Overflow : An Approximate Dynamic Programming Approach

Problem definition: Inpatient beds are usually grouped into several wards, and each ward is assigned to serve patients from certain "primary" specialties. However, when a patient waits excessively long before a primary bed becomes available, hospital managers have the option to assign her to a non-primary bed though it is undesirable. Deciding when to use such "overflow" is difficult in real time and under uncertainty. Relevance: To aid the decision making, we model hospital inpatient flow as a multi-class, multi-pool parallel-server queueing system and formulate the overflow decision problem as a discrete-time, infinite-horizon average cost Markov decision process (MDP). The MDP incorporates many realistic and important features such as patient arrival and discharge patterns depending on time of day. Methodology: To overcome the curse-of-dimensionality of this formulated MDP, we resort to approximate dynamic programming (ADP). A critical part in designing an ADP algorithm is to choose appropriate basis functions to approximate the relative value function. Using a novel combination of fluid control and single-pool approximation, we develop analytical forms to approximate the relative value functions at midnight, which then guides the choice of the basis functions for all other times of day. Results: We demonstrate, via numerical experiments in realistic hospital settings, that our proposed ADP algorithm is remarkably effective in finding good overflow policies. These ADP policies can significantly improve system performance over some commonly used overflow strategies, e.g., in a baseline scenario, the ADP policy achieves a congestion level similar to that achieved by a complete bed sharing policy, while reduces the overflow proportion by 20%. Managerial Implications: We quantify the trade-off between the overflow proportion and congestion from implementing ADP policies under a variety of system conditions and generate useful insights. The plotted efficient frontiers allow managers to observe various performance measures in different parameter regimes, and the ADP policies provide managers with operational strategies to achieve the desired performance