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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beliën J (2007). Exact and heuristic methodologies for scheduling in hospitals: Problems, formulations and algorithms. 4OR-Q J Oper Res 5: 157–160.
Beliën J and Demeulemeester E (2008). A branch-and-price approach for integrating nurse and surgery scheduling. Eur J Opl Res 189: 652–668.
Burke EK, De Causmaecker P and Vanden Berghe G (2004). Novel metaheuristic approaches to nurse rostering problems in Belgian hospitals. In: Leung J (ed). Handbook of Scheduling: Algorithms, Models and Performance Analysis. CRC Press: Boca Raton, pp 1–18.
Burke EK, De Causmaecker P, Petrovic S and Vanden Berghe G (2006). Metaheuristics for handling time interval coverage constraints in nurse scheduling. Appl Artif Intell 20: 743–766.
Cheang B, Li H, Lim A and Rodrigues B (2003). Nurse rostering problems—a bibliographic survey. Eur J Opl Res 151: 447–460.
Chern CC, Chien PS and Chen SY (2008). A heuristic algorithm for the hospital health examination scheduling problem. Eur J Opl Res 186: 1137–1157.
Garey MR and Johnson DS (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman: New York.
Godart D, Laborie F and Nuijten W (2005). Randomized large neighborhood search for cumulative scheduling. In: Biundo S, Myers KL and Rajan K (eds). Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS). Monterrey. AAAI Press: Menlo Park, pp 81–89.
Hansen P and Mladenović N (1999). An introduction to variable neighborhood search. In: Voss S, Martello S, Osman IH and Roucairol C (eds). Metaheuristic: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers: Dordrecht, pp. 433–458.
Hansen P and Mladenović N (2001). Variable neighbourhood search: Principles and applications. Eur J Opl Res 130: 449–467.
Hansen P and Mladenović N (2002). Variable neighborhood search. In: Pardalos P and Resende M (eds). Handbook of Applied Optimization. Oxford University Press: New York, pp. 221–234.
Hansen P and Mladenović N (2003). Variable neighborhood search. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer Academic Publisher: Dordrecht, pp. 145–184.
Krempels KH and Panchenko A (2006). An approach for automated surgery scheduling. In: Burke EK and Rudová H (eds). Proceedings of the Sixth International Conference on the Practice and Theory of Automated Timetabling (PATAT), Brno. Springer: Berlin, pp 209–233.
Mladenović N and Hansen P (1997). Variable neighborhood search. Comput Opl Res 24: 1097–1100.
Mooney EL and Rardin RL (1993). Tabu search for a class of scheduling problems. Ann Opns Res 41: 253–278.
Negenman EG (2001). Local search algorithms for the multiprocessor flow shop scheduling problem. Eur J Opl Res 128: 147–158.
Nuijten W and Le Pape C (1998). Constraint-based job shop scheduling with ILOG SCHEDULER. J Heuristics 3: 271–286.
Oğuz C and Fikret Ercan M (1997). Scheduling multiprocessor tasks in a two-stage flow-shop environment. Comput Ind Eng 33: 269–272.
Sier D, Tobin P and McGurk C (1997). Scheduling surgical procedures. J Opl Res Soc 48: 884–891.
Souza MC and Martins P (2008). Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem. Eur J Opl Res 191: 677–690.
Van Oostrum JM, Van Houdenhoven M, Hurink JL, Hans EW, Wullink G and Kazemier G (2008). A master surgical scheduling approach for cyclic scheduling in operating room departments. OR Spektrum 30: 355–374.
Vasilakis C, Sobolev BG, Kuramoto L and Levy AR (2007). A simulation study of scheduling clinic appointments in surgical care: Individual surgeon versus pooled lists. J Opl Res Soc 58: 202–211.
Vlah S and Lukač Z (2005). A doctor–patient-treatment problem arising in hospitals. Presented at the Eighteenth Mini EURO Conference on Variable Neighbourhood Search (MECVNS), Puerto de la Cruz, Tenerife.
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).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vlah, S., Lukač, Z. & Pacheco, J. Use of VNS heuristics for scheduling of patients in hospital. J Oper Res Soc 62, 1227–1238 (2011). https://doi.org/10.1057/jors.2010.73
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.73