A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation

Öztürkoğlu, Yücel

doi:http://dx.doi.org/10.17093/alphanumeric.659121

A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation

Yücel Öztürkoğlu, Ph.D.

Abstract

The problem of nurse scheduling is categorized in an 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: Lagrangian Relaxation, Mathematical Model, Nurse, Scheduling

Jel Classification: C46

Suggested citation

Öztürkoğlu, Y. (2020). A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation. Alphanumeric Journal, 8(2), 237-248. http://dx.doi.org/10.17093/alphanumeric.659121

bibtex

References

Aickelin, U., & Dowsland, K. A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers & Operations Research, 31(5), 761-778.
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.
Azaiez, M. N., & Al Sharif, S. S. (2005). A 0-1 goal programming model for nurse scheduling. Computers & Operations Research, 32, 491-507.
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.
Beliën, J. (2007). Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms (Doctoral dissertation, Springer-Verlag).
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.
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.
Cheang B., Li H., Lim A., & Rodrigues B. (2003). Nurse rostering problems—a bibliographic survey. European Journal of Operations Research, 151, 447–460.
Cummings Jr, D. D., & Shelton, R. H. (2002). U.S. Patent No. 6,345,260. Washington, DC: U.S. Patent and Trademark Office.
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.
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.
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.
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.
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.
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.
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.
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.
Maenhout, B., & Vanhoucke, M. (2007). An electromagnetic meta-heuristic for the nurse scheduling problem. Journal of Heuristics, 13(4), 359-385.
Maenhout, B., & Vanhoucke, M. (2012). An integrated nurse staffing and scheduling analysis for longer-term nursing staff allocation problems. Omega, 41(2), 485-499.
Moslemi, S., Sabegh, M. H. Z., Mirzazadeh, A., Ozturkoglu, Y., & Maass, E. (2017). A multi-objective model for multi-production and multi-echelon closed-loop pharmaceutical supply chain considering quality concepts: NSGAII approach. International Journal of System Assurance Engineering and Management, 8(2), 1717-1733.
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.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization, 2nd Edition, New York: Springer.
Ozbekler, T. M., & Ozturkoglu, Y. (2020). Analyzing the importance of sustainability‐oriented service quality in competition environment. Business Strategy and the Environment, 29(3), 1504-1516.
Ozturkoglu, Y. (2015). An efficient time algorithm for makespan objectives. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 5(2), 75-80.
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.
Ö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.
Randhawa, S. U., & Sitompul, D. (1993). A heuristic-based computerized nurse scheduling system. Computers & Operations Research, 20(8), 837-844.
Robinson, L. W., & Chen, R. R. (2003). Scheduling doctors' appointments: optimal and empirically-based heuristic policies. IIE Transactions, 35(3), 295-307.
Saygili, E., & Ozturkoglu, Y. (2020). Patients’ rights and professional conduct issues in hospitals’ codes of ethics. International Journal of Human Rights in Healthcare, 13(3), 201-208.
Thongsanit, K., Kantangkul, K., & Nithimethirot, T. (2015). Nurse’s shift balancing in nurse scheduling problem. Silpakorn U Science & Tech J, 10, 43-48, 2015.
Wolfe, H., & Young, J. P. (1965). Staffing the nursing unit: Part I. controlled variable staffing. Nursing Research, 14(3), 236-242.
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.
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.