進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2107201615181400
論文名稱(中文) 系統模擬結合樣本平均近似法求解手術排程問題
論文名稱(英文) Combining System Simulation and Sample Average Approximation to Solve Surgical Scheduling Problem
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 蘇聖煒
研究生(英文) Sheng-Wei Su
學號 R36034139
學位類別 碩士
語文別 中文
論文頁數 62頁
口試委員 指導教授-蔡青志
口試委員-翁慈宗
口試委員-葉英傑
口試委員-張裕清
中文關鍵字 手術排程  模擬最佳化  樣本平均近似法  快速篩選法 
英文關鍵字 surgical scheduling  optimization via simulation  sample average approximation  rapid screening 
學科別分類
中文摘要 本研究針對手術排程問題進行求解,當手術室數量相對於手術而言供不應求時,如何妥善安排手術執行的時間即成了一個重要的課題,安排手術時必須考慮各種資源的限制,不同狀況的發生也需要納入考量,而非僅專注於單一項績效,在本研究中考量了手術執行的時間、急診的需求、病患病情的緊急程度、手術室逾時狀況等因子建構模型,進行多台手術排入單間手術室的多天排程,決定每一台手術預定執行的日子。
而由於手術時間和急診的發生皆為隨機變數,造成此問題具有隨機目標式與多條隨機限制式,並不適用僅能求解確定性問題的數學規劃,而龐大的解空間也無法利用窮舉法來得到品質較佳的解甚至可行解;
因此本研究利用樣本平均近似法(Sample Average Approximation; SAA)的演算法進行求解,將問題的隨機性呈現於模型中;此外也會利用快速篩選法(Rapid Screening)做為另一種求解方法,加速候選解的搜尋,且在一定程度的統計保證下增加求解的效率;並將此兩種方法與其他啟發式解法進行比較,分析不同情境下的問題各種方法的優劣與適用性。
當手術耗時變異程度大時,結合SAA的快速篩選法會得到較佳的目標值,但其抽樣成本較其他方法多出許多;而SAA演算法則可以以明顯較低的抽樣成本來求得品質也不錯的解;而手術耗時變異小時,這兩種方法亦可以求得品質很好的解。
相較於此,啟發式排程方法僅能在手術耗時變異小的情況下求得較佳的解,當手術耗時變異大時,其求得的解品質皆與其他方式有落差。而在求解速度上,SAA演算法相較於快速篩選法則較為耗時。
英文摘要 Duration of surgeries and occurrence of emergency are important random factors in surgical scheduling problem. These factors cannot be known as deterministic values, so the surgical scheduling problem cannot be solved by mathematical programming methods. In our research, we use sample average approximation (SAA) algorithm and rapid screening (RS) to cope with these stochastic factors. In this way, surgical scheduling problem can be solved while its randomness is taken into account. Moreover, we solve surgical scheduling problem via several heuristic methods as well, and compare the results with the ones via SAA and RS.
論文目次 中文摘要 i
英文延伸摘要 ii
誌謝 v
目錄 vi
圖目錄 viii
表目錄 ix
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 資料來源與研究限制 2
1.4 論文架構 3
第二章 文獻回顧 4
2.1 手術排程問題與決策 4
2.2 常見排程法則與績效指標 5
2.3 求解方法 7
2.4 樣本平均近似法 10
第三章 研究方法 13
3.1 資料整理 13
3.2 Arena模型 16
3.3 最佳化模式 18
3.4 式3.8、3.9差異 25
3.5 樣本平均估計模型 27
3.6 模擬最佳化求解演算法 29
第四章 實驗設計與分析 33
4.1 實驗評估 33
4.1.1 實驗參數設定 36
4.1.2 啓發式排程方法 40
4.2 實驗結果 43
4.2.1 情境一實驗結果 43
4.2.2 情境二實驗結果 46
4.2.3 情境三實驗結果 49
4.2.4 情境四實驗結果 51
4.2.5 各方法求解耗時 53
第五章 結論與未來研究方向 55
5.1 結論 55
5.2 未來研究方向 56
參考文獻 58
參考文獻 [1] 童麗清,運用系統模擬技術縮短手術房病患等候時間之研究-以中部某區域教學醫院手術室為例。東海大學工業工程與經營資訊學系碩士論文(2013)。
[2] 運用系統模擬技術縮短手術房病患等候時間之研究-以中部某區域教學醫院手術室為例。東海大學工業工程與經營資訊學系碩士論文(2013)。
[3] 蔡典霖,應用系統模擬於手術排程之研究。長庚大學資訊管理學系碩士論文(2011)。
[4] B. Addis, G. Carello, A. Grosso, E. T´enfani, Operating room scheduling and
rescheduling : a rolling horizon approach. Flexible Services and Manufacturing
Journal 28 (2016) 206–232.
[5] B. Addis, G. Carello, E. T´enfani, A robust optimization approach for the operating
room planning problem with uncertain surgery duration, in: Proceedings of the International
Conference on Health Care Systems Engineering, pp.175–189, Springer,
New York, 2014.
[6] T. Al-Khamis, R. M’Hallah, A two-stage stochastic programming model for the parallel
machine scheduling problem with machine capacity. Computers and Operations
Research 38 (2010) 1747–1759.
[7] J. Atlason, M.A. Epelman, S.G. Henderson, Call center staffing with simulation and
cutting plane methods. Annals of Operations Research 127 (2004) 333–358.
[8] V. Augusto, X. Xie, V. Perdomo, Operating theatre scheduling with patient recovery
in both operating rooms and recovery beds. Computers and Industrial Engineering
58 (2010) 231–238.
[9] G. Bayraksan, D.P. Morton, Assessing solution quality in stochastic programs via
sampling. Operations Research 5 (2009) 102–122.
[10] B. Cardoen, E. Demeulemeester, J. Beli¨en, Operating room planning and scheduling
: A literature review. European Journal of Operational Research 201 (2010) 921–
932.
[11] V.S. Chow, M.L. Puterman, N. Salehirad, W. Huang, D. Atkins, Reducing surgical
ward congestion through improved surgical scheduling and uncapacitated simulation.
Production and Operations Management 20 (2011) 418–430.
[12] B. Denton, A.J. Miller, H.J. Balasubramanian, T.R. Huschka, Optimal allocation of
surgery blocks to operating rooms under uncertainty. Operations Research 58 (2010)
802–816.
[13] B.T. Denton, A.S. Rahman, H. Nelson, A.C. Bailey, Simulation of a multiple operating
room surgical suite, Proceeding of the 2006 Winter Simulation Conference,
2006, pp.414–424.
[14] B. Denton, J. Viapiano, A. Vogl, Optimization of surgery sequencing and scheduling
decisions under uncertainty. Health Care Management Science 10 (2007) 13–24.
[15] E. Erdem, X. Qu, J. Shi, Rescheduling of elective patients upon the arrival of emergency
patients. Decision Support Systems 54 (2012) 551–563.
[16] Y.B. Ferrand, M.J. Magazine, U.S. Rao, Managing operating room efficiency and
responsiveness for emergency and elective surgeries - A literature survey. IIE Transaction
on Healthcare Systems Engineering 4 (2014) 49–64.
[17] F. Guerriero, R. Guido, Operational research in the management of the operating
theatre : a survey. Health Care Management Science 14 (2011) 89–114.
[18] E. Hans, G. Wullink, M.V. Houdenhoven, G. Kazemier, Robust surgery loading.
European Journal of Operational Research 185 (2008) 1038–1050.
[19] T. Homem-de-Mello, G. Bayraksan, Monte Carlo sampling-based methods for stochastic
optimization. Surveys in Operations Research and Management Science 19
(2014) 56–85.
[20] L.J. Hong, J. Luo, B.L. Nelson, Chance constrained selection of the best. INFORMS
Journal on Computing 27 (2015) 317–334.
[21] K.J. Klassen, R. Yoogalingam, Strategies for appointment policy design with patient
unpunctuality. Decision Sciences 45 (2014) 881–911.
[22] A.J. Kleywegt, A. Shpiro, T. Homem-De-Mello, The sample average approximation
method for stochastic discrete optimization. SIAM Journal on Optimization 12
(2001) 479–502.
[23] M. Lamiri, F. Grimaud, X. Xie, X., Optimization methods for a stochastic surgery
planning problem. International Journal of Production Economics 120 (2009) 400–
410.
[24] M. Lamiri, X. Xie, A. Dolgui, F. Grimaud, A stochastic model for operating room
planning with elective and emergency demand for surgery. European Journal of Operational
Research 185 (2008) 1026–1037.
[25] L.H. Lee, N.A. Pujowidianto, L.W. Li, C.H. Chen, C.M. Yap, Approximate Simulation
Budget Allocation for Selecting the Best Design in the Presence of Stochastic
Constraints. IEEE Transaction on Automatic Control 57 (2012) 5940–5945.
[26] J.H. May,W.E. Spangler, D.P. Strum, L.G. Vargas, The surgical scheduling problem
: current research and future opportunities. Production and Operations Management
20 (2011) 392–405.
[27] J.H. May, D.P. Strum, L.G. Vargas, Fitting the lognormal distribution to surgical
procedure times. Decision Sciences 31 (2000) 129–148.
[28] D. Min, Y. Yih, Scheduling elective surgery under uncertainty and downstream capacity
constraints. European Journal of Operational Research 206 (2010) 642–654.
[29] S.N. Ogulate, R. Erol, A hierarchical multiple criteria mathematical programming
approach for scheduling general surgery operations in large hospitals. Journal of
Medical Systems 27 (2003) 259–270.
[30] D. O¨ zdemir, E. Yu¨cesan, Y.T. Herer, Multi-location transshipment problem with
capacitated production. European Journal of Operational Research 226 (2013) 425–
435.
[31] M.J. Persson, J.A. Persson, Analysing management policies for operating room
planning using simulation. Health Care Management Science 13 (2010) 182–191.
[32] D.N. Pham, A. Klinkert, Surgical case scheduling as a generalized job shop scheduling
problem. European Journal of Operational Research 185 (2008) 1011–1025.
[33] A. Shapiro, Asymptotic analysis of stochastic programs. Annals of Operations Research
30 (1991) 169–186.
[34] J. Tang, Y. Wang, An adjustable robust optimisation method for elective and emergency
surgery capacity allocation with demand uncertainty. International Journal of
Production Research 53 (2015) 7317–7328.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-07-21起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw