建構變動鄰域搜尋法求解醫護人員排班問題

Developing a variable neighborhood search to solve the medical staff scheduling problem

葉爾鈞(Erh-Chun Yeh)

指導教授 ： 陳平舜

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

https://doi.org/10.6840/cycu201700544

摘要

本研究應用變動鄰域搜尋法求解醫護人員排班問題，在區域搜尋上根據個案醫院限制條件發展出3種鄰域搜尋方式，並測試7種鄰域結構在不同人力配置下去做分析與比較，本研究最佳結果班表其鄰域數為2個，證明鄰域結構內鄰域數量愈多並不會愈容易跳脫區域最佳解。不過對目標值影響較大為鄰域搜尋的方式，主要依據問題去建構出適合此問題的鄰域搜尋方式與其結構。
本研究經過變動鄰域搜尋法求解過後，7種鄰域結構其求解結果皆有找到最佳解的情形，平均差異也非常小，證明變動鄰域搜尋法應用在醫護人員排班上能夠提供醫院一份品質好且穩定的醫護人員班表。

關鍵字

醫護人員排班 ； 變動鄰域搜尋法 ； 鄰域結構 ； 區域搜尋

並列摘要

This research adopted the variable neighborhood search to solve the medical staff scheduling problem. Based on the case radiologists’ constraints, this study developed three neighborhood searches as the local searches and tested seven neighborhood structures under different numbers of radiologists. The numerical results showed that the two neighborhood structures had better performance than others. Furthermore, the results showed that more neighborhood structures did not guarantee to have better performance than few neighborhood structures. The good neighborhood search had better impacts on the objective function. Therefore, researchers should design a good neighborhood search and its neighborhood structure based on the radiologists’ constraints.
Through the numerical tests, the outcome showed that all seven neighborhood structures had found the optimal solution, and that the average objective function values among the seven neighborhood structures are close. The finding of this research proved that the variable neighborhood search could provide a good and stable medical staff schedule for hospital managers.

並列關鍵字

Medical staff scheduling ； variable neighborhood search ； neighborhood structure ； local search

參考文獻

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

Awadallah, M. A., Al-Betar, M. A., Khader, A. T., Bolaji, A. L. a., & Alkoffash, M. (2015). Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem. Neural Computing and Applications, 28(3), 463-482.

Azab, A., & Naderi, B. (2014). A variable neighborhood search metaheuristic for cellular manufacturing with multitask machine tools. Procedia CIRP, 20, 50-55.

Bäumelt, Z., Dvořák, J., Šůcha, P., & Hanzálek, Z. (2016). A novel approach for nurse rerostering based on a parallel algorithm. European Journal of Operational Research, 251(2), 624-639.

Behnamian, J., Zandieh, M., & Fatemi Ghomi, S. M. T. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 36(6), 9637-9644.