A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation

Abstract

The problem of nurse scheduling is categorized in a Np-Hard complexity as it is inherently composed of many limitations and assumptions. As the number of nurses and the number of days increase, finding the solution of the problem becomes quite difficult. Therefore, this paper propose both an integer-programming model and a Lagrangian relaxation approach for solving nurse-scheduling problem. Numerical results show that while the developed mathematical model works on small-scale problems, Lagrangian relaxation method finds better results for large scale scheduling problem with much smaller duality gap in a reasonable computational time.

Keywords

• Nurse
• Scheduling
• Lagrangian Relaxation

References

1. Aickelin, U., & Dowsland, K. A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers & Operations Research, 31(5), 761-778.
2. Anderson, K., Zheng, B., Yoon, S. W., & Khasawneh, M. T. (2015). An analysis of overlapping appointment scheduling model in an outpatient clinic. Operations Research for Health Care, 4, 5-14.
3. Azaiez, M. N., & Al Sharif, S. S. (2005). A 0-1 goal programming model for nurse scheduling. Computers & Operations Research, 32, 491-507.
4. Bard, J., & Purnomo, H. (2005). Short-term nurse scheduling in response to daily fluctuations in supply and demand. Health Care Management Science, 8, 315-324.
5. Beliën, J. (2007). Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms (Doctoral dissertation, Springer-Verlag).
6. Bowers, M. R., Noon, C. E., Wu, W., & Bass, J. K. (2016). Neonatal physician scheduling at the University of Tennessee Medical Center. Interfaces, 46(2), 168-182.
7. Burke E. K., De Causmaecker P., Vanden Berghe G., &Van Landeghem H. (2004). The state of the art of nurse rostering. Journal of Scheduling 7, 441–499.
8. Cheang B., Li H., Lim A., & Rodrigues B. (2003). Nurse rostering problems—a bibliographic survey. European Journal of Operations Research, 151, 447–460.

9. Cummings Jr, D. D., & Shelton, R. H. (2002). U.S. Patent No. 6,345,260. Washington, DC: U.S. Patent and Trademark Office.
10. De Grano, M. L., Medeiros, D. J., & Eitel, D. (2009). Accommodating individual preferences in nurse scheduling via auctions and optimization. Health Care Management Science, 12(3), 228.
11. Dowsland, K. A., & Thompson, J. M. (2000). Solving a nurse scheduling problem with knapsacks, networks and tabu search. Journal of the Operational Research Society, 51(7), 825-833.
12. El Adoly, A. A., Gheith, M., & Fors, M. N. (2018). A new formulation and solution for the nurse scheduling problem: A case study in Egypt. Alexandria Engineering Journal, 57(4), 2289-2298.
13. Erhard, M., Schoenfelder, J., Fügener, A., & Brunner, J. O. (2018). State of the art in physician scheduling. European Journal of Operational Research, 265(1), 1-18.
14. Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. (2018). A Lagrangian relaxation-based algorithm to solve a Home Health Care routing problem. International Journal of Engineering, 31(10), 1734-1740.
15. Glass, C. A., & Knight, R. A. (2010). The nurse rostering problem: A critical appraisal of the problem structure. European Journal of Operational Research, 202, 379-389.
16. Hidri L., & Labidi M. (2016). Optimal physicians schedule in an Intensive Care Unit. IOP Conf. Series: Materials Science and Engineering 131, 1-8. Howell, J. P. (1966). Cyclical scheduling of nursing personnel. Hospitals, 40(2), 77-85.
17. Jafari, H., & Salmasi, N. (2015). Maximizing the nurses’ preferences in nurse scheduling problem: mathematical modeling and a meta-heuristic algorithm. Journal of Industrial Engineering International, 11(3), 439-458.
18. Maenhout, B., & Vanhoucke, M. (2007). An electromagnetic meta-heuristic for the nurse scheduling problem. Journal of Heuristics, 13(4), 359-385.
19. Maenhout, B., & Vanhoucke, M. (2012). An integrated nurse staffing and scheduling analysis for longer-term nursing staff allocation problems. Omega, 41(2), 485-499.
20. Moz, M., & Pato, M. V. (2004). Solving the problem of re-rostering nurse schedules with hard constraints: New multicommodity flow models. Annals of Operations Research, 128(1-4), 179-197.
21. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization, 2nd Edition, New York: Springer.
22. Randhawa, S. U., & Sitompul, D. (1993). A heuristic-based computerized nurse scheduling system. Computers & Operations Research, 20(8), 837-844.
23. Robinson, L. W., & Chen, R. R. (2003). Scheduling doctors' appointments: optimal and empirically-based heuristic policies. IIE Transactions, 35(3), 295-307.
24. Ozturkoglu, Y., & Bulfin, R. L. (2011). A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine. The International Journal of Advanced Manufacturing Technology, 57(5-8), 753-762.
25. Öztürkoğlu, Y., & Çalışkan, F. (2014). Hemşire çizelgelenmesinde esnek vardiya planlanması ve hastane uygulaması. Dokuz Eylül Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 16, 115-133.
26. Thongsanit, K., Kantangkul, K., & Nithimethirot, T. (2015). Nurse’s shift balancing in nurse scheduling problem. Silpakorn U Science & Tech J, 10, 43-48, 2015.
27. Youssef, A., & Senbel, S. (2018, January). A bi-level heuristic solution for the nurse-scheduling problem based on shift swapping. In 2018 IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC) (pp. 72-78), IEEE.
28. Wolfe, H., & Young, J. P. (1965). Staffing the nursing unit: Part I. controlled variable staffing. Nursing Research, 14(3), 236-242.
29. Zhou, B. H., Yin, M., & Lu, Z. Q. (2016). An improved Lagrangian relaxation heuristic for the scheduling problem of operating theatres. Computers & Industrial Engineering, 101, 490-503.