臺灣博碩士論文加值系統

隨著經濟發展，人力成本亦不斷提高。對於若干無法以科技自動化取代的全年無休服務業(如運輸、醫療等)而言，人員排班確是一項重要的課題。護理人員排班(Nurse Scheduling)為典型之24小時全年無休之範例，護理人員排班除須滿足勞基法(法律)、連續值班、包班、人員需求等(醫院)眾多硬性限制，並儘量滿足護理人員需求之軟性限制外，預先排班的特性更讓此問題的複雜度變得相當高，故此問題即被視為一高複雜度之組合搜尋問題。
護理人員排班問題，為求解滿足複雜限制之問題，其目標式並不明顯，特性較近似於限制滿足問題(CSP)，故本研究定義此問題為一限制滿足問題，利用限制規劃法求解，並以某署立醫院內科病房為個案病房。本研究之排班期為月，大於大部分以週或雙週為排班期之研究，並考慮多種排班情況，故其問題極為複雜。為有效求解此大規模排班問題，本研究將其分為兩階段求解，第一階段為「排休」模式，求解每位護理人員排班期之休假日期，並將休假結果匯入第二階段「派班」模式，求解整月護理人員值班班表。
本研究測試環境為Windows XP作業系統、1.8G Hz處理器速度，以ILOG OPL Studio 3.0軟體撰寫程式並求解個案三月至五月班表。測試結果每月可於15分鐘內求解完成，與實際班表比較，在兩週休假最少四天、010班別組合與包班之硬限制中，個案病房均有出現違反之情況，平均每月會出現11次違反次數，本研究則為全部符合；而在五項公平性指標分析中，個案病房平均全距最小為2天(休假天數)，但最大平均全距為9天(白班天數)，相較於本研究平均全距之結果，皆為1至2天，公平性結果亦優於實際班表。對於需反覆產生護理人員值班班表之排班者可提供一排班參考依據。

For most service industries, the crew scheduling or rostering is a major concern of the management because the increasing cost of service professionals. Nurse scheduling problem (NSP) is a typical case of year-round service crew scheduling problems. The scheduler not only has to provide a timetable or roster to satisfy all labor and the hospital regulations (hard constraints) but also needs to consider to fit individual preferences (soft constraints) as much as possible. Moreover, some nurse shift pre-assignments often reduce the choice for other unfilled slots. Thus the complicated NSP is considered as a combinatorial search problem.
The character of NSP is like a constraint satisfaction problem (CSP). Thus, we formulate the NSP as a CSP, using constraint programming (CP) Model to solve the problem and conducted a case study of the medical ward in a general hospital, department of health. In order to solve the problem efficiently, we separate the NSP in two phases. The first phase is “Off-day Scheduling Problem”, which solve the off-day roster for each nurse. The second phase is “Shift Scheduling Problem”, which use the off-day roster result to solve the equitable roster.
The CP models were implemented on a P4 1.8G Hz personal computer and used the ILOG OPL Studio 3.0 to solved our CP. The result of a full-month roster of case problem can be generated in 15 minutes. Compared with case rosters, and obtained very positive response. In addition to the roster schedule results, our model also provides as a reference for the scheduler.

中文摘要 i
英文摘要 ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 viii
第一章 續論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 2
1.3 研究方法與流程 2
第二章　文獻回顧 5
2.1 護理人員排班 5
2.2 護理人員排班限制 7
2.3 限制規劃法 10
2.3.1 限制滿足問題 10
2.3.2 限制規劃法 11
2.3.3 限制規劃之求解演算法 12
第三章　護理人員排班問題介紹 19
3.1 護理人員排班概述 19
3.2 護理人員排班問題定義 20
3.3 排班限制整理 21
第四章　護理人員排班個案介紹與模式構建 26
4.1 個案介紹 26
4.2 個案限制條件整理 27
4.3 兩階段求解模式設計 30
4.4 第一階段：排休(Offday Scheduling) 31
4.4.1 限制滿足問題模式構建 31
4.4.2 限制規劃演算程序 36
4.4.3 第一階段求解結果 39
4.5 第二階段：派班模式(Shift Scheduling) 39
4.5.1 限制滿足問題模式構建 39
4.5.2 限制規劃演算程序 45
4.5.3 第二階段求解結果 46
第五章 護理人員排班個案結果分析 48
5.1 各階段模式規模及求解時間 48
5.2 個案參數設定及資料輸入 49
5.2.1 第一階段模式參數設定與資料輸入 49
5.2.2 第二階段模式參數設定與資料輸入 50
5.3 個案執行結果與分析 52
第六章 結論與建議 57
6.1 結論 57
6.2 建議 58
參考文獻 59
附錄 A─護理人員排班三月班表結果 62
附錄 B─護理人員排班四月班表結果 63
附錄 C─護理人員排班五月班表結果 64

表目錄
表2.1 護理人員排班限制條件彙整表 10
表3.1 國外文獻與本研究整理之護理人員排班限制比較表 25
表4.1 護理人員排班考慮限制比較表 29
表4.2 兩階段模式求解綜合說明 31
表4.3 護理人員之工作與休假時間示意表 39
表4.4 兩階段變數數值對應表 40
表4.5 各階段限制式對應表 44
表4.6 護理人員之值班班表 47
表4.7 護理人員公平性指標累積表 47
表5.1 個案之模式變數個數、限制式數及求解時間 48
表5.2 三、四、五月護理人員每日休假人數 49
表5.3 三月預排班表資料 49
表5.4 四月預排班表資料 50
表5.5 五月預排班表資料 50
表5.6 三月護理人員每日各班別需求人數 51
表5.7 四月護理人員每日各班別需求人數 51
表5.8 五月護理人員每日各班別需求人數 51
表5.9 每月包班與預定班別之護理人員 52
表5.10 計劃期間休假數結果 52
表5.11 計劃期間例假日休假數結果 53
表5.12 三月未包班護理人員各值班班別之天數 53
表5.13 四月未包班護理人員各值班班別之天數 53
表5.14 五月未包班護理人員各值班班別之天數 54
表5.15 護理人員排班公平性結果(CV值)比較表 54
表5.16 護理人員排班休假天數分佈結果比較表 55
表5.17 護理人員排班例假日休假天數分佈結果比較表 55
表5.18 護理人員排班白班值班天數分佈結果比較表 55
表5.19 護理人員排班小夜值班天數分佈結果比較表 55
表5.20 護理人員排班大夜值班天數分佈結果比較表 56
表5.21 護理人員排班公平性結果比較表 56

圖目錄
圖1.1 研究流程圖 4
圖2.1 BT搜尋法-以4-queens為例 15
圖2.2 FC搜尋法-以4-queens為例 16
圖2.3 MAC搜尋法-以4-queens為例 18
圖4.1 模式求解架構 30
圖4.2 排休OPL模式 38
圖4.3 排休OPL資料檔 38
圖4.4 派班OPL模式PartI 45
圖4.5 派班OPL模式PartII 46
圖4.6 派班OPL資料檔 46

1.Berrada, I., J. A. Ferland, and P. Michelon (1996), “A multi-objective approach to nurse scheduling with both hard and soft constraints,” Socio-Economic Planning Science 30, pp.183-193.
2.Brailsford, S. C., C. N. Potts, and B. M. Smith (1999), “Constraint Satisfaction Problems: Algorithms and Applications,” European Journal of Operational Research 119, pp. 557-581.
3.Cheang, B., H. Li, and A. Lim (2003), “Nurse rostering problems – a bibliographic survey, ” European Journal of Operational Research, Vol. 151, pp. 447-460.
4.Chun, H. W., H. C. Chan, P. S. Lam, M. F. Tsang, J. Wang and W. M. Yeung (2000), “Nurse Rostering at the Hospital Authority of Hong Kong,” In Proceedings of AAAI/IAAI Conference.
5.Cheng, B. M. W., K. M. F. Choi, J. H. M. Lee, and J. C. K. Wu (1999), “Increasing constraint propagation by redundant modeling: an experience report,” Constraints: An international journal, 4, pp. 167-192.
6.Cheng, B. M. W., J. H. M. Lee, and J. C. K. Wu (1997), “A nurse rostering system using constraint programming and redundant modeling,” IEEE Transactions in Information Technology in Biomedicine, Vol. 1, pp. 44-54.
7.Cheng, B. M. W., J. H. M. Lee, and J. C. K. Wu (1996), “A constraint-based nurse rostering system using a redundant modeling approach,” 8th International Conference on Tools with Artificial Intelligence(ICTAI ‘96), November 16-19, pp. 140-148.
8.Darmoni, S. J., A. Fajner, N. Mahé, A. Leforestier, M. Vondracek, O. Stelian and M. Baldenweck (1995), “Horoplan: Computer-Assisted Nurse Scheduling Using Constraint Based Programming,” Journal of the Society for Health Systems, Vol. 5, No. 1, pp. 41-54.
9.Hare, D. R., and B. C. Kelowna (1998), “Staff scheduling with ILOG Solver”, In Proceedings of INFORMS National Meeting Conference,.
10.Jaumard, B., F. Semet, and T. Vovor (1998), “a generalized linear programming model for nurse scheduling,” European Journal of Operational Research 107, pp. 1-18.
11.Lustig, I. J. and J. F. Puget (2001), “Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming, ” Interfaces, Vol. 31, No. 6, pp. 29-53.
12.Kusumoto, S. (1996), “Nurse scheduling system using ILOG Solver”, In Proceedings of the Second ILOG Solver and Scheduler Users Conference. Paris:ILOG.
13.Millar, H., and M. Kiragu (1998), “Cyclic and non-cyclic scheduling of 12h shift nurses by network programming,” European Journal of Operational Research 104, pp. 582- 592.
14.Miller, H. E., P. William, and J. R. Gustave (1976), “Nurse scheduling using mathematical programming,” Operations Research 24(5), pp. 857-870.
15.Pesant, G., M. Gendreau (1999), “A constraint programming framework for local search methods,” Journal of Heuristic, 5, pp. 255-279.
16.Soft constraints in the nurse Rostering problem, Full description of all the constraint types in use in Plane System, February 6, 2001. Available from <http://www.cs.nott.ac. uk/~gvb/constraints.ps21>
17.Wang, Y. C., and H. W. Chun (2003), “Nurse rostering using constraint programming and meta-level reasoning,” IEA/AIE 2003, pp. 712-721.
18.王國琛 (2002)，「結合限制規劃與數學規劃求解大型後艙空勤組員排班問題」，國立交通大學運輸科技與管理學系碩士論文。
19.王裕元 (2003)，「應用多目標決策模式建立護理人員排班方法之研究」，屏東科技大學工業管理系碩士論文。
20.李麗傳 (1994)，「排班」，護理行政與病室管理，華杏出版公司。
21.林美玲、周幸生，「加護病房護理人員自我排班法之成效評值」，護理雜誌，民國八十八年六月，第四十六卷第三期，第29-38頁。
22.林詩芹 (2003)，「以限制規劃構建全年無休服務人員排班模式─以客服人員排班為例」，國立交通大學運輸科技與管理學系碩士論文。
23.唐依伶 (2003)，「以限制規劃求解公平性空服組員派遣問題─以座艙長為例」，國立交通大學運輸科技與管理學系碩士論文。
24.徐子玲 (2001)，「建構一Web-Based護理排班支援系統」，台北醫學院醫學資訊研究所碩士論文。
25.郭金青 (1996)，「整數目標規劃應用於護士排班之個案研究」，國立中正大學企業管理研究所碩士論文。
26.郭娓吟 (2002)，「整數目標規劃應用於護理人力-以中部某醫院附設護理之家為例」，中國醫藥學院醫務管理研究所碩士論文。
27.高建元 (1994)，「護理人員之排班研究」，國立台灣科技大學管理技術研究所碩士論文。
28.莊凱翔 (2001)，「求解護理人員排班最佳化之研究─以遺傳演算法求解」，國立成功大學工業管理學系碩士論文。
29.劉光宗 (2001)，「數位化護理人員排班系統之研究」，國立東華大學企業管理學系碩士論文。
30.謝水森 (2002)，「醫院管理」，國興出版社。
31.CP-AI-OR網頁 http://cpaior05.mff.cuni.cz/