應用粒子群演算法求解醫療人員重新排班問題

Applying the particle swarm optimization method to solve medical staff rerostering problems

10.6840/cycu201900637

邱啓源

醫療人員重新排班 ； 原定班表與重新排班班表之班表變動數量 ； 粒子群演算法 ； 禁忌名單 ； 重新產生粒子 ； Medical staff rerostering ； the number of shift differences between the original and rerostering schedules ； Particle swarm optimization ； Taboo list ； Regenerating a new particle

中原大學工業與系統工程學系學位論文

2019年

碩士

陳平舜

繁體中文

當醫療人員因突發狀況必須把原定班表更改成其他班次或是休假時，排班人員必須更動其他剩餘醫療人員的班表，以滿足醫院每日所需的醫療人數需求並符合相關的排班限制，此種重新排班問題稱為醫療人員重新排班問題(Medical Staff Rerostering Problem, MSRP)。本研究的目的是考量軟和硬限制之醫療人員排班規則下，發展一改良式粒子群演算法求解醫療人員重新排班問題，並且搭配修復機制，以縮短產生醫療人員重新排班問題初始解可行解的求解時間。此改良式粒子群演算法分別加入禁忌名單和重新產生粒子的概念，發展出兩種不同版本的改良式粒子群演算法，其研究結果顯示，在進行30次測試設置後，原始粒子群演算法和本研究發展之二種改良式粒子群演算法之執行結果都能找出最佳解。根據變異數分析(Analysis of Variance, ANOVA)檢定之方法，其結果顯示在相同的求解品質下，改良式粒子群演算法搭配禁忌名單的求解速度明顯優於其他兩種演算法。

As a medical staff has an unexpected reason to have a day off or change his or her scheduled shift to another shift, the scheduler must update the remaining medical staff’s shifts in order to satisfy the daily medical staff requirement of hospitals and meet the scheduling regulations. This kind of rescheduled problems is called the medical staff rerostering problem (MSRP). The goal of this research is to develop the modified particle swarm optimization (PSO) algorithms to solve the MSRP, which consists of soft and hard constraints of scheduling rules. The repair mechanisms of the modified PSO algorithms are used to shorten the solution time of generating an initial feasible solution of the MSRP. Two concepts, using a taboo list and regenerating a new particle, are applied to develop two versions of the modified PSO algorithms. The results show that, after performing 30 times of the testing setting, all of the original PSO algorithm and the two modified PSO algorithms, PSO with the taboo list and PSO with regenerating a new particle, can find the optimal solution. According to the analysis of variance (ANOVA), the results show that the solution time of the PSO with the taboo list outperforms those of the other two algorithms.

1. 蔡嘉哲，運用萬用啟發式演算法解醫護人員排班問題，中原大學工業與系統工程學系碩士論文，2015。
   連結：
2. Bard, J. F., and Purnomo, H. W. (2006). Incremental changes in the workforce to accommodate changes in demand. Health Care Management Science, 9(1), 71-85.
3. Beheshti, Z., and Shamsuddin, S. M. H. (2013). A review of population-based meta-heuristic algorithm. International Journal of Advances in Soft Computing and Its Applications, 5(1), 1-35.
4. Clark, Moule, P., Topping, A., and Serpell, M. (2015). Rescheduling nursing shifts: Scoping the challenge and examining the potential of mathematical model based tools. Journal of Nursing Management, 23(4), 411-420.
5. Clark, A. R., and Walker, H. (2011). Nurse rescheduling with shift preferences and minimal disruption. Journal of Applied Operational Research, 3(3), 148-162.
6. Forbes. (2013). The causes and costs of absenteeism in the workplace. Retrieved from https://www.forbes.com/sites/investopedia/2013/07/10/the-causes-and-costs-of-absenteeism-in-the-workplace/#6e38b0b53eb6
7. Glover, F. (1989). Tabu Search：Part I. Operations Research Society of America, 1, 190-206.
8. Glover, F. (1990). Tabu Search：Part II. Operations Research Society of America, 2, 4-32.
9. Kitada, M., Morizawa, K., and Nagasawa, H. (2010, December 7-10). A heuristic method in nurse rerostering following a sudden absence of nurses. Paper presented at the Asia Pacific Regional Meeting of International Foundation for Production Research, Melaka.
10. Maenhout, B., and Vanhoucke, M. (2011). An evolutionary approach for the nurse rerostering problem. Computers & Operations Research, 38(10), 1400-1411.
11. Maenhout, B., and Vanhoucke, M. (2013). Reconstructing nurse schedules: Computational insights in the problem size parameters. Omega, 41(5), 903-918.
12. Michael, M., and Charles, M. (2016, March 8-10). Fuzzy multi-criteria simulated evolution for nurse re-rostering. Paper presented at the Proceedings of the 2016 International Conference on Industrial Engineering and Operations Management, Kuala Lumpur, Malaysia,.
13. Moz, M., and Vaz Pato, M. (2003). An integer multicommodity flow model applied to the rerostering of nurse schedules. Annals of Operations Research, 119, 285-301.
14. Moz, M., and Vaz Pato, M. (2004). Solving the problem of rerostering nurse rosters with hard constraints new multicommodity flow models. Annals of Operations Research, 128, 179-197.
15. Moz, M., and Vaz Pato, M. (2007). A genetic algorithm approach to a nurse rerostering problem. Computers & Operations Research, 34(3), 667-691.
16. Mutingil, and Mbohwa. (2017, April 11-13). The nurse rerostering problem: An explorative study. Paper presented at the Proceedings of the International Conference on Industrial Engineering and Operations Management Rabat, Rabat, Morocco.
17. Pato, M. V., and Moz, M. (2008). Solving a bi-objective nurse rerostering problem by using a utopic Pareto genetic heuristic. Journal of Heuristics, 14(4), 359-374.
18. Shi, Y., and Eberhart, R. C. (1998). Parameter selection in particle swarm optimization. Lecture Notes in Computer Science, 1447, 591-600.
19. Wickert, T. I., Smet, P., and Vanden Berghe, G. (2019). The nurse rerostering problem: Strategies for reconstructing disrupted schedules. Computers & Operations Research, 104, 319-337.
20. Wu, T. H., Yeh, J. Y., and Lee, Y. M. (2015). A particle swarm optimization approach with refinement procedure for nurse rostering problem. Computers & Operations Research, 54, 52-63.
21. Zdeněk Bäumelt, Jan Dvořák, Přemysl Šůcha, and Zdeněk Hanzálek. (2016). A novel approach for nurse rerostering based on aparallel algorithm. European Journal of Operational Research, 251, 624-639.
22. 吳明隆. (2007). SPSS操作與應用：變異數分析實務. 台北市: 五南圖書.