跳到主要內容

臺灣博碩士論文加值系統

(44.211.26.178) 您好!臺灣時間:2024/06/24 20:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:嚴正翰
研究生(外文):YEN, CHENG-HAN
論文名稱:搜尋演算法於醫師工作排班問題之研究—以輔大醫院麻醉科為例
論文名稱(外文):Search Algorithm of Rostering for Doctor Scheduling Problem: A Case of Application on Department of Anesthesiology in FJCUH
指導教授:蔡明志蔡明志引用關係
指導教授(外文):TSAI, MING-JYH
口試委員:游張松陳子立蔡明志
口試委員(外文):YU, CHANG-SUNGCHEN, TZU-LITSAI, MING-JYH
口試日期:2021-01-14
學位類別:碩士
校院名稱:輔仁大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2021
畢業學年度:109
語文別:中文
論文頁數:81
中文關鍵詞:醫師排班工作排班限制滿足問題最佳化搜尋演算法
外文關鍵詞:doctor rosteringwork shiftoptimizationconstraint satisfactionsearch algorithm
Facebook:https://www.facebook.com/ken0924
相關次數:
  • 被引用被引用:1
  • 點閱點閱:362
  • 評分評分:
  • 下載下載:53
  • 收藏至我的研究室書目清單書目收藏:0
醫療工作業務內容繁多且複雜,每個醫療單位皆有其專屬工作排班方式。本篇研究以輔大醫院麻醉科醫師工作排班為例,實作排班演算法以節省排班時間,滿足各醫師提出工作安排需求,以公平分配工作量、拉長值班間隔與降低值班後勞累程度為目標,產生品質更佳排班結果。排班演算法分為二階段,第一階段求排班組合可行解,分為搜尋與最佳化兩部份,搜尋演算法探討回溯法、廣度優先搜尋法、最佳優先搜尋法與輪狀優先搜尋法;最佳化方法分別探討粒子群演算法、模擬退火法與基因演算法。第二階段為班表工作區域分配公平性最佳化,以吉尼係數為工作區域分配公平性衡量標準。本研究探討排班限制問題求解及最佳化演算法,設計目標函數以評估班表優劣,並比較人工排班歷史資料與排班演算法產生班表,結果顯示本研究可提供醫療單位排班問題更有效率且品質更佳解決方法,節省人力花費於排班作業,以更短時間產生符合各醫師排班條件需求、較低勞累度值班安排方式,以及工作區域分配更公平之排班結果。
In hospital daily work, there are many different and complicated rules for scheduling in order to keep medical service running. Each medical unit has specific scheduling rules of working assignment according to its characteristics. The purpose of the study is to solve the complicated and time-consuming scheduling problem for doctor rostering in the department of anesthesiology in Fu Jen Catholic University Hospital (FJCUH). Every doctor is allowed to appoint the vacation or days not on duty. To alleviate the fatigue after duty, the interval between duty days should not be too close. Another concern is the fairness of working area. This study develops a set of methods to solve the constraint satisfaction problem on rostering. The first part is to find and optimize the feasible combinatorial solutions, and the second part is to make working amount of each area balanced. Objective and heuristic functions are designed to guide solution searching and optimization. The searching algorithms in the first part include backtracking search, breadth first search, best first search, best first search and cyclic best first search for feasible solutions. Particle swarm optimization, simulated annealing and genetic algorithm are applied subsequently to optimize the feasible solutions. In the second part, Gini coefficient is introduced to evaluate balance on working area. The above process generates the optimized schedule which is better than manual rostering. The study provides the method better than ever to save the time cost on rostering and bring the schedule with higher quality.
表 次 vi
圖 次 vii

第壹章 緒論 1
第一節 研究背景 1
第二節 研究動機與目的 2

第貳章 文獻探討 3
第一節 工作輪班與排班 3
第二節 排班問題 4
第三節 排班演算法 5
第四節 限制滿足求解 6
第五節 演算法搜尋順序 10
第六節 組合最佳化演算法 13
第七節 最佳化問題求解 15

第參章 研究方法 17
第一節 研究架構 17
第二節 研究流程 18
第三節 研究對象 19
第四節 研究工具 26
第五節 資料取得與處理 26
第六節 排班限制衝突檢查 29
第七節 排班組合數計算 30
第八節 排班限制問題之數學表達式 31
第九節 目標函數與啟發函數設計 33
第十節 演算法架構 38

第肆章 研究結果 41
第一節 建構排班問題 41
第二節 回溯法求解 42
第三節 廣度優先搜尋 43
第四節 約束傳遞方法縮減組合定義域 44
第五節 最佳優先搜尋 46
第六節 廣度優先與最佳優先混合搜尋(CBFS特例型) 48
第七節 模擬退火法 50
第八節 粒子群演算法 53
第九節 基因演算法 56
第十節 日排班組合最佳化 59
第十一節 程式排班與人工排班結果比較 62
第十二節 討論 63

第伍章 結論 69
第一節 研究貢獻 69
第二節 研究限制 69
第三節 未來展望 70
第四節 結語 70

參考文獻 71

附錄一、排班相關資料JSON內容 75
附錄二、排班組合定義域 76
附錄三、排班變數 77
附錄四、非值班區域人力對應組合定義域 78
附錄五、自動排班求解及最佳化運算過程 79
附錄六、最佳化班表生成內容 81
1. 中華民國衛生福利部(2020)。住院醫師適用勞動基準法相關 Q&A。取自https://www.mohw.gov.tw/dl-60226-933f5aef-33bb-40b9-bede-3c87572f9047.html
2. 王治傑(2012)。應用多目標模擬最佳化求解急診室醫療資源配置問題(碩士論文)。新北市:輔仁大學。
3. 李俊德(2005)。以限制規劃法求解全年無休人員排班問題之研究—以護理人員排班為例(碩士論文)。新竹市:國立交通大學。
4. 周怡均(2017)。以基因演算法求解公車駕駛員排班問題之研究(碩士論文)。新竹市:國立交通大學。
5. 林詩芹(2003)。以限制規劃構建全年無休服務人員排班模式—以客服人員排班為例(碩士論文)。新竹市:國立交通大學。
6. 邱啓源(2019)。應用粒子群演算法求解醫療人員重新排班問題(碩士論文)。桃園縣:中原大學。
7. 洪翊豪(2012)。應用回溯法於護理人員換班程式設計(碩士論文)。新竹市:中華大學。
8. 胡利歐(2019)。應用改良式變動鄰近搜尋法求解醫院急診室醫師排班最佳化問題(碩士論文)。新竹市:國立清華大學。
9. 陳宇揚(2017)。基因演算法於餐飲業排班之應用—以鼎泰豐為例(碩士論文)。台北市:國立臺灣大學。
10. 陳冠霖(2020)。多目標機率分支界限法之模擬最佳化醫療資源分配—以急診室為例(碩士論文)。桃園縣:元智大學。
11. 陳翊含(2019)。便利商店員工排班問題研究—運用Python設計基因演算法程式求解(碩士論文)。台北市:國立臺灣科技大學。
12. 黃瑛媚(2020)。0-1 整數規劃在排班問題之應用(碩士論文)。嘉義縣:國立中正大學。
13. 蔡秉芸(2017)。以基因演算法加入模糊邏輯求解急診醫師排班問題(碩士論文)。新北市:輔仁大學。
14. 蔡雅萍(2016)。數規劃法於跨院區醫師排班之應用(碩士論文)。屏東縣:國立屏東科技大學。
15. 錢漢恩(2016)。整數規劃法於警察人員排班最佳化之應用(碩士論文)。屏東縣:國立屏東科技大學。
16. Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557-581.
17. Güler, M. G., İdi˙n, K., & Yilmaz Güler, E. (2013). A goal programming model for scheduling residents in an anesthesia and reanimation department. Expert Systems with Applications, 40(6), 2117-2126. doi:https://doi.org/10.1016/j.eswa.2012.10.030
18. Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial intelligence, 14(3), 263-313.
19. Holland, J. H. (1984). Genetic Algorithms and Adaptation: Springer, Boston, MA.
20. Huang, Y.-C., Lee, P.-T., & Huang, T.-L. (2016). A rostering optimization model for physician scheduling in medical department – a case study in district hospital. Journal of Industrial and Production Engineering, 33(8), 533-557. doi:10.1080/21681015.2016.1180327
21. Kennedy, J., & Eberhart, R. (1995, 27 Nov.-1 Dec. 1995). Particle swarm optimization. Paper presented at the Proceedings of ICNN'95 - International Conference on Neural Networks.
22. Kennedy, J., & Eberhart, R. C. (1997, 12-15 Oct. 1997). A discrete binary version of the particle swarm algorithm. Paper presented at the 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation.
23. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671. doi:10.1126/science.220.4598.671
24. Knauth, P. (1993). The design of shift systems. Ergonomics, 36(1-3), 15-28. doi:10.1080/00140139308967850
25. Knauth, P. (1996). Designing better shift systems. Appl Ergon, 27(1), 39-44. doi:10.1016/0003-6870(95)00044-5
26. Land, A. H., & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3), 497-520. doi:10.2307/1910129
27. Mackworth, A. K., & Freuder, E. C. (1993). The complexity of constraint satisfaction revisited. Artificial intelligence, 59(1), 57-62. doi:https://doi.org/10.1016/0004-3702(93)90170-G
28. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087-1092.
29. Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79-102. doi:https://doi.org/10.1016/j.disopt.2016.01.005
30. Morrison, D. R., Sauppe, J. J., Zhang, W., Jacobson, S. H., & Sewell, E. C. (2017). Cyclic best first search: Using contours to guide branch-and-bound algorithms. Naval Research Logistics (NRL), 64(1), 64-82.
31. Sabin, D., & Freuder, E. C. (1994). Contradicting conventional wisdom in constraint satisfaction. Paper presented at the International Workshop on Principles and Practice of Constraint Programming.
32. Singh, G. (2019). Algorithms: Breadth-First Search vs. Depth-First Search. Retrieved from https://medium.com/better-programming/algorithms-searching-through-a-tree-33610e4577bd
33. Valouxis, C., & Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial Intelligence in Medicine, 20(2), 155-175.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊