利用擴散式粒子群最佳化進行多目標護士排程

Multi-Objective Nurse Scheduling Using Scatter PSO

蔣雅慈(Ya-Tzu Chiang)

指導教授 ： 尹邦嚴

國立暨南國際大學/管理學院/資訊管理學系/碩士(2009年)

https://doi.org/10.6837/NCNU.2009.00109

摘要

醫院為了兼顧管理營運、經營利益、政府法規、和護理人員排班公平性等因素，在傳統人工作業模式下，需要花費很多時間才能產生合理的排班表，但又無法客觀評估各種目標的達成效益。本論文提出擴散式粒子群最佳化演算法結合禁制搜尋法來解決護士排班問題，醫院經營者可擬訂多個營運目標（如降低成本及提高員工滿意度等），並述明排班限制（如符合營運實務及政府法規等），利用本論文提出的數學規劃模式即可自動求得既符合限制又優化目標的一組近似最佳解的集合，提供醫院經營者量化的參考依據。我們以兩種不同類型的問題來評估Scatter MOPSO的效率，第一為標準測試函數，第二為護士排班測試問題，實驗結果顯示，在標準測試函數問題上，我們所提出的方法Scatter MOPSO在某些策略上勝過文獻上用來解決多目標問題的NSGA II與MOPSO；在護士排班測試問題也比MOPSO得到更佳的排班品質。

關鍵字

擴散式粒子群最佳化演算法 ； 禁制搜尋法 ； 多目標最佳化 ； 護士排程問題

並列摘要

It is time-consuming to generate nurse scheduling using traditional human-involved manner in order to account for administrative operations, business benefits, governmental regulations, and fairness perceived by nurses. Moreover, the objectives cannot be measured quantitatively even when the nurse scheduling is generated after a lengthy manual process. This paper presents a Multi-Objective Scatter PSO combined with Tabu Search to tackle the real-world nurse scheduling problem. By the proposed mathematical formulation, the hospital administrator can set up multiple objectives (such as cost reduction and nurse-satisfaction raising) and stipulate a set of scheduling constraints (such as operational practice and governmental regulations), and our system can automatically generate a set of solutions which nearly optimize the given objectives and meet the specified constraints. We used two kinds of problems to evaluate the performance of Scatter MOPSO, first is benchmark functions and second is nurse scheduling problem. The experimental results manifest that our method performs better than NSGA II and MOPSO on benchmark functions, and better than MOPSO on nurse scheduling problem.

並列關鍵字

Scatter PSO ； tabu search ； multi-objective optimization ； nurse scheduling problem

參考文獻

Aichelin, U., & Dowsland, K. A. (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. Journal of Scheduling, vol. 3, pp. 139-153.

Aichelin, U., & Dowsland, K. A. (2003). An indirect genetic algorithm for a nurse scheduling problem. Computers & Operations Research, vol. 31, pp. 761-778.

Aprio, J., Better, M., Glover, F., Kelly J., & Laguna, M. (2006). Enhancing business process management with simulation optimization. Proceedings of the 38th conference on Winter simulation, pp. 642-649.

Azaiez, M. N., & Al Sharif, S. S. (2005). A 0-1 goal programming model for nurse scheduling. Computers & Operations Research, vol. 32, pp. 491-507.

Bard, J. F., & Purnomo, H. W. (2005). Preference scheduling for nurses using column generation. European Journal of Operational Research, vol. 164, pp. 510-534.