以基因演算法求解動態醫療健檢排程問題

Heuristic Methods And Genetic Algorithms For Health Inspection Scheduling Problems

林詠軒(Yung-Hsuan Lin)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202002548

摘要

健檢中心常以人工方式進行健康檢查排程，在時間有限及諸多限制下，難以有效排出適當的排程。過往文獻也都以靜態排程且不考量受檢者於診間之間的行走時間為主要探討內容。本研究完整定義了具多重限制式的動態醫療健檢排程問題，建立完整的數學模式。健檢排程的限制有前行健檢項目限制、接續健檢項目限制、時間間隔健檢項目限制、及診間醫療資源數限制等。本研究考量受檢者行於診間之間行走的時間，且全盤考量了受檢者從報到開始直到結帳離院的完整健檢流程，能更貼近健檢中心的實務運作。本研究針對此健檢排程問題研擬一啟發式排程演算程序與一套使用遺傳演算優化的求解系統。採用三個優化子目標，分別是受檢者的候檢和行走時間平均、診間閒置時間平均、及診間完診時間平均等三個子目標值的加總為目標函數值來衡量排程品質。排程目標是達到各子目標均望小的最佳排程。求解的範例數據來自國內某健檢中心的實際數據組成標竿問題，作為不同求解模式的求解範例，以分析與討論不同求解模式的成效。
此外，健檢中心的實務運作可能發生受檢者早到、遲到、檢查項目診查提早或延後結束等隨機情況，此時系統狀態會發生變化。排程系統須依狀態的變化進行重排程，否則實用性不高。本研究將使用離散事件模擬真實健檢中心實務作業產生的系統狀態改變進行排程，以展示系統使用實用性。結果顯示動態排程功能可在受檢者到達診間或結束檢塊診查時，根據目前系統狀態進行重排程，緊密使用醫療資源。求解結果也皆較初排程結果佳，顯示動態排程模式能求得更佳的排程結果。

關鍵字

動態醫療健檢排程問題 ； 重排程 ； 啟發式排程演算程序 ； 遺傳演算法 ； 離散事件模擬

並列摘要

The health inspection center often schedules the health inspection manually. According to the limited time and numerous constrains, it is hardly to schedule properly. The previous literature also focused on static scheduling and did not consider walking time of examinees. This research completely defines the dynamic health inspection scheduling problem with multiple constraints, and establishes a complete mathematical model. Constraints in health inspection scheduling include the precedent constraint, subsequent constraints, time interval constraints, and number of medical resources constraints. This study also considers the walking time taken by the examinees between clinics, and fully considers the complete health inspection process from beginning of registration to leaving the hospital, which can be closer to the practical operation of the health inspection center. This research develops a heuristic scheduling algorithm and a genetic algorithm for this health inspection scheduling problem. This research involves three sub-objectives, which are average waiting and walking time, average idle time, and average makespan. The weighted sum of these three sub-objectives drives the scheduling results to achieve the best schedule. The sample data comes from actual data from a domestic health inspection center to form a benchmark problem, which is used to analyze the effects of different methods.
In addition, the actual operation of the health inspection center may occur in random situations such as early or late arrival of examinees, early or late end of diagnosing, and the system status will change at this time. The scheduling system must reschedule according to the status changes to meet the practical situation. This study uses discrete event simulation to simulate the system status changes and reschedule immediately to create a dynamic scheduling system. The results show that the dynamic scheduling system which reschedules according to the current status changes is better than the static(initial) scheduling results, showing that the dynamic scheduling system can obtain better scheduling results.

並列關鍵字

Dynamic Health Inspection Scheduling Problem ； Rescheduling ； Heuristic Scheduling Algorithm ； Genetic Algorithm ； Discrete Event Simulation

參考文獻

Ala, A. and F. Chen (2019). "Alternative mathematical formulation and hybrid meta-heuristics for patient scheduling problem in health care clinics." Neural Computing and Applications 32(13): 8993-9008.

Cardoen, B., E. Demeulemeester and J. Beliën (2010). "Operating room planning and scheduling: A literature review." European Journal of Operational Research 201(3): 921-932.

Chern, C.-C., P.-S. Chien and S.-Y. Chen (2008). "A heuristic algorithm for the hospital health examination scheduling problem." European Journal of Operational Research 186: 1137-1157.

Deep, K. and H. Mebrathu (2011). "Combined Mutation Operators of Genetic Algorithm for the Travelling Salesman Problem." IJCOPI 2: 2-24.

Gen, M. and R. Cheng (1997). Genetic algorithms and engineering optimization. New York, John Wiley Sons.