替護理人員排班對於醫院來說一直都是一個棘手的問題，由於近年來醫療產業環境的惡化，導致許多護理人員離職，其原因不外乎工時過長、工作壓力大以及作息不正常等等。此外，班表品質的好壞，都會直接影響到員工的服務品質與士氣。且若以人工排班之方式排班往往需花費極長時間，還容易產生不合理的班表，進而造成護理人力的流失。
本研究旨在根據政府法律、醫院內部法規、醫師綁定特定護理人員、護理人員對班別與休假日的偏好及他們的個人需求，最大化護理人員對班表的滿意度。並針對此問題，提出了兩種結合基因演算法與粒子群優化的混合啟發式演算法，以有效地產生高品質的解。再將此兩種方法與其他三種不同的啟發式演算法包括傳統的基因演算法，使用菁英主義的基因演算法以及另外一種運用不同手法與粒子群優化結合的基因演算法做比較。
研究結果顯示，本研究提出的兩種與粒子群優化所結合的基因演算法在兩種不同的情境下其計算時間和班表的品質皆優於其他的啟發式演算法。此外，本文所提出的演算法皆已在真實醫療產業裡進行測試，與人工排班結果相比，減少了93%的排班時間，並提升了31%的班表滿意度，進一步提升了員工的服務品質與工作效率。

The nurse scheduling problem (NSP) has been a crucial and challenging research issue for hospitals, considering especially the serious deterioration in nursing shortage in recent years owing to long working hours, considerable work pressure, and irregular lifestyle. This study investigates the NSP that is aimed at maximizing the nurse satisfaction with the generated schedule subject to the government laws, internal regulations of hospital, doctor-nurse pairing rules, shift and day off preferences of nurses, etc.
Due to the NP-hardness of the studied NSP, the hybrid metaheuristics of genetic algorithm (GA) and particle swarm optimization (PSO) method are proposed to produce quality solutions efficiently. The developed GA-PSO hybrid metaheuristics are compared with several metaheuristics including the GA, elitism GA, and PSO-based metaheuristics. Our computational experiment results show that the presented hybrid metaheuristic outperforms other metaheuristics in terms of both computation time and solution quality under two different testing scenarios. Furthermore, the presented solution procedure has been implemented practically in a real-world dentist clinic, which is used as a case study. With the help of the developed scheduling technique, it reduced the time spend on scheduling by 93% and increased the satisfaction of the schedule by 31%, which further enhanced the operating efficiency as well as service quality.

Acar, I., & Butt, S. E. (2016). Modeling nurse-patient assignments considering patient acuity and travel distance metrics. Journal of Biomedical Informatics, 64, 192-206.

Aickelin, U., & Dowsland, K. A. (2004). An indirect Genetic Algorithm for a nurse-scheduling problem. Computers & Operations Research, 31(5), 761-778.

Aiken, L. H., Clarke, S. P., Sloane, D. M., Sochalski, J. A., Busse, R., Clarke, H., . . . Shamian, J. (2001). Nurses’ Reports On Hospital Care In Five Countries. Health Affairs, 20(3), 43-53.

Bagheri, M., Gholinejad Devin, A., & Izanloo, A. (2016). An application of stochastic programming method for nurse scheduling problem in real word hospital. Computers & Industrial Engineering, 96, 192-200.

Bai, R., Burke, E. K., Kendall, G., Li, J., & McCollum, B. (2010). A Hybrid Evolutionary Approach to the Nurse Rostering Problem. IEEE Transactions on Evolutionary Computation, 14(4), 580-590.

Betkus, M., & Macleod, M. (2004). Retaining Public Health Nurses in Rural British Columbia: The Influence of Job and Community Satisfaction. Canadian journal of public health. Revue canadienne de santé publique, 95, 54-58.

Chen, P.-S., & Zeng, Z.-Y. (2020). Developing two heuristic algorithms with metaheuristic algorithms to improve solutions of optimization problems with soft and hard constraints: An application to nurse rostering problems. Applied Soft Computing, 93, 106336.

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), 165-183.

fayçal, C., Riffi, M., & Ahiod, B. (2015). Hybrid genetic algorithm and greedy randomized adaptive search procedure for solving a nurse scheduling problem. Journal of Theoretical and Applied Information Technology, 73, 313-320.

Gao, S.-C., & Lin, C.-W. (2013, 2013//). Particle Swarm Optimization Based Nurses’ Shift Scheduling. Paper presented at the Proceedings of the Institute of Industrial Engineers Asian Conference 2013, Singapore.

Hamid, M., Barzinpour, F., Hamid, M., & Saeed, M. (2018). A multi-objective mathematical model for nurse scheduling problem with hybrid DEA and augmented ε-constraint method: a case study. 11, 98-108.

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), 179-199.

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), 320-332.

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.

Kang, J.-R., & Lin, C.-C. (2015). Nurse Scheduling with Multiple Preference Ranks for Shifts and Days-off. Unpublished doctoral dissertation, National Chiao Tung University, Taiwan.

Kim, S.-J., Ko, Y.-W., Uhmn, S., & Kim, J. (2014). A strategy to improve performance of genetic algorithm for nurse scheduling problem. International Journal of Software Engineering and Its Applications, 8(1), 53-62.

Leksakul, K., & Phetsawat, S. (2014). Nurse Scheduling Using Genetic Algorithm. Mathematical Problems in Engineering, 2014, 246543.

Lin, C.-C., Kang, J.-R., Liu, W.-Y., & Deng, D.-J. (2014). Modelling a Nurse Shift Schedule with Multiple Preference Ranks for Shifts and Days-Off. Mathematical Problems in Engineering, 2014, 937842.

Liu, Z., Liu, Z., Zhu, Z., Shen, Y., & Dong, J. (2018). Simulated annealing for a multi-level nurse rostering problem in hemodialysis service. Applied Soft Computing, 64, 148-160.

Lu, K.-Y., Lin, P.-L., Wu, C.-M., Hsieh, Y.-L., & Chang, Y.-Y. (2002). The relationships among turnover intentions, professional commitment, and job satisfaction of hospital nurses. Journal of Professional Nursing, 18(4), 214-219.

Millar, H. H., & Kiragu, M. (1998). Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming. European Journal of Operational Research, 104(3), 582-592.

Mohd Rasip, N., Basari, A. S., Hussin, B., & Khilwani, N. (2014). A guided particle swarm optimization algorithm for nurse scheduling problem. Applied Mathematical Sciences, 8, 5625-5632.

Ramli, M., Hussin, B., Abas, Z., & Ibrahim, N. (2016). Solving complex nurse scheduling problems using particle swarm optimization. International Review on Computers and Software (IRECOS), 11(8), 1-10.

Topaloglu, S., & Selim, H. (2010). Nurse scheduling using fuzzy modeling approach. Fuzzy Sets and Systems, 161(11), 1543-1563.

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), 9506-9512.

Valouxis, C., Gogos, C., Goulas, G., Alefragis, P., & Housos, E. (2012). A systematic two phase approach for the nurse rostering problem. European Journal of Operational Research, 219(2), 425-433.

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, 99-110.

Wright, P. D., & Mahar, S. (2013). Centralized nurse scheduling to simultaneously improve schedule cost and nurse satisfaction. Omega, 41(6), 1042-1052.

Wu, J., Lin, Y., Zhan, Z., Chen, W., Lin, Y., & Chen, J. (2013, 13-16 Oct. 2013). An Ant Colony Optimization Approach for Nurse Rostering Problem. Paper presented at the 2013 IEEE International Conference on Systems, Man, and Cybernetics.

Wu, T.-H., Yeh, J.-Y., & Lee, Y.-M. (2015). A particle swarm optimization approach with refinement procedure for nurse rostering problem. Computers & Operations Research, 54, 52-63.

Yilmaz, E. (2012). A Mathematical Programming Model for Scheduling of Nurses’ Labor Shifts. Journal of Medical Systems, 36(2), 491-496.

Youssef, A., & Senbel, S. (2018, 8-10 Jan. 2018). A Bi-level heuristic solution for the nurse scheduling problem based on shift-swapping. Paper presented at the 2018 IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC).

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, 337-347.

Zeytinoglu, I. U., Denton, M., Davies, S., Baumann, A., Blythe, J., & Boos, L. (2007). Deteriorated External Work Environment, Heavy Workload and Nurses' Job Satisfaction and Turnover Intention. Canadian Public Policy, 33(Supplement 1), S31-S47.

Zhang, Z., Hao, Z., & Huang, H. (2011, 2011//). Hybrid Swarm-Based Optimization Algorithm of GA & VNS for Nurse Scheduling Problem. Paper presented at the Information Computing and Applications, Berlin, Heidelberg.