AN APPLICATION OF GRAPH COLORING: NURSE SCHEDULING PROBLEM

Authors

  • Anjali Gangrade Department of Mathematics, Rabindranath Tagore University, Bhopal (M.P), India
  • Bhawna Agrawal Department of Mathematics, Rabindranath Tagore University, Bhopal (M.P), India
  • Sanjit Kumar Department of Mathematics Lakshmi Narain College of Technology & Science, Bhopal (M.P), India

DOI:

https://doi.org/10.29121/shodhkosh.v5.i3.2024.2521

Keywords:

Graph Coloring, NSP- Nurse Scheduling Problem, NR- Nurse Roster, Scheduling Techniques

Abstract [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

2024-03-31

How to Cite

Gangrade, A., Agrawal, B., & Kumar, S. (2024). AN APPLICATION OF GRAPH COLORING: NURSE SCHEDULING PROBLEM. ShodhKosh: Journal of Visual and Performing Arts, 5(3), 573–579. https://doi.org/10.29121/shodhkosh.v5.i3.2024.2521