Local search and lower bounds for the patient admission scheduling problem

We propose a multi-neighborhood local search procedure to solve a healthcare problem, known as the Patient Admission Scheduling problem. We design and experiment with different combinations of neighborhoods, showing that they have diverse effectiveness for different sets of weights of the cost components that constitute the objective function. We also compute many lower bounds based on the relaxation of some constraints. The outcome is that our results compare favorably with the previous work on the problem, improving all available instances, and in some cases are also quite close to the lower bounds. Finally, we propose the application of the technique to the dynamic case, in which admission and discharge dates are not predictable in advance. (c) 2011 Elsevier Ltd. All rights reserved.