Decentralized online scheduling of combination-appointments in hospitals

We consider the online problem of scheduling combination appointments for outpatients. Scheduling multiple appointments on a single day is high on the list of outpatient preferences. It is hard to achieve for two reasons: first, due to the typical distributed authority in hospitals, scheduling combination appointments requires coordination between departments. Second, there is a trade-off between local scheduling efficiency and the fulfillment of patient scheduling preferences. We present a multi-agent approach, where patient agents coordinate with department agents. For individual departments, we design an efficient yet flexible local scheduling method with dynamic usage of capacity. Department agents use this method and use its flexibility to trade-off local efficiency against making single day combination appointments. We show in a stylized model of a real hospital setting that this multi-agent scheduling approach is highly effective and allows a hospital to set a desired level of efficiency versus fulfilled patient preferences.