臺灣博碩士論文加值系統

大部份醫療院所的營運成本結構中，護理人力成本佔總成本的30％-40％。因此如何妥善管理護理人力，加以合情、合理及有效率的運用，成為醫療院所經營管理的重要課題。以往護理人員排班的相關研究中，所採用的方法多半是利用整數規劃、週期式排班方法，抑或是啟發式演算法則等，以尋找可行解或是最適宜解。
護理排班問題(Nurse Scheduling Problem, NSP)是一個組合最佳化問題，亦就是在三種常見換班型態限制下，分派護士的值勤工作。本論文使用一種較新智慧型有效率之螞蟻演算法，利用其智慧型的機制，在既有螞蟻系統基礎上將人工螞蟻搜尋的方式，提出一些策略且運用於護理排班問題上，以增加求解的效果。其求解結果雖無法證明其最佳解，但卻能在短時間內得到許多成效不錯的近似最佳解，能有利於解決護理人員之排班問題。
將實作護理排班支援系統之結果與之前的諸多文獻作比較，證實本論文所提的方法，確實可將護理排班所需排班時間大幅度的縮短，並在符合各種軟硬條件的限制條件下，排出最適宜、合乎公平合理且人性化之排班品質，成功的將智慧型方法應用於護理排班問題上。
關鍵詞:護理排班問題、螞蟻演算法、基因演算法

Nursing expenditure occupies 30~40 percentage of overall expenditure in most hospitals business operation costs. So how to successfully manage human resource and efficiently achieve business operation is crucial topic in hospital management. Nurse Scheduling is the process of generating timetables which specify the duty shifts to nurses over given period of time. In the past, correlated researches regarding nurse scheduling were presented using integer programming model, cyclical scheduling and elicitation method and so on, for getting fittest solutions (timetables).
The Nurse Scheduling Problem (NSP) is a combinatorial optimization problem. It is the task of allocating nurse duty in three shift modes under constraints.
In this thesis, an intelligent and efficient ant-based searching algorithm is, although used the ant system cannot be demonstrated whether it is optimal solution or not, but it can produce many approximately fittest solutions in a short time. Consequently, they are more suitable for nurse scheduling problems.
According to the experiment results, it is observed that the ant system is very efficient for solving nurse scheduling problem.
Keywords: Nurse Scheduling Problem, Ant Algorithm, Genetic Algorithm.

目　錄
摘 要 Ⅰ
Abstract Ⅱ
誌 謝 III
目 錄 IV
圖 目 錄 VII
表 目 錄 X
第1章 緒論 1
1.1 研究背景及目的1
1.2 研究限制 3
1.3 研究方法 4
1.4 研究流程 5
1.5論文架構 7
第2章 文獻探討 8
2.1 護理排班限制與規則 8
2.2 人員排班之相關研究 10
2.2.1人員排班的定義 10
2.2.2人員排班的類型 11
2.2.3人員排班應用範疇 12
2.3護理人員排班之相關研究 15
2.3.1護理人員排班的定義 15
2.3.2護理人員排班的考量因素 15
2.3.3護理人員排班的方式 16
2.4 人員排班問題演算法之探討 21
2.4.1最佳解法 21
2.4.2啟發式解法 22
2.5 護理人員排班啟發式演算法則介紹 23
2.5.1模擬退火法 23
2.5.1.1 緣起與特性 24
2.5.1.2模擬退火法相關發展與應用之文獻 25
2.5.2基因演算法 26
2.5.2.1 緣起與特性 26
2.5.2.2基因演算在護理人員排班之相關文獻 28
2.5.3螞蟻演算法 29
2.5.3.1螞蟻族群特性 30
2.5.3.2人工螞蟻搜尋能力 32
2.5.3.3螞蟻演算法之概念 34
2.5.3.4螞蟻族群最佳化相關發展與應用之文獻 35
2.6 小結 38
第3章 問題定義 40
3.1問題定義 40
3.2護理排班之評估標準 42
3.3時間成本之評估標準 42
3.4護理排班最佳化計算之評估標準 43
3.5護理排班演算法參數決定之標準 44
第4章 護理排班演算法 45
4.1護理排班思考流程 45
4.2以螞蟻系統解決護理排班（NSP）問題及實際應用 46
4.2.1螞蟻系統解決TSP問題 47
4.2.2螞蟻系統在NSP問題上之實際應用 48
4.2.3螞蟻系統的編碼方式 50
4.3護理排班演算法執行步驟 51
4.4護理排班演算法(AN System)執行架構流程 55
5章 模擬實驗 56
5.1 測試資料 58
5.2 參數設定 58
5.2.1 預設值參數設定 59
5.2.2 理想值參數設定 59
5.3 排班結果 59
5.3.1 護理排班系統(ACO)模擬排班實驗結果 60
5.3.2 模擬ACO護理排班支援系統之排班結果 64
5.3.3 AN System護理排班系統實驗結果 75
5.3.4 護理排班系統文獻排班結果比較 83
5.3.4.1 SA(模擬退火法)護理之班表 84
5.3.4.2 EGA(菌化基因演算法)護理班表及模擬實驗班表 86
5.3.5 AN System護理班表支援系統排班結果 90
5.4 實驗探討 111
第6章 結論與建議 112
6.1 結論 112
6.2 建議 115
參考文獻 116
作者簡介 123












圖 目 錄
圖 1.1 研究流程圖 6
圖 2.1 自然界螞蟻的覓食行為圖 31
圖 2.2 人工螞蟻的行為模式圖 33
圖 2.3 螞蟻族群演算法架構圖 35
圖 3.1 Sample of nurse schedule 40
圖 4.1 護理排班演算法(AN System)程式流程圖 55
圖 5.1 護理人員排班支援系統LOG in畫面 56
圖 5.2 AN System 人機介面 57
圖 5.3 AN System 執行結果 57
圖 5.4 10 Nurse /7天之班表(模擬ACO) 65
圖 5.5 20 Nurse /7天之班表(模擬ACO) 66
圖 5.6 30 Nurse /7天之班表(模擬ACO) 66
圖5.7 40 Nurse /7天之班表(模擬ACO) 67
圖 5.8 50 Nurse /7天之班表(模擬ACO) 67
圖 5.9 10 Nurse /14天之班表(模擬ACO) 68
圖 5.10 20 Nurse /14天之班表(模擬ACO) 68
圖 5.11 30 Nurse /14天之班表(模擬ACO) 69
圖 5.12 10 Nurse /31天之班表(模擬ACO) 69
圖 5.13 改變換班參數1(α)、參數2(β) 理想參數值之介面 70
圖 5.14 10 Nurse /7天之班表(模擬ACO) 70
圖 5.15 20 Nurse /7天之班表(模擬ACO) 71
圖 5.16 30 Nurse /7天之班表(模擬ACO) 71
圖 5.17 40 Nurse /7天之班表(模擬ACO) 72
圖 5.18 50 Nurse /7天之班表(模擬ACO) 72
圖 5.19 10 Nurse /14天之班表(模擬ACO) 73
圖 5.20 20 Nurse /14天之班表(模擬ACO) 73
圖 5.21 30 Nurse /14天之班表(模擬ACO) 74
圖 5.22 10 Nurse /31天之班表(模擬ACO) 74
圖 5.23 BEA之護理排班支援系統人機介面 87
圖 5.24 BEA之護理排班支援系統輸出班表顯示 87
圖 5.25 本論文模擬BEA之護理排班支援系統人機介面 88
圖 5.26 本論文模擬BEA之護理排班支援系統班表顯示結果 88
圖 5.27 本論文(AN System)螞蟻演算法護理排班支援系統班表結果 89
圖 5.28 AN 護理排班系統登入畫面 91
圖 5.29 AN 護理排班系統(預設)畫面 92
圖 5.30 20 Nurse /7天之班表 92
圖 5.31 20 Nurse /14天之班表 93
圖 5.32 20 Nurse /31天之班表 93
圖 5.33 50 Nurse /7天之班表 94
圖 5.34 50 Nurse /14天之班表 94
圖 5.35 50 Nurse /31天之班表 95
圖 5.36 50 Nurse /14天之改變換班衰減值及α、β參數下之介面 95
圖 5.37 20 Nurse/7天之改變換班衰減值及α、β參數下之班表(1) 96
圖 5.38 20 Nurse/7天之改變換班衰減值及α、β參數下之班表(2) 96
圖 5.39 20 Nurse/7天之改變換班衰減值及α、β參數下之班表(3) 97
圖 5.40 20 Nurse/7天之改變換班衰減值及α、β參數下之班表(4) 97
圖 5.41 20 Nurse/7天之改變換班衰減值及α、β參數下之班表(5) 98
圖 5.42 50 Nurse/7天之改變換班衰減值及α、β參數下之班表(1) 98
圖 5.43 50 Nurse/7天之改變換班衰減值及α、β參數下之班表(2) 99
圖 5.44 50 Nurse/7天之改變換班衰減值及α、β參數下之班表(3) 99
圖 5.45 50 Nurse/7天之改變換班衰減值及α、β參數下之班表(4) 100
圖 5.46 50 Nurse/7天之改變換班衰減值及α、β參數下之班表(5) 100
圖 5.47 20 Nurse/14天之改變換班衰減值及α、β參數下之班表(1) 101
圖 5.48 20 Nurse/14天之改變換班衰減值及α、β參數下之班表(2) 101
圖 5.49 20 Nurse/14天之改變換班衰減值及α、β參數下之班表(3) 102
圖 5.50 20 Nurse/14天之改變換班衰減值及α、β參數下之班表(4) 102
圖 5.51 20 Nurse/14天之改變換班衰減值及α、β參數下之班表(5) 103
圖 5.52 50 Nurse/14天之改變換班衰減值及α、β參數下之班表(1) 103
圖 5.53 50 Nurse/14天之改變換班衰減值及α、β參數下之班表(2) 104
圖 5.54 50 Nurse/14天之改變換班衰減值及α、β參數下之班表(3) 104
圖 5.55 50 Nurse/14天之改變換班衰減值及α、β參數下之班表(4) 105
圖 5.56 50 Nurse/14天之改變換班衰減值及α、β參數下之班表(5) 105
圖 5.57 20 Nurse/31天之改變換班衰減值及α、β參數下之班表(1) 106
圖 5.58 20 Nurse/31天之改變換班衰減值及α、β參數下之班表(2) 106
圖 5.59 20 Nurse/31天之改變換班衰減值及α、β參數下之班表(3) 107
圖 5.60 20 Nurse/31天之改變換班衰減值及α、β參數下之班表(4) 107
圖 5.61 20 Nurse/31天之改變換班衰減值及α、β參數下之班表(5) 108
圖 5.62 50 Nurse/31天之改變換班衰減值及α、β參數下之班表(1) 108
圖 5.63 50 Nurse/31天之改變換班衰減值及α、β參數下之班表(2) 109
圖 5.64 50 Nurse/31天之改變換班衰減值及α、β參數下之班表(3) 109
圖 5.65 50 Nurse/31天之改變換班衰減值及α、β參數下之班表(4) 110
圖 5.66 50 Nurse/31天之改變換班衰減值及α、β參數下之班表(5) 110










表 目 錄
表 2.1 護理排班限制條件之彙整比較表 18
表 2.2 各種排班方式優點及其求解問題之比較 20
表 2.3 螞蟻演算法分類表 34
表 2.4 螞蟻族群最佳化應用問題 36
表 2.5 人員排班求解相關文獻 39
表5.1 ACO 護理排班系統各項參數之設定(預設值) 60
表5.2 ACO 護理排班系模擬排班實驗結果（a）7天 60
表5.3 ACO 護理排班系模擬排班實驗結果（b）14天 61
表5.4 ACO 護理排班系模擬排班實驗結果（c）31天 61
表 5.5 ACO 護理排班系統各項參數之設定(理想值) 62
表 5.6 ACO 護理排班系模擬排班實驗結果（a）7天 62
表5.7 ACO 護理排班系模擬排班實驗結果（b）14天 63
表5.8 ACO 護理排班系模擬排班實驗結果（c）31天 63
表 5.9 AN System護理排班系統各項參數之設定(預設值) 76
表 5.10 AN System 護理排班系統之排班結果（a）20 Nurse 76
表5.11 AN System 護理排班系統之排班結果（b）50 Nurse 77
表 5.12 AN System護理排班系統各項參數之設定(理想值) 77
表 5.13 AN System 護理排班系統之排班結果（a）20 Nurse/ 7天 78
表 5.14 AN System 護理排班系統之排班結果（b）50 Nurse/ 7天 78
表 5.15 AN System 護理排班系統之排班結果（a）20 Nurse/ 14天 79
表 5.16 AN System 護理排班系統之排班結果（b）50 Nurse/ 14天 79
表 5.17 AN System 護理排班系統之排班結果（a）20 Nurse/ 31天 80
表 5.18 AN System 護理排班系統之排班結果（b）50 Nurse/ 31 天 80
表 5.19 護理排班支援系統求解效益比較分析表 83
表 5.20 一般護理人員第一週排班表 84
表 5.21 一般護理人員第二週排班表 85

[1]王行一，2001「最佳排課系統之建立」，技術學刊，第十六卷，第四期，第587- 593 頁。
[2]王裕元，2003「應用多目標決策模式建立護理人員排班方法之研究」，國立屏東科技
大學工業管理研究所碩士論文。
[3]林瑞堯、馬少平，1992「人工智慧導論」，儒林圖書公司。
[4]張慶源、李淑賢，1992「護理人員排班系統之實驗設計」，醫院與電腦，第八期，
65~70頁。
[5]郭彥秀，2000「鐵路駕駛員排班問題之研究」，國立成功大學交通管理研究所碩士論文。
[6]杜宇平，2000「空服員排班網路模式之研究」，國立中央大學土木工程學系博士論文。
[7]莊凱祥，2001「求解護理人員排班最佳化之研究—以遺傳演算法求解」，國立成功大學工業管理研究所碩士論文。
[8]連志平，1998「警察人員排班問題之研究」，國立交通大學運輸工程與管理系碩士論文。
[9]陳玉枝等，1992「發展護理人員電腦排班系統之初探」，榮總護理，第九卷第二期，第183-193頁。
[10]蔡宗明，2004「滿足多目標之護理人員最佳化班表之探討」，國立屏東科技大學工業管理研究所碩士論文。
[11]顏上堯、林錦翌，1997「空服員排班組合最佳化之研究」，中國土木水利工程學刊，第九卷第二期，第303-313頁。
[12]劉承春、邱昭彰、張創然，1998「基因演算專家系統在血液透析室護理人員排班的應用」，醫學資訊雜誌，第八期，第19-37頁。
[13]蕭宗勝，2001「螞蟻族群演算法應用在組合問題之研究」，銘傳大學資訊管理研究所
碩士論文。
[14]Abboud ,N. Inuiguchi, M. Sakawa, M.and Uemura, Y. “Manpower allocation using genetic annealing, ” European Journal of Operational Research, Vol. 111, pp. 405-420, 1998.
[15]Ahuja, H. and Sheppard, R. “Computerized Nurse Scheduling,” Industrial Engineering, Vol. 7, pp. 24-29, 1975.
[16]Bartholdi, J.J. “A Guaranteed-Accuracy Round-Off Algorithm For Cyclic Scheduling And Set Covering,” Operation Research, Vol. 29, pp. 501-510, 1981.
[17]Beasley, J. E. and Cao, B. “A Tree search algorithm for the crew scheduling problem, ” European journal of operational research, Vol. 94, No. 3, pp. 517-526, 1996.
[18]Beckers, R., Deneubourg, J. L. and Goss, S., “Trails and u-turns in the selection of the shortest path by the ant lasius niger,” Journal of Theoretical Biology, Vol. 159, pp. 397-415, 1992.
[19]Bout,D.E.V. and Miller,T.K; “Graph partitioning using annealed neural network, ” IEEE Transaction on Neural Networks, Vol. 2, pp. 192-203, 1990.
[20]Bolte, A.and Thonemann, U. W., “OPtimizing simulated annealing
schedules with genetic programming," European Journal of
operational research, Vol. 92, pp. 402-416, 1996.
[21]Browne, J., “Scheduling Employees for Around-the-clock
Operation,” IEE Solutions, pp. 30-33, 2000.
[22]Cheng. B.M. W., Lee, J. H. M. and Wu, J. C. K. “A Constraint-
Based Nurse Rostering System Using A Redundant Modeling
Approach, ” Proceedings Eighth IEEE on Tools With Artificial Intelligence International Conference, pp. 140-148,1996.
[23]Denebourg, J.L., Pasteels, J.M., and Verhaeghe, J.C., “Probabilistic Behavior in Ants: a Strategy of Errors,” Journal of Theoretical Biology, Vol. 105, pp. 259-271, 1983.
[24]Dorigo, M., Maniezzo, V. and Colorni, A., “ Positive feedback as a search strategy, ” Technical Report No. 91-016, Politecnico di Milano, Italy, 1991.
[25]Dorigo, M., Maniezzo, V., and Colorni, A., “The ant system：an autocatalytic optimizing process,” Technical Report No.91-016, Politecnico di Milano, Italy, 1991.
[26]Dorigo, M., “Learning by probabilistic Boolean network,”IEEE Transactions on Neural Networks, Vol. 12, pp. 887-891, 1994.
[27]Dorigo M. and Gambardella, L.M., “A study of some properties of
Ant-Q, ” Proceedings of PPSN IV-Fourth International Conference
on Parallel Problem Solving From Nature, pp. 22-27, 1996.
[28]Dorigo M., Maniezzo, V. and Colorni, A., “The ant system:
Optimization by a colony of cooperating agents,” IEEE
Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26,
No. 1, pp. 29-41, 1996.
[29]Dorigo, M. and Gambardella, L.M., “Ant colony system: A
cooperative learning approach to the traveling salesman
problem,” IEEE Transactions on Evolutionary Computation, Vol. 1,
No. 1, pp. 53-66, 1997.
[30]Dorigo, M. and Gambardella, L.M., “Ant colonies for the
traveling salesman problem,” BioSystems, Vol. 43, pp. 73-81,
1997.
[31]Dorigo M., Di Caro, G. and Gambardella, L. M., “Ant algorithms for discrete optimization,” Artificial Life, Vol. 5, No. 3, pp. 137-172, 1999.
[32]Dorigo, M., Bonabeau, Eric and Theraulaz, Guy, “Ant algorithms and stigmergy,” Future Generation Computer Systems, Vol. 16, pp. 851– 871, 2000.
[33]Fitzpatrick, T.,et.al, “An Automated Staff Scheduling System
that Minimizes Payroll Costs and Maximizes Nurse Satisfaction,”
Computers in Nursing, Vol. 5,pp.10-14, 1987.
[34]Glover, F, “Heuristics for integer programming using surrogate constraints,” Decision Science, Vol. 8, pp. 156-166, 1977.
[35]Glover, F, “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, Vol. 13, No. 5, pp. 533-549, 1986.
[36]Glover, F, “Tabu search-part I,” Orsa Journal of computing, Vol. 1, No. 3, pp. 190-206, 1989.
[37]Holland, J.H., “Adaption in natural and artificial systems,” Boston, MA：MIT press, 1992.
[38]Inoue, T.; FuruhaT.; Fujii, M.; Maeda, H.; Takaba, M.; “Development of nurse scheduling support system using interactive EA, ” 1999 IEEE International Conference on Systems, Man, and Cybernetics, Vol. 5, pp. 12-15 , 1999.
[39]Inoue, T.; Furuhashi, T.; M.; Maeda, H.; Takaba, M.; , “ A study on bacterial evolutionary algorithm engine for interactive nurse scheduling support system,”, 26th Annual Conference of the IEEE Industrial Electronics Society, Vol. 1, pp. 22-28, 2000.
[40]Inoue, T.; Furuhashi, T.; Fujii, M.; Maeda, H.; Takaba, M.; “A proposal of combined method of evolutionary algorithm and heuristics for nurse scheduling support system, ”Industrial Electronics, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 50, pp. 833 – 838, 2003.
[41]Kirkpatrick, S., C.D. Gelatt and M.P. Vecchi, “Optimization By Simulated Annealing,” Science, Vol. 220, pp. 671-680, 1983.
[42]Kolonko, M. “Some new results on simulated annealing applied to the job shop scheduling problem,” European Journal of Operational Research, pp. 113-119, 1999.
[43]Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., and Shmoys D. B., The Traveling Salesman Problem — A Guided Tour of Combinatorial Optimization, John Wiley & Sons Ltd, 1985.
[44]Lau, H. C. “On The Complexity of Manpower Shift Scheduling,” Operation Research, Vol. 23, pp. 93-102, 1996.
[45]Levine, D. “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling, ” Computers Operations Research, Vol. 23, No. 6, pp. 547-558, 1996.
[46]Martello, P.M. “Modified Cyclical Scheduling：A Practical Approach,” Nursing Management, Vol. 8, No. 10, pp.61, 1987.
[47]Morris. J. G and Showalter, M. J.“Simple Approaches To Shift, Day-Off And Tour scheduling problems,” Management Science, Vol. 29, No. 8, pp. 942-950, 1983.
[48]Metropolis, N., A. Rosenblush, M.Rosenblush, A. Teller and E. Teller, “Equation of State Calculations by fast Computing Machines,” Journal of Chemical Physics, Vol. 21, pp. 1087-1092, 1953.
[49]Ozdemir, H. T. and Mohan, K. M., “Flight graph based genetic algorithm for crew scheduling in airline,” Information Sciences, Vol. 133, pp. 165-173, 2001.
[50]Van Laarhoven, P.J.M. E.H.L. Arts and J.K. Lenstra, “Job Shop Scheduling by Simulated Annealing,” Operations Research, Vol. 40, pp. 113-125, 1992.
[51]Warner, D. M. and Prawda, J. “A Mathematical Programming Model for Scheduling Nursing Personnel In A Hospital,” Management Science, Vol. 19, No. 4, pp. 411-422, 1972.
[52]Yamamoto et al, “Propose a collective multi-agent approach using pheromone style communication of real arts for solution of NSP,” proceeding of ITC-CSCC, pp. 1479-1482, 2000.
[53]Yamamoto, Jan. A., Ohuchi, M. A. “Evolutionary algorithms for nurse scheduling problem,” Proceedings of the 2000 Congress on Evolutionary Computation, Vol. 1, pp.16-19, 2000.
[54]Yannis, E. I. and E. Wong, “Query Optimization by simulated Annealing,” ACM SIGMOD Annual Conference on Management of Data, pp. 9-22, 1987.