Stochastic patient admission scheduling with an exponential number of scenarios

Overstay patients—those who remain hospitalized longer than planned—generate substantial operational costs, worsen bed shortages, and delay care for other patients. This paper studies a stochastic variant of the well-known patient admission scheduling problem, which aims to assign patients to rooms during hospitalization while considering uncertain overstay lengths. We build two-stage stochastic programming models to formulate the problem, where the first stage assigns patients to rooms during their fixed length of stay, and the second stage evaluates the expected costs resulting from patient overstay. Compared to the typical scenario-based model, the proposed state-variable (SV) model is significantly reduced by having a pseudo-polynomial number of variables and constraints. To solve the SV model efficiently, we introduce the sample average approximation (SAA) method as the first attempt to provide a high-quality initial feasible solution for the Gurobi solver. To support practical decision-making under dynamic patient arrivals, the SAA-SV method is further embedded into a rolling horizon planning framework. Experimental results show that our SAA-SV method outperforms the methods of directly solving the scenario-based model and the state-variable model in terms of solution quality and computational time. In particular, the SAA-SV method can provide high-quality solutions with an average optimality gap of 3.75% for instances reaching 500 patients with 1-day overstay and 3.27 × 10150 scenarios within 1 hour. Additional analysis has also been carried out to verify the advantage of our proposed method over the typical deterministic approach and the SAA method.