Improving Patient Schedules by Multi-agent Pareto Appointment Exchanging

We present a dynamic and distributed approach to the hospital patient scheduling problem: the multi-agent Pareto-improvement appointment exchanging algorithm, MPAEX. It respects the decentralization of scheduling authorities and is capable of continuously adjusting the different patient schedules in response to the dynamic environment. We present models of the hospital patient scheduling problem in terms of the ``health care cycle'' where a doctor repeatedly orders sets of activities (partial plans) to diagnose and/or treat a patient. We introduce the Theil index to the health care domain to characterize different hospital patient scheduling problems in terms of the degree of relative workload inequality between required resources. In experiments that simulate a broad range of stylized hospital patient scheduling problems, we extensively compare the performance of MPAEX to a set of heuristics. The distributed and dynamic MPAEX has performances almost as good as the best centralized and static scheduling heuristics.