1 Introduction

The distributed organizational structure, costly infrastructure, diversity of medical processes, decreasing budget in public health insurances and the need for prompt response to patients pose challenges in management of hospitals. These challenges call for the development of an effective methodology to reduce time and cost and provide quality services based on a flexible distributed organizational architecture. The issues in hospitals range from allocation of resources, scheduling of patients to delivery of healthcare services. In existing literature, there are several studies on planning and scheduling in hospitals [1,2,3,4,5]. For example, Decker and Jinjiang propose a multi-agent solution using the Generalized Partial Global Planning (GPGP) approach that preserves the existing human organization and authority structures, while providing better system-level performance (increased hospital unit throughput) [1]. Kutanoglu and Wu investigate a new method based on a distributed and locally autonomous decision structure using the notion of combinatorial auction [2]. Oddi and Cesta explore constraint-based scheduling techniques and implement a mixed-initiative problem solving approach in order to achieve satisfactory solutions to the problem of managing medical resources in a hospital environment [3]. Daknou, Zgaya, Hammadi and Hubert focus on treatment scheduling for patients at emergency department in hospitals [4] based on multi-agent systems (MAS). Marinagi et al. consider patients as the entities that evaluate hospital services to achieve quality services [18].

Among the research issues mentioned above, how to properly handle patients timely under resource constraints to reduce risk is an essential one. In a hospital, an urgent patient often needs to be handled properly by a time constraint. It is critical to determine whether the medical procedure of a patient can be completed by a time constraint based on the available resources in hospitals. The problem to determine whether a single patient can be handled by a time constraint can be stated as a constraint satisfaction problem (CSP) [9, 17] in existing artificial intelligence (AI) literature whereas the problem to determine whether multiple patients can be handled by a time constraint can be described as a patient scheduling problem. Scheduling patients in a hospital is a challenging problem due to computational complexity involved, distributed resources and dynamic changing environment. Our interest is to propose a viable approach to develop a scalable and sustainable software system for scheduling patients. Given a set of requests from patients in a hospital, the problem is to find schedules that handle patients’ requests timely. The objective is to propose a scalable and dynamic scheme to shorten patient stay in hospital under resource constraints and precedence constraints of medical workflows.

In AI, MAS provides a flexible architecture to model operations and dynamically allocate resources in a hospital to handle patients [6, 7]. Entities and resources in a hospital such as doctors, staffs, specialists and nurses can all be modeled as agents. The key issue is how to make these agents work together coherently to handle patients timely. Although MAS provides a flexible architecture to capture the characteristics of entities in medical information systems, how to develop a patient scheduling algorithm that can be applied by individual agents to generate coherent schedules for health care workers to handle patients timely is an important issue.

In this paper we exploit recent advancement in MAS, scheduling theory and information technologies to propose a framework for scheduling patients and develop a scalable, sustainable and flexible solution methodology by extending the preliminary results presented in [33]. To develop a solution methodology, the concept of cooperative distributed problem solving (CDPS) [8], formal temporal models [13, 15], optimization theory [19] and negotiation mechanism [14] are adopted in this study to make agents work together to schedule patients timely. To propose a pragmatic methodology for solving the patient scheduling problem in MAS, a proper architecture and suitable models must be selected to capture the operations, interaction and workflows of agents. In our architecture, the workflow to be performed by an agent is represented by a workflow agent and each resource is modeled by a resource agent. To make these agents work together coherently to handle patients, a negotiation mechanism is used. In MAS, a well known protocol for coordination and negotiation is the contract net protocol (CNP) [14], which defines procedures such as task announcement, bidding mechanism, contract awarding and negotiation [20]. There are a lot of works on distributing tasks in MAS with CNP [21,22,23,24,25]. We focus on how agent technology can be further developed to support collaborative scheduling.

As we use the contract net protocol as the negotiation protocol, messages such as Call for Proposal, Proposals and Request sent and processed by agents must be specified by a structured format that can be easily parsed and interpreted by agents. Extensible Markup Language (XML) is a markup language that defines a set of rules for encoding structured data in a human-readable and machine-readable format. Furthermore, as we develop the proposed system based on Java programming language, there are several application programming interfaces (APIs) available for processing XML data. Therefore, while Ontology is a standard content format supported in FIPA, we adopt Extensible Markup Language (XML) as the format for the messages exchanged between agents. Using XML as a data exchange format also facilitates interactions with other information systems such as HL7.

Our approach is different from these existing ones in that we introduce timed Petri net models in workflow agents and resource agents. Petri net is a graphical formal model for modeling and analysis of workflows [26,27,28]. The Petri Net Markup Language (PNML) [29] is an XML-based interchange standard for representing Petri nets. Many Petri net tools support PNML format, e.g. WoPeD, Renew, PNK, PEP, VIPtool) [30]. Therefore, PNML is used as the format for representing the Petri net models of agents in the system. To endow each agent with the knowledge and capability to perform operations in workflows, we construct the timed Petri net (TPN) model [15] for each workflow agent and resource agent. Our solution methodology combines MAS architecture with Petri net models. To formulate the optimization problem for a workflow agent, we first obtain the parameters from the corresponding timed Petri net models. Due to the dependency of workflows between agents in MAS, the workflow scheduling problem can be decomposed into a number of interrelated workflow scheduling subproblems that are solved by individual agents. The scheduling algorithm is developed by applying optimization theories based on minimum cost network flow problem formulation [19].

In our system, we define four types of agents, including workflow agents, resource agents, patient agents and scheduling agents. We construct models for workflow agents and resource agents. A medical workflow usually involves a complex process described by a workflow. To facilitate optimization of patient schedule, we adopt timed Petri nets (TPN) [13] as the modeling tool in this paper instead of using informal workflow specification languages such as XPDL [10], BPMN [11] and WS-BPEL [12]. We propose a scheduling method based on interactions between patient agents, workflow agents and resource agents using contract net protocol (CNP) [14] to efficiently allocate resources. We develop a problem solver based on Java Agent Development Environment (JADE) to verify our method. We illustrate effectiveness and scalability of our approach by examples. To illustrate the benefit of our approach, we compare the performance of our method with a heuristic rule commonly used in practice. In hospitals, the rule of first-come first-serve (FCFS) has been widely adopted and used in practice. An interesting issue is to compare the performance of our approach with that of the FCFS rule for handling patients. In this paper, we will demonstrate the benefit of our approach by examples. In addition, we also analyze and demonstrate scalability of our approach by experiments.

The remainder of this paper is organized as follows. In Section 2, we review related works. In Section 3, we describe the patient scheduling problem and our approach. In Section 4, we introduce the TPN models for agents. In Section 5, we formulate the scheduling problem based on the construction of network models obtained from TPN models and develop solution algorithms for it. We present our prototype system implementation and examples in Section 6. In Section 7, we analyze scalability of our approach and present the results. We conclude this paper in Section 8.

2 Related works

In practice, hospitals and healthcare service providers usually use a clinical guideline to guide decisions regarding diagnosis, management, and treatment in a specific of healthcare area [37, 38, 41]. In the existing literature, Fox et al. pointed out that existing clinical guideline suffer from several drawbacks such as inaccessibility of guidance at the point of care, ambiguity and inapplicability in local settings [39]. They turned their attention from clinical guidelines to decision support services and developed tools to author, edit, publish and maintain process for active decision support and guideline services in the OpenClinical project (www.openclinical.net). In [40], Kaiser and Marcos found that modeling of clinical practice guidelines is a labor-intensive task even with tool assistance. They facilitated the clinical practice guidelines modeling task based on a set of procedural patterns described in an implementation-independent notation in BPMN 2.0 that can be then semi-automatically transformed into one of the alternative executable clinical practice guideline languages. However, BPMN 2.0 lack formal analysis method and it is not a suitable model for analyzing, formulating and solving scheduling problems. Therefore, we adopt Petri nets as the tools to model workflows and schedule patients in hospitals. A wide variety of free open source editing software tools are available. Users only need to create graphical workflow and resource models in Petri net for entities in hospitals and specify the relevant data in our approach. Our model transformation component will formulate and solve the scheduling problem behind the scenes.

The essence of our model transformation approach is inspired by the concept of model driven development (MDD) [47, 48], which has been widely adopted in software development by expressing models less bound to the underlying implementation technology and closer to the problem domain. The benefits of MDD include reducing the barrier and learning time for users by using graphical standardized platform independent models to enhance efficiency of communication and accommodate changes. In our approach, we use Petri nets as the platform independent models to specify the models for the scheduling problem. As our approach is based on MDD, our approach enjoys some of the benefits of the MDD approach. In practice, workers of hospitals are usually not familiar with optimization theory. Application of optimization theory to patient scheduling problem requires some background on the mathematical modeling for the problem. Therefore, it is very difficult for workers of hospitals to apply software tools that are based on optimization theory. Our approach reduces the barrier and learning time for users not familiar with optimization theory by using a graphical workflow model based on Petri nets.

The patient scheduling problem considered in this paper and our approach to scheduling patients are different from those reported in [16, 34,35,36]. The appointment scheduling of outpatient surgeries in a multistage operating room department with stochastic service times serving multiple patient types has been addressed in [34]. In [35], the authors formulated and solved a discounted infinite-horizon Markov decision process for scheduling cancer treatments in radiation therapy units. The goal of [36] is to propose and solve a new formulation of the recently-formalized patient admission scheduling problem by a meta-heuristic approach. In [16], the author proposed a hierarchical goal programming (HGP) model for scheduling the outpatient clinics. This paper is also different from our previous works [31]. Paper [31] demonstrates the capabilities of PNML in the development of context-aware applications instead of an industrial interchange format only. However, Papers [31] does not address the scheduling problem in MAS.

There are many papers and several frameworks that apply agent technology in hospitals or healthcare systems. For example, Agent.Hospital [43, 44] is an open agent-based framework for distributed applications in the healthcare domain. A review of the most recent literature of applications of agents in healthcare is discussed in [42], which indicates a growing interest of researchers in the development of agent based applications in healthcare systems. This paper is also based on agent technology. Each agent in our system is an autonomous, co-operative and intelligent entity able to collaborate with other agents in handling patients. This paper is different from papers [45, 46], which also use agents in scheduling hospitals. The problem studied in this paper is to shorten patient stay in a hospital and is different from the problem setting of [45], which presents an agent based model for the selection of optimal mix for patient admissions in hospitals. In [46], patients and hospital resources are modeled as agents with individual goals that negotiate to find appropriate solutions without applying optimization theory. This paper is different from [46] in that we combine the distributed architecture of multi-agent systems with optimization theory to attain the benefits of improving performance in distributed environment with decision autonomy and flexibility of agents.

3 Patient scheduling problem and the proposed approach

Patients in a hospital are handled by following medical procedures. A medical procedure abstracts the workflows and operations in a hospital. A typical medical procedure may consist of a number of steps such as registration, diagnosis, radiology test, blood examination, anesthesia, surgery, intensive and discharge, etc. Different steps throughout the lifecycle of a medical procedure usually require distinct resources for processing. In practice, these steps may be performed by different hospital workers or resources such as doctor, staff, specialist and nurse. Due to the complexity of the operations performed and the distributed information and resources, medical workflows in a hospital require considerable coordination of resources. How to effectively manage the concurrent workflows in the system is a challenge. We are mainly concerned with the management of related resources for effective enactment of these steps. The patient scheduling problem is to find schedules that allocate resources over the scheduling horizon to minimize earliness/lateness in handling patients while satisfying all the precedence constraints and resource constraints associated with the workflows. In this paper, we will propose a scheduling system based on MAS to determine the schedules to handle patients timely based on the available resources in a hospital. In this section, we focus on the architecture for solving patient scheduling problem. Formal problem formulation will be described in Section 4 based on the models of medical workflows and activities described in Section 3.

Our approach to scheduling patients is based on collaboration of agents in the system. Figure 1(a) shows our architecture for solving the patient scheduling problem. There are four types of agents, including patient agents, medical workflow agents, resource agents and scheduling agents. A patient is represented by an agent called patient agent. Doctors, staffs, specialists and nurses and other workers in a hospital are modeled by resource agents. The medical procedure for a patient usually consists of a sequence of medical workflow agents. A scheduling agent implements the algorithm to optimize schedules. The last medical workflow agent in a medical procedure is called the target medical workflow agent. The request from a patient agent propagates from the patient agent to its target medical workflow agent progressively until it reaches the first medical workflow agent at the upstream in the medical procedure. For example, consider a medical procedure with three medical workflow agents: radiology agent, anesthesia agent and surgery agent. For this example, the target medical workflow agent for the patient agent is the surgery agent. Therefore, the scheduling request will propagate from the patient agent to the surgery agent and then the anesthesia agent and finally the radiology test agent. Each medical workflow agent applies a scheduling algorithm by interacting with the scheduling agent and relevant resource agents. If a schedule can be found, the medical workflow agent will issue a request to its upstream medical workflow agent next. The processes will continue until the scheduling request reaches the first medical workflow agent at the upstream in the medical procedure. Figure 1(b) illustrates the scheduling requests and responses sent between a patient agent and the relevant upstream medical workflow agents.

Fig. 1
figure 1

(a) Architecture to schedule medical workflows in health care systems. (b) Scheduling requests and responses sent between a patient agent and the relevant upstream medical workflow agents

Full size image

The interaction between a patient, the relevant medical workflow agents, resource agents and scheduling agent can be specified by a sequence diagram in Unified Modeling Language (UML). Let PA be a patient agent. Let MA1, MA2 and MA3 denote three medical workflow agents, including surgery agent, anesthesia agent and radiology test agent, in the medical procedure and RA1, RA2 and RA3 be three different resource agents that can perform the operations of MA1, MA2 and MA3, respectively. Figure 2(a) shows the UML sequence diagram of PA, MA1, MA2, MA3, RA1, RA2 and RA3.

Fig. 2
figure 2

(a) A sequence diagram for scheduling patients based on collaboration of agents CFP: Call for proposals AOC: Awarding of contracts. EOC: Establishment of contracts. (b) Internal structure of a medical workflow agent. (c) Internal structure of a resource agent. (d) Internal structure of a scheduling agent

Full size image

As the function of patient agents is to provide graphical user interface (GUI) for users to specify and issue the scheduling requests, we only briefly describe the internal structure of medical workflow agents, resource agents and scheduling agents in Fig. 2(b), (c) and (d), respectively. With the exception of scheduling agents, each agent provides a GUI for users to interact with other agents in the system. The service discovery module facilitates the processes to discover the services provided by other agents. A medical workflow agent consists of a GUI to describe relevant workflow information. Figure 2(b) shows the internal structure of a medical workflow agent. The properties of a medical workflow agent are described by an XML file (Workflow.xml). Table 7 in Appendix I shows an example of Workflow.xml used in our system. The medical workflow model is described by a timed Petri net model., which will be described in the nest section. A medical workflow agent needs to discover and interact with other agents. A request from a patient agent is represented in XML format. Table 8 in Appendix I shows a patient request example in our system. On receiving a request from a patient agent, a medical workflow agent will parse the patient request to extract the medical workflow type and the deadline for handling the patient.

Figure 2(c) shows the internal structure of a resource agent. The capability of a resource agent is defined by a GUI and is described by an XML (Resource.xml) file. Table 9 in Appendix I shows an example of Resource.xml used in our system. The activities in the medical workflow to be performed by resource agents are also represented by timed Petri net models, which will be defined in the next section. Figure 2(d) shows the internal structure of a scheduling agent. A scheduling agent is invoked by a medical workflow agent when a patient request is received. Based on timed Petri net models, a scheduling agent constructs a network model and combines it with a subgradient algorithm to optimize the schedules. The timed Petri net models will be defined in Section 4 and the network model will be introduced in Section 5.

4 TPN models for medical workflows and activities

In a hospital, operation of one worker may depend on or influence the operations of other ones. The scheduling problem is dynamic and subject to several constraints. To deal with the dynamic scheduling problems in a hospital, one strategy is to develop a software agent that elicits the scheduling problem based on well-known process specification languages or models to automate the scheduling problem formulation. In this way, users do not need to get acquainted with mathematical optimization theories to use our tools to schedule operations. Petri nets have been widely adopted as a tool for modeling processes in industry [15]. The medical procedures in a hospital usually form complex workflows which may involve synchronous/asynchronous/concurrent workflows and activities that can be modeled by Petri nets. Therefore, we adopt timed Petri net (TPN) [15] in this paper to model the medical workflows and activities performed by agents and use PNML format to represent the model.

A TPN [15] G is a five-tuple G = (P, T, F, μ, m 0), where P is a finite set of places, T is a finite set of transitions, \(F\subseteq (P\times T)\cup (T \times P)\) is the flow relation, μ : T → Z +) is a mapping that specifies the discrete firing time for each transition, where Z + is the set of nonnegative integer numbers, and m 0 : P → Z |P| is the initial marking of the PN with Z as the set of nonnegative integers. A Petri net with initial marking m 0 is denoted by G(m 0). A marking of G is a vector m ∈ Z |P| that indicates the number of tokens in each place under a state. • t denotes the set of input places of transition t. A transitiont is enabled and can be fired under m iff m(p) ≥ F(p, t)∀p∈• t. • p denotes the set of input transitions of place p and p • denotes the set of output transitions of place p. In a TPN, each transition is associated with a firing time. Firing a transition removes one token from each of its input places and adds one token to each of its output places. A marking \({m}^{\prime }\) is reachable from m if there exists a firing sequence s bringing m to \({m}^{\prime }\). A TPN G = (P, T, F, μ, m 0) is live if, no matter what marking has been reached from m 0, it is possible to ultimately fire any transition of G by progressing through some further firing sequence.

To model a medical workflow as a TPN, we use a place to denote a state in the workflow while a transition denotes an operation. A Petri net is called a marked graph [15] if it is an ordinary Petri net such that each place p has exactly one input transition and exactly one output transition, i.e., |• p| = |p •| = 1 for all p ∈ P. A medical workflow is modeled by a subclass of Petri nets that is very similar to marked graphs. We call this subclass class of Petri nets an acyclic sequential timed marked graph (ASTMG) as follows.

Definition 4.1

A timed marked graph \(TSMG{W}^{\prime }_{n} \!\!\,=\, ({P}^{\prime }_{n} ,{T}^{\prime }_{n} ,{F}^{\prime }_{n} ,{\mu }^{\prime }_{n} ,{m}^{\prime }_{n0})\) is called a sequential timed marked graph if each transition in \({T}^{\prime }_{n} \) has only one input place and one output place.

Definition 4.2

A transition in \({T}^{\prime }_{n} \) without any input place is called a terminal input transition. A transition in \({T}^{\prime }_{n} \) without output place is called a terminal output transition.

Definition 4.3

An acyclic sequential timed marked graph (ASTMG) W n = (P n , T n , F n , μ n , m n0) is obtained by augmenting \({W}^{\prime }_{n} = ({P}^{\prime }_{n} ,{T}^{\prime }_{n} ,{F}^{\prime }_{n} ,{\mu }^{\prime }_{n} ,{m}^{\prime }_{n0})\) with an input place ε n and a service output place 𝜃 n and adding an arc connecting ε n to the terminal input transition of \({W}^{\prime }_{n}\) and adding an arc connecting the terminal output transition to 𝜃 n .

Definition 4.4

The model of a medical workflow agent w n is an ASTMG W n = (P n , T n , F n , μ n , m n0).

Figure 3(a) shows the Petri net models of three medical workflows w 1 through w 3. Note that the individual medical workflow model for each step has one start state, several processing state and one finished state. For example, the workflow Petri net model w 1 for Step 1 consists of one start state (p 1), one busy state (p 2) and one finished state (p 3).

Fig. 3
figure 3

(a) ASTMG models of workflow agents w 1 ∼ w 3. (b) A medical workflow model obtained by merging the models of agents w 1∼w 3

Full size image

To handle a patient, the Petri net models of multiple workflow agents can be merged to construct a complete medical workflow We define the operator “ |” to merge multiple Petri nets through service input place and service output place or common places, transitions, or arcs.

Definition 4.5

Given two Petri nets G 1 = (P 1, T 1, W 1, m 10) and G 2 = (P 2, T 2, W 2, m 20), G 1|G 2 = (P, T, W, m 0), where \(P=P_{1} \cup P_{2}\), \(T=T_{1} \cup T_{2}\), \(W(p,t)\,=\,\left \{ {\begin {array}{l} W_{1} (p,t)\;if\;p\in P_{1} \;and\;t\in T_{1} \\ W_{2} (p,t)\;if\;p\in P_{2} \;and\;t\in T_{2} \; \\ \end {array}} \right .\), \(W(t,p)\,=\,\left \{ {\begin {array}{l} W_{1} (t,p)\;if\;p\in P_{1} \;and\;t\in T_{1} \\ W_{2} (t,p)\;if\;p\in P_{2} \;and\;t\in T_{2} \; \\ \end {array}} \right .\), and \(m_{0} (p)=\left \{ {\begin {array}{l} m_{10} (p)\;if\;p\in P_{1} \\ m_{20} (p)\;if\;p\in P_{2} \\ \end {array}} \right .\).

Definition 4.6

Let S denote the set of workflow agents required to construct a complete medical workflow. CW = | n∈S W n .

By applying the operator “ |” to the workflow models of w 1 ∼ w 3, we can construct a complete medical workflow in Fig. 3(b).

An activity is a sequence of operations to be performed by a certain type of resources. The Petri net model for the k − th activity of resource r is described by a Petri net \({{\Gamma }_{r}^{k}}\) that starts and ends with the resource idle state place p r as follows.

Definition 4.7

Petri net \({{\Gamma }_{r}^{k}} ({m_{r}^{k}} )= ({P_{r}^{k}} ,{T_{r}^{k}} ,{F_{r}^{k}} ,{\mu _{r}^{k}} ,{m_{r}^{k}})\) denotes the k − th activity of resource r. There is no common transition between \({{\Gamma }_{r}^{k}}\) and \({\Gamma }_{r}^{{k}^{\prime }}\) for \(k\ne k^{\prime }\). The initial marking \({m_{r}^{k}} (p_{r} )=1\) and \({m_{r}^{k}} (p)=0\) for each \({P_{r}^{k}} \setminus \{p_{r} \}\), where p r is the idle state place of resource r.

Figure 4 illustrates a resource activity associated with the work flow w 1 in Fig. 3(a). To solve the dynamic scheduling problem, a problem formulation based on the proposed Petri net models will be detailed in the next section.

Fig. 4
figure 4

Specification of a resource activity by a Petri net

Full size image

5 Scheduling problem formulation and our solution approach

Although Petri net models can be used to represent the workflows and activities in medical procedures, it is hard to optimize the schedules using Petri nets. In our approach, we develop a method to transform the proposed discrete timed Petri nets to a network that can capture the flow of tokens (representing patients and resources) at different time points in different states. We formulate and solve the patient scheduling problem based on the network constructed. To formulate the optimization problem, we first obtain the parameters from the corresponding discrete timed Petri net models. The constraints of the optimization problem are then represented by a network to facilitate the development of our solution algorithm. Formally, the scheduling problem for each workflow agent is formulated based on the following notation.

\(\boldsymbol {WA}= \left \{ 1, 2, 3, \ldots , N \right \}:\) :

The set of workflow agents in the system.

N = |W A| ::

The number of workflow agents in the system.

\(\boldsymbol {PA}= \left \{1, 2, 3, \ldots , {\Pi } \right \}:\) :

The set of patient agents in the system.

π::

π = |P A|, the number of patient agents.

W n ::

The workflow model of workflow agent n ∈W A.

Kn ::

The number of different resource activities in W n .

\({\Gamma }_{r}^{k} :\!\!\) :

The k-th resource activity in W n , \(k\in \left \{ \text {1, 2}, {\ldots } , \text {K}_{\text {n}} \right \}\). Suppose the k-th resource activity in W n is performed by resource agent r k .

π nk ::

The processing time of the k-th resource activity \({\Gamma }_{r}^{k} \) in W n with \(\pi _{nk} ={\mu _{r}^{k}} ({t_{s}^{k}} )+\mu _{r}^{k} ({t_{e}^{k}} )\), where \({t_{s}^{k}} \) and \({t_{e}^{k}} \) denote the starting and ending transitions of the k-th activity of resource agent a r .

τ p ::

The due date of patient agent p ∈P A.

d p ::

The number of patients in the request of a patient agent p.

T ::

The total number of time periods.

t ::

A time period and \(t\in \left \{ 1, 2, 3, {\ldots } , T \right \}\).

R rt ::

The capacity of resource r at time period t, where \(R_{rt} =m_{r0}^{k} (r)\).

v pkt ::

The number of patients in the request of patient agent p that requires resource r k for processing the k-th resource activity in W n during time period t with v pkt ≥ 0 and v pkt ∈ Z +, the set of non-negative integers.

η pt ::

The number of patients in workflow W n finished during time period t; i.e., η pt = v pK n (t−π nK n ),∀p,∀t.

h pkt ::

The number of patients in the request of patient agent p waiting at for the k-th resource activity in W n at the beginning of period t, where h pkt ≥ 0 and h pkt ∈ Z +, the set of non-negative integers.

Without loss of generality, we assume different resource activities in a workflow W n are performed by different resources. For the k-th resource activity in W n , the time that elapses from a start node to the corresponding end node is equal to the processing time π nk of the k-th resource activity.

Note that the due date τ p for workflow agent w n is either set by its corresponding patient agent or its downstream workflow agents in the negotiation processes.

To timely handle a patient, we introduce an earliness/lateness penalty function ψ(t, τ p ) for patient agent p ∈P A completed at time t. Note that the earliness/lateness penalty function ψ(τ p , τ p ) satisfies the following requirements:

  1. (i)

    ψ(τ p , τ p ) = 0 and (ii) ψ(t, τ p ) ≥ 0 to handle patients just-in-time.

The patient scheduling problem is to find the schedules to allocate resource over the scheduling horizon to minimize earliness/lateness in handling patients while satisfying all the precedence constraints and resource constraints. Given a set P A of patient agents with specified requirements and a set W A of workflow agents, the patient scheduling problem is formulated as follows.

Patient Scheduling Problem (PSP n ) for Medical Workflow Agent n with model W n

$$\begin{array}{@{}rcl@{}} &&\min \sum\limits_{p=1}^{\Pi} {\sum\limits_{t=1}^{T} {\psi (t,\tau_{p} )\eta_{pt}}}\\ &&s.t.\\ &&h_{p11} =d_{p} \;\forall p \end{array} $$
(5.1)
$$\begin{array}{@{}rcl@{}} &&h_{p1(t+1)} =h_{p1t} -v_{p1t} \;\forall p,\forall t \end{array} $$
(5.2)
$$\begin{array}{@{}rcl@{}} &&h_{pk(t+1)} =h_{pkt} -v_{pkt} +v_{p(k-1)(t-\pi_{n(k-1)} )} \end{array} $$
(5.3)
$$\begin{array}{@{}rcl@{}} &&\forall p,\forall t,k\in \left\{ {\text{}2,\text{}3, {\ldots} ,\text{K}_{\mathrm{n}} } \right\}\\ &&h_{p(K_{n} +1)(t+1)} =h_{p(K_{n} +1)(t+1)} +v_{pK_{n} (t-\pi_{nk} )} \forall p,\forall t \end{array} $$
(5.4)
$$\begin{array}{@{}rcl@{}} &&\eta_{pt} =v_{pK_{n} (t-\pi_{nK_{n} } )} \;\forall p,\forall t \end{array} $$
(5.5)
$$\begin{array}{@{}rcl@{}} &&\sum\limits_{p=1}^{\Pi} {\sum\limits_{\tau =t-\pi_{nk} +1}^{t}\!\!\!\! {v_{pk\tau } } \le R_{r_{k} t} } \quad \quad \forall k\in \left\{ {\text{1},\text{2}, \ldots, \text{K}_{\mathrm{n}}} \right\},\forall t\\ \end{array} $$
(5.6)

To ensure the allocated time slots cannot exceed the overall capacities of resources, the capacity constraints defined in inequality (5.6) must be satisfied. Furthermore, the flow balance (5.1), (5.2), (5.3) and (5.4) must be satisfied.

In this paper, we combine optimization theories with multi-agent system architecture to allocate resources and perform operations of workflows. We adopt a divide and conquer approach to achieve optimization locally. Optimization is achieved by applying the Lagrangian relaxation technique to develop a solution algorithm for the dual problem of the problem PSP n . In problem PSP n , we observe that the coupling among workflows of different patients is caused by contention for resources. Based on this observation, we apply Lagrangian relaxation to relax resource capacity constraints (5.6) and form the Lagrangian function as follows:

$$\begin{array}{@{}rcl@{}} L(\lambda) &\equiv& \sum\limits_{p=1}^{\Pi}\min \sum\limits_{t-1}^{T}(\psi (t,\tau_{p} )\eta_{pt})\\ && + \sum\limits_{k=1}^{K_{n}} {\sum\limits_{t=1}^{T} \lambda_{kt}\left(\sum\limits_{\tau =t-\pi_{nk} +1}^{t} {v_{pk\tau}} -R_{r_{k} t} \right)} \qquad \qquad\qquad\qquad\qquad (5.7) \end{array} $$

s.t. constraints (5.1) ∼(5.5), where λ kt is the associated Lagrange multiplier that must be nonnegative.

Note that the flow balance equations described by constraints (5.1) ∼ (5.5) can be represented by a network flow model, which is constructed by applying our network construction algorithm.

To represent the timing of an activity, we transform the discrete timed Petri net model of a medical workflow agent to a network model. We first create a time axis. We use a sequence of nodes placed horizontally in the time axis to denote different time points of a state. To represent a token entering a start state, we create a sequence of start nodes along the time axis. To represent a token leaving an end state, we create a sequence of end nodes along the time axis. To represent the flow of tokens from one start transition to the corresponding end transition, we create a sequence of arcs connecting start nodes to end nodes. In addition, we use one source node and one sink node. In this way, the flow of token at different time periods can be represented by a network model. To penalize earliness/lateness, we assign penalty cost on the arcs that connect the end nodes to the sink node. We assign the cost of ω pt for patient p to minimize earliness/lateness. The algorithm to construct the network associated with an activity is as follows. By applying the minimum cost flow algorithm [19], the flow will follow the minimal cost path in the network.

figure b

To optimize the schedule, the cost of each arc should be assigned properly. Each arc in the network will be assigned some cost properly according to Lagrangian relaxation technique described later in this section.

The dual problem corresponding to the problem PSP n is defined as follows:

$$\underset{\lambda \ge 0}\max L(\lambda) $$

A subgradient algorithm is used in this paper to solve the above problem. Subgradient method is an iterative method for solving convex optimization problems. It can be used with a non-differentiable objective function. When the objective function is differentiable, subgradient method for unconstrained problems uses the same search direction as the method of steepest descent. Moreover, by combining the subgradient method with primal or dual decomposition techniques, it is possible to develop a distributed algorithm for a problem. The optimal Lagrange multiplier is determined by solving the dual problem \(\max \limits _{\lambda \ge 0}L(\lambda )\). Since L(λ) is not differentiable due to integrality constraints in subproblems, we adopt a simple, iterative subgradient method [32] to solve the dual problem. Our approach to finding a solution of \(\max \limits _{\lambda \ge 0} L(\lambda )\) is based on an iterative scheme for adjusting Lagrangian multipliers according to the solutions of minimum cost flow subproblems.

Let i be the iteration index. Let v i denote the optimal solution to minimum cost flow subproblems for given Lagrange multipliers λ i at iteration i. We define the subgradients of L(λ) with respect to Lagrangian multipliers λ i as follows:\(g_{kt}^{i} =\sum \limits _{p=1}^{\Pi } {\sum \limits _{\tau =t-\pi _{nr} +1}^{t} {v_{pk\tau }^{i} -R_{r_{k} t} } } , \forall k=1,{\ldots } ,K_{n} ,\forall t=1, \ldots , T\) The subgradient method proposed by Polyak [32] is adopted to update λ as follows: \(\lambda _{kt}^{i+1} =\left \{ \begin {array}{cl} \lambda _{kt}^{i} +\alpha ^{i}g_{kt}^{i} , & ~~~~~~~\text { if } \lambda _{kt}^{i} >0\text { or \, if \,}\lambda _{kt}^{i} =0\;\;\;\; \text { and }\;\;\;g_{kt}^{i} \ge 0\\ ~~~~0, & ~~~~~~~\text { if }\;\;\lambda _{kt}^{i} =0\;\;\text { and }\;\;\;g_{kt}^{i} < 0\\ \end {array} \right .\), where \(\alpha ^{i}=\frac {\beta [\bar {{L}}(\lambda ^{\ast })-L (\lambda ^{i})]}{\sum \limits _{k,t} {(g_{kt}^{i} )^{2}}}\) and \(\bar {{L}}\) is an estimate of the optimal dual cost and 0 < β < 2.

Figure 5 shows the flow chart of our algorithm. Iterative application of the subgradient algorithm will converge to an optimal dual solution (v ∗, λ ∗). It should be emphasized that Lagrangian relaxation does not guarantee the optimal solution to the underlying problem. Rather, it finds an optimal solution to a relaxation of it. Furthermore, while Lagrangian relaxation will yield the optimal objective function value for the linear relaxation of the underlying integer program, it is not guaranteed to produce a feasible solution. Thus the solution generated may not satisfy the complementary slackness conditions. In case the solution is not feasible, we must develop a heuristic algorithm to find a feasible solution. In our system, we implement a simple heuristic algorithm that removes the excessive flows from the arcs with capacity violation by setting the arc capacity to zero and reroute these flows to other part of the network based on minimum cost flow algorithm.

Fig. 5
figure 5

Flow chart of our algorithm

Full size image

6 Numerical results

We have developed a multi-agent patient scheduling system based on JADE and the methodology proposed in previous sections. In this section, we will first briefly introduce our implementation and illustrate the functions of our system. We then illustrate the effectiveness of our method by examples.

6.1 The Scheduling system

In our system, each resource in a hospital, including doctors, specialists and nurses, is modeled by a resource agent. The patients to be handled in a hospital are represented by patient agents. Our approach to schedule patients relies on interaction between patient agents, medical workflow agents, resource agents and scheduling agents. Interactions among different types of agents are based on a negotiation mechanism that extends the well-known contract net protocol (CNP) [14]. CNP relies on an infrastructure for individual agents to publish and discover their services and communicate with each other based on the ACL language defined by the FIPA international standard for agent interoperability. JADE is a middleware that facilitates the development of multi-agent systems. Each type of entities in the hospital is implemented as an agent in JADE platform. Messages exchanged by JADE agents have a format specified by the ACL language defined by the FIPA international standard for agent interoperability. One of the essential functions required for agents in the system to discover each others is directory service. To apply the CNP, an agent must be able to search for the services provided by the other agent(s). In our scheduling system, we define different service types for patient agents, workflow agents and resource agents. Each time an agent is added to the system, its services are published through the DF (Directory Facilitator) agent in JADE.

Patient agents, workflow agents and resource agents are accompanied with proper graphical user interface (GUI) for users to input and display the data. Scheduling agents, which are invoked by workflow agents, have no GUI as they work behind the scenes. Some of the screen shots of our scheduling system are shown in this section. Figure 6 illustrates the GUI for setting the requirement of a patient. Interactions of agents to schedule patients are shown in Fig. 7. The output of our scheduling software includes the schedules for executing each medical workflow and the schedules for performing the operations in medical workflows by each resource agents. Our system provides several forms of outputs to represent the solutions of a patient scheduling problem, including graphs that representing the contracts established between a resource agent for handling patients and the Gantt chart for the schedule of a resource agent. These outputs will be illustrated by an example in the next subsection.

Fig. 6
figure 6

The GUI for setting the requirement of a patient

Full size image
Fig. 7
figure 7

Interaction of agents to schedule patients

Full size image

Our system provides several forms of outputs to represent the solutions of a patient scheduling problem. Figure 8 shows the schedule for a resource agent to handle different patients’ workflows. The Gantt chart for representing the schedule of a resource agent is shown in Fig. 9. Note that all the schedules generated by our system satisfy the capacity constraints of resources and the flow balance constraints of workflows.

Fig. 8
figure 8

The schedule for a resource agent to handle different patients’ workflows

Full size image
Fig. 9
figure 9

The Gantt chart for representing the schedule of a resource agent

Full size image

To demonstrate the effectiveness of our method, we compare the schedules generated by our system with the ones generated by the rule of FCFS.

6.2 Examples

In the remainder of this section, we use an application scenario to demonstrate the practicality of our scheduling system. Suppose the requests of ten patients are received. The input data for this example are shown in Tables 1 and 2. Table 1 shows three medical workflow agents defined for this example. Each medical workflow represents a task required for handling a patient. These three medical workflows are distributed in different departments. The three medical workflow models are shown in Fig. 10. A medical workflow is described by a Petri net model represented in PNML file format. There are three types of resource agents. The activities that can be performed by the three types of resource agents are specified by Petri net models in PNML format. The properties of resource agents are listed in Table 2.

Table 1 Definition of Workflows
Full size table
Table 2 Definition of Resource Activities
Full size table
Fig. 10
figure 10

Three workflow models

Full size image

The requirements of a patient agent are specified by a due date, a medical workflow type, number of patients, and the penalty cost (earliness penalty cost and lateness penalty cost). In Taiwan, many hospitals provide on-line appointment systems for patients. These systems generate planned appointment time for each patient based on the appointment records of existing patients. Each patient then goes to the hospital according to the planned appointment time. However, the planned appointment time generated by the on-line appointment system may not be accurate. In addition, some patients may arrive at the hospital much earlier than their planned appointment time whereas other patients may arrive at the hospital only a few minutes before the planned appointment time. There exist discrepancy between the planned appointment time and the actual time the medical procedure of a patient is completed.

Table 3 shows the planned appointment time and expected finished time for ten patients. The target medical workflow type for the fourth, the fifth, the sixth and the seventh patients is type-3 medical workflow whereas the target workflow type for all other patients is type-2 workflow. Each type of medical workflows needs to be processed by one resource agent. Table 4 shows the earliness/lateness penalty coefficients for each patient. Based on this application scenario, we compare the performance of our method with the rule of first-come first-serve (FCFS) widely used in practice. The patients may not arrive at the hospital punctually at the planned appointment time. Some arrive earlier whereas others arrive later. Table 5 shows patients’ arrival time.

Table 3 Patients’ planned appointment time and expected finished time
Full size table
Table 4 Earliness/Lateness Penalty coefficients
Full size table
Table 5 Patients’ arrival time
Full size table

By applying our algorithm, the results are shown in Tables 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 in Appendix II. By applying FCFS to the above example, the results are shown in Tables 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 in Appendix II. Table 6 summarizes the difference in total processing time for this example. The schedules generated by applying the rule of FCFS lead to significant delay for most patients. The results indicate that the discrepancy between the scheduled appointment time and arrival time can be significantly reduced by applying our method. Our method improves accuracy in scheduling patients based on just-in-time philosophy. It indicates that our method outperforms FCFS for this example.

Table 6 Comparison with FCFS
Full size table

In addition to the examples above, we also conduct experiments for several examples with 20 to 100 patients to study the effectiveness of our approach. Some of the results are shown in Fig. 11, where the average time for handling patients is compared.

Fig. 11
figure 11

Comparison with FCFS (in minute)

Full size image

7 Scalability analysis and numerical results

To study scalability of the proposed approach, we analyze and conduct experiments to estimate and illustrate how the response time grows as the number of patients and the number of resource activities increase. To illustrate the benefit of our agent based approach, we also analyze and compare the response time of our approach with that of a centralized approach. In this section, we first analyze the response time for our agent based approach. Then we analyze the response time for the centralized approach. Finally, we verify our analysis by numerical results.

For our agent based approach, note that the Lagrangian function for workflow agent w n is defined by

$$\begin{array}{@{}rcl@{}} L(\lambda )&\equiv& \sum\limits_{p=1}^{\Pi}\min \sum\limits_{t-1}^{T}(\psi (t,\tau_{p} )\eta_{pt})\\ &&+\sum\limits_{r=1}^{K_{n}} {\sum\limits_{t=1}^{T} \lambda_{kt} \left(\sum\limits_{\tau =t-\pi_{nk} +1}^{t} {v_{pk\tau } } -R_{r_{k} t} \right)} \end{array} $$

s.t. constraints (5.1) ∼(5.5) , where λ kt is the associated Lagrange multiplier that must be nonnegative.

To compute L(λ) for given λ, it is necessary to solve the minimal cost network flow problem. The computational complexity to solve a minimal cost network flow problem with n nodes and flow of f is O(n 2 f). As the number of nodes in the network associated with L(λ) is proportional to Kn T and the flow is d p , the computational complexity is \(O(\mathrm {K}_{\mathrm {n}}^{\text {2}} T^{2}d_{p})\).

Note that the Lagrange multipliers are updated as follows: \(\lambda _{kt}^{i+1} =\left \{\begin {array}{cl} \lambda _{kt}^{i} +\alpha ^{i}g_{kt}^{i} , & ~~~~~~~\text { if }\lambda _{kt}^{i} >0\text { or if }\lambda _{kt}^{i} =0\text { and }g_{kt}^{i} \ge 0\\ 0, & ~~~~~~~\text { if }\lambda _{kt}^{i} =0\text { and }g_{kt}^{i} < 0 \\ \end {array} \right .\).

As the number of Lagrange multipliers are proportional to Kn and T, the computation time involved in updating λ will increase approximately with Kn T. Therefore, the overall computational complexity is \(O(\mathrm {K}_{\mathrm {n}}^{\text {2}} T^{2}d_{p})\). This indicates the computational complexity of our algorithm is polynomial with respect to problem size.

For the centralized approach, we define the centralized patient scheduling problem as follows. If we solve the scheduling problem for based on a centralized computing architecture, the Petri net models of all workflow agents will be merged first. Let Ω denote the set of workflow agents required for a complete medical workflows. The centralized patient scheduling problem CPSP for the complete medical workflows CW = | n∈Ω W n is formulated similarly. CPSP is also defined based on the requirements of patient agents. But the flow balance equations are defined based on CW instead of W n .

As the number of nodes in the network associated with L(λ) is proportional to \(\left (\sum \limits _{\mathrm {n}} \mathrm {K}_{\mathrm {n}}\right )T\) and the flow is \(D=\sum \limits _{p} d_{p}\), the computational complexity to compute L(λ) is bounded by O(|Ω|2K2 T 2 D). As the number of Lagrange multipliers are proportional to \(\left (\sum \limits _{\mathrm {n}} \mathrm {K}_{\mathrm {n}}\right )T\), the computation time involved in updating λ will increase approximately with \(O\left (\left (\sum \limits _{\mathrm {n}} \mathrm {K}_{\mathrm {n}}\right )T\right )\) and is bounded by O(|Ω|KT). Therefore, the overall response time for centralized architecture will be bounded by O(|Ω|2K2 T 2 D n ).

Figure 12 shows response time with respect to the number of patients for our agent based approach and a centralized problem solver, CPLEX. Obviously, our approach is more efficient than the centralized problem solver. Figure 13 shows the growth of response time with respect to the length of workflows. As expected, the response time of our agent based approach is much less than that of centralized approach as the length of workflows grows.

Fig. 12
figure 12

Response time with respect to the number of patients. (a: Our agent based approach, b: Centralized approach)

Full size image
Fig. 13
figure 13

Response time with respect to the length of workflows

Full size image

8 Conclusion

The healthcare sector faces an intense and growing competitive pressure. How to take advantage of the cutting-edge technologies to effectively acquire competitive advantage is critical for healthcare service providers to survive. Scheduling patients in hospitals is an important issue. Development of a sustainable methodology that combines the state of the art technologies with new organizational structure and management strategy to effectively and dynamically schedule medical operations is required. Recent trends on scheduling operations in hospitals concentrate on the development of dynamic and distributed scheduling techniques to rapidly respond to changing need and requests of patients and achieve sustainability. The problem to optimize the schedule to handle patients using the available resources in a hospital can be formulated as a patient scheduling problem in distributed environment. In this paper, we propose a sustainable solution methodology to dynamically optimize and schedule medical activities based on multi-agent system architecture and collaboration of agents to meet the requirements of patients.

To achieve sustainability, flexibility and scalability, several requirements must be met. First, the medical procedure in a hospital must be described and specified by a standard format. Second, the multi-agent system platform used for implementation must also support information infrastructure and interaction protocols/mechanism defined by industrial standard organization to attain interoperability between agents. Third, the scheduling algorithm must be developed based on dynamic publication and discovery of resources. Fourth, the scheduling method must take advantage of the distributed computing architecture to achieve scalability by solving the scheduling problem based on a divide and conquer strategy. Fifth, all the information in the negotiation processes, including call for proposals, proposals, awarding of contracts and establishment of contracts, must be described based on a standard format such as XML. Our proposed methodology meets all the above mentioned requirements by (1) using Petri net as the workflow specification language, (2) adopting JADE, a FIPA compliant multi-agent platform that supports ACL and the contract net protocol (CNP), (3) using the publication/discovery infrastructure provided in the JADE platform, (4) developing scalable algorithms based on distributed computing architecture to solve the scheduling problem and (5) specifying all the messages of CNP in XML and designing the associated XML schemas.

We propose a viable and systematic approach to develop a system for scheduling patients in a hospital based on MAS. Workflows and resources such as doctors, staffs, specialists and nurses are all modeled as agents. The key issue is to make these agents work together coherently to handle patients timely. Our approach schedules patients based on dynamically discovered resources. As Petri net is adopted as a workflow specification language in our scheduling system, users do not have to formulate the scheduling problem manually. In this way, users not familiar with optimization theories can also apply our tool to schedule patients in a hospital. Moreover, the cost and time involved in the development of scheduling software can be significantly reduced. In our solution methodology, the scheduling problem is divided into several scheduling subproblems that are solved by several cooperative scheduling agents, with one scheduling subproblem being automatically formulated by a scheduling agent based on the PNML models for the relevant workflow agent and resource agents. Each scheduling subproblem is then solved internally based on the developed algorithm.

We present our implementation and illustrate the functions of the proposed system. We demonstrate the effectiveness and scalability of our method by application scenarios and compare the schedules generated by our method with those generated by the heuristic rule used in practice for scheduling patients. The results indicate that our approach outperforms the heuristic rule. We also analyze and illustrate scalability of our approach by examples. To study scalability of our approach, we analyze response time with respect to the number of patients and the length of workflows. Both our analysis and numerical results indicate that our approach is more efficient than centralized problem solver as the number of patients and the length of workflows grow. One of our future research directions is to develop a scheme to improve overall system performance and relationships between agents by creating different scenarios using different organizational structure of agents in our proposed system. Another future research direction is to study proper mechanisms to form coalitions for agents in a hospital to handle and schedule patients. How to develop an effective scheme to deal with uncertainties in hospitals is also an important issue.