Distributed Patient Scheduling in Hospitals

1 Introduction

Patient scheduling in hospitals is concerned with the optimal assignment of patients to hospital resources. Hospitals are divided into several autonomous wards and ancillary units, which are visited by the patients for treatments and exami­ nations during hospitalisation in accordance with their illness [Schliichtermann, 1990]. However, the pathways (the needed treatments and examinations) and the medical priorities (the health condition of the patients) are likely to change due to new findings about the diseases of the patients during exami­ nation. Further, complications and arrivals of emergency pa­ tients, which are in urgent need for treatment, result in sched- K. S. Decker Comp. & Inf. Sci. Dept. Univ. ofDelaware Newark, Delaware, USA decker@cis. udel.edu A. Heinzl*

*We would like to thank the DFG, Deutsche Forschungsgemein­ schaft for funding this work as part ofSPP 1083.

Inf. Sys. Dept. University of Mannheim Mannheim, Germany heinzl@uni -mannheim.de

ule disturbances 1 [Schliichtermann, 1990]. Due to this, pa­ tient scheduling in hospitals requires an approach which is distributed, in order to leave the authority at the responsible hospital units, and flexible, to be able to react to plan changes in an efficient manner.

We have chosen to adopt a multi-agent based approach to this problem, because such systems allow the representation of every single coordination object, i.e. the responsible enti­ ties, as single autonomous agents with their own goals [Wein­ hardt and Gomber, 1996]. This, in turn, reflects the existing decentralised structures in hospitals [Decker and Li, 2000]. Through social abilities, the agents can interact with each other to reach their own goals. Moreover they can react with the needed flexibility to changes (as new information about the health status of a patient becomes available) and distur­ bances (e.g. emergencies and complications) through proac­ tiveness and responsiveness [Jennings, 2001].

This paper advances the state of the art in two main ways. First is the design of a novel procedure, i.e. a patient cen­ tred multi-agent based coordination mechanism, where the patients are represented as autonomous agents, trying to im­ prove their current scheduling state by negotiation with other agents. Second is the derivation of health state dependent op­ portunity cost functions, based upon which the agents eval­ uate their current schedule and compute the gains and losses through plan modifications.

The remainder of the paper is structured as follows. Sec­ tion 2 describes the domain of patient-scheduling in hospitals. Section 3 details the conceptual framework of our multi-agent system, the relevant coordination objects and the coordination mechanism. The results of the proposed mechanism are also evaluated. The paper ends with conclusions and an outlook to further work in section 4.

2 The Patient Scheduling Problem

In addition to the complexity arising from the distributed structure of hospitals, patient scheduling has to be performed in the face of a high degree of uncertainty about the treatment pathways of patients within the hospital. Thus patients arrive continuously at the hospital and the necessary medical treat­ ments are often not able to be completely determined at the beginning of the treatment process. Moreover the results of a diagnostic examination might change the (medical) priority of the patients, invoke additional activities and/or make other medical actions obsolete.

1 This problem can be ameliorated by the provision of addi­ tional (exclusive) emergency resources (e.g. separate x-ray facili­ ties). However, for economic reasons, hospitals try to minimise these extra resources.

Due to this complexity, the application of traditional ( op­ erations research) methods from industrial scheduling to the patient scheduling problem is problematic [Schliichtermann, 1990]. To be able to handle the process dynamics in a dis­ tributed environment, hospitals commonly use a very flexible approach for patient scheduling. Typically, the wards send treatment and examination requests to the ancillary units. Based upon these requests, the ancillary units order the pa­ tients from the wards. This allows the units to react very flex­ ibly to changes with very low communication needs. If, for example, an emergency patient needs to be inserted, the next patient will simply be called from the ward later, leaving this patient available to other ancillary units.

However, because there is no inter-unit coordination, this procedure cannot resolve resource conflicts, which occur if the same patient is requested by more than one ancillary unit at the same time [Decker and Li, 2000]. Because the ancil­ lary units only have a local view, i.e. they do not- and cannot - take the whole pathway of the treated patients into their scheduling consideration, no inter-unit process optimisation can be undertaken (i.e. the medical tasks for the patients can­ not be scheduled and coordinated in an efficient manner). This causes undesired idle times as well as overtime hours for the hospital resources and extended patient stay times.

3 Agent-Based Patient Scheduling

In this section the conceptual framework of our multi-agent system is described. Then, the relevant coordination ob­ jects, i.e. the patients and hospital resources, are modelled as agents. After this, a coordination mechanism is introduced. Finally, examples are given and the first results of the imple­ mentation are presented.

3.1 Conceptual Framework

Using a multi-agent system, [Decker and Li, 2000] addressed the problem of resource conflicts in the patient scheduling domain. Specifically, by adding a coordination mechanism to handle mutually exclusive resources (i.e. the patients) to the Generalized Partial Global Planning (GPGP) approach 2 , they achieved significant scheduling improvements compared to current patient scheduling without coordination. ln their work, they took a function-oriented approach, where only the units are represented as autonomous agents. The treatment pathway of the patients is captured by the nursing units. How­ ever, the dynamics of the patient scheduling problem and the medical priorities of the patients were not considered.

For this reason, we use a patient-centred approach, in which the patients are modelled as agents, too. This allows the representation- and therefore consideration- of the hos­ pital processes as a whole [Adam and Gorschliiter, 1999]. In contrast to the resource agents, who only see the patients as entities to be treated, the patient agents only see the medi­ cal actions as tasks that need to be performed. Due to these opposing forces, the patient agents ensure that the resource agents also consider the treatments of the patients outside their unit (without any explicit knowledge of them) and vice versa.

2 GPGP is a domain independent, task environment centred, scheduling approach to coordination [Decker and Li, 2000].

To this end, the relevant coordination objects in the hospi­ tal (i.e. the entities to be coordinated), which will be repre­ sented as agents, can be identified as patients and resources (i.e. rooms, machines and personnel). To reduce complexity, all resources needed for a specific medical action are repre­ sented by the hospital unit responsible for this action, which will be implemented as the resource agents.

If more than one patient agent now wants to use the iden­ tical resource at the same time interval, a resource conflict occurs. To solve these conflicts, a coordination mechanism is needed. For this inter-agent coordination, we decided to use a market mechanism. The rationale for this is that a market mechanism is a distributed coordination mechanism which facilitates efficient solutions with low communication needs. In particular, only prices for specific goods are com­ municated, keeping all other information private to the mar­ ket participants [Wellman eta!. , 2001]. Additionally, a mar­ ket facilitates a dynamic environment, where the market par­ ticipants take actions according to their current (dynamically changing) situation based upon private information and pref­ erences. In this market, the coordination objects are modelled as autonomous, self-interested market participants, trying to improve their local schedule. In markets, the price mecha­ nism leads to an efficient resource allocation because the re­ sources are assigned to the agents that are willing to pay the highest price (assuming that the agents bid rationally, these are the agents who gain the highest utility from this resource). A pareto optimal solution will be achieved, because no agent will accept a deal, which worsens its current state. Therefore, the agents will trade resources until no agent can improve its schedule without harming another agent [Weigelt, 1994].

3.2 Coordination Objects

To implement a coordination mechanism, the above men­ tioned coordination objects have to be modelled. In this work the main goal for the patients is to minimise their stay time and for the resources to minimise idle times. This kind of scheduling problems represents a worth-oriented environ­ ment [Rosenschein and Zlotkin, 1994 ], where the degree of goal achievement can be evaluated by a util ity function (rather than a state or task oriented environment, where a sin­ gle goal cannot be achieved partially). The usage of contin­ uous worth functions instead of single worth values assigned to specific goals enables the agents to relax their goals, i.e. to compromise in order to achieve a better solution [Rosen­ schein and Zlotkin, 1994]. For example, if two agents want the same time slots at the same resource, the agents can agree upon a solution which does not fully satisfy their own goals, but reaches a better overall solution. This situation is illus­ trated in the figures 2(a) and 2(b).

Because we adopt a patient-centred approach, the main fo­ cus will be on the patient agents, which will be modelled in the first subsection. Within this part, we introduce the health state dependent cost-functions, which are needed for price ar­ ticulation in the market mechanism. In the second subsection, the resource agents are described.

Patient Agents

Each patient is represented by an agent. The patient agents can only see their own schedule, containing their pathway through the hospital. The pathway of a patient agent com­ prises the needed treatments and examinations as well as the order constraints between those tasks. The patient agents are also equipped with a private worth function to be able to ne­ gotiate in a goal driven manner. This worth function is re­ alised as a cost function, which they try to minimise. These cost functions increase over time, setting incentives for the patient agents to schedule their treatments and examinations as early as possible in order to reduce costs.

In contrast to commercial domains, the utility or cost func­ tions cannot be based upon monetary values in hospitals. While in e-commerce scenarios the human principals reveal their preferences through their willingness to pay (e.g. by specifying maximum buy and minimum sell prices), patients do not - and should not - reveal their preferences through their willingness to pay for a specific treatment time slot. The preferences rather have to be based upon medical priorities, i.e. their health state. This absence of normalised monetary units additionally causes the problem of inter-agent utility comparison. To solve this problem, we operationalised the progress of the patients' health state. In current hospital prac­ tice, numerous health states or patient priority measures and indices are in use (e.g. APACHE II (Acute Physiology And Chronic Health Evaluation) [Knaus et al., 1985] in intensive care units). The choice of the measurement to use is up to the hospital. However, we propose, that it should support a cardinal measurement of the health state progress over time.

The cardinal measurement is necessary for inter-agent util­ ity comparison and transfer (as we have to calculate with these units). Because these health state (utility) units cannot be transferred between the actual patients in the hospital, the multi-agent system has to be separated from the actual patient world, where only the agents transfer utility units in order to reach a better overall solution (minimisation of health state adjusted patient stay time).

The health state progress is important, because the priority of the patients should not be based upon their current state, but on their health state development. For example, a patient with a currently reasonable but rapidly deteriorating health condition should have a higher priority than a patient with a (slightly) lower current, but continuously constant, health state.

For the necessary cardinal measurement of health, we rely on the concept of years of well being [Torrance, 1987] be­ cause it handles the health state progress over time (a good overview can be found in [Pedroni and Zweifel, 1990]). In this method, the question is what time period xT of total health (1) equals one specific time period IT of a certain health state H, i.e.

Through this, the health state of a patient can be described in time units.

The primary goal of patients in hospitals is to increase their current health state through treatment, where a disease could be viewed as disutility (decrease in quality of life) for the pa­ tient. This loss of utility adds up as long as this disease is not cured. Based on this assumption, the (opportunity) cost copp for not curing the patient right away equals the differ­ ence between the achievable health state (through treatment) z and the patient's health state over the time H(t). Formally, this can be expressed by

In addition, it has to be considered that the health state and the achievable health state can change over time. Therefore, the patient's opportunity costs are influenced by his current health state a, the development of his health state over time H(t), and the maximal reachable health state through treat­ ment z. If the health state does not change over time, i.e. H(t) =a, the opportunity costs are

If the health state of a patient worsens over time, assump­ tions about the course of the health state have to be made by a physician. If we assume- for clarity- a linear reduction by b of the health state, i.e. H ( t) = a - bt, we get

However, this approach works with any health decrease rate, as the health state of a patient normally does not decrease linearly. Nevertheless, a linear approximation of the decrease in health can be justified by practical reasons. Instead of try­ ing to estimate the exact shape of the curve, a physician could rather specify two or more specific points in time and in be­ tween a linear reduction could be estimated. Figure 1 shows an exemplary course of an illness with linear reduction of the health state, resulting in a quadratic opportunity cost curve.

Finally, if the maximal reachable health state decreases, the patient must be treated immediately to prevent lifelong dam­ age to his health.

With these cost functions in place, the agents can now eval­ uate their current state, i.e. the degree of goal achievement. Further, based on these functions, the agents are able to com­ pute supply and demand prices for time slots which corre­ spond to the losses or benefits caused by plan changes, which is essential for a market mechanism. How these prices are computed will be explained later in the context of the descrip­ tion of the coordination mechanism (section 3.3).

Resource Agents

In contrast to the patients, the hospital resources are directly comparable with the resources in industrial scheduling do­ mains. Their main goal can be described as maximising their utilisation or, equivalently, minimising idle time.

To reach this goal, cost-functions can also be articulated for the resource agents. These cost functions represent the reserve prices (i.e. the price that will be charged for an empty slot) for the possible appointments [Wellman et al., 2001]. Through this, priorities between different resources can be established that allow penalisation of undesired appointment times (e.g. evening shift or overtime hours). Here, the basis for the resource agents' cost functions comes from cost ac­ counting.

However, for inter-agent utility comparison (i.e. between patient and resource agents) these measurements have to be equalised, which can be a very difficult task, because the health state of a patient has to be compared with monetary values from cost accounting. A good way out of this problem are trade-off considerations, e.g. what amount of idle time of a specific resource equals one hour waiting time for a patient with a specific health state.

3.3 The Coordination Mechanism

The main goal of the coordination mechanism is to minimise the health state adjusted stay time of the patients, which is equivalent to an overall minimisation of suffering for the pa­ tients. The basic idea of our coordination mechanism is that the patient agents try to buy into resource time slots for the needed treatments and examinations. However, the usage of (central) auction mechanisms is obstructed by the dynamics of the patient scheduling problem described in section 2.

To ensure feasible (i.e. conflict free) initial task appoint­ ments for the patients, all new treatments and examinations are scheduled on a first-come first-served (fcfs) basis. To do this, the patient agents who want to add a task to their path­ way contact the responsible unit for the execution of this task in order to obtain the earliest time slot which is available at the unit as well as in their own schedule. To illustrate this, figure 2(a) shows a possible initial resource allocation. These initial appointments determine the budget (or better the initial opportunity costs) of the agents. This is important because a hypothetical price system is used (as per section 3.2).

Based upon this initial schedule, the agents try to improve their schedule in order to reduce their opportunity costs. The price p they are willing to pay for a specific time slot (ex­ pected gain) or they charge for a time slot (expected loss) is the difference between the cost-value of the current alloca­ tion told and the cost-value for the wanted appointment t new, according to their individual cost function described in the previous section, i.e.

Because in this approach the (opportunity) costs of an ap­ pointment increase over time for the patient agents, they must try to schedule their treatments and examinations as early as possible. If a demanded time slot is already occupied by an­ other patient agent, the initial demander must try to buy the time slot from the current owner. With respect to the proper­ ties of a market mechanism, the agents act in a rational, self­ interested manner. Therefore, the owners of the time slots will only release them, if the price offered equals the losses invoked through rescheduling. Since they only charge for the costs invoked through rescheduling they can be viewed as act­ ing in a partially cooperative manner.

The detailed negotiation process goes as follows :

1. A patient agent initiates a negotiation for rescheduling, if the pathway (additional or obsolete medical actions) or the health state of its patient has changed.
2. The initiating agent selects the task with the highest pos­ sible improvement (difference between the costs of the current owned and the best reachable time slot) and con­ tacts the resource agent that is responsible for the execu­ tion of this task.
3. The resource agent reserves that time slot, and contacts all affected patient agents, i.e. the agents that currently own this interval, and informs them about the proposal of the initiator.
4. The affected patient agents (sellers) try to reschedule to the first nonreserved time slots (see step 3) and notify the initiator about their costs due to rescheduling. To prevent cycles, reserved intervals cannot be demanded by other agents.
5. If the alternative time slots for the sellers are already occupied, they again become demanders for those time slots and accumulate the invoked costs. Here, order con­ straints can invoke additional rescheduling in other re­ sources.
6. After all prices are computed and submitted to the ini­ tiator, the initiator compares its expected gains from rescheduling to the total price asked for this interval. If the gains exceed the costs it accepts or rejects otherwise, and the negotiation for this time slot terminates.

The former initiator continues its rescheduling activities by opening new negotiations for the next task with the (now) highest possible improvement until it cannot improve any task any further. Previously rejected time slots will not be consid­ ered unless these time slots are released by their owners. For concurrency issues only one (randomly chosen) agent can ini­ tiate a negotiation at a time.

In this coordination mechanism only the patient agents are active components. However, as described earlier, cost func­ tions can be implemented into the resource agents, allowing prioritisation between the resources. The resource price for a time slot is charged when a patient agent buys a time slot, and reimbursed when the patient agent releases this time slot.

As described earlier, the pathway of the patients through the hospital is likely to change during the treatment process, that is, additional treatments and/or examinations may be­ come necessary while other tasks may become obsolete. In our coordination mechanism, additional tasks (as well as ad­ ditional patients) can be added at any time using the fcfs rule explained above. If a treatment becomes obsolete, the respon­ sible patient agent notifies the affected resource agent that, again, informs the other patient agents in its schedule.

3.4 Example Scenarios

Figure 2(a) and 2(b) illustrate the functioning of our coordi­ nation mechanism. Figure 2(a) shows an initial schedule with three patients (A,B,C). For illustration purposes, we start with identical cost-functions with an assumed initial health state a of 0. 7, an achievable health state z of l.O, a decrease rate b of 0.001 and equal possible starting times for all patients. The used cost function resolves as 0.3t + 0.0005t 2 . Further, in this example, all task durations are set to lOt. We will use the $-sign to indicate utility units.

Based upon this initial schedule, agent C negotiates with agent B in unit 2 in order to improve its current situa­ tion. Agent C's current opportunity costs in unit 2 are $12.8 (0.3 x 40 + 0.0005 x 40 2 ) . Its opportunity costs for the first time slot would be $3.05 (i.e. a difference of $9. 75). For the calculation of the offer price, agent B has to determine its additional rescheduling costs. Therefore agent B has to ne­ gotiate with agent A in unit 2 for the next best time slot and in unit 1, because the patients are exclusive resources which can only perform one task at a time. Agent A looses $3.25 in unit 2 and another $3.15 in unit l. Agent B looses $3 .15 in unit 2 but gains $3.15 in unit l. Agent B is charged with the losses of Agent A ($6.40) and adds this to its supply price for agent C (here $3.15- $3.15 = $0.00). Because the total supply price ($6.40) is less than agent C's gains ($9. 75) agent C accepts the deal (because it can compensate the losses of the other agents) and the plan is changed. No more deals are possible and figure 2(b) shows the result of this negotiation.

In this example, patient agent A accepted a schedule of lower quality in favour of patient agent C. However, only pa­ tient agent A - not the real patient - has received a compen­ sation from patient agent C. This illustrates the necessary dis­ junction between the real patients and the multi-agent system in the hospital domain as described earlier (section 3.2).

In the next step, we relax the assumption, that all agents have the same cost functions . If agent C would have had a lower health state (e.g. J.L = 0.35) it could have even improved its appointment in unit I because it would have gained $3.75 from moving to the second slot (agent A in figure 2(b)) while agent A would only ask $3.25 for its slot (agent A moves to slot 1 and gains $3 .15, and agent B moves to slot 3 and looses $6.40).

We have applied the described coordination mechanism to the first Taillard 5 x 5 open shop problem [Taillard, 1993 ] to analyse the behaviour for tasks with different durations. Figure 3 shows the resulting Gantt chart with a solution of 349. The optimal solution is 300. To analyse the convergence of the mechanism, we logged the changes of the latest task for each agent. Figure 4 shows the corresponding convergence behaviour, which indicate a fast convergence in the first third of the graph.

The number of negotiation rounds counts each improve­ ment attempt (successful or not) of the agents. The same pro­ cedure was executed for the n x n open shop problems with equal task durations. For these problems the optimal solution will be always achieved. The resulting Gantt chart is shown in figure 5. Figure 6 shows the corresponding convergence, illustrating the simplicity of this problem type in contrast to the used Taillard benchmark.

However, a better agent-based solution to this problem can be achieved through the usage of (central) appointment auc­ tions. Implementing an auction based approach using the same cost functions resulted in a solution at 308. How­ ever, these auctions cannot handle the dynamics of the patient scheduling problem, because the auction process would have to restart again after severe changes in the pathway occurred.

4 Conclusions and Future Work

ln this paper, we presented a patient-centred coordination mechanism for inter-unit patient scheduling in hospitals. Therefore, health state dependent cost functions were devel­ oped. We described the implemented coordination mecha­ nism and evaluated first results, showing the different conver­ gence for problems with equal and different task durations.

In the next step, we will run our approach on real hospi­ tal data, already retrieved out of a field study in five hospitals. Based upon these results, our coordination mechanism will be enhanced in future work, where the main focus is on the de­ velopment of a flexible auction mechanism in order to handle the dynamics of the patient scheduling problem. In this con­ text, we will analyse how the usage of texture measurements (here: criticality and goodness measures) [Sycara eta/., 1990] can facilitate our coordination mechanism in order to reduce backtracking. Additionally, our agent based approach will be benchmarked with a genetic and evolutionary algorithm, which is under development in the context of this work. Fur­ ther, a decision theoretic approach facilitating stochastic task duration will be presented in the near future.