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

Document Type : Research Paper


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


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.


Main Subjects

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 Sciences30(3), 183-193.
Blöchliger, I. (2004). Modeling staff scheduling problems. A tutorial.European Journal of Operational Research158(3), 533-542.
Brucker, P., Qu, R., & Burke, E. (2011). Personnel scheduling: Models and complexity. European Journal of Operational Research210(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 scheduling7(6), 441-499.
Burns, R. N. (1978). Manpower scheduling with variable demands and alternate weekends off. INFOR: Information Systems and Operational Research16(2), 101-111.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems––a bibliographic survey. European Journal of Operational Research151(3), 447-460.
Dowsland, K. A. (1998). Nurse scheduling with tabu search and strategic oscillation. European journal of operational research106(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 Research127(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 research107(1), 1-18.
Marchionno, P. M. (1987). Modified Cyclical Scheduling: A Practical Approach: A step-by-step guide for developing a cyclical schedule. Nursing management18(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 research104(3), 582-592.
Smith, L. D., & Wiggins, A. (1977). A computer-based nurse scheduling system. Computers & Operations Research4(3), 195-212.
Thompson, G. M. (1996). A simulated-annealing heuristic for shift scheduling using non-continuously available employees. Computers & Operations Research23(3), 275-288.