Nurse scheduling problem by considering total number of required nurses as well as nurses’ preferences for working shifts: An algorithmic game-theoretic approach

Document Type : Article


Industrial Engineering Group, Golpayegan College of Engineering, Isfahan University of Technology, Golpayegan 87717-67498, Iran


In this paper, nurse scheduling problem (NSP) is studied by minimizing the total number of the required nurses as well as by maximizing the nurses’ preferences for working shifts. In this setting, hospital’s managers set the total number of the required nurses while nurse-chiefs select the required part-timers and then assign shifts to all nurses including the full-timers and the selected part-timers. Obviously, competition between the managers and nurse-chiefs to make decisions leads to a conflict between their objectives. In this point of view, a two-player game-theoretic framework can be established between them to set decisions. To our knowledge, this study is the first one that develops the game-theoretic approach to solve the NSP. In this setting, four game-theoretic models, including Managers-Stackelberg, Nurses-Stackelberg, Nash, and Centralized, are proposed based on the various competitive and cooperative interactions between the players. Moreover, a mathematical programming model is developed to obtain the equilibrium strategies. It is found that the managers and nurse-chiefs gain their best responses under the Managers-Stackelberg and Nurses-Stackelberg games, respectively. In the Nash game, they make decisions in order to meet their objectives, mostly. Moreover, the equilibrium strategies given by the Managers-Stackelberg and Centralized games are the same.


  1. References

    1. Winberg, D.R., Lu, Y., Chen, Y., et al. “Can health technology assessments assist the global campaign against poverty?”, Global Health Journal, Inpress (2021).
    2. Zheng, Z., Liu, X. and Gong, X. “A simple randomized variable neighbourhood search for nurse rostering”, Computers & Industrial Engineering, 110, pp. 165-174 (2017).
    3. Moreno, M.S. and Blanco, A.M. “A Fuzzy Programming Approach for the Multi-objective Patient Appointment Scheduling Problem under Uncertainty in a Large Hospital”, Computers & Industrial Engineering, 123, pp. 33-41 (2018).
    4. Jafari, H. and Haleh, H. “Nurse scheduling problem by considering fuzzy modeling approach to treat uncertainty on nurses’ preferences for working shifts and weekends off”,Journal of Optimization in Industrial Engineering, 14, pp. 275-284 (2021).
    5. Aloisio, L.D., Coughlin, M. and Squires, J.E. “Individual and organizational factors of nurses' job satisfaction in long-term care: A Systematic Review”, International Journal of Nursing Studies, 104073 (2021).
    6. Jafari, H., Bateni, S., Daneshvar, P., et al. “Fuzzy Mathematical Modeling Approach for the Nurse Scheduling Problem: A Case Study”, International Journal of Fuzzy Systems, 25, pp. 1-13 (2017).
    7. Chen, P.S., Lin, Y.J. and Peng, N.C. “A two-stage method to determine the allocation and scheduling of medical staff in uncertain environments”, Computers & Industrial Engineering, 99, pp. 174-188 (2016).
    8. Purnomo, H.W. and Bard, J.F. “Cyclic Preference Scheduling for Nurses Using Branch and Price. Naval Research Logistics, 2006. 54: p. 200-220.
    9. Li, X., Rafaliya, N., Baki, M., et al. “Scheduling elective surgeries: the tradeoff among bed capacity, waiting patients and operating room utilization using goal programming”, Health Care Management Science, 20, pp. 33-54 (2017).
    10. Quan, V. “Retail labor scheduling”, OR/MS Today, 31, pp. 33–35 (2005).
    11. Bagheri, M., Devin, A.G. and Izanloo, A. “An application of stochastic programming method for nurse scheduling problem in real word hospital”, Computers & Industrial Engineering, 96, pp. 192-200 (2016).
    12. Lu, K.Y., Lin, P.L., Wu, C.M., et al. “The relationships among turnover intentions, professional commitment, and job satisfaction of hospital nurses”, Journal of Professional Nursing, 18, pp. 214-219 (2002).
    13. Bard, J.F. and Purnomo, H.W. “A column generation-based approach to solve the preference scheduling problem for nurses with downgrading”, Socio-Economic Planning Sciences, 39, pp. 193-213 (2005).
    14. Lopes, M.A., Almeida, A.S. and Almada-Lobo, B. “Forecasting the medical workforce: a stochastic agent-based simulation approach”, Health Care Management Science, 21, pp. 52-75 (2018).
    15. Guo, M., Wu, S., Li, B., et al. “Maximizing the efficiency of use of nurses under uncertain surgery durations: a case study”, Computers & Industrial Engineering, 78, pp. 313-319 (2014).
    16. Jafari, H. and Salmasi, N. “Maximizing the nurses’ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm”, Journal of Industrial Engineering International, 11, pp. 1-20 (2015).
    17. Smalley, H.K. and Keskinocak, P. “Automated medical resident rotation and shift scheduling to ensure quality resident education and patient care”, Health Care Management Science, 19, pp. 66-88 (2016).
    18. Michael, C., Jeffery, C. and David, C. “Nurse preference rostering using agents and iterated local search”, Annals of Operations Research, 226, pp. 443-461 (2015).
    19. Miller, H., Pierskalla, E.W. and Rath, G. “Nurse scheduling using mathematical programming”, Operations Research, 24, pp. 857-870 (1976).
    20. Azaiez, M.N. and Al-Sharif, S.S. “A 0-1 goal programming model for nurse scheduling”, Computers & Operations Research, 32, pp. 491-507 (2005).
    21. Al-Yakoob, M. and Sherali, H.D. “Mixed integer programming models for an employee scheduling problem with multiple shifts and work locations”, Annals of Operational Research, 155, pp. 119–142 (2007).
    22. Bard, J.F. and Purnomo, H.W. “Cyclic preference scheduling of nurses using a lagrangian-based heuristic”, Journal of Scheduling, 10, pp. 5-23 (2007).
    23. Maenhout, B. and Vanhoucke, M. “Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem”, Journal of Scheduling, 13(1), pp. 77-93 (2010).
    24. Burke, E.K. and Curtois, T. “New approaches to nurse rostering benchmark instances”, European Journal of Operational Research, 237, pp. 71-81 (2014).
    25. Gutjahr, W.J. and Rauner, M.S. “An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria”, Computers & Operations Research, 34, pp. 642-666 (2007).
    26. Majumdar, J. and Bhunia, A.K. “Elitist genetic algorithm for assignment problem with imprecise goal”, European Journal of Operational Research, 177, pp. 684–692 (2007).
    27. Hadwan, M., Ayob, M., Sabar, N.R., et al. “A harmony search algorithm for nurse rostering problems”, Information Sciences, 233, pp. 126-140 (2013).
    28. Wong, T.C., Xu, M. and Chin, K.S. “A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department”, Computers & Operations Research, 51, pp. 99-110 (2014).
    29. Legrain, A., Bouarab, H. and Lahrichi, N. “The Nurse Scheduling Problem in Real-Life”, Journal of Medical Systems, 39, pp. 1-11 (2014).
    30. Issaoui, B., Zidi, I., Marcon, E., et al “New Multi-Objective Approach for the Home Care Service Problem Based on Scheduling Algorithms and Variable Neighborhood Descent”, Electronic Notes in Discrete Mathematics, 47, pp. 181-188 (2015).
    31. Aickelin, U. and Dowsland, K.A. “An indirect Genetic Algorithm for a nurse-scheduling problem”, Computers & Operations Research, 31, pp. 761-778 (2014).
    32. Tassopoulos, I.X., Solos, I.P. and Beligiannis, G.N. “Α two-phase adaptive variable neighborhood approach for nurse rostering”, Computers & Operations Research, 60, pp. 150-169 (2015).
    33. Chen, L. “Design of shared unit-dose drug distribution network using multi-level particle swarm optimization”, Health Care Management Science, 22, pp. 304-317 (2019).
    34. Dowsland, K.D. and Thompson, J.M. “Nurse scheduling with knapsacks, networks and tabu search”, Journal of the Operational Research Society, 51, pp. 825–833 (2000).
    35. Bard, J.F. and Purnomo, H.W. “Preference scheduling for nurses using column generation”, European Journal of Operational Research, 164, pp. 510-534 (2005).
    36. He, F. and Qu, R. “A constraint programming based column generation approach to nurse rostering problems”, Computers & Operations Research, 39, pp. 3331-3343 (2012).
    37. Li, J., Burke, E.K., Curtois, T., et al. “The falling tide algorithm: A new multi-objective approach for complex workforce scheduling”, Omega, 40, pp. 283-293 (2012).
    38. Van Oostveen, C.J., Mathijssen, E. and Vermeulen, H. “Nurse staffing issues are just the tip of the iceberg: A qualitative study about nurses’ perceptions of nurse staffing”, International Journal of Nursing Studies, 52, pp. 1300-1309 (2015).
    39. Jafari, H., Hejazi, S.R. and Rasti-Barzoki, M. “Pricing decisions in dual-channel supply chain including monopolistic manufacturer and duopolistic retailers: a game-theoretic approach”,Journal of Industry, Competition and Trade, 16, pp. 323-343 (2016).
    40. Jafari, H. “Sustainable development by reusing of recyclables in a textile industry including two collectors and three firms: A game-theoretic approach for pricing decisions”,Journal of Cleaner Production, 229, pp. 598-610 (2019).
    41. Jafari, H., Hejazi, S.R. and Rasti, M. “Pricing decisions in dual-channel supply chain with one manufacturer and multiple retailers: A game-theoretic approach”,RAIRO-Operations Research, 51, pp. 1269-1287 (2017).
    42. Jafari, H., Hejazi, S.R. and Rasti-Barzoki, M. “Game theoretical approach to price a product under two-echelon supply chain containing e-tail selling channel”,International Journal of Services and Operations Management, 36, pp. 131-160 (2020).
    43. Pinedo, M.L. “Scheduling: Theory, Algorithms, and Systems”, Third Edition ed, ed. P. Hall, NewYork, NY 10013, USA: Springer (2008).
    44. Saati, T.L. “A scaling method for priorities in hierarchical structures”, Journal of Mathematical Psychology, 15, pp. 234–281 (1977).