Abstract
Hospital personnel scheduling deals with a large number of constraints of a different nature, some of which need to be satisfied at all costs. It is, for example, unacceptable not to fully support patient care needs and therefore a sufficient number of skilled personnel has to be scheduled at any time. In addition to personnel coverage constraints, nurse rostering problems deal with time-related constraints arranging work load, free time, and personal requests for the staff.
Real-world nurse rostering problems are usually over-constrained but schedulers in hospitals manage to produce solutions anyway. In practice, coverage constraints, which are generally defined as hard constraints, are often relaxed by the head nurse or personnel manager.
The work presented in this paper builds upon a previously developed nurse rostering system that is used in several Belgian hospitals. In order to deal with widely varying problems and objectives, all the data in the model are modifiable by the users.
We introduce a set of specific algorithms for handling and even relaxing coverage constraints, some of which were not supposed to be violated in the original model. The motivation is that such practices are common in real scheduling environments. Relaxations enable the generation of better-quality schedules without enlarging the search space or the computation time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahmad, J., Yamamoto, M., Ohuchi, A.: Evolutionary Algorithms for Nurse Scheduling Problem. In: Proc. 2000 Congress Evolut. Comput., CEC 2000, San Diego, CA, pp. 196–203 (2000)
Aickelin, U., Dowsland, K.: Exploiting Problem Structure in a Genetic Algorithm Approach to a Nurse Rostering Problem. J. Scheduling 3, 139–153 (2000)
Berrada, I., Ferland, J., Michelon, P.: A Multi-Objective Approach to Nurse Scheduling with both Hard and Soft Constraints. Socio-Econ. Planning Sci. 30, 183–193 (1996)
Burke, E.K., Cowling, P., De Causmaecker, P., Vanden Berghe, G.: A Memetic Approach to the Nurse Rostering Problem. Appl. Intell (special issue on Simulated Evolution and Learning) 15, 199–214 (2001)
Burke, E.K., De Causmaecker, P., Petrovic, S., Vanden Berghe, G.: Floating Personnel Requirements in a Shift Based Timetable, Working Paper, KaHo St-Lieven (2001)
Burke, E.K., De Causmaecker, P., Petrovic, S., Vanden Berghe, G.: Fitness Evaluation for Nurse Scheduling Problems. In: Proc. Congress Evolut. Comput., CEC 2001, Seoul, South Korea, pp. 1139–1146. IEEE Press, Los Alamitos (2001)
Burke, E.K., De Causmaecker, P., Petrovic, S., Vanden Berghe, G.: Variable Neighbourhood Search for Nurse Rostering Problems. In: Proc. 4th Metaheuristics Int. Conf., MIC 2001, Porto, Portugal, pp. 755–760 (2001) (accepted for publication in the selected papers volume by Kluwer)
Burke, E.K., De Causmaecker, P., Vanden Berghe, G.: A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem. In: McKay, B., Yao, X., Newton, C.S., Kim, J.-H., Furuhashi, T. (eds.) SEAL 1998. LNCS (LNAI), vol. 1585, pp. 187–194. Springer, Heidelberg (1999)
Chen, J.-G., Yeung, T.: Hybrid Expert System Approach to Nurse Scheduling. Comput. Nursing 11, 183–192 (1993)
Chiarandini, M., Schaerf, A., Tiozzo, F.: Solving Employee Timetabling Problems with Flexible Workload using Tabu Search. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 298–302. Springer, Heidelberg (1996)
Dowsland, K.: Nurse scheduling with Tabu Search and Strategic Oscillation. Eur. J. Oper. Res. 106, 393–407 (1998)
Isken, M., Hancock, W.: A Heuristic Approach to Nurse Scheduling in Hospital Units with Non-Stationary, Urgent Demand, and a Fixed Staff Size. J. Soc. Health Syst. 2, 24–41 (1990)
Kawanaka, H., Yamamoto, K., Yoshikawa, T., Shinogi, T., Tsuruoka, S.: Genetic Algorithm with the Constraints for Nurse Scheduling Problem. In: Proc. Congress Evolut. Comput., CEC 2001, Seoul, South Korea, pp. 1123–1130. IEEE Press, Los Alamitos (2001)
Meisels, A., Gudes, E., Solotorevski, G.: Employee Timetabling, Constraint Networks and Knowledge-Based Rules: a Mixed Approach. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 93–105. Springer, Heidelberg (1996)
Meyer auf’m Hofe, H.: Solving Rostering Tasks as Constraint Optimization. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 191–212. Springer, Heidelberg (2001)
Miller, M.L., Pierskalla, W., Rath, G.: Nurse Scheduling Using Mathematical Programming. Oper. Res. 24, 857–870 (1976)
Okada, M.: An Approach to the Generalised Nurse Scheduling Problem – Generation of a Declarative Program to Represent Institution-Specific Knowledge. Comput. Biomed. Res. 25, 417–434 (1992)
Ozkarahan, I.: A Disaggregation Model of a Flexible Nurse Scheduling Support System. Socio-Econ. Planning Sci. 25, 9–26 (1991)
Vanden Berghe, G.: Soft constraints in the Nurse Rostering Problem (2001), http://www.cs.nott.ac.uk/~gvb/constraints.ps
Warner, M.: Scheduling Nursing Personnel According to Nursing Preference: a Mathematical Programming Approach. Oper. Res. 24, 842–856 (1976)
Warner, M., Prawda, J.: A Mathematical Programming Model for Scheduling Nursing Personnel in a Hospital. Manage. Sci. 19, 411–422 (1972)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
De Causmaecker, P., Vanden Berghe, G. (2003). Relaxation of Coverage Constraints in Hospital Personnel Rostering. In: Burke, E., De Causmaecker, P. (eds) Practice and Theory of Automated Timetabling IV. PATAT 2002. Lecture Notes in Computer Science, vol 2740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45157-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-45157-0_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40699-0
Online ISBN: 978-3-540-45157-0
eBook Packages: Springer Book Archive