AN APPLICATION OF GRAPH COLORING: NURSE SCHEDULING PROBLEM
DOI:
https://doi.org/10.29121/shodhkosh.v5.i3.2024.2521Keywords:
Graph Coloring, NSP- Nurse Scheduling Problem, NR- Nurse Roster, Scheduling TechniquesAbstract [English]
The Nurse Rostering Problem (NRP), also known as the Nurse Scheduling Problem (NSP), represents a challenging scheduling issue that significantly impacts hospital staff worldwide on a daily basis. Nursing staff scheduling is one of the most important but complex problem for the hospital management. NSP is a critical subclass of scheduling problems known for their complexity. This paper introduces an efficient approach to solving the Nurse Scheduling Problem (NSP), aiming to meet the needs of nurses, patients, and hospital management. It requires critical thinking and good decision-making skills to develop a roster that effectively balances patient care, employee and other needs in the organization. To reduce the problem's complexity, graph coloring techniques have been utilized.
References
Baumelt, Z., Sucha, P., Hanzalek, Z. (2007), Nurse Scheduling Web Application, In Proceedings of the 26th Workshop of the UK Planning and Scheduling Special Interest Group, Prague, UK MFF.
Dowsland K. A. (1998), Nurse scheduling with tabu search and strategic oscillation, European Journal of Operational Research, vol. 106, pp. 393–407. DOI: https://doi.org/10.1016/S0377-2217(97)00281-6
Ernst, A. T., Jiang, H., Krishnamoorthy, M. and Sier. D. (2004), Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research. vol.153, pp. 3-27. DOI: https://doi.org/10.1016/S0377-2217(03)00095-X
Gangrade, A., Agrawal, B. and Kumar, S. (2023), Subject Allocation Bipartite Graph Coloring. Samdarshi, vol. 16(4), pp. 3128-3132.
Gangrade, A., Agrawal, B., Kumar, S. and Mansuri, A. (2022), A study of applications of graph colouring in various fields, International Journal of Statistics and Applied Mathematics, 7(2), pp 51-53. DOI: https://doi.org/10.22271/maths.2022.v7.i2a.795 DOI: https://doi.org/10.22271/maths.2022.v7.i2a.795
Goodman, M. D., Dowsland, K. A., and Thompson, J. M. (2009), A grasp-knapsack hybrid for a nurse-scheduling problem. Journal of Heuristics, vol.15(4), pp. 351-379. DOI: https://doi.org/10.1007/s10732-007-9066-7
Grano, M.L.D., Medeiros, D. J. and Eitel, D. (2009), Health Care Manage Sci, vol. 12, pp. 228–242. DOI: https://doi.org/10.1007/s10729-008-9087-2
Hsia, T. L., Lin, L. M., Wu, J. H. and Tsai, H. T. (2006), A framework for designing nursing
knowledge management system, Interdisciplinary Journal of Information, Knowledge, and Management. 1, 13-22.
Kumara B.T.G.S. and Perera, A.A.I. (2011), Automated system for nurse scheduling using Graph Colouring. Indian Journal of Computer Science and Engineering, vol. 2 (3), pp. 476-485.
Malviya, A., Agrawal, B., Kumar, S. and Mansuri, A. (2022), Study of algorithm for coloring in various graph, International Journal of Statistics and Applied Mathematics, vol. 7(2), pp 88-91. DOI: https://doi.org/10.22271/maths.2022.v7.i2b.798 DOI: https://doi.org/10.22271/maths.2022.v7.i2b.798
Miller, H. E., Pierskalla, W. P. and Rath, G. J. (1976), Nurse scheduling using mathematical programming. Operations Research. vol. 24(5), pp. 857-870. DOI: https://doi.org/10.1287/opre.24.5.857
Teahan, B. (1998), Implementation of a self-scheduling system: a solution to more than just schedules, Journal of Nursing Management, vol. 6(6), pp. 361-68. DOI: https://doi.org/10.1046/j.1365-2834.1998.00096.x
Wren, A. (1996), Scheduling, Timetabling and Rostering: A Special Relationship, International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153, Burke, E., Ross, P. (editors.), Springer Verlag, Berlin, Heidelberg, New York, pp. 46-75. DOI: https://doi.org/10.1007/3-540-61794-9_51
Wright, P. D., Bretthauer, K. M. and Cote, M. J. (2006), Re-examining the nurse scheduling problem: Staffing ratios and nursing shortages. Decision Sciences, vol. 37(1), pp.39-67. DOI: https://doi.org/10.1111/j.1540-5414.2006.00109.x
Yi, Y. (2005). Application of finite-state machines in medical care scheduling. Electrical and Computer Engineering, Duke
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Anjali Gangrade, Bhawna Agrawal, Sanjit Kumar

This work is licensed under a Creative Commons Attribution 4.0 International License.
With the licence CC-BY, authors retain the copyright, allowing anyone to download, reuse, re-print, modify, distribute, and/or copy their contribution. The work must be properly attributed to its author.
It is not necessary to ask for further permission from the author or journal board.
This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge.