健康檢查作業排程模式之研究

簡佩思(Pei-Szu Chien)

指導教授 ： 陳靜枝

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00092

摘要

本研究主要著重在健康檢查作業排程模式部分，找出一套模式可使在檢查時間、檢查項目資源數量與其他如先後順序、資源分享與連續檢查等特殊限制之下，完成所有受檢者符合其個人的健康檢查作業，並且達到最小化醫師和受檢者的檢查時間及等待時間。
為了找出最佳化的排程結果，一般會採行整數線性規劃模型來求取最佳解，但由於所有的變數皆為0、1變數，以及隨著整數線性規劃模型的變數和限制式數量成長，求解的困難性、複雜度也隨之增加，往往會耗費大量時間和系統資源來求解，甚至仍會出現無解的結果，因此在整數線性規劃模型之外，本研究提供啟發性演算法的方式來解決健康檢查作業排程的問題。
本研究分為兩大方向建構出啟發性演算法：以受檢者為基礎與以醫師為基礎；雖然提出兩套演算法，但仍有採用部分相同的演算法作為排程的準備，包含受檢者、檢查項目的分組排序。排程演算法採取以受檢者為基礎的主要作法為，自受檢者開始檢查的時間之後，受檢者一有空閒就排進可行的檢查項目，除非所有未被規劃的檢查項目皆無法滿足限制條件，受檢者才會出現等待時間。而以醫師為基礎排程的作法就改以醫師為考量對象，改自該名醫師開始檢查後，緊密時間裡規劃出下一位受檢者，只有在缺乏符合條件的受檢者時，醫師才會有等待時間出現。此外無論是採用何種排程演算法，隨時都需要檢查前置檢查項目、資源限制、連續檢查等限制，以及確保每組組內受檢者皆為同一時間點開始進行檢查。因此本研究的啟發性演算法可以達到最小化醫師和受檢者的檢查時間及等待時間的目標，實務上也能運用在不同的環境中。

關鍵字

啟發性演算法 ； 健康檢查 ； 排程

並列摘要

This study focused on the model of the scheduling in health examination, and develops a model which completes all patients’ health examination with their own requirements under the constraints of time, resources and other particular limits like the sequence, continuing time of examination to the objective of minimizing the total examination and waiting time counting by examinees and doctors.
For the optimizing solution of scheduling, formulate an integer linear programming model to gain the best solution. But in this integer linear programming model according to the scheduling in health examination, all the variables are binary variables. With the growing numbers of the variables and constraints followed by the increasing parameter, the difficulty and complexity are getting greater. Solving an integer linear programming model especially spends much more time and system resources, even results to infeasible solutions. Therefore, this study proposes the method of heuristic algorithm.
This study proposes two kinds of the heuristic algorithms solving the scheduling in health examination, the examinee based and the doctor based. Although there are two heuristic algorithms based on different targets, both apply for some common steps for the preparation of scheduling. The same parts of the two algorithms are the sort of examinees and operations, and the way to divide the examinees and operations into group. In the algorithm, based on the examinee, the main solution for scheduling is try to plan any operation for one examinee since he has started without any break. Unless all the unplanned operations are dissatisfied the constraints, the examinee must wait in this case. However, according to solution of the doctor based algorithm in scheduling, the considering subject becomes doctors instead of examinees. The method arranges any feasible examinees for doctors as possible in a period of time. Under the only condition of searching out no feasible examinee, the doctor would wait. Whatever applying for any scheduling algorithm, it still check the sequence of operations, resource constraints, continuing working limit, etc. and make sure all the examinees in one group start to accept examination at the same time. Therefore, the heuristic algorithms this study proposed would achieve the objective of minimizing the total examination and waiting time counting by examinees and doctors. In practice, these algorithms could actually used in different environment.

並列關鍵字

Heuristic Algorithm ； Health Examination ； Scheduling

參考文獻

5. Bistline, Sr. W.G., S. Banerjee, and A. Banerjee, “RTSS: An Interactive Decision Support System for Solving Real Time Scheduling Problems Considering Customer and Job Priorities with Schedule Interruptions,” Computers & Operations Research, Vol. 25, No. 11, 1998, pp. 981—995.

6. Brah, S.A., and L.L. Loo, “Theory and Methodology: Heuristics for Scheduling in a Flow Shop with Multiple Processors,” European Journal of Operational Research 113, 1999, pp. 113—122

9. Hall, L.A., “Approximability of Flow Shop Scheduling,” Mathematical Planning 82, 1998, pp. 175—19

10. Marinagi, C.C., “Knowledge Representation and Reasoning in Planning and Scheduling Environment,” PhD Thesis, Athens, Greek, 1999

11. Marinagi, C.C., C.D. Spyropoulos, C. Papatheodorou, and S. Kokkotos, “Continual Planning and Scheduling for Managing Patient Tests in Hospital Laboratories,” Artificial Intelligence in Medicine, Vol.20, 2000, pp. 139—154