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

摘要：

核磁共振检查（MRI）是现代医学影像诊断的重要手段之一。MRI设备在扫描不同部位时会产生转换成本，为同时提高设备利用率和患者满意度，建立了马尔可夫决策过程模型，以最小化医院的长期成本。该模型是首个对MRI设备转换成本和患者日间等候成本进行权衡的优化模型。通过策略迭代算法可得到该模型的最优调度。为降低计算复杂度，设计了基于单日规则、开放获取规则和短视规则的多项式时间算法。除此之外，通过忽略容量约束，提出了分解算法，在MRI设备检查能力紧张或充足时，其表现与最优解接近。通过对比上海某大型综合医院的实际排程，验证了上述算法能够在检查能力、患者拒绝比例、患者平均等待天数、日平均检查类型数等指标上取得显著改善。

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