具值班暨休假公平性的護理師排班問題及其遺傳演算求解法

Impartial Schedule Targeted Nurse Scheduling Problems and Genetic Algorithm Based Methods

吳威霆(Wei-Ting Wu)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01186

摘要

中文摘要
護理師排班問題較一般員工排班問題特殊。護理師排班有許多應避免的值班狀況及限制條件，因此目前護理師排班均由護理長採用人工的方式進行排班。本研究分別建立經訪視國內醫院依月別包班模式和非包班模式的護理師排班問題。包班模式下護理師於某月中值班時限值同一種班別，反之則無此限。國內的排班問題會考量排班迄今的歷史資料包括資歷等級、積欠假、要假成功點數等，以判斷護理師要求休假的優先順序。國外醫院的標竿問題屬非包班模式。
本研究提出遺傳演算法為基的護理師自動化排班方法及軟體系統求解包班暨非包班模式問題。依月別包班模式問題會使用各護理師的歷史資料，以值班量、休假量為排班公平原則。本研究求解的非包班模式問題是比利時醫院的BCV系列問題，須先判定題型以執行不同題型的問題專用遺傳演算程序。遺傳演算模式以數個優化子目標引導排班結果朝著違反限制式次數最小化的方向演化。經與文獻上各求解法的比較求解文獻上的標竿問題成果，顯示本研究的求解模式成效較佳。整體而言數值範例測試結果顯示本研究提示的求解法能有效替代人工排班法，且較有效地應用於包班暨非包班的護理師排班問題。

關鍵字

護理師排班問題 ； 公平性 ； 包班 ； 非包班 ； 遺傳演算法

並列摘要

Nurse scheduling problem is a more specific problem comparing with the general employee scheduling problem. Generally, in our survey, nurse scheduling is solved manually by the head nurse due to the consideration of many conflict restrictions. However sometimes errors and time cost took places in the manually scheduling mode. Therefore, in order to increase the efficiency and provide a time-saving method to solve the nurse scheduling problem, this research establish two nurse scheduling modes - The Package Shift mode and Non-Package Shift mode.
The Package Shift mode is restricted to that the nurse only can take one type shift throughout one month. For example, once the Package Shift mode is adopted, the nurse is on night shift throughout this month, if starting on night shift. Contrary to the Package Shift mode, the Non-Package Shift mode is without this restriction.
In Taiwan, the head nurse will take the historical information about the nurses, such as nurse rank, accrued/owed leave and the number of furlough, in order to determine nurse requested leave priorities and carrying on nurse scheduling problem. On the other hand, the Benchmark problems of foreign hospitals belong to Non-Package Shift mode.
In order to solve the nurse scheduling problem automatically rather than manually, this research provide a huristic algorithm which is based on genetic algorithm and an automation software package is provided to solve nurse scheduling problem under Package Shift mode and Non-Package Shift mode.
Under Package Shift mode, for the sake of impartial of principle, historical data are utilized, such as the amount of leaves and the amount of shifts. Under Non-Package Shift mode, the Belgian hospital BCV range of issues are utilized to study the scheduling problem, in which, the Questions in the implementation of Various types of problem-specific GA program must be determined in first. Genetic algorithm model optimizes a number of sub-goals and guides the results toward the violation of constraint scheduling to minimize the number of the direction of evolution.
Compare to literatures, our result shows that this research perform much more effective and better on solving benchmark problem. Moreover, the numerical examples show that our proposed method can be an alternative of manual nurse scheduling, furthermore, applicable effectively on nurse scheduling under both Package Shift mode and Non-Package Shift mode.

並列關鍵字

nurse scheduling problems ； impartial ； Package Shift ； Non-Package Shift ； genetic algorithms

參考文獻

蔣雅慈，利用擴散式粒子群最佳化進行多目標護士排程，碩士論文，國立暨南大學資訊管理研究所。

Aickelin, U. and K. Dowsland (2000). "Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem." Journal of scheduling 3(3): 139-153.

Aickelin, U. and K. Dowsland (2004). "An indirect genetic algorithm for a nurse-scheduling problem." Computers & Operations Research 31(5): 761-778.

April, J., M. Better, et al. (2006). Enhancing business process management with simulation optimization, Winter Simulation Conference.

Azaiez, M. and S. Al Sharif (2005). "A 0-1 goal programming model for nurse scheduling." Computers and Operations Research 32(3): 491-508.