(Universiti Teknikal Malaysia Melaka (UTeM), Malaysia)(2) Zeratul Izzah Mohd Yusoh
(Universiti Teknikal Malaysia Melaka (UTeM), Malaysia)(3) Halizah Basiron
(Universiti Teknikal Malaysia Melaka (UTeM),, Malaysia)(4) Azlina Daud
(International Islamic University Malaysia (IIUM), Malaysia)*corresponding author
AbstractThe Nurse Scheduling Problem (NSP) is a complex workforce planning task that involves assigning nurses to shifts while satisfying operational feasibility, legal regulations and preference-based quality requirements. Classical Genetic Algorithms (GA) are widely applied to NSP but rely on monolithic optimisation structures that evaluate all constraints within a single population, which can lead to constraint interference and reduced stability as problem realism increases. This study investigates a Cooperative Co-Evolutionary approach for NSP (Coop-NSP), which decomposes optimisation into two interacting subpopulations corresponding to hard and soft constraints. Both subpopulations employ an identical nurse-by-day chromosome representation and evolve independently under specialised objectives, with cooperation introduced through contextual fitness evaluation. Experiments were conducted on a weekly NSP with a seven-day planning horizon and multiple nurse roles, evaluated for 15,000 generations across 30 independent runs under identical parameter settings. The Classical GA achieved a mean best penalty of 651.30 ± 37.90, with a minimum best penalty of 581.7, while Coop-NSP obtained a higher mean best penalty of 768.72 but achieved a lower minimum best penalty of 507.64. The Classical GA exhibited rapid convergence, whereas Coop-NSP demonstrated stepwise convergence with sustained population diversity. Although Coop-NSP incurred higher computational cost, its structured cooperative optimisation framework provides a stable and extensible foundation for future integrated healthcare scheduling research.
KeywordsNurse Scheduling Problem; Cooperative Co-evolutionary Algorithm; Genetic Algorithm; Evolutionary Optimisation; Healthcare Scheduling.
|
DOIhttps://doi.org/10.26555/ijain.v12i3.2409 |
Article metricsAbstract views : 186 | PDF views : 1 |
Cite |
Full Text Download
|
References
[1] A. Jan, M. Yamamoto, and A. Ohuchi, “Search Algorithms for Nurse Scheduling with Genetic Algorithms,” Springer, Boston, MA, 2002, pp. 149–161. doi: 10.1007/978-1-4615-0819-9_9.
[2] A. C. Adamuthe and R. Bichkar, “Hybrid Genetic Algorithmic Approaches for Personnel Timetabling and Scheduling Problems in Healthcare,” in International Journal of Computer Applications®, IJCA, 2011, p. 8. [Online] Available at: https://www.ijcaonline.org/proceedings/ictsm/number2/2785-108/.
[3] C. M. Ngoo, S. L. Goh, S. N. Sze, N. R. Sabar, S. Abdullah, and G. Kendall, “A Survey of the Nurse Rostering Solution Methodologies: The State-of-the-Art and Emerging Trends,” IEEE Access, vol. 10, pp. 56504–56524, 2022, doi: 10.1109/ACCESS.2022.3177280.
[4] P.-S. Chen and Z.-Y. Zeng, “Developing two heuristic algorithms with metaheuristic algorithms to improve solutions of optimization problems with soft and hard constraints: An application to nurse rostering problems,” Appl. Soft Comput., vol. 93, no. August, p. 106336, Aug. 2020, doi: 10.1016/j.asoc.2020.106336.
[5] N. Nico, N. Charibaldi, and Y. Fauziah, “Comparison of Memetic Algorithm and Genetic Algorithm on Nurse Picket Scheduling at Public Health Center,” Int. J. Artif. Intell. Robot., vol. 4, no. 1, pp. 9–23, May 2022, doi: 10.25139/ijair.v4i1.4323.
[6] H. İ. Koruca, M. S. Emek, and E. Gulmez, “Development of a new personalized staff-scheduling method with a work-life balance perspective: case of a hospital,” Ann. Oper. Res., vol. 328, no. 1, pp. 793–820, Sep. 2023, doi: 10.1007/s10479-023-05244-2.
[7] M. R. Hassani and J. Behnamian, “A scenario-based robust optimization with a pessimistic approach for nurse rostering problem,” J. Comb. Optim., vol. 41, no. 1, pp. 143–169, Jan. 2021, doi: 10.1007/s10878-020-00667-0.
[8] P. Rerkjirattikal, V.-N. Huynh, S. Olapiriyakul, and T. Supnithi, “A Goal Programming Approach to Nurse Scheduling with Individual Preference Satisfaction,” Math. Probl. Eng., vol. 2020, no. 1, pp. 1–11, Nov. 2020, doi: 10.1155/2020/2379091.
[9] E. C. Yagmur and A. Sarucan, “Nurse scheduling with opposition-based parallel harmony search algorithm,” J. Intell. Syst., vol. 28, no. 4, pp. 633–647, Oct. 2021, doi: 10.1515/JISYS-2017-0150/XML.
[10] C.-C. Lin, J.-R. Kang, and T.-H. Hsu, “A Memetic Algorithm with Recovery Scheme for Nurse Preference Scheduling,” J. Ind. Prod. Eng., vol. 32, no. 2, pp. 83–95, Feb. 2015, doi: 10.1080/21681015.2014.997815.
[11] X. Ma et al., “A Survey on Cooperative Co-Evolutionary Algorithms,” IEEE Trans. Evol. Comput., vol. 23, no. 3, pp. 421–441, Jun. 2019, doi: 10.1109/TEVC.2018.2868770.
[12] Q. Xiao, J. Zhong, L. Feng, L. Luo, and J. Lv, “A Cooperative Coevolution Hyper-Heuristic Framework for Workflow Scheduling Problem,” IEEE Trans. Serv. Comput., vol. 15, no. 1, pp. 150–163, Jan. 2022, doi: 10.1109/TSC.2019.2923912.
[13] S. Qin, D. Pi, Z. Shao, and Y. Xu, “A Cluster-Based Cooperative Co-Evolutionary Algorithm for Multiobjective Workflow Scheduling in a Cloud Environment,” IEEE Trans. Autom. Sci. Eng., vol. 20, no. 3, pp. 1648–1662, Jul. 2023, doi: 10.1109/TASE.2022.3183681.
[14] C. Wang et al., “Cooperative co-evolutionary differential evolution algorithm applied for parameters identification of lithium-ion batteries,” Expert Syst. Appl., vol. 200, no. August, p. 117192, Aug. 2022, doi: 10.1016/j.eswa.2022.117192.
[15] M. Blocho, T. Jastrzab, and J. Nalepa, “Cooperative co-evolutionary memetic algorithm for pickup and delivery problem with time windows,” in GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, Jul. 2022, pp. 176–179. doi: 10.1145/3520304.3528782;TOPIC:TOPIC:CONFERENCE-COLLECTIONS.
[16] W.-J. Ou, X.-L. Shi, and W.-N. Chen, “A Distributed Cooperative Co-Evolutionary Algorithm Based on Ring Network for Distributed Large-Scale Optimization,” in 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), IEEE, Oct. 2022, pp. 3018–3025. doi: 10.1109/SMC53654.2022.9945430.
[17] L. Sun, L. Lin, H. Li, and M. Gen, “Cooperative Co-Evolution Algorithm with an MRF-Based Decomposition Strategy for Stochastic Flexible Job Shop Scheduling,” Mathematics, vol. 7, no. 4, p. 318, Mar. 2019, doi: 10.3390/math7040318.
[18] A. Tayyab and U. Saif, “A Two-Stage Genetic Artificial Bee Colony Algorithm for Solving Integrated Operating Room Planning and Scheduling Problem With Capacity Constraints of Downstream Wards,” IEEE Access, vol. 10, pp. 131109–131127, 2022, doi: 10.1109/ACCESS.2022.3229709.
[19] J.-J. Wang, Z. Dai, A.-C. Chang, and J. J. Shi, “Surgical scheduling by Fuzzy model considering inpatient beds shortage under uncertain surgery durations,” Ann. Oper. Res., vol. 315, no. 1, pp. 463–505, Aug. 2022, doi: 10.1007/s10479-022-04645-z.
[20] M. Arab Momeni, A. Mostofi, V. Jain, and G. Soni, “COVID19 epidemic outbreak: operating rooms scheduling, specialty teams timetabling and emergency patients’ assignment using the robust optimization approach,” Ann. Oper. Res., vol. 359, no. 3, pp. 1–31, May 2022, doi: 10.1007/s10479-022-04667-7.
[21] H. Xu, Y. Fang, C.-A. Chou, N. Fard, and L. Luo, “A reinforcement learning-based optimal control approach for managing an elective surgery backlog after pandemic disruption,” Health Care Manag. Sci., vol. 26, no. 3, pp. 430–446, Sep. 2023, doi: 10.1007/s10729-023-09636-5.
[22] A. L. Bolaji et al., “A room-oriented artificial bee colony algorithm for optimizing the patient admission scheduling problem,” Comput. Biol. Med., vol. 148, no. September, p. 105850, Sep. 2022, doi: 10.1016/j.compbiomed.2022.105850.
[23] R. Hosseini Rad, S. Baniasadi, P. Yousefi, H. Morabbi Heravi, M. Shaban Al-Ani, and M. Asghari Ilani, “Presented a Framework of Computational Modeling to Identify the Patient Admission Scheduling Problem in the Healthcare System,” J. Healthc. Eng., vol. 2022, no. 1, pp. 1–15, Nov. 2022, doi: 10.1155/2022/1938719.
[24] S. Ashraf, N. Rehman, S. Abdullah, B. Batool, M. Lin, and M. Aslam, “Decision support model for the patient admission scheduling problem based on picture fuzzy aggregation information and TOPSIS methodology,” Math. Biosci. Eng., vol. 19, no. 3, pp. 3147–3176, 2022, doi: 10.3934/mbe.2022146.
[25] L. Zhou, N. Geng, Z. Jiang, and S. Jiang, “Integrated Multiresource Capacity Planning and Multitype Patient Scheduling,” INFORMS J. Comput., vol. 34, no. 1, pp. 129–149, Jan. 2022, doi: 10.1287/ijoc.2020.1048.
[26] B. Spratt and E. Kozan, “An integrated rolling horizon approach to increase operating theatre efficiency,” J. Sched., vol. 24, no. 1, pp. 3–25, Feb. 2021, doi: 10.1007/s10951-020-00655-6.
[27] M. Squires, X. Tao, S. Elangovan, R. Gururajan, X. Zhou, and U. R. Acharya, “A novel genetic algorithm based system for the scheduling of medical treatments,” Expert Syst. Appl., vol. 195, no. June, p. 116464, Jun. 2022, doi: 10.1016/j.eswa.2021.116464.
[28] J. Zhao and H. Wen, “Dynamic planning with reusable healthcare resources: application to appointment scheduling,” Flex. Serv. Manuf. J., vol. 34, no. 4, pp. 859–878, Dec. 2022, doi: 10.1007/s10696-021-09411-0.
[29] M. I. Restrepo, L.-M. Rousseau, and J. Vallée, “Home healthcare integrated staffing and scheduling,” Omega, vol. 95, no. September, p. 102057, Sep. 2020, doi: 10.1016/j.omega.2019.03.015.
[30] X. Zhan, Z. Xie, and D. Yao, “An Integrated Scheduling Algorithm Based on a Process End Time-Driven and Long-Time Scheduling Strategy,” Symmetry (Basel)., vol. 14, no. 10, p. 2106, Oct. 2022, doi: 10.3390/sym14102106.
[31] A. Sadeghi and M. J. Sadeghi, “Manpower Planning Scheduling in hospital operating rooms,” Int. J. Integr. Care, vol. 22, no. S3, p. 7, Nov. 2022, doi: 10.5334/ijic.ICIC22264.
[32] A. Salami, B. Afshar-Nadjafi, and M. Amiri, “A Two-Stage Optimization Approach for Healthcare Facility Location- Allocation Problems With Service Delivering Based on Genetic Algorithm,” Int. J. Public Health, vol. 68, p. 1605015, Feb. 2023, doi: 10.3389/ijph.2023.1605015.
[33] N. Larrain, S. Wang, T. Stargardt, and O. Groene, “Cooperation Improvement in an Integrated Healthcare Network: A Social Network Analysis,” Int. J. Integr. Care, vol. 23, no. 2, p. 32, Jun. 2023, doi: 10.5334/ijic.6519.
[34] S. M. Nagarajan, G. G. Devarajan, A. S. Mohammed, T. V. Ramana, and U. Ghosh, “Intelligent Task Scheduling Approach for IoT Integrated Healthcare Cyber Physical Systems,” IEEE Trans. Netw. Sci. Eng., vol. 10, no. 5, pp. 2429–2438, Sep. 2023, doi: 10.1109/TNSE.2022.3223844.
[35] A. Ala, F. E. Alsaadi, M. Ahmadi, and S. Mirjalili, “Optimization of an appointment scheduling problem for healthcare systems based on the quality of fairness service using whale optimization algorithm and NSGA-II,” Sci. Rep., vol. 11, no. 1, p. 19816, Oct. 2021, doi: 10.1038/s41598-021-98851-7.
[36] J. Wang, Z. Dai, J. Chang, J. (Junmin) Shi, and H. Liu, “Robust surgical scheduling for nonoperating room anesthesia (NORA) under surgical duration uncertainty,” Decis. Sci., vol. 55, no. 3, pp. 262–280, Jun. 2024, doi: 10.1111/deci.12584.
[37] A. Nikfarjam, A. Moosavi, A. Neumann, and F. Neumann, “Computing High-Quality Solutions for the Patient Admission Scheduling Problem Using Evolutionary Diversity Optimisation,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13398 LNCS, no. 1, Springer Science and Business Media Deutschland GmbH, 2022, pp. 250–264. doi: 10.1007/978-3-031-14714-2_18.
[38] V. Junet et al., “A decision support system based on artificial intelligence and systems biology for the simulation of pancreatic cancer patient status,” CPT Pharmacometrics Syst. Pharmacol., vol. 12, no. 7, pp. 916–928, Jul. 2023, doi: 10.1002/psp4.12961.
[39] N. A. Ab Rashid and S. Ya’acob, “Predictive Analytics on Scheduled Surgery Cases in Forecasting the Operating Theatre Utilisation,” Open Int. J. Informatics, vol. 9, no. 1, pp. 45–52, Jun. 2021, doi: 10.11113/oiji2021.9n1.20.
[40] P. Zhang, J. F. Bard, D. J. Morrice, and K. M. Koenig, “Extended open shop scheduling with resource constraints: Appointment scheduling for integrated practice units,” IISE Trans., vol. 51, no. 10, pp. 1037–1060, Oct. 2019, doi: 10.1080/24725854.2018.1542544.
[41] O. Stan, C. Avram, I. Stefan, and A. Astilean, “Integrated innovative solutions to improve healthcare scheduling,” in 2016 IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR), IEEE, May 2016, pp. 1–6. doi: 10.1109/AQTR.2016.7501301.
[42] Y. Fu, H. Wang, and M. Huang, “Integrated scheduling for a distributed manufacturing system: a stochastic multi-objective model,” Enterp. Inf. Syst., vol. 13, no. 4, pp. 557–573, Apr. 2019, doi: 10.1080/17517575.2018.1545160.
[43] A. M. Turhan and B. Bilgen, “Mixed integer programming based heuristics for the Patient Admission Scheduling problem,” Comput. Oper. Res., vol. 80, no. April, pp. 38–49, Apr. 2017, doi: 10.1016/j.cor.2016.11.016.
[44] S. Ceschia and A. Schaerf, “Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays,” J. Sched., vol. 19, no. 4, pp. 377–389, Aug. 2016, doi: 10.1007/s10951-014-0407-8.
[45] X. Zhuo, H. Huang, Z. Cai, and H. Hu, “An hybrid evolutionary algorithm with scout bee global search strategy for Chinese nurse rostering problems,” in 2015 IEEE Congress on Evolutionary Computation (CEC), IEEE, May 2015, pp. 769–775. doi: 10.1109/CEC.2015.7256969.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0