A hybrid and scalable multi-agent approach for patient scheduling based on Petri net models

Scheduling patients in a hospital is a challenging issue due to distributed organizational structure, dynamic medical workflows, variability of resources and the computational complexity involved. It calls for a sustainable architecture and a flexible scheduling scheme that can dynamically allocate available resources to promptly react to patients in a hospital and deliver healthcare services timely. The objectives of this paper are to propose a viable and systematic approach to develop a scalable and sustainable scheduling system based on multi-agent system (MAS) to shorten patient stay in a hospital and plan schedules based on the medical workflows and available resources. To develop a patient scheduling system, we combine MAS architecture, contract net protocol (CNP), workflow specification models based on Petri nets and the cooperative distributed problem solving concept. To achieve interoperability and sustainability, Petri Net Markup Language (PNML) and XML are used to specify precedence constraints of operations in medical workflows and capabilities of resource agents, respectively. Agent communication language (ACL) and CNP are used to achieve communication and negotiation/mutual selection of agents. A collaborative algorithm is invoked by individual agents to optimize the schedules locally based on a problem formulation automatically obtained by Petri net models. We have developed a scheduling system based on a FIPA compliant MAS platform to solve the dynamic patient scheduling problem. To illustrate the benefit of our approach, we compare the performance of our method with a heuristic rule commonly used in practice. In addition, we also analyze and verify scalability of our approach by experiments.