系統模擬結合樣本平均近似法求解手術排程問題

Abstract

本研究針對手術排程問題進行求解，當手術室數量相對於手術而言供不應求時，如何妥善安排手術執行的時間即成了一個重要的課題，安排手術時必須考慮各種資源的限制，不同狀況的發生也需要納入考量，而非僅專注於單一項績效，在本研究中考量了手術執行的時間、急診的需求、病患病情的緊急程度、手術室逾時狀況等因子建構模型，進行多台手術排入單間手術室的多天排程，決定每一台手術預定執行的日子。 而由於手術時間和急診的發生皆為隨機變數，造成此問題具有隨機目標式與多條隨機限制式，並不適用僅能求解確定性問題的數學規劃，而龐大的解空間也無法利用窮舉法來得到品質較佳的解甚至可行解； 因此本研究利用樣本平均近似法(Sample Average Approximation; SAA)的演算法進行求解，將問題的隨機性呈現於模型中；此外也會利用快速篩選法(Rapid Screening)做為另一種求解方法，加速候選解的搜尋，且在一定程度的統計保證下增加求解的效率；並將此兩種方法與其他啟發式解法進行比較，分析不同情境下的問題各種方法的優劣與適用性。 當手術耗時變異程度大時，結合SAA的快速篩選法會得到較佳的目標值，但其抽樣成本較其他方法多出?多；而SAA演算法則可以以明顯較低的抽樣成本來求得品質也不錯的解；而手術耗時變異小時，這兩種方法亦可以求得品質很好的解。 相較於此，啟發式排程方法僅能在手術耗時變異小的情況下求得較佳的解，當手術耗時變異大時，其求得的解品質皆與其他方式有落差。而在求解速度上，SAA演算法相較於快速篩選法則較為耗時。

Date of Award	2016 Jul 25
Original language	Chinese
Supervisor	Shing-Chih Tsai (Supervisor)