用随机键算法优化手术室调度,提升资源利用率与排程灵活性。
Random-Key Algorithms for Optimizing Integrated Operating Room Scheduling
- 将调度问题映射到连续空间,通过解码器转换为实际排程方案。
- 在真实场景数据上显著降低等待时间,首次证明某案例最优解。
- 适合医院管理者与运筹优化研究者参考,解决多约束复杂排程问题。
高效手术室调度对医院效率、患者满意度和资源利用至关重要。本文提出一种新型随机键优化器(RKO),在文献实例与新生成的真实场景实例上进行严格测试。该组合优化问题涵盖多手术室调度、设备分配及房间、患者、医生的复杂可用性约束,支持动态重排与运营弹性。RKO将解表示为连续空间中的点,通过确定性解码函数映射至问题解空间,使元启发式算法在随机键空间中运行而无需了解原始解空间结构。设计了基于Q-学习的有偏随机键遗传算法、模拟退火与迭代局部搜索,统一使用单一解码函数。所提方法结合下界构造,可评估启发式结果的最优性差距。实验表明,对文献实例的上下界均有显著改进,尤其首次证明一例为最优解;对新引入实例,即使在高度约束条件下也能高效生成可行调度。本研究为优化手术室排程提供实用方案,有助于提升资源分配效率、缩短患者等待时间、增强整体运营效能。
原文摘要 · Abstract (English)
Efficient surgery room scheduling is essential for hospital efficiency, patient satisfaction, and resource utilization. This study addresses this challenge by introducing a novel concept of Random-Key Optimizer (RKO), rigorously tested on literature and new, real-world inspired instances. Our combinatorial optimization problem incorporates multi-room scheduling, equipment scheduling, and complex availability constraints for rooms, patients, and surgeons, facilitating rescheduling and enhancing operational flexibility. The RKO approach represents solutions as points in a continuous space, which are then mapped in the problem solution space via a deterministic function known as a decoder. The core idea is to operate metaheuristics and heuristics in the random-key space, unaware of the original solution space. We design the Biased Random-Key Genetic Algorithm with $Q$-Learning, Simulated Annealing, and Iterated Local Search for use within an RKO framework, employing a single decoder function. The proposed metaheuristics are complemented by lower-bound formulations, providing optimal gaps for evaluating the effectiveness of the heuristic results. Our results demonstrate significant lower and upper bounds improvements for the literature instances, notably proving one optimal result. Furthermore, the best-proposed metaheuristic efficiently generates schedules for the newly introduced instances, even in highly constrained scenarios. This research offers valuable insights and practical solutions for improving surgery scheduling processes, offering tangible benefits to hospitals by optimising resource allocation, reducing patient wait times, and enhancing overall operational efficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。