使用改良型基因演算法解決醫師排班問題

Using A Modified Genetic Algorithm to Solve the Scheduling of Physician’s Shifts

孫雷銘(Lei-ming Sun)

指導教授 ： 劉立

臺北醫學大學/醫學院/醫學資訊研究所/碩士(2005年)

摘要

臺北醫學大學醫學資訊研究所碩士論文摘要 研究所別：臺北醫學大學醫學資訊研究所碩士班 論文名稱：使用改良型基因演算法解決醫師排班問題 指導教授：劉立副教授 研究生：孫雷銘 背景：近年來由於病患安全意識提昇，如何讓值班醫師能有合理適量的工作時間，以減少醫療錯誤的發生，應該會逐漸獲得重視。 目的：以電腦運算自動產生醫師值班表。值班表須符合1.公平性；2. 可因個人需要而調整值班日期；3.無連續值班，或是隔日值班的情形。 材料和方法：以基因演算法為基礎，提出二種改良式交配子(crossover operators)，第一種稱為互斥法( repelling)；第二種稱為鍵結法( bonding)。另外以四種不同類型的排班需求為測試題，來檢驗傳統的基因演算法與二種改良後的演算法在最佳解、收斂速度、和執行時間上的差異。 實驗結果：每種方法在每個題目上各進行十次，然後求其平均。結果發現互斥法比傳統演算法而言，最佳解進步了7%；收斂速度快了3.5%；執行時間則慢了7.6%，而鍵結法比傳統演算法而言，最佳解進步了30%；收斂速度快了22%；執行時間則慢了2.7%。 結論：鍵結法比傳統的基因演算法不論上收斂速度、最佳解上都有長足的進步，而執行速度只差了一點。主要的原因在於交配子的精細運算，另外也可能得力於二點交配。以後可進行更多點的交配分析及更複雜的排班題目研究。

關鍵字

基因演算法 ； 醫師排班 ； 交配子

並列摘要

Background: For the sake of patient safety, the residents’ work hours have got a lot of attentions. It is important to prevent resident physicians working for more than 24 hours to reduce the possibility of accompanying medical errors. Purpose: To generate an on-duty timetable automatically with computers. This timetable should satisfy 1. fairness; 2. individual needs; 3. no consecutive shifts or shifts of every other day. Methods: On the basis of the classical genetic algorithms, two newly devised crossover operators have been proposed. The first one is repelling method; the second one is bonding methods. We tested the two methods with four different kinds of problems. The tests were done on a platform of personal computer and the genetic algorithm Results: Each problem had been tested for each genetic algorithm methods. The results are the average of 10 independent runs. The repelling method is 7% better than classical one in the best individuals; 3.5% quicker in convergent speed; lags 7.6 % in running time. The bonding method is 30% better than classical one in the best individuals; 22% quicker in convergent speed; lags 2.7% in running time. Conclusion: The bonding method overtook both classical and repelling methods in the search of global optima and convergent speed. This may attribute to its effective crossing points selection or its 2-point crossover nature. In the future, we can test multiple-point crossover or uniform crossover and try to solve the more complex scheduling problems.

並列關鍵字

genetic algorithm ； physician scheduling ； crossover

參考文獻

LM Sun, SM Juang, JJ Guo, et al: Scheduling Physians’ Duties automatically with computer. J Plast Surg Asso ROC 2003;12:177-183.

JP Caldeira, AC Rosa. School Timetabling using Genetic Search. Practice and Theory of Automatied Timetabling 1997; 115-122.

David E. Goldberg. Genetic Algorithms in Search, Optimization & Machine Learning. Massachusetts: Addison-Wesley, 1989:10-14.

PS Butterfield. The Stress of Residency: A Review of the Literature. Arch Intern Med. 1989;149:471-2.

JS Samkoff, CH Jacques. A review of studies concerning effects of sleep deprivation and fatigue on residents’ performance. Acad Med. 1991;66:687-93.