Use of VNS heuristics for scheduling of patients in hospital

Abstract

One of the important problems in hospital management is how to schedule the treatments of resident patients in hospital for a given day due to the restrictions imposed by their medical condition as well as restrictions on medical machines and qualified medical personnel availability. Patients are to be subjected to different kinds of treatments, each requiring a medical machine of a certain type as well as a physician being qualified to operate it. This is a highly complex problem not yet adequately addressed in the literature. At present in most hospitals the problem is being solved manually by specialized personnel. However, the resulting schedules are very often inaccurate and inefficient with patients waiting for a long time to be treated and medical personnel often working overtime. In this paper we formulate the model for this problem and develop a simple and efficient method based on Variable Neighbourhood Search for solving it. The heuristics has been tested on real-life as well as on generated instances. Numerical results show that the heuristics proposed outperform commercial software for optimization as well as manual solutions both in quality of solution and in computational time.

Keywords:

• health service
• scheduling
• hospitals
• heuristics
• reduced VNS

Acknowledgements

Authors are grateful for financial support from the Spanish Ministry of Education and Science and FEDER founds (National Plan of R&D—Projects SEJ2005-08923/ECON and ECO2008-06159/ECON) and from University of Burgos and ‘Caja de Burgos’ (grants to develop research projects 2009).