Competitive Algorithms for the Online Minimum Peak Job Scheduling
受癌症输液中心预约调度启发，提出实时在线算法最小化资源峰值需求，理论证明其性能接近全知算法，为医疗等场景提供高效调度策略。
Algorithms to schedule medical appointments This paper was inspired by a field collaboration effort to develop and disseminate a real-time appointment scheduling decision support tool for an outpatient cancer infusion center in a large healthcare system. Two challenging aspects of scheduling daily medical appointments are that each patient is scheduled upon arrival without knowledge on future patients and that the appointments typically consume scarce physical resources (e.g., chairs, nurses, and doctors). A desirable schedule should have relatively smooth utilization over the course of a day to minimize the peak demand for the scarce resources. This paper develops new real-time (online) algorithms to schedule appointments in medical and other settings. It establishes theoretical properties of these algorithms, showing that they perform close to algorithms that could exploit full retrospective information on all the appointments. Additionally, it provides important insights to guide efficient real-time appointment scheduling policies in practice.