使用GRASP為基底之超經驗演算法進行護士排程多目標優化

A GRASP-Based Hyperheuristic for Multiobjective Optimization of Nurse Scheduling

李韋鋒(Wei-Fong Li)

指導教授 ： 尹邦嚴

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

摘要

過去文獻中的護士排班問題，往往只考慮單一目標(如人員成本、政府法規、護士滿意度等)，在現實世界中，也很難在同時考量多個準則的情況下排出一張好的班表。本論文提出以GRASP為基底之超經驗演算法，來解決過去文獻所提出之多目標護士排班問題模型。利用挑選不同解題策略，並同時考量多個目標的概念來改進護士排班。醫院的排班人員可以利用此方法，在需要考慮多種排班最佳化目標與滿足限制式的情況下排出一張好的護士班表，以符合現實世界的需求。我們將以GRASP為基底之超經驗演算法與文獻中同樣解決多目標護士排程問題之Scatter PSO演算法，以及著名之多目標演算法NSGA-II測試比較。實驗結果顯示，本研究所提出之演算法在某些測試問題上優於Scatter PSO，並且與NSGA-II的效能接近。

關鍵字

超經驗演算法 ； 多目標最佳化 ； 護士排程問題

並列摘要

In the past, most existing nurse scheduling models consider only one single objective, such as staff cost, governmental regulations or staff preference. In the real world practices, it is also very difficult for hospital administrators to generate a nurse schedule considering multiple-objectives. This paper presents a GRASP-based hyperheuristic to solve a real world nurse scheduling problem. We improve the nurse schedule by applying different combinations of strategies for nurse scheduling problem and keep the best solutions using the dominance concepts in multi-objective optimization problems. Hospital administrators can use this approach to generate a nurse schedule that considers multiple objectives and satisfies a set of hard constraints. We compared our GRASP-based hyperheuristic with a benchmark program NSGA-II and the Scatter PSO, which was recently proposed to solves the multi-objective nurse scheduling problem. The experimental results show that the GRASP-based method is better than Scatter PSO in the test cases, and it is comparable with NSGA-II.

並列關鍵字

GRASP ； Hyperheuristic ； multi-objective optimization ； nurse scheduling problem

參考文獻

蔣雅慈.(民98). 利用擴散式粒子群最佳化進行多目標護士排程. 國立暨南國際大學資訊管理研究所碩士論文, 南投縣.

Aickelin U., Burke E. K., & Li , J.(2007). An Estimation of Distribution Algorithm with Intelligent Local Search for Rule-based Nurse Rostering. Journal of the Operational Research Society, 58, 1574-1585

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

Aichelin, U., & Dowsland, K. A. (2003). An indirect genetic algorithm for a nurse scheduling problem. Computers & Operations Research, 31, 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, 642-649.