本研究考量具有隨機性的單一間手術室排程問題，提出能夠處理具有隨機目標式及單一隨機限制式的模擬最佳化~(Simulation Optimization)~演算法求解問題。當手術室數量供不應求，如何妥善安排手術即成為重要的課題，安排手術時，除去成本的考量，也必須考慮各項資源，而非僅專注於單一項績效指標。為了讓問題更貼近現實情形，因此本研究考量急診的需求、所有手術耗時的不確定性、病患病情的緊急程度、手術室逾時時長、手術延遲時長等因子建構模型，進行多台手術排入單間手術室的多天排程。由於原問題過於複雜，難以在合理時間內求解出良好的手術排程，因此我們將原問題轉換為兩階段混整數問題進行求解，在第一階段，先決定每台手術被排入的時間區塊，接著將該解代入第二階段數學模型，求解每個時間區塊下，各台手術的先後順序以及預定開始時間。本研究希望能夠在合理時間內，求解出最佳排程，此排程在最小化總成本的同時，也能使得相關的績效指標達到標準值。

由於手術時間和急診的發生皆為隨機變數，使得本問題的目標式包含期望值，且具有隨機限制式的存在，並不適用數學規劃方法直接進行求解，而龐大的解空間，也無法利用窮舉法來得到品質較佳的解，因此本研究提出快速篩選演算法與隨機近似演算法，分別針對第一與第二階段問題進行求解。在使用這兩種演算法的過程中，皆可以運用拉普拉斯變換~(Laplace transform)~或是模擬方法去計算目標式及隨機限制式的值。實驗結果顯示本研究所提出的演算法，在不同的手術耗時變異程度以及不同的手術個數情形下，皆能求解出品質良好的解，而與其他已存在的求解方法相比，其求解出來的手術排程也都能在滿足績效指標標準的同時，產生較低的總成本。

This thesis describes a stochastic optimization model for surgical scheduling problem when there is a single operating room. We arrange multiple elective surgeries in appropriate time blocks and determine their planned start time and specific sequence. To make the problem more realistic, the arrivals of emergency surgeries, the uncertain operating time of both elective and emergency surgeries, the severity level of patients, and the length of overtime and tardiness are considered in our model. Due to the complexity of the original formulation, we reformulate our model as a two-stage mixed-integer model. In the first stage, we consider the planning decision first. Then the sequencing decisions are determined based on the planning decision in the second stage. The goal of this thesis is to obtain an optimal schedule in reasonable computational time, where the term ``optimal" is defined by the smallest surgical-related cost while achieving the given threshold with respect to some performance measures.

Since expected function and probabilistic formulation of overtime and tardiness are all analytically intractable, the proposed optimization model cannot be solved directly by traditional mathematical programming. Therefore, we propose a rapid screening algorithm and a stochastic approximation algorithm to deal with the first stage and the second stage problems, respectively. In both algorithms, we can apply either Laplace transform or simulation method to evaluate the performance measures of each solution (i.e., the expectation or probability function). Experimental results demonstrate favorable outcomes of the proposed algorithms comparing to existing approaches.

Asmussen, S., Jensen, J.L., & Rojas-Nandayapa, L. (2016). On the Laplace transform of the log- normal distribution. Methodology and Computing in Applied Probability, 18 (2), 441–458.
Augusto, V., Xie, X., & Perdomo, V. (2010). Operating theatre scheduling with patient recovery in both operating rooms and recovery beds. Computers and Industrial Engineering, 58 (2), 231–238.
Batun, S., Denton, B.T., Huschka, T.R., & Schaefer, A.J. (2011). Operating room pooling and parallel surgery processing under uncertainty. INFORMS Journal on Computing, 23 (2), 220– 237.
Berg, B.P., & Denton, B.T. (2017). Fast approximation methods for online scheduling of outpatient procedure centers. INFORMS Journal on Computing, 29 (4), 631–644.
Boesel, J., Nelson, B.L., & Kim, S.H. (2003). Using ranking and selection to “clean up” after simulation optimization. Operations Research, 51 (5), 814–825.
Campbell, G. M. (2012). On-call overtime for service workforce scheduling when demand is uncer- tain. Decision Sciences, 43 (5), 817–850.
Cardoen, B., Demeulemeester, E., & Beli¨en, J. (2010). Operating room planning and scheduling: A literature review. European Journal of Operational Research, 201 (3), 921–932.
Chau, M., & Fu, M.C. (2015). An overview of stochastic approximation, in: Fu, M.C. (Eds.), Chapter 6 of Handbook of simulation optimization, New York, NY: Springer.
Denton, B.T., Miller, A.J., Balasubramanian, H.J., & Huschka, T.R. (2010). Optimal allocation of surgery blocks to operating rooms under uncertainty. Operations Research, 58 (4), 802–816.
Denton, B.T., Viapiano, J., & Vogl, A. (2007). Optimization of surgery sequencing and scheduling decisions under uncertainty. Health Care Management Science, 10 (1), 13–24.
Erdem, E., Qu, X., & Shi, J. (2012). Rescheduling of elective patients upon the arrival of emergency patients. Decision Support Systems, 54 (1), 551–563.
Ferrand, Y.B., Magazine, M.J., & Rao, U.S. (2014). Managing operating room efficiency and respon- siveness for emergency and elective surgeries - A literature survey. IIE Transaction on Healthcare Systems Engineering, 4 (1), 49–64.
Freeman, N.K., Melouk, S.H., & Mittenthal, J. (2016). A scenario-based approach for operating theater scheduling under uncertainty. Manufacturing and Service Operations Management, 18 (2), 245–261.
Ganguly, S., Lawrence, S., & Prather, M. (2014). Emergency department staff planning to improve
patient care and reduce costs. Decision Sciences, 45 (1), 115–145.
Guerriero, F., & Guido, R. (2011). Operational research in the management of the operating theatre: A survey. Health Care Management Science, 14 (1), 89–114.
Gul, S., Denton, B.T., Fowler, J.W., & Huschka, T. (2011). Bi-criteria scheduling of surgical services for an outpatient procedure center. Production and Operations Management, 20 (3), 406–417.
Hans, E., Wullink, G., Houdenhoven, M.V., & Kazemier, G. (2008). Robust surgery loading. Eu- ropean Journal of Operational Research, 185 (3), 1038–1050.
Hong, L.J., Luo, J., & Nelson, B.L. (2015). Chance constrained selection of the best. INFORMS Journal on Computing, 27 (2), 317–334.
Klassen, K.J., & Yoogalingam, R. (2009). Improving performance in outpatient appointment ser- vices with a simulation optimization approach. Production and Operations Management, 18 (4), 447–458.
Klassen, K.J., & Yoogalingam, R. (2014). Strategies for appointment policy design with patient unpunctuality. Decision Sciences, 45 (5), 881–911.
Lamiri, M., Grimaud, F., & Xie, X. (2009). Optimization methods for a stochastic surgery planning problem. International Journal of Production Economics, 120 (2), 400–410.
Lamiri, M., Xie, X., Dolgui, A., & Grimaud, F. (2008). A stochastic model for operating room planning with elective and emergency demand for surgery. European Journal of Operational Research, 185 (3), 1026–1037.
Macario, A., Vitez, T.S., Dunn, B., & McDonald, T. (1995). Where are the costs in perioperative care? Analysis of hospital costs and charges for inpatient surgical care. Anesthesiology, 83 (6), 1138–1144.
May, J.H., Spangler, W.E., Strum, D.P., & Vargas, L.G. (2011). The surgical scheduling problem: Current research and future opportunities. Production and Operations Management, 20 (3), 392– 405.
May, J.H., Strum, D.P., & Vargas, L.G. (2000). Fitting the lognormal distribution to surgical procedure times. Decision Sciences, 31 (1), 129–148.
Min, D., & Yih, Y. (2010). Scheduling elective surgery under uncertainty and downstream capacity constraints. European Journal of Operational Research, 206 (3), 642–654.
Nelson, B.L., Swann, J., Goldsman, D., & Song, W. (2001). Simple procedures for selecting the best
simulated system when the number of alternatives is large. Operations Research, 49 (6), 950–963.
Persson, M.J., & Persson, J.A. (2010). Analysing management policies for operating room planning using simulation. Health Care Management Science, 13 (2), 182–191.
Stepaniak, P.S., Heij, C., & De Vries, G. (2010). Modeling and prediction of surgical procedure times. Statistica Neerlandica, 64 (1), 1–18.
Tellambura, C., & Senaratne, D. (2010). Accurate computation of the MGF of the lognormal distribution and its application to sum of lognormals. IEEE Transactions on Communications, 58 (5), 1568–1577.
Tsai, S.C. (2013). Rapid screening procedures for zero-one optimization via simulation. INFORMS Journal on Computing, 25 (2), 317–331.
Tsai, S.C., & Yang, T. (2017). Rapid screening algorithms for stochastically constrained problems.
Annals of Operations Research, 254 (1-2), 425–447.
Widder, D. (1946). The Laplace transform. Princeton, NJ: Princeton University Press.
Wright, P., & Bretthauer, K.M. (2010). Strategies for addressing the nursing shortage: Coordinated decision making and workforce flexibility. Decision Sciences, 41 (2), 373–401.