关键词: 预约调度, 调度策略, 马尔科夫决策过程, 门诊患者

Abstract: Timely examinations are important for patients to be properly diagnosed and treated. Different urgency levels of patients, different requirement of examinations, and patients’ behaviors, for example, no-shows, make patient scheduling difficult to solve. To deal with this problem, this paper starts from two different examinations, two urgency levels, patients’ no-shows and physicians’ overtime, and proposes a discount-cost Markov Decision Process(MDP) with the objective to maximize the expected revenue from examining patients and minimize the overtime penalty. Due to the complexity of the MDP model, it is difficult to analyze structural properties of the optimal control policies. Therefore, numerical results of MDP are solved. Based on the observed structural properties of the numerical optimal control policies, this paper proposes two parameterized heuristics for patient scheduling, where the parameters are improved by using Genetic Algorithm. Numerical experiments compare the optimal control policy, the two heuristics, and the First-Come-First-Serve(FCFS)rule. The numerical results show that the performance of the proposed heuristics is within 10% of deviation from the optimal control policy. When the workload of the system is high, the proposed heuristics are much better than FCFS.

Key words: appointment scheduling, scheduling policies, markov decision process, outpatients