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

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

邱啓源(Chi-Yuan Chiu)

指導教授 ： 陳平舜

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2019年)

https://doi.org/10.6840/cycu201900637

摘要

當醫療人員因突發狀況必須把原定班表更改成其他班次或是休假時，排班人員必須更動其他剩餘醫療人員的班表，以滿足醫院每日所需的醫療人數需求並符合相關的排班限制，此種重新排班問題稱為醫療人員重新排班問題(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.

並列關鍵字

Medical staff rerostering ； the number of shift differences between the original and rerostering schedules ； Particle swarm optimization ； Taboo list ； Regenerating a new particle

參考文獻

蔡嘉哲，運用萬用啟發式演算法解醫護人員排班問題，中原大學工業與系統工程學系碩士論文，2015。

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.

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.

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.

Clark, A. R., and Walker, H. (2011). Nurse rescheduling with shift preferences and minimal disruption. Journal of Applied Operational Research, 3(3), 148-162.