Clustering clinical departments for wards to achieve a prespecified blocking probability

When the number of available beds in a hospital is limited and fixed, it can be beneficial to cluster several clinical departments such that the probability of not being able to admit a patient is acceptably small. The clusters are then assigned to the available wards such that enough beds are available to guarantee a blocking probability below a prespecified value. We first give an exact formulation of the problem to be able to achieve optimal solutions. To reduce computation times, we also introduce two heuristic solution methods. The first heuristic is similar to the exact solution method, however, the number of beds needed is approximated by a linear function. The second heuristic uses a local search approach to determine the assignment of clinical departments to clusters and a restricted version of the exact solution method to determine the assignment of clusters to wards.