关键词: 医疗卫生, 预约调度, 马尔可夫决策过程, 组合优化, 近似算法

Abstract:

Magnetic resonance imaging (MRI) is one of the important methods of modern medical imaging diagnosis. MRI equipment will incur changeover costs when scanning different organs. To improve the utilization rate of the equipment and the satisfaction of patients, a Markov decision process model was established to minimize the long-term cost. This optimization model is the first one to weight the changeover cost and the inter-day waiting cost of patients. The optimal schedule can be obtained by using the policy iteration algorithm. To reduce the computational complexity, a polynomial time algorithm based on single day policy, open access policy and myopic policy is designed. In addition, by ignoring the capacity constraint, a decomposition algorithm is proposed, and the performance is close to the optimal solution when the inspection capacity is tight or sufficient. By comparing the actual scheduling of a general hospital in Shanghai, the above algorithms is verified to achieve significant improvements in terms of examination capacity, rejection rate, average waiting, and average number of daily examination types.

Key words: healthcare, appointment scheduling, Markov decision process, combination optimization, approximation algorithm