Nurse Scheduling Problem Optimization based on Water Flow-like, Vibration Damping and Bee Colony Algorithms
محورهای موضوعی : فصلنامه ریاضی
Parisa Shahnazari-Shahrezaei
1
1 - Department of Industrial Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran
کلید واژه: Nurse Scheduling, Multi-objective Model, Water Flow-like Algorithm, Vibration Damping Optimization, Bee Colony Optimization.,
چکیده مقاله :
This research involves a nurse scheduling problem which is formulated as an integer programming model dealing with diverse constraints such as multi-skilled nurses’ requirements with different preferences and availabilities plus the hours and shifts related regulations. Due to its complex nature, two new meta-heuristic algorithms, namely, Water Flow-like Algorithm (WFA) and Vibration Damping Optimization (VDO) and another well-known meta-heuristic called Bee Colony Optimization (BCO) are developed. Two problem instances with up to 50 nurses and 35 days are defined considering a real case study via the data extracted from Isfahan-based Sina Hospital’s Infant Ward in Iran, the problems are solved to verify the effectiveness of the proposed algorithms and some comparison metrics are applied to evaluate their reliability. As the first problem yielded results displayed, 17 Pareto solutions have been gained for each objective function by the WFA algorithm, 2 Pareto solutions by VDO algorithm and 4 Pareto solutions through the BCO algorithm. And for the second problem, 50 Pareto solutions have been achieved by the WFA algorithm, 6 Pareto solutions by the VDO algorithm, and 9 Pareto solutions using the BCO algorithm. According to the results, the three approaches have the potential to solve the real nurse scheduling problems in large scale optimally (near-optimal) within minutes for both instances. Besides, the reported results show that compared to the other two algorithms, the WFA algorithm discovers the solutions with higher reliability.
This research involves a nurse scheduling problem which is formulated as an integer programming model dealing with diverse constraints such as multi-skilled nurses’ requirements with different preferences and availabilities plus the hours and shifts related regulations. Due to its complex nature, two new meta-heuristic algorithms, namely, Water Flow-like Algorithm (WFA) and Vibration Damping Optimization (VDO) and another well-known meta-heuristic called Bee Colony Optimization (BCO) are developed. Two problem instances with up to 50 nurses and 35 days are defined considering a real case study via the data extracted from Isfahan-based Sina Hospital’s Infant Ward in Iran, the problems are solved to verify the effectiveness of the proposed algorithms and some comparison metrics are applied to evaluate their reliability. As the first problem yielded results displayed, 17 Pareto solutions have been gained for each objective function by the WFA algorithm, 2 Pareto solutions by VDO algorithm and 4 Pareto solutions through the BCO algorithm. And for the second problem, 50 Pareto solutions have been achieved by the WFA algorithm, 6 Pareto solutions by the VDO algorithm, and 9 Pareto solutions using the BCO algorithm. According to the results, the three approaches have the potential to solve the real nurse scheduling problems in large scale optimally (near-optimal) within minutes for both instances. Besides, the reported results show that compared to the other two algorithms, the WFA algorithm discovers the solutions with higher reliability.
[1] Cheang, B., Li, H., Lim, A. & Rodrigues, B. (2003). “Nurse rostering problems-a bibliographic survey”. European Journal of Operational Research, 151 (3), pp. 447-460.
[2] 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 (6), pp. 441-499.
[3] Ernst, A., Jiang, H., Krishnamoorthy, M. & Sier, D. (2004). “Staff scheduling and rostering: A review of applications, methods, and models”. European Journal of Operations Research, 153 (1), pp. 3-27.
[4] Ernst, A., Jiang, H., Owens, M.K.B., Krishnamoorthy, M. & Sier, D. (2004). “An annotated bibliography of personnel scheduling and rostering”. Annals of Operations Research, 127 (1), pp. 21-144.
[5] Glass, C.A. & Knight, R.A. (2010). “The nurse rostering problem: A critical appraisal of the problem structure”. European Journal of Operational Research, 202 (2), pp. 379-389.
[6] Chiaramonte, M.V. & Chiaramonte, L.M. (2008). “An agent-based nurse rostering system under minimal staffing conditions”. International Journal of Production Economics, 114 (2), pp. 697- 713.
[7] Tsai, C.C. & Li, S.H.A. (2009). “A two-stage modeling with genetic algorithms for the nurse scheduling problem”. Expert Systems with Applications, 36 (5), pp. 9506-9512.
[8] Burke, E.K., Li, J. & Qu, R. (2010). “A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems”. European Journal of Operational Research, 203 (2), pp. 484-493.
[9] Shahnazari-Shahrezaei, P., Tavakkoli-Moghaddam, R., Azarkish, M. & Sadeghnejad-Barkousaraie, A. (2012). “A differential evolution algorithm developed for a nurse scheduling problem”. South African Journal of Industrial Engineering, 23(3), pp. 68-90.
[10] Buyukozkan, K. & Sarucan, A. (2014). “Applicability of artificial bee colony algorithm for nurse scheduling problems”. International Journal of Computational Intelligence Systems, 7(sup1), pp.121-136.
[11] Wong, T.C., Xu, M. & Chin, K.S. (2014). “A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department”. Computers & Operations Research, 51, pp.99-110.
[12] Constantino, A.A., Landa-Silva, D., de Melo, E.L., de Mendonça, C.F.X., Rizzato, D.B. & Romão, W. (2014). “A heuristic algorithm based on multi-assignment procedures for nurse scheduling”. Annals of Operations Research, 218(1), pp.165-183.
[13] Legrain, A., Bouarab, H. & Lahrichi, N. (2015). “The nurse scheduling problem in real-life”. Journal of medical systems, 39(1), p.160.
[14] Jafari, H., Bateni, S., Daneshvar, P., Bateni, S. & Mahdioun, H. (2016). “Fuzzy mathematical modeling approach for the nurse scheduling problem: a case study”. International Journal of Fuzzy Systems, 18(2), pp.320-332.
[15] Lim, G.J., Mobasher, A., Bard, J.F. & Najjarbashi, A. (2016). “Nurse scheduling with lunch break assignments in operating suites”. Operations Research for Health Care, 10, pp.35-48.
[16] Bagheri, M., Devin, A.G. & Izanloo, A. (2016). “An application of stochastic programming method for nurse scheduling problem in real word hospital”. Computers & Industrial Engineering, 96, pp.192-200.
[17] Di Martinelly, C. & Meskens, N. (2017). “A bi-objective integrated approach to building surgical teams and nurse schedule rosters to maximise surgical team affinities and minimise nurses' idle time”. International Journal of Production Economics, 191, pp.323-334.
[18] Legrain, A., Omer, J. & Rosat, S. (2018). “An Online Stochastic Algorithm for a Dynamic Nurse Scheduling Problem”. European Journal of Operational Research, 285(1), pp. 196-210.
[19] Zanda, S., Zuddas, P. & Seatzu, C. (2018). “Long term nurse scheduling via a decision support system based on linear integer programming: A case study at the University Hospital in Cagliari”. Computers & Industrial Engineering, 126, pp. 337-347.
[20] Wickert, T.I., Smet, P. & Berghe, G.V. (2018). “The nurse rerostering problem: strategies for reconstructing disrupted schedules”. Computers & Operations Research, 104, pp. 319-337.
[21] Hamid, M., Tavakkoli-Moghaddam, R., Golpaygani, F. & Vahedi-Nouri, B. (2019). “A multi-objective model for a nurse scheduling problem by emphasizing human factors”. Proceedings of the Institution of Mechanical Engineers, Part H: Journal of Engineering in Medicine, 234(2), pp. 179-199.
[22] Svirsko, A.C., Norman, B.A., Rausch, D. & Woodring, J. (2019). “Using mathematical modeling to improve the emergency department nurse-scheduling process”. Journal of emergency nursing, 45(4), pp. 425-432.
[23] Chen, P.S., Huang, W.T., Chiang, T.H. & Chen, G.Y.H. (2020). “Applying heuristic algorithms to solve inter-hospital hierarchical allocation and scheduling problems of medical staff”. International Journal of computational intelligence systems, 13(1), pp. 318-331.
[24] Khalili, N., Shahnazari-Shahrezaei, P. & Gholam Abri, A. (2020). “A multi-objective optimization approach for a nurse scheduling problem considering the fatigue factor (Case Study: Labbafinejad Hospital)”. Journal of Applied Research on Industrial Engineering, 7(4), pp. 396-423.
[25] Khalili, N., Shahnazari-Shahrezaei, P. & Gholam Abri, A. (2022). “Nurse scheduling problem considering service level in uncertain conditions”. Journal of Decisions and Operations Research, 7(Special Issue), pp. 1-23.
[26] Jafari, H. (2020). “Developing a fuzzy model for the nurse scheduling problem”. Journal of operational research in its applications (applied mathematics)-Lahijan Azad University, 17(2), pp. 93-107.
[27] Benzaid, M., Lahrichi, N. & Rousseau, L.M. (2020). “Chemotherapy appointment scheduling and daily outpatient–nurse assignment”. Health care management science, 23(1), pp. 34-50.
[28] Hamid, M., Tavakkoli-Moghaddam, R., Golpaygani, F. & Vahedi-Nouri, B. (2020). “A multi-objective model for a nurse scheduling problem by emphasizing human factors”. Proceedings of the institution of mechanical engineers, Part H: journal of
engineering in medicine, 234(2), pp. 179-199.
[29] Osogami, T. & Imai, H. (2000). “Classification of various neighbourhood operations for the nurse scheduling problem”. Lecture Notes in Computer Science, 1969, pp. 72-83.
[30] Vanhoucke, M. & Maenhout, B. (2009). “On the characterization and generation of nurse scheduling problem instances”. European Journal of Operational Research, 196(2), pp.457-467.
[31] Yang, F.C. & Wang, Y.P. (2007). “Water flow-like algorithm for object grouping problems”. Journal of the Chinese Institute of Industrial Engineers, 24 (6), pp. 475-488.
[32] Wu, T.H., Chung, S.H. & Chang, C.C. (2010). “A water flow-like algorithm for manufacturing cell formation problems”. European Journal of Operational Research, 205 (2), pp. 346-360.
[33] Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). “A fast and elitist multi-objective genetic algorithm: NSGA-II”. IEEE Transactions on Evolutionary Computation, 6 (2), pp. 182-197.
[34] Geiger, M.J. (2007). “On operators and search space topology in multi-objective flow shop scheduling”. European Journal of Operational Research, 181 (1), pp. 195-206.
[35] Mehdizadeh, E. & Tavakkoli-Moghaddam, R. (2008). “Vibration damping optimization”. In Proceedings of the International Conference of Operations Research and Global Business, Germany, pp. 3-5.
[36] Pham, D.T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S. & Zaidi, M. (2005). “Bee Algorithm-A Novel Approach to Function Optimisation”. Technical Note MEC 0501.
[37] Abraham, A., Jain, L. & Goldberg, R. (2005). “Evolutionary Multiobjective Optimization-Theoretical Advances and Applications”. Springer-Verlag London Limited, United States of America.
[38] Zhuang, Z. Y., & Vincent, F. Y. (2021). Analyzing the effects of the new labor law on outpatient nurse scheduling with law-fitting modeling and case studies. Expert Systems with Applications, 180, 115103.
[39] Leung, F., Lau, Y. C., Law, M., & Djeng, S. K. (2022). Artificial intelligence and end user tools to develop a nurse duty roster scheduling system. International journal of nursing sciences, 9(3), 373-377.
[40] Guo, J., & Bard, J. F. (2022). A column generation-based algorithm for midterm nurse scheduling with specialized constraints, preference considerations, and overtime. Computers & Operations Research, 138, 105597.
[41] Forthun, I., Waage, S., Pallesen, S., Moen, B. E., & Bjorvatn, B. (2022). A longitudinal study of work time schedule and prescribed sleep medication use in Norwegian nurses. Sleep Medicine, 100, S176.
[42] Turhan, A. M., & Bilgen, B. (2022). A mat-heuristic based solution approach for an extended nurse rostering problem with skills and units. Socio-Economic Planning Sciences, 101300.
[43] Chen, P.-S., Huang, W.-T., Chen, G. Y.-H., Dang, J.-F., & Yeh, E.-C. (2024). "Constructing Modified Variable Neighborhood Search Approaches to Solve a Nurse Scheduling Problem." International Journal of Production Research, 62(12), 7186-7204.
[44] Thomas, J. (2024). "Optimizing Nurse Scheduling: A Supply Chain Approach for Healthcare Institutions." Journal of Engineering and Science, 20(6s).
[45] Okoro, C. N., Egbuji, E. R., & Mmahi, E. C. (2024). "Integer Programming Approaches to Nurse Scheduling Problems (NSPs) in Management of Alex Ekwueme Federal University Teaching Hospital (AEFUTH), Abakaliki, Ebonyi State, Nigeria." Unpublished Manuscript.
[46] Torres Ramos, A. F., Castaño, F., Velasco, N., & Montoya, C. (2025). "A Multi-Objective Approach for the Nurse Scheduling Problem: A Home Health Care Delivery Case Study." SSRN Electronic Journal.
[47] Ghavampour, A. (2025). "Heuristic Approaches for the Home Health Care Staff Scheduling Problem." University of Ottawa Thesis.
[48] Abolghasemian, M., Kanai, A. G., & Daneshmandmehr, M. (2020). A two-phase simulation-based optimization of hauling system in open-pit mine. Iranian journal of management studies, 13(4), 705-732.
[49] Abolghasemian, M., & Darabi, H. (2018). Simulation based optimization of haulage system of an open-pit mine: Meta modeling approach. Organizational resources management researchs, 8(2), 1-17.
