以 BIP 與 GA 方法應用於手術指派與排程問題之研究

The Study of Surgery Assignment and Scheduling Problem Using BIP and GA Methods

莊景有(Chin-Yu Chuang)

指導教授 ： 林榮禾

國立臺北科技大學/管理學院/商業自動化與管理研究所/碩士(2006年)

摘要

近年來由於國內外醫療環境快速變遷，醫院面臨競爭激烈的經營環境，加上全民健保連年虧損造成醫療給付的緊縮，以及手術室醫療相關設備費用昂貴。如果醫院無法有效運用手術室相關資源以敷設備成本，醫院也會在面臨競爭和管理成效不彰的情況下面臨倒閉。醫院的重要醫療資源其中之一就是手術室，手術室每年的開銷佔醫院整體預算的 9% 以上 (Gordon et al., 1988) 。另外，在 Teil (2000) 的研究中，指出醫院手術室使用效率的重要性，如醫院手術室使用效率低必然會使醫院手術室負擔昂貴的營運成本及呈現瓶頸資源的狀態 (Jebali, 2005)。因此，如何提升醫院手術室的使用效率、降低醫院手術室的營運成本，並提供良好的手術品質，讓有限的醫療資源做最充分的運用是醫院管理者刻不容緩的要事。為了達到上述目的必須做好醫院手術室指派 (Assignment) 與排程 (Scheduling)管理。因此，本研究的目的為提高手術室醫療資源的有效利用及提升醫院手術室管理的有效性，利用二元整數規劃 (Binary Integer Programming, BIP) 和基因演算法 (Genetic Algorithm, GA) 以求算出較佳的手術室指派與排程規劃。進而，進行兩種模式的手術指派與手術室排程個案分析，來瞭解個案醫院手術室利用現況，找出其使用效率不彰的原因，並比較兩種指派與排程方法的求解效率結果，以提供醫院作為實際參考。最後，由兩個案醫院案例顯示於手術指派研究得知，手術室利用率有顯著的提高，其 BIP 與 GA 的手術室平均利用率值分別為 92.9% (求算時間為 2137 秒) 和 89.4% (求算時間為 1346 秒) ，皆比原始個案手術室的平均利用率 73.6% 較好。再於手術排程案例中，其 BIP 與 GA 的手術排程的平均使用率分別為 94.8% (493 秒) 和 91.4% (238 秒) ，其結果表示 BIP 所求得解為最佳解，但是求算時間過長，當需要快速求解時，利用 GA 可快速求得近似最佳解。因此，本研究所建構的手術指派和排程方法可提供醫院手術室實際使用。

關鍵字

手術指派 ； 手術排程 ； 二元整數規劃 ； 基因演算法 ； 最佳化

並列摘要

The domestic and international medical environment is changed fast in recent years, and the hospital faces the management environment with keen competition. In addition, Health Care Insurance Bureau decreases the medical pay year after year, and the medical equipment of operating room is expensive. If the operation room is unable to use medical resources in order to cover the equipment cost, the hospital will face going bankrupt under keen competition and efficient use of medical resource. One of the important medical resources of the hospital is the operating room, the annual expenses of operating room account for more than 9% of whole budget of the hospital (Gordon et al., 1988). In addition, Teil (2000) point out the importance of the resource using efficiency of operating room of the hospital. If the utilization rate of the operation room is low, the operation room of the hospital will afford expensive cost and become bottleneck (Jebali, 2005). So, how to increase the utilization rate of operation room, offer the good operation quality, and let limited medical resources make the most abundant application are very important for hospital administrator.
There, the objective of my research is to increase the utilization rate of operation room and promote the administrant performance. Using BIP and GA Methods to provide a good operation room assignment and scheduling. Then try to understand the utilization of operating room of case hospital, and find out its apparent reason of bad utilization rate. Analyzing two models of surgery assignment and operation room scheduling and comparing the solution of two models, and these two methods can provide a reference to hospital. At last, using BIP and GA methods to find out good surgery assignment, I found that the solutions of utilization rate of BIP and GA are 92.9% (solving time is 2137seconds) and 89.4% ( solving time is 1346 seconds) , these two utilization rate are better than original utilization rate (73.6%). In operation room scheduling, the solutions of utilization rate of BIP and GA are 94.8% (solving time is 493 seconds) and 91.4% (solving time is 238 seconds). The result is that the solution of BIP is optimal, but its running time is longer than GA. If we want to find out a good assignment and scheduling, we can use GA methods to find a good solution but not optimal. The models of surgery assignment and operation room scheduling our research construct can provide reference for hospital.

並列關鍵字

Surgery Assignment ； Operation Room Scheduling ； Genetic Algorithm ； Binary Integer Programming ； Optimization

參考文獻

[8] 葉進儀、陳民枝、吳軍劼，使用UML與模擬技術於醫院急診室流程改善之研究-以中部某區域醫院為例，大葉學報，11(1):91-102.，2002。

Fineberg, H. V., “Strategies to decrease tuberculosis in us homeless populations : a

[13] Chin, L., Fleisher, G., ” Planning model of resource utilization in an academic pediatric emergency department”, Pediatric Emergence Care, vol. 14, no.1, 1998, pp.4-9.

[15] Dexter, F., “Design of appointment systems for preanesthesia evaluation clinics to minimize patient waiting times : a review of computer simulation and patient survey studies.”, Anesth Analg, vol. 89 no. 4, 1999, pp. 925-931.

[16] Dexterm, F., Traub, R. D., ”How to schedule elective surgical cases into specific operating rooms to maximize the efficiency of use of operating room time”, Anesth Analg, vol. 94, no. 4, 2002, pp. 933-942.