臺灣博碩士論文加值系統

中文摘要
護理師排班問題較一般員工排班問題特殊。護理師排班有許多應避免的值班狀況及限制條件，因此目前護理師排班均由護理長採用人工的方式進行排班。本研究分別建立經訪視國內醫院依月別包班模式和非包班模式的護理師排班問題。包班模式下護理師於某月中值班時限值同一種班別，反之則無此限。國內的排班問題會考量排班迄今的歷史資料包括資歷等級、積欠假、要假成功點數等，以判斷護理師要求休假的優先順序。國外醫院的標竿問題屬非包班模式。
本研究提出遺傳演算法為基的護理師自動化排班方法及軟體系統求解包班暨非包班模式問題。依月別包班模式問題會使用各護理師的歷史資料，以值班量、休假量為排班公平原則。本研究求解的非包班模式問題是比利時醫院的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.

目錄
誌謝 I
中文摘要 II
ABSTRACT III
目錄 V
圖目錄 VII
表目錄 VIII
中英文名詞對照表 IX
第1章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究流程 3
1.4 章節概要 5
第2章 文獻探討 6
2.1 員工排班問題 6
2.1.1 限制式 6
2.1.2 目標式 7
2.1.3 求解方法 8
2.2 護理師排班問題 9
2.2.1 限制式 10
2.2.2 目標式 12
2.2.3 求解方法 13
2.3 遺傳演算法 14
2.4 文獻探討小結 19
第3章 衡量值班暨休假公平性的護理師排班問題及其遺傳演算求解法 20
3.1 依月別包班模式的護理師排班問題 20
3.2 非包班模式的護理師排班問題 47
第4章 演算法效能分析與實例驗證 79
4.1 排班系統執行平台 79
4.2 效能分析測試 83
4.2.1 遺傳演算參數的設定比較 83
4.2.2 依月別包班模式排班問題的求解結果比較 88
4.2.3 非包班模式排班問題的求解結果比較 93
第5章 結論與未來研究建議 101
5.1 結論 101
5.2 未來研究建議 102
參考文獻 103
附錄A 106
附錄B 110

參考文獻
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.
Bard, J., C. Binici, et al. (2003). "Staff scheduling at the United States postal service." Computers & Operations Research 30(5): 745-771.
Bard, J. and H. Purnomo (2005). "Preference scheduling for nurses using column generation* 1." European Journal of Operational Research 164(2): 510-534.
Beaumont, N. (1997). "Scheduling staff using mixed integer programming." European Journal of Operational Research 98(3): 473-484.
Berrada, I., J. Ferland, et al. (1996). "A multi-objective approach to nurse scheduling with both hard and soft constraints." Socio-Economic Planning Sciences 30(3): 183-193.
Blochliger, I. (2004). "Modeling staff scheduling problems. A tutorial." European Journal of Operational Research 158(3): 533-542.
Brusco, M. and L. Jacobs (1995). "Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations." European Journal of Operational Research 86(2): 249-261.
Brusco, M. and T. Johns (1996). "A sequential integer programming method for discontinuous labor tour scheduling* 1." European Journal of Operational Research 95(3): 537-548.
Brucker, P., E. Burke, et al. (2006). "Adaptive construction of nurse schedules: A shift sequence based approach." Journal of Heuristics, ta.
Burke, E., P. De Causmaecker, et al. (1999). "A hybrid tabu search algorithm for the nurse rostering problem." Simulated Evolution and Learning: 187-194.
Burke, E., P. Cowling, et al. (2001). "A memetic approach to the nurse rostering problem." Applied Intelligence 15(3): 199-214.
Burke, E., T. Curtois, et al. (2007). A time pre-defined variable depth search for nurse rostering, Citeseer.
Burke, E., J. Li, et al. (2007). "Pareto-Based Optimization for Multi-objective Nurse Scheduling."
Burke, E., T. Curtois, et al. (2009). "A scatter search methodology for the nurse rostering problem." Journal of the Operational Research Society.
Cai, X. and K. Li (2000). "A genetic algorithm for scheduling staff of mixed skills under multi-criteria* 1." European Journal of Operational Research 125(2): 359-369.
Cheang, B., H. Li, et al. (2003). "Nurse rostering problems--a bibliographic survey." European Journal of Operational Research 151(3): 447-460.
Dowsland, K. (1998). "Nurse scheduling with tabu search and strategic oscillation." European Journal of Operational Research 106(2-3): 393-407.
Easton, F. and N. Mansour (1999). "A distributed genetic algorithm for deterministic and stochastic labor scheduling problems." European Journal of Operational Research 118(3): 505-523.
Jan, A., M. Yamamoto, et al. (2000). Evolutionary algorithms for nurse scheduling problem, Citeseer.
Kawanaka, H., K. Yamamoto, et al. (2001). Genetic algorithm with the constraints for nurse scheduling problem.
Moz, M. and V. Pato (2007). "A genetic algorithm approach to a nurse rerostering problem." Computers & Operations Research 34(3): 667-691.
Seckiner, U. (2007). "An integer programming model for hierarchical workforce scheduling problem." European Journal of Operational Research 183(2): 694-699.
Tanomaru, J. (1995). Staff scheduling by a genetic algorithm with heuristic operators.
Tsang, E. and C. Voudouris (1997). "Fast local search and guided local search and their application to British Telecom''s workforce scheduling problem." Operations Research Letters 20(3): 119-127.
蔣雅慈，利用擴散式粒子群最佳化進行多目標護士排程，碩士論文，國立暨南大學資訊管理研究所。