臺灣博碩士論文加值系統

醫院為了兼顧管理營運、經營利益、政府法規、和護理人員排班公平性等因素，在傳統人工作業模式下，需要花費很多時間才能產生合理的排班表，但又無法客觀評估各種目標的達成效益。本論文提出擴散式粒子群最佳化演算法結合禁制搜尋法來解決護士排班問題，醫院經營者可擬訂多個營運目標（如降低成本及提高員工滿意度等），並述明排班限制（如符合營運實務及政府法規等），利用本論文提出的數學規劃模式即可自動求得既符合限制又優化目標的一組近似最佳解的集合，提供醫院經營者量化的參考依據。我們以兩種不同類型的問題來評估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.

誌　謝 i
摘　要 ii
Abstract iii
目　錄 iv
圖　目　錄 vi
表　目　錄 viii
第一章 緒論 1
1.1研究背景 1
1.2研究目的 2
1.3論文架構 3
第二章　文獻探討 5
2.1員工排班問題 5
2.1.1限制式 5
2.1.2目標式 7
2.1.3求解方法 8
2.2護士排班問題 10
2.2.1限制式 11
2.2.2目標式 13
2.2.3求解方法 14
2.3 次經驗演算法 16
2.3.1 粒子群最佳化演算法 16
2.3.3 禁制搜尋法 17
2.4多目標最佳化 17
2.4.1問題背景 17
2.4.2多目標次經驗演算法 18
2.4.2.1 NSGA II 19
2.4.2.2 MOPSO 22
2.4.2.3 NSPSO 23
2.4.2.4 DNPSO與m-DNPSO 24
2.4.2.5 挑選Pbest與Gbest策略 25
2.4.3效能評估機制 28
3.1問題定義 30
3.2 Scatter MOPSO求解護士排班問題 32
3.2.1外部存放空間 34
3.2.2參考解集合 35
3.2.3禁制搜尋 36
3.2.4三點引導 37
3.2.5 Pareto front 37
4.1實驗環境 39
4.2測試問題 39
4.2.1 標準測試函數 39
4.2.2 護士排班問題 41
4.3參數設定 42
4.4相對效能 44
4.5收斂分析 57
第五章 結論及未來展望 63
參考文獻 64

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.
Bard, J. F., Binici, C., & deSilva, A. H. (2003). Staff scheduling at the United States Postal Service. Computers & Operations Research, vol. 30, pp. 745-771.
Beaumont, N. (1997). Case Study : Scheduling staff using mixed integer programming. European Journal of Operational Research, vol. 98, pp. 473-484.
Berrada, I., Ferland, J. A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard and soft constraints. Socio-Economic Planning Sciences, vol. 30, issue 3, pp. 183-193.
Blochliger, I. (2004). Modeling staff scheduling problems. A tutorial. European Journal of Operational Research, vol. 158, pp. 533-542.
Branke, J., & Mostaghim, S. (2006, September). About selecting the personal best in multi-objective particle swarm optimization. Proceedings of the 9th International Conference on Parallel Problem Solving from Nature – PPSN IX, Reykjavik, Iceland, pp. 523-532.
Brusco, M. J., & Jacobs, L. W. (1995). Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations. European Journal of Operational Research, vol. 86, pp. 249-261.
Brusco, M. J., & Johns, T. R. (1996). A sequential integer programming method for discontinuous labor tour scheduling. European Journal of Operational Research, vol. 95, pp. 537-548.
Burke, E. K., Curtois, T., & Post, G. (2008). A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. European Journal of Operational Research, vol. 188, pp. 330-341.
Cai, X., & Li, K. N. (2000). A genetic algorithm for scheduling staff of mixed skills under multi-criteria. European Journal of Operational Research, vol. 125, pp. 359-369.
Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems – a bibliographic survey. European Journal of Operational Research, vol. 151, pp. 447-460.
Clerc, M., & Kennedy, J. (2002). The particle swarm explosion, stability, and convergence in a multidimensional complex space. IEEE Transaction on Evolutionary Computation, vol. 6, pp. 58-73.
Coello, C. A. C., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transaction on Evolutionary Computation, vol. 8, No. 3, pp. 256-279.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation, vol. 6, No. 2, pp. 42-50.
Dowsland, K. A. (1998). Nurse scheduling with tabu search and strategic oscillation. European Journal of Operational Research, vol. 106, pp. 393-407.
Easton, F. F., & Mansour, N. (1999). A distributed genetic algorithm for deterministic and stochastic labor scheduling problems. European Journal of Operational Research, vol. 118, pp. 505-523.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering A review of applications, methods and models. European Journal of Operational Research, vol. 153, pp. 3-27.
Glover, F. (1989). Tabu search – Part I. ORSA Journal on Computing, vol.1, No.3, pp. 190-206.
Hu, X., & Eberhart, R. (2002). Multiobjective optimization using dynamic neighborhood particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii, USA., pp. 1677-1681.
Hu, X., Eberhart, R., & Shi, Y. (2003). Particle swarm with extended memory for multiobjective optimization. Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, Indiana, USA., pp. 193-197.
Jan, A., Yamamoto, M., & Ohuchi, A. (2000). Evolutionary algorithms for nurse scheduling problem. Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, pp. 196-203.
Kennedy, J., & Eberhurt, R. (1995). Particle Swarm Optimization. Proceedings of IEEE Conference on Neural Networks, pp. 1942-1948.
Laguna, M., & Marti, R. (2003). Scatter Search: Methodology and Implementation in C. Kluwer Academic Publishers, London.
Li, X. (2003). A nondominated sorting particle swarm optimizer for multiobjective optimization. Proceedings of Genetic and Evolutionary Computation, In Springer-Verlag Lecture Notes in Computer Science, vol. 2723, pp. 37-48.
Moore, J., & Chapman, R. (1999). Application of particle swarm to multiobjective optimization. Department of Computer Science and Software Engineering, Auburn University.
Mostaghim, S., & Teich, J. (2003). Strategies for finding local guides in multi-objective particle swarm optimization (MOPSO). Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, Indiana, USA., pp. 26-33.
Moz, M., & Pato, M. V. (2007). A genetic algorithm approach to a nurse rerostering problem. Computers & Operations Research, vol. 34, pp. 667-691.
Seckiner, S. U., Gokcen, H., & Kurt, M. (2007). An integer programming model for hierarchical workforce scheduling problem. European Journal of Operational Research, vol. 183, pp. 694-699.
Srinivas, N., & Deb, K. (1994). Multiobjective optimization using non-dominated sorting in genetic algorithms. Evolutionary Computation, vol. 28, No. 3, pp. 221-248.
Tanomaru, J. (1995). Staff scheduling by a genetic algorithm with heuristic operators. Proceedings of the IEEE International Conference on Evolutionary Computation, vol. 1, pp. 456-461.
Tsang, E., & Voudouris, C. (1997). Fast local search and guided local search and their application to British Telecom’s workforce scheduling problem. Operations Research Letters, vol. 20, pp.119-127.
Van Veldhuizen, D. A. (1999, June). Multiobjective evolutionary algorithms classifications, analyses, and new innovations. PhD thesis, Graduate School of Engineering of the Air Force Institute of Technology, Air University.
Yin, P. Y., Glover, F., Laguna, M., & Zhu, J. X. (2007). Scatter PSO – A more effective form of Particle Swarm Optimization. IEEE Congress on Evolutionary Computation, pp. 2289-2296.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and strengthen Pareto approach. IEEE Transaction on Evolutionary Computation, vol. 3, No. 4, pp. 257-271.
Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multi-objective evolutionary algorithms: Empirical results. MIT Evolutionary Computation, vol. 8, No. 2, pp. 173-195.