臺灣博碩士論文加值系統

為護理師規劃一個公平且滿意的班表，是近年來護理師班表排程中重要的議題。過去研究中護理師的班表滿意度，只著重目前規劃週期內全體人員偏好的工作班次與休假日之總數量。然而，這種滿意度的設計有一些缺陷，如護理師對不同的工作班次或休假日有不同的偏好等級，隨著過去這些等級被滿足的程度會影響班表的公平性；及因工作班次與休假日的偏好數量是不相等以導致班表結果有偏差。因此，本研究考量工作班次與休假日的偏好權重、多偏好等級的工作班次與休假日、指派人員的優先順序及過去資料，提出一個新穎的滿意度公式。此滿意度公式能公平地滿足護理師偏好的工作班次與休假日，使護理師的班表總滿意度最大。首先，本研究考量排程限制，建構一個整數規劃模型去求解小規模問題中班表的最佳解，接著發展三個改良的基因演算法包括改良型基因演算法、混合型基因演算法及移民基因演算法，去搜尋較大規模問題中班表的近似最佳解。最後，基於高雄市某醫院的門診資料做實驗模擬，實驗結果顯示，班表的規劃結果中護理師偏好的工作班次與休假日的滿足程度達到80%以上。在研究的貢獻方面，護理師的班表滿意度會受到偏好等級及優先順序之影響，在班表品質的衡量上更合理。

It has been important to make a fair and satisfactory schedule for nursing staff. In the previous works, the satisfaction of nursing staff for schedule was usually based on the total amount of assignments of the preferred shifts and days-off of the nursing staff at the current planning period. However, the design of such satisfaction has some flaws, as nursing staff have other different preference ranks for shifts and days-off, which may affect fairness of schedule, and numbers of the preferred shifts and days-off are not equivalent so that the planned schedule might be biased. Therefore, this dissertation proposes a novel satisfaction which takes into account the balance of the preference weights for shifts and days-off, different preference ranks towards each shift, the priority ordering of the nursing staff for planning their shift schedule, and the historical data of previous planning period. The proposed satisfaction can fairly satisfy all the nursing staff’s preferences for shifts and days-off to maximize the satisfaction of the nursing staff for their schedules. In addition, the dissertation considered schedule constraints to build a model based upon integer programming to an optimal solution of schedule in small-scale problems, and develops three improved genetic algorithms including improved genetic algorithm (IGA), hybrid genetic algorithm (HGA) and genetic algorithm with immigrant scheme (GAIS), to search near optimal solutions of schedules in large-scale problems. The main contribution of our research is that we consider that the nursing staff’s satisfaction is affected by multiple preference ranks and their priority ordering to be scheduled, so that the quality of the generated schedule is more reasonable.

中文摘要 i
Abstract ii
誌謝 iv
圖目錄 vii
表目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的與方法 3
1.4 論文架構介紹 4
第二章 文獻探討 5
2.1 護理師班表排程的類型 5
2.2 護理師班表排程的求解方法 6
2.2.1 數學規劃法 6
2.2.2 啟發式演算法 8
2.3 小結 9
第三章 護理師班表排程 10
3.1 問題描述 10
3.1.1 護理師班表的介紹 10
3.1.2 護理師班表的作業流程 11
3.2 建構整數規劃模型 14
3.2.1 研究假設 14
3.2.2 符號定義 15
3.2.3 數學模型 16
第四章 基因演算法應用於護理師班表排程 18
4.1 基因演算法 19
4.1.1 編碼設計 19
4.1.2 初始化與適應值 20
4.1.3 交配與突變的運算 21
4.1.4 區域搜尋 23
4.1.5 終止條件 23
4.2 提出新穎的基因演算法 24
4.2.1 改良型基因演算法 27
4.2.2 混合型基因演算法 33
4.2.3 移民基因演算法 35
第五章 實驗執行與結果 36
5.1 參數設定 37
5.1.1 演算法迭代數的分析 37
5.1.2 母群體大小的分析 38
5.2 實驗結果與績效比例 39
5.2.1 四個不同規模的問題的最佳解 39
5.2.2 GA、IGA、HGA及GAIS的實驗結果的比較與分析 39
第六章 結論與未來研究方向 41
參考文獻 42
附錄A 46
附錄B 54

Aickelin, U. and K. A. Dowsland, “Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem,” Journal of Scheduling, 3(3), pp. 139–153, 2000.
Aickelin, U. and K. A. Dowsland, “An indirect genetic algorithm for a nurse-scheduling problem,” Computers and Operations Research, 31(5), pp. 761–778, 2004.
Alistair, R. C. and W. Hannah, “Nurse rescheduling with shift preferences and minimal disruption,” Journal of Applied Operational Research, 3(3), pp. 148-162, 2011.
Asgeirsson, E. I., “Bridging the gap between self schedules and feasible schedules in staff scheduling,” Annals of Operations Research, 218(1), pp. 51-69, 2014.
Azaiez, M. N. and S. S. Sharif, “A 0-1 goal programming model for nurse scheduling,” Computers &; Operational Research, 32(3), pp. 491-507, 2005.
Bergh, J. V., J. Belien, P. D. Bruecker, E. Demeulemeester, and L. D. Boeck, “Personnel scheduling: a literature review,” European Journal of Operational Research, 226(3), pp. 367–385, 2013.
Bard, J. F. and W. Purnomo, “Preference scheduling for nurses using column generation,” European Journal of Operational Research, 164(2), pp. 510–534, 2005.
Bai, R., E. K. Burke, G. Kendall, J. Li, and B. McCollum, “A hybrid evolutionary approach to the nurse rostering problem,” IEEE Transactions on Evolutionary Computation, 14(4), pp. 580-590, 2010.
Behnamian, J. and S. M. F. Ghomi, “The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine,” Information sciences, 219(10), pp. 181–196, 2013.
Clark, P. A., K. Leddy, M. Drain, and D. Kaldenberg, “State nursing shortages and patient satisfaction: More RN—better patient experiences,” Journal of Nursing Care Quality, 22(2), pp. 119–127, 2007.
Cheng, H. and S. Yang, “Genetic algorithms with immigrants schemes for dynamic multicast problems in mobile ad hoc networks,” Engineering Applications of Artificial Intelligence, 23(5), pp. 806–819, 2010.
DeCola1 RN, P. R. and P. Riggins, “Nurses in the workplace: Expectations and needs,” International Nursing Review, 57(3), pp. 335-342, 2010.
Ernst, A. T., H. Jiang, M. Krishnamoorthy, and D. Sier, “Staff scheduling and rostering: a review of applications, methods and models,” European Journal of Operational Research, 153(1), pp. 3–27, 2004.
Felici, G. and C. Gentile, “A polyhedral approach for the staff rostering problem,” Management Science, 50(3), pp. 381-393, 2004.
Griesmer, H., “Self-scheduling turned us into a winning team,” Manage Decisions, 56(12), pp. 21-23, 1993.
Grefenstette, J., “Genetic algorithm for changing environments,” in Proceedings of the 2nd international conference on parallel problem solving from nature, pp. 137-144, 1992.
Glass, C. A. and R. A. Knight, “The nurse rostering problem: A critical appraisal of the problem structure,” European Journal of Operational Research, 202(2), pp. 379-389, 2010.
Hadwan, M., M. Ayob, N. R. Sabar, and R. Qu, “A harmony search algorithm for nurse rostering problems,” Information Sciences, 233(6), pp. 126–140, 2013.
Inoue, T., T. Furuhashi, H. Maed, and M. Takaba, “A proposal of combined method of evolutionary algorithm and heuristics for nurse scheduling support system,” IEEE Transactions on Industrial Electronics, 50(5), pp. 833-838, 2003.
Kang, M. W., P. Schonfeld, and N. Yang, “Prescreening and repairing in a genetic algorithm for highway alignment optimization,” Computer-aided Civil and Infrastructure Engineering, 24(2), pp. 109–119, 2009.
Lian, Z., B. Jiao, and X. Gu, “A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan,” Applied Mathematics and Computation, 183(2), pp. 1008–1017, 2006.
M’Hallah, R. and A. Alkhabbaz, “Scheduling of nurses: a case study of a Kuwaiti health care unit,” Operations Research for Health Care, 2(1-2), pp. 1–19, 2013.
Maenhout, B. and M. Vanhoucke, “An integrated nurse staffing and scheduling analysis for loner-term nursing staff allocation problems,” Omega, 41(2), pp. 485–499, 2013.
Maenhout, B. and M. Vanhoucke, “An evolutionary approach for the nurse rerostering problem,” Computers and Operations Research, 38(10), pp. 1400-1411, 2011.
Moz, M. and M. Vaz Pato, “A genetic algorithm approach to a nurse rerostering problem,” Computers and Operations Research, 34(3), pp. 667-691, 2007.
Purnomo, H. W. and J. F. Bard, “Cyclic preference scheduling for nurses using branch and price,” Naval Research Logistics, 54(2), pp. 200–220, 2007.
Robinson, J., S. Sinton, and Y. Rahmat-Samii, “Particle swarm, genetic algorithm, and their hybrids: optimization of a profiled corrugated horn antenna,” in Proceedings of IEEE Antennas and Propagation Society International Symposium, Vol. 1, pp. 314-317, 2002.
Soza, C., R. L. Becerra, M. C. Riff, and C. A. Coello, “Solving timetabling problems using a cultural algorithm,” Applied Soft Computing, 11(1), pp. 337-344, 2011.
Todorovic, N. and S. Petrovic, “Bee colony optimization algorithm for nurse rostering,” IEEE Transactions on Systems, 43(2), pp. 467–473, 2013.
Topaloglu, S. and H. Selim, “Nurse scheduling using fuzzy modeling approach,” Fuzzy Sets and Systems, 161(11), pp. 1543–1563, 2010.
Valouxis, C. and E. Housos, “Hybrid optimization techniques for the workshift and rest assignment of nursing personnel,” Artificial Intelligence in Medicine, 20(2), pp. 155–175, 2000.
Valouxis, C., C. Gogos, G. Goulas, P. Alefragis, and E. Housos, “A systematic two phase approach for the nurse rostering problem,” European Journal of Operational Research, 219(2), pp. 425–433, 2012.
Wu, T.-H., J.-Y Yeh, and Y.-M. Lee, “A particle swarm optimization approach with refinement procedure for nurse rostering problem,” Computers and Operations Research, 54, pp. 52–63, 2015.
Yilmaz, E., “A mathematical programming model for scheduling of nurses' labor shifts,” Journal of Medical Systems, 36(2), pp. 491-496, 2012.