Solving a nurse rostering problem considering nurses preferences by graph theory approach

Document Type : Research Paper

Authors

School of Industrial Engineering, University of Tehran, Tehran , IRAN

Abstract

Nurse Rostering Problem (NRP) or the Nurse Scheduling Problem (NSP) is a complex scheduling problem that affects hospital personnel on a daily basis all over the world and is known to be NP-hard.The problem is to decide which members of a team of nurses should be on duty at any time, during a rostering period of, typically, one month.It is very important to efficiently utilize time and effort, to evenly balance the workload among people and to attempt to satisfy personnel preferences.With demand ever fluctuating, designing a timetable to definea work schedule for each nurse is not an easy task.A NRP deals with a very high number of constraints.A lot of big healthcare organizations around the world still construct nurses’ duty roster manually.Many optimization algorithms have been proposedto solve NRPs such as exact algorithms and (Meta)heuristic algorithms. In this paper we propose an approach that use the graph theory concept to solve the problem. We use the graph coloring and bipartite graph concept. In our approach we first formulize the problem and solve it with exact algorithm and then by using the graph concept, the solution is improved. Finally by results obtained from the graph approaches the final timetable is available.In in order to validate the proposed approach some problems with different scales are solved. We solved the problems for 30, 40, 45 and 50 nurses. In all problems the proposed approach is efficient and for instance the relationship between the nurses are presented.

Keywords

Main Subjects

References

Aickelin, U. & Dowsland, K. (2001). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem, Journal of Scheduling, 3(3), 139–153.
Berrada, I., Ferland, J. A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard and soft constraints. Socio-Economic Planning Sciences, 30(3), 183-193.
Blöchliger, I. (2004). Modeling staff scheduling problems. A tutorial.European Journal of Operational Research, 158(3), 533-542.
Brucker, P., Qu, R., & Burke, E. (2011). Personnel scheduling: Models and complexity. European Journal of Operational Research, 210(3), 467-473.
Burke, E. K., De Causmaecker, P., Berghe, G. V., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of scheduling, 7(6), 441-499.
Burns, R. N. (1978). Manpower scheduling with variable demands and alternate weekends off. INFOR: Information Systems and Operational Research, 16(2), 101-111.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems––a bibliographic survey. European Journal of Operational Research, 151(3), 447-460.
Dowsland, K. A. (1998). Nurse scheduling with tabu search and strategic oscillation. European journal of operational research, 106(2), 393-407.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1-4), 21-144.
Haspeslagh, S., De Causmaecker, P., Stolevik, M., Schaerf, A. First International Nurse Rostering Competition 2010, in: Proceedings of the 8th International Conference for the Practice and Theory of Automated Timetabling, Northern Ireland, 2010, pp. 498–501.
Jan, A., Yamamoto, M., & Ohuchi, A. (2000). Evolutionary algorithms for nurse scheduling problem. In Evolutionary Computation, 2000. Proceedings of the 2000 Congress on (Vol. 1, pp. 196-203). IEEE.
Jaumard, B., Semet, F., & Vovor, T. (1998). A generalized linear programming model for nurse scheduling. European journal of operational research, 107(1), 1-18.
Marchionno, P. M. (1987). Modified Cyclical Scheduling: A Practical Approach: A step-by-step guide for developing a cyclical schedule. Nursing management, 18(10), 60.
Millar, H. H., & Kiragu, M. (1998). Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming. European journal of operational research, 104(3), 582-592.
Smith, L. D., & Wiggins, A. (1977). A computer-based nurse scheduling system. Computers & Operations Research, 4(3), 195-212.
Thompson, G. M. (1996). A simulated-annealing heuristic for shift scheduling using non-continuously available employees. Computers & Operations Research, 23(3), 275-288.

Files

History

  • Receive Date: 16 June 2017
  • Revise Date: 01 August 2017
  • Accept Date: 05 August 2017

Share

How to cite

Statistics