臺灣博碩士論文加值系統

護理人員排班問題是一個複雜和考量限制相當多的問題，若是一次考慮全部的排班限制，求解過程不但耗時，求解品質也會受影響。經由個案部門所得到的相關資料，本研究利用多目標規劃法來建構護理人員排班模式，期望能夠更貼近現實層面來了解問題本質，求解目標為滿足人員對班表的需求，即班表總違背次數最小化，為了能有效縮短求解時間與提昇求解品質，將輔以基因演算法搭配其他修正機制來進行求解。
研究結果顯示利用基因演算法能夠有效率地排出班表；而以基因演算法為基礎建構之啟發式演算法，得到的績效較一般基因演算法來得優良，達到最小化目的，驗證了研究結果能夠在符合相關法律規定與醫療院所經營政策之前提下，提供人員排出滿足其需求的班表。

In this search, the discussion of this research is nurse scheduling problem, which is according to relevant laws and regulations of the nurse department to make an appropriate roster and human resources to satisfy the requirements of the nursing staffs. The solution goal of the addressed problem is to meet the needs of staffs, that is, minimizes the violate times of the soft constraints. First, a multi-objective programming model is constructed for solving the problem optimally. Then, a genetic algorithm based heuristic is presented to obtain a near optimal solution. The real data provided from the National Taiwan University Hospital Yun-Lin branch is applied to demonstrate the adaptability of the constructed heuristic. The computational results shown that using genetic algorithm is more efficient than manually for nurse scheduling, the results also shown that the performance which is obtained from the heuristic algorithm is better than genetic algorithm. It validates the findings of the study that can meet the laws and the policies of the nurse department, then provides staffs a roster which can satisfy the needs of staffs.

目錄
中文摘要......................................................................i
英文摘要.....................................................................ii
誌謝........................................................................iii
目錄.........................................................................iv
表目錄......................................................................vii
圖目錄.....................................................................viii
第一章 緒論...................................................................1
1.1 研究背景與動機 ............................................................1
1.2 研究目的..................................................................2
1.3 研究限制..................................................................2
1.4 研究流程與架構說明........................................................3
第二章 文獻探討...............................................................6
2.1 護理人員排班問題..........................................................6
2.1.1 護理人員排班特性........................................................6
2.1.2 護理人員排班限制........................................................7
2.1.3 護理人員排班類別.......................................................10
2.1.4 護理人員排班方式.......................................................11
2.2 多目標規劃法.............................................................13
2.2.1 多目標規劃法特性.......................................................13
2.2.2 多目標規劃求解方法.....................................................14
2.2.3 多目標規劃法相關應用...................................................17
2.3 基因演算法...............................................................18
2.3.1 何謂基因演算法.........................................................18
2.3.2 基因演算法特性.........................................................19
2.3.3 一般基因演算法操作步驟.................................................20
2.3.4 基因演算法相關應用.....................................................26
2.4 總結.....................................................................28
第三章 問題描述與研究方法....................................................29
3.1 問題描述.................................................................29
3.1.1 部門排班原則 ...........................................................29
3.1.2 人員對班表的需求.......................................................30
3.2 符號定義.................................................................31
3.3 數學模式之建構...........................................................32
3.3.1 護理人員排班數學模式之建構.............................................32
3.3.2 本研究數學模式之驗證...................................................34
3.4 演算法之建構.............................................................36
3.4.1 編碼方式與說明.........................................................36
3.4.2 產生初始族群...........................................................38
3.4.3 評估適合度函數.........................................................40
3.4.4 複製...................................................................41
3.4.5 交配............................................................... ....41
3.4.6 突變...................................................................42
3.4.7 判斷機制...............................................................43
3.4.8 子代產生與保留.........................................................43
3.4.9 測試終止...............................................................45
第四章 實證分析..............................................................47
4.1 護理部6B病房護理人員之排班分析...........................................47
4.1.1 護理部6B病房護理人員之整體班表.........................................48
4.1.2 基因演算法之參數設定與績效評估.........................................48
4.2 驗證與分析...............................................................49
4.2.1 排班方式...............................................................49
4.2.2 兩種排班方式之比較.....................................................50
4.2.3 基因演算法執行後成效...................................................51
4.3 研究結果.................................................................61
第五章 研究結論與建議........................................................62
5.1 研究結論.................................................................62
5.2 研究建議.................................................................62
參考文獻.....................................................................64
附錄一 利用Lingo產生之問題規模三班表.........................................68
附錄二 利用基因演算法產生之班表..............................................69
表目錄
表一 排班限制彙整表...........................................................9
表二 利用Lingo 8.0求解結果...................................................36
表三 排班需求條件............................................................38
表四 班表限制條件............................................................39
表五 護理部排班需求條件......................................................47
表六 護理部班表限制條件......................................................47
表七 演算法之因子與設定值....................................................49
表八 利用一般基因產生的求解結果－族群數40為例................................52
表九 利用一般基因產生的求解結果－族群數60為例................................53
表十 利用一般基因產生的求解結果－族群數80為例................................54
表十一 利用最佳化基因產生的求解結果－族群數40為例............................57
表十二 利用最佳化基因產生的求解結果－族群數60為例............................58
表十三 利用最佳化基因產生的求解結果－族群數80為例............................59
表十四 研究方法求解結果之比較................................................61
圖目錄
圖一 研究流程圖...............................................................5
圖二 二元編碼示意圖..........................................................19
圖三 排列編碼示意圖..........................................................19
圖四 實數編碼示意圖..........................................................20
圖五 單點交配示意圖..........................................................22
圖六 雙點交配示意圖..........................................................22
圖七 均勻交配示意圖..........................................................23
圖八 基因突變示意圖..........................................................23
圖九 移轉突變示意圖..........................................................24
圖十 一般基因演算法流程圖....................................................25
圖十一 四位護理人員、排班週期七天的班表......................................35
圖十二 八位護理人員、排班週期十四天的班表....................................35
圖十三 編碼示意圖............................................................37
圖十四 利用隨機方式產生之班表................................................39
圖十五 經由局部交換後之班表..................................................40
圖十六 初始班表產生流程圖....................................................40
圖十七 輪盤法示意圖..........................................................41
圖十八 多點交配示意圖........................................................42
圖十九 突變示意圖............................................................43
圖二十 合併後選取適合度值較高者產生新子代....................................44
圖二十一 利用最佳化概念產生新子代............................................45
圖二十二 本研究基因演算法流程圖..............................................46
圖二十三 程式架構圖..........................................................48
圖二十四 一般基因產生的求解結果-族群數40為例.................................55
圖二十五 一般基因產生的求解結果-族群數60為例.................................55
圖二十六 一般基因產生的求解結果-族群數80為例.................................55
圖二十七 一般基因與最佳化基因產生的求解結果－族群數40為例....................60
圖二十八 一般基因與最佳化基因產生的求解結果－族群數60為例....................60
圖二十九 一般基因與最佳化基因產生的求解結果－族群數80為例....................60

[1]許志義（2003）。多目標決策（二版）。台北市：五南出版社。
[2]李麗傳（2001）。護理行政與病室管理（四版）。台北市：華杏出版股份有限公司。
[3]馮正民、邱裕鈞（2004）。研究分析方法。新竹市：建都文化事業股份有限公司。
[4]劉承春（1998）。綜合啟發式／基因演算法之混合式專家系統在護理人員排班的應用。元智大學，碩士論文，桃園縣。
[5]莊凱翔（2001）。求解護理人員排班最佳化之研究–以遺傳演算法求解。國立成功大學，碩士論文，台南市。
[6]廖國維（2005）。應用多目標規劃建構護理人員非週期性最佳班表之研究。國立屏東科技大學，碩士論文，屏東縣。
[7]葉進儀、林彣珊、朱慶餘（2007）。應用平行基因演算法改善護理人員排班品質。品質學報，14（3），337-350。
[8]Aickelin Uwe and Dowsland Kathryn A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers and Operations Research, 31, 761-778.
[9]Azaiez, M. N. and Al Sharif, S. S. (2005). A 0-1 goal programming model for nurse scheduling. Computers and Operations Research, 32,491-507.
[10]Bard Jonathan F. and Purnomo Hadi W. (2005). A column generation-based approach to solve the preference scheduling problem for nurses with downgrading. Socio-Economic Planning Sciences, 39, 193-213.
[11]Beddoe Gareth R. and Petrovic Sanja. (2006). Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering. European Journal of Operational Research, 175, 649-671.
[12]Bellanti, F., Carello, G.., Croce, F. Della and Tadei, R. (2004). A greddy-based neighborhood search approach to a nurse rostering problem. European Journal of Operational Reaearch, 153, 28-40.
[13]Berrada Ilham, Ferland Jacques A. and Michelon Philippe (1996). A multi-objective approach to nurse scheduling with both hard and soft constraints. Socio-Economic Planning Sciences, 30, 183-193.
[14]Burke Edmund K., Causmaecker Patrick de, Berghe Greet Vanden and Landeghem Hendrik Van. (2004). The stste of art of nurse rostering. Journal of Scheduling, 7, 453-469.
[15]Cheang, B., Li, H., Lim, A. and Rodrigues, B. (2003). Nurse rostering problems-a bibliographic survey. Eoropean Journal of Operational Research, 151, 447-460.
[16]Garey, M. and Johnson, D. (1979). Computers and Intractability：A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
[17]Gillies, D. A. (1982). Nursing management：a system approach. W.B. Saunders CO.
[18]Goldberg, D. E. (1989). Genetic algorithm in search, optimization and machine learning. Addison-Wesley.
[19]Jan Ahmad, Yamamoto Masahito and Ohuchi Aguma (2000). Evolutionary algorithms for nurse scheduling problem. Evolutionary Computation, 2000. Proceedings of the 2000 Congress on (pp.196-203).
[20]Kawanaka Hiroharu, Yamamoto Kosuke, Yoshikawa Tomohiro, Shinogi Tsuyoshi and Tsuruoka Shinji (2001). Genetic algorithm with the constraints for nurse scheduling problem. Evolutionary Computation, 2001. Proceedings of the 2001 Congress on (pp.1123-1130).
[21]Millar Harvey H. and Kiragu Mona (1998). Cyclic and non-cyclic scheduling of 12h shifts nurses by network programming. European Journal of Operational Research, 104, 582-592.
[22]Moz Margarida and Pato Margarida Vaz (2007). A genetic algorithm approach to a nurse rerostering problem. Computers and Operations Research, 34, 667-691.
[23]Musa, A. A. and Saxena, U. (1984). Scheduling nurses using goal-programming techniques. IIE Transactions, 16(3), 216-221.
[24]Oldenkamp, J. H. and Simons, J. L. (1995). Quality factors of nursing schedules. Planning and Evalution-Proceeding. AMICE, 95, 69-74.
[25]Parr, D. and Thompson, J. M. (2007). Solving the multi-objective nurse scheduling problem with a weighted cost function. Annals of Operations Research, 155, 279-288.
[26]Rowland, H. S. and Rowland, B. L. (1985). Nursing Administration Handbook. Aspen Publisher Inc.
[27]Tsai Chang-Chun and Sherman Li, H. A. (2009). A two-stage modeling with genetic algorithm for the nurse scheduling problem. Expert Systems with Applications, 36(5), 9506-9512.
[28]Valouxis, C. and Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial Intelligence in Medicine, 20, 155-175.
[29]Yeh Jinn-Yi and Lin Wen-Shan (2007). Using simulation technique and genetic algorithm to improve the quality care of a hospital emergency department. Expert Systems with Applications, 32, 1073-1083.