A data-driven hierarchical MILP approach for scheduling clinical pathways: a real-world case study from a German university hospital

In Germany, hospitals cause around 25% of the total costs of the health care system (Destatis 2014). To reduce these costs of about 76bn Euro per year, the German Diagnosis-Related Groups (DRG) system was established in 2003. In contrast to the earlier length-of-stay-based reimbursement system, hospitals now receive a diagnosis-dependent lump sum per case. As a consequence, hospitals have a strong incentive to reduce their patients’ lengths of stay and to effectively manage clinical processes and resources.

At the time of writing, however, every third hospital is still unprofitable (Augurzky 2015) which, together with demographic change, yields a great need for increasing the efficiency of hospitals. According to Villa et al. (2009), clinical pathways (CP) are among the most promising instruments for achieving an efficient utilization of both human and physical hospital resources. CP are specific sets of time-constrained treatments and ward stays to be performed between a patient’s admission and discharge to cure a certain disease. Besides increasing the transparency and the standardization of medical processes, CP are instrumental in hospitalization scheduling and controlling (Jacobs 2007). Despite this often-stated potential, however, CP and patient flow scheduling are still waiting to form an integral part of day-to-day practice in many hospitals.

According to Roeder et al. (2003), Kirschner et al. (2007), Küttner and Roeder (2007), and Salfeld et al. (2009), an important obstacle for a widespread utilization of CP is the fact that manually creating CP forms a tedious endeavor. In addition, since CP are mostly used in a descriptive way, only few CP formalisms discussed in the literature enable both the automatic extraction of CP structures from hospital data and their employment for scheduling. Furthermore, many important parameters affecting pathway schedules such as emergency patient arrivals, (exact) treatment durations, resource availability or complications arising in surgeries are subject to uncertainty. Moreover, given that the pathway-scheduling problem has to consider complex constraints as well as all relevant resources, it constitutes a complex large-scale optimization problem. As a consequence, many pathway-scheduling approaches rely on simplifications and operate on a high level of aggregation which makes putting the resulting schedules into practice difficult: The approach from Saadani et al. (2014), for example, completely ignores bed resources. Finally, while hospital scheduling typically considers multiple objectives related to economics, patients and staff members, many approaches focus on one-dimensional performance indicators, typically based on cost minimization or profit maximization (Hulshof et al. 2012).

Motivated from a case study with a German university hospital, this paper addresses most of the issues discussed above and proposes a tactical pathway-scheduling approach intended to support hospital case managers responsible for the coordination and scheduling of treatments and ward stays. The main contributions of this paper can be summarized as follows.

First, we propose a data-driven approach to pathway scheduling. Our approach is based on scheduling relevant pathway information automatically extracted from standardized hospital billing data available for every hospital in Germany using the pathway-mining approach introduced by Helbig et al. (2015). As a result, one of the most time-consuming data preparation steps necessary for pathway scheduling—defining pathways and their constraints—is automated to a large extent. To the best of our knowledge, the resulting approach is the first to combine process mining techniques with optimization-based decision support for scheduling clinical pathways.

Second, we propose a day-level pathway-scheduling approach considering all pathway constraints and hospital resources on an adequate level of detail which is flexible enough to consider multiple scheduling criteria: it considers multiple ward stays during hospitalization and gender-separated room assignments. Moreover, it explicitly accounts for resource eligibility constraints for treatments, e.g., based on specific feature and skill requirements. In addition, it allows considering important resources individually while aggregating identical resources if appropriate. Finally, to support scheduling pathways for a broad range of possible objective structures, the objective function in our approach involves a weighted combination of multiple hospital- and patient-related criteria including fairness and workload-balancing criteria.

Third, to tackle the resulting complex large-scale scheduling problem for realistic problem instances involving up to 300 patients with a planning horizon of a full month, we propose a two-stage mixed-integer linear programming (MILP) approach based on a hierarchical decomposition: The first-stage model determines the admission dates and schedules complex treatments with a high duration. Given instructions from the first model, the second model schedules the ward stays, assigns all patients to gender-separated rooms and schedules the remaining treatments. To align the first-stage instructions with the second-stage requirements, the first-stage model involves anticipation components to account for the gender separation requirement and to consider pathway constraints involving the full set of treatments.

Fourth, we evaluate the overall approach including the automatic CP extraction in a set of experiments conducted with real-world data from a German university hospital involving 286 elective patients and 1088 treatments. On the one hand, we evaluate our hierarchical approach in comparison with a monolithic mixed integer linear programming (MILP) approach: we compare solution times as well as solution quality of both approaches; furthermore, we investigate the effect of employing different degrees of anticipation within the hierarchical approach. On the other hand, we provide a detailed evaluation of two scheduling scenarios: in the first scenario, our approach is used to establish balanced resource utilization throughout the planning horizon; in the second scenario, the main goal is to obtain a high resource utilization at the beginning of the planning horizon.

Note that in this paper, we do not explicitly address the stochastic character of the pathway-scheduling problem: on the one hand, our approach only deals with scheduling elective patients for which most planning-relevant information is known ahead. Nonetheless, one of the goals of the planning approach is to establish balanced resource utilization and resource buffers to ensure that emergency cases can be handled adequately. On the other hand, our approach employs conservative point estimates for uncertain treatment times to obtain schedules which are robust with regard to treatment time variations. Like the other authors dealing with clinical pathway planning (see e.g., Gartner and Kolisch 2014 and Burdett and Kozan 2018), we assume that additional uncertainties such as absence of medical staff, resource breakdowns or stochastic patient arrivals are addressed by embedding our pathway-scheduling approach in a rolling planning process.

The remainder of this paper is structured as follows. Section 2 provides an overview of the rich literature dealing with offline operational scheduling in hospitals and identifies possible objectives, efficient modeling techniques and aspects to be considered in clinical pathway scheduling. Section 3 introduces the constraint-based CP concept according to which the scheduling is carried out and sketches the automated CP mining approach mentioned above. In Sect. 4, we introduce our hierarchical MILP approach consisting of an aggregated first-stage model for scheduling complex treatments and determining the admission day and a detailed second-stage model for scheduling the remaining treatment and assigning patients to rooms. In Sect. 5, we explain the real-world dataset from a university hospital used in our computational experiments. In addition, we illustrate the results from mining CP for the hospital’s largest department. Section 6 presents the results from using our MILP approach for scheduling the extracted CP for all elective patients of the department of urology. To demonstrate the effects of varying the weights in the multi-criteria objective function, we discuss two scenarios: in the first scenario, the resource allocation is balanced across the planning horizon; in the second scenario, resources are preferably allocated at the beginning of the horizon. Section 7 concludes the paper and points to further research opportunities.

We employ the taxonomy of planning decisions in health care introduced by Hulshof et al. (2012) to structure the following literature review. According to this taxonomy, the problem considered in this paper can be characterized as an offline operational planning problem: complete CP for elective patients are scheduled within a planning horizon of about 1 month considering activities at the level of individual patients and resources. Since our approach takes all kinds of hospital resources into account, the following literature review does not only regard CP-related literature but also considers more general hospital resource scheduling approaches to identify aspects relevant for our research. Since the assignment of staff to shifts and inventory management issues are not in the scope of this paper, articles dealing with these topics are not included in the following review. Furthermore, the review is restricted to articles involving mathematical programming as solution technique published after 2005. Table 1 shows the related work classified by the combinations of considered resources and treatments.

Since surgeries form the greatest source of income for most hospitals (Denton et al. 2007) and at the same time operating rooms (OR) constitute the most expensive type of resource using more than 10% of a typical hospital budget (Jebali et al. 2006; Chaabane et al. 2008), there is a rich body of literature dealing with surgery scheduling. The main goals of surgery scheduling are to reduce costs (overtime costs, penalties for idle time or fixed costs for opening an OR) and to increase the utilization of the available OR. This is achieved by either allocating surgeries to a given set of OR (Lamiri et al. 2007; Lamiri et al. 2008a, b; Fei et al. 2009; Denton et al. 2010; Riise and Burke 2011; Meskens et al. 2013), sequencing a set of given surgeries (Denton et al. 2007; Cardoen et al. 2009a; Cardoen and Demeulemeester 2011) or both (Jebali et al. 2006; Testi and Tànfani 2009; Roland et al. 2010; Batun et al. 2011; Marques et al. 2012; Clavel et al. 2017). In most cases, mathematical programming, heuristics, column generation or combinations of these methods are used to find a good or even optimal solution with respect to a typically multi-criteria objective function. With regard to the scope of the present article, the main insights from the surgery scheduling literature can be summarized as follows: Overtime should be avoided and the well-being of the medical staff should be considered (Roland et al. 2010; Meskens et al. 2013), a flexible pooling strategy of OR has significant benefits (Batun et al. 2011), the eligibility of operating rooms for surgeries may depend on special operating room equipment (Denton et al. 2007) and the patients’ welfare should be taken into account (Testi and Tànfani 2009). Regarding the solution methods, carefully decomposing the problem into solving multiple small problems often yields a good performance in terms of solution time without having a significantly negative impact on solution quality (Jebali et al. 2006; Lamiri et al. 2007; Lamiri et al. 2008a, b; Fei et al. 2009; Denton et al. 2010; Batun et al. 2011; Marques et al. 2012). For a recent survey on OR scheduling, see Samudra et al. (2016).

As stated by Helm and Van Oyen (2014), a proper bed management is necessary to avoid having to dismiss patients because of blocked beds, surgical cancelations and operational chaos. In the literature, two kinds of bed management problems are discussed both of which typically consider medical needs as well as patient preferences: elective admission scheduling and the patient-to-room assignment. Elective admission scheduling problems are solved, e.g., by local search heuristics (Ceschia and Schaerf 2011), MILP (Helm and Van Oyen 2014) or random forest models (Schmidt et al. 2013). Demeester et al. (2010) solve the patient-to-room assignment problem using a tabu search heuristic. Vancroonenburg et al. (2014) develop an integrated model to solve both problems at once to increase both planning flexibility and operational efficiency. Gender-separated room assignment is typically considered as a crucial issue, see Demeester et al. (2010, Ceschia and Schaerf (2011), Schmidt et al. (2013), and Vancroonenburg et al. (2014).

According to Schimmelpfeng et al. (2012), scheduling treatments (encompassing not only surgeries but all types of medical activities) manually often leads to an inefficient resource allocation and can have negative effects on quality of care and patient satisfaction. To avoid this, Vlah Jerić and Figueira (2010) develop a decision support system (DSS) to support the construction of a daily schedule of medical treatments considering available resources and other criteria. They use a scatter search heuristic to construct a set of Pareto-optimal solutions among which the user can interactively choose. Another approach by the same authors presented in Vlah Jerić and Figueira (2012) determines daily treatment schedules considering the availability of medical equipment and physicians. Their approach is based on a multi-objective binary programming formulation for which different solution approaches such as variable neighborhood search, scatter search and non-dominated sorting genetic algorithms are compared. Schimmelpfeng et al. (2012) outline a conceptual framework for a DSS to support the scheduling process of treatments in a rehabilitation hospital. To handle realistic problem dimensions, a hierarchical approach is developed using a daily model for aggregated long-term scheduling and an intra-day model (either time- or resource-oriented) for short-term scheduling.

As argued by Chow et al. (2011), trying to achieve a high OR utilization without considering further surgery-related resources often results in issues such as staff overtime, surgical cancelations and long surgical waiting times. In particular, scheduling surgeries without taking the availability of recovery beds into account often leads to problems. To avoid this issue, several authors propose to simultaneously schedule both the surgery and the following stay in a recovery bed or on a ward. For instance, Pham and Klinkert (2008) propose to allocate hospital resources to individual surgical cases divided into preoperative, perioperative (= surgery), postoperative intensive care unit (ICU) modes and formulate this problem as a MILP multi-mode blocking job shop model. Cardoen et al. (2009b) solve a surgical case scheduling problem in a day-care facility. They formulate a multi-objective model to minimize peaks in recovery bed usage, the occurrence of recovery overtime and violations of staff and patients’ preferences. Their approach is based on a combination of column generation and dynamic programming. To analyze the impact of recovery in OR when no recovery bed is available, Augusto et al. (2010) use a Lagrangian relaxation-based approach. Their results show a high benefit of this improved flexibility in resource usage, in particular in case of high demands for recovery beds. Fei et al. (2010) construct weekly surgery schedules for OR considering recovery beds to maximize resource utilization while minimizing overtime and idle time between surgeries. They use a hierarchical two-stage solution approach which first computes the date of the surgeries based on a set partitioning formulation solved by a column generation technique. In the second step, taking into account the availability of recovery beds the daily surgery scheduling problem in which the sequence of surgeries is determined is formulated as a flow-shop problem and solved by a hybrid genetic heuristic. The authors show that their overall approach allows reducing idle- and overtime increasing resource utilization. Chow et al. (2011) use Monte Carlo Simulation to predict bed requirements from historical data. Based on this, they formulate a MILP to reduce peaks in bed occupancy by scheduling surgeon blocks and patient types. Another simulation optimization approach for the surgery scheduling problem aiming at a maximal patient throughput is developed by Banditori et al. (2013). The authors first use a MILP model to determine the number of cases to be treated by surgery groups in each time slot of a month. The model is then fine-tuned with a simulation approach to obtain both robust and easy-to-implement schedules. Sun et al. (2013) propose a weekly scheduling approach to achieve a high OR utilization. The authors formulate a MILP taking into account limited key resources like ICU-beds and workload of surgeons. Vancroonenburg et al. (2013) incorporate OR and gender separation constraints in their approach for the elective patient admission scheduling problem. Their goal is to determine how scheduling surgical and non-surgical admissions impacts room assignments at wards. Ceschia and Schaerf (2014) address a similar patient admission problem considering OR utilization constraints, gender-separated room assignment, a flexible planning horizon and the notion of patient delay using a local search heuristic. Li et al. (2015) develop a MILP-based lexicographic goal programming approach of scheduling OR and beds considering competing resources such as surgical and nursing staff, anesthesiologists and recovery beds.

The most promising way to avoid bottlenecks, idle time and overtime during hospital patient flow is to schedule not only surgeries, possibly augmented with induced bed resources, but each patient’s full CP. Vissers (2005) proposes a master surgery scheduling approach for CP involving cardiothoracic surgeries based on computing the patient mix with a MILP model. He divides the care process into four successive steps (medium care unit (MCU), surgery, ICU, MCU) and computes the master schedule for a planning cycle of 4 weeks taking OR, MCU-beds, ICU-beds and nursing staff for ICU-beds into account. An approach to schedule full CP of elective patients for a week hospital¹ is introduced by Conforti et al. (2011). The authors show their results from scheduling clinical services (diagnostics and surgeries) as well as patient admissions to maximize the patient flow using a MILP model in a case study with 20 patients. Helbig (2011) presents a MILP model for the operational hour-based scheduling of interdisciplinary CP containing treatments, surgeries, order constraints and ward stays. The aim of the model is to minimize waiting time and to finish each CP as early as possible within the planning horizon under consideration of practical constraints like gender separation in rooms and a fair distribution of waiting time among all patients. The paper reports results from experiments with artificial small-scale problem instances with up to four patients. A patient flow planning approach to maximize the length of stay (LOS)-based contribution margin for DRG-based reimbursement policies is developed by Gartner and Kolisch (2014). The authors formulate two MILP models to schedule CP, one with fixed and one with variable patient admission dates. They experiment with these models in a static and in a dynamic setting in which the MILP is embedded in a rolling horizon approach. The results dealing with a planning horizon of 28 days and 150 patients show the potential to achieve a higher contribution margin and a significantly reduced time between admission and surgery compared to given manual solutions. Saadani et al. (2014) propose a MILP-based CP scheduling approach in which treatments using different resources are scheduled to minimize the patients’ length of stay. Their CP contain multiple treatments but no bed requirements. The authors present results for an instance of 20 patients and a planning horizon of 14 days. Recently, Burdett and Kozan (2018) proposed an approach using constructive heuristics and metaheuristics for scheduling CP operating on a very high level of detail: They schedule not only the day, but also the time of day of the treatments. Their approach takes into account all major treatment resources under consideration of resource eligibility constraints; in addition, it considers multiple ward stays and bed resources on wards.

Summarizing the results of the literature review, the most promising way to improve the patient flow in hospitals is to consider the full CP of each patient. As shown above, scheduling CP involves various complex aspects to be considered by a CP scheduling approach to achieve practically useful and implementable schedules:

We are not aware of any mathematical programming-based CP scheduling approach taking into account all the aspects mentioned above. As a consequence, this paper proposes a novel hierarchical MILP approach to schedule whole CP with hospital-wide ward stays able to handle the mentioned aspects for real-world problem instances.

An additional important feature of our approach is its data-driven nature: by employing the pathway-mining approach and the constraint-based representation of CP introduced by Helbig et al. (2015), the structure of the CP to be scheduled can be automatically extracted from standardized data available in every German hospital. It becomes clear from the recent survey articles Yang and Su (2014) and Rojas et al. (2016) that process mining for clinical pathways and in healthcare in general forms a very active field of research. As described in Rojas et al. (2016), however, the results of the process mining are typically used for analyzing and improving healthcare processes using techniques from business process management. Our approach in contrast is, to the best of our knowledge, the first one tightly coupling process mining with mathematical optimization for scheduling clinical pathways.

Even though the general concept of CP is well-known and widely accepted, there is no standard formalism for representing CP (Vanhaecht et al. 2006). While the formal representation of a CP is of secondary importance if it serves merely descriptive purposes, it is crucial when CP form the basis of scheduling patient flow. Conforti et al. (2011), for example, consider a CP as a set of treatments to be scheduled without imposing inter-treatment dependencies. Gartner and Kolisch (2014) represent the possible schedules for each CP on a directed graph in which the arcs form minimum time lags between the clinical activities. The CP scheduling approach proposed in this work relies on the constraint-based CP representation introduced in (Helbig et al. 2015). We give a brief overview and example of this representation in this section; for details regarding the representation as well as regarding the pathway-mining approach, we refer the reader to (Helbig et al. 2015).

As illustrated in Fig. 1, the time scale of the pathway representation is days and a CP is considered on two levels: the level of ward stays and the level of treatments. On the level of ward stays, a CP forms a chronological sequence of ward stays \( {\mathcal{S}} \). Note that while in many cases, the set of ward stays \( {\mathcal{S}} \) is a singleton, there are cases in which ward changes are part of the planned pathway of elective patients: as an example, in the department of urology considered in our case study, there are several cases with complex surgeries involving both a stay in an intensive care unit (ICU) and on a regular ward; in total, 6% of the cases in the dataset involve multiple ward stays.

In the CP representation, a ward stay \( s \in {\mathcal{S}} \) is associated with a set of eligible wards \( {\mathcal{W}}_{s} \); this means that for stay \( s \), the patient may be assigned to one of the wards in \( w_{s} \). In Fig. 1, for example, the ward stay \( s_{2} \) may either be assigned to ward \( w_{2} \) or to ward \( w_{3} \). A ward stay is characterized by an admission event \( v_{s}^{\text{ad}} \) and a discharge event \( v_{s}^{\text{dis}} \). The admission event \( v_{{s_{1} }}^{\text{ad}} \) of the first stay \( s_{1} \) corresponds to the hospital admission and always takes place at the first day of the CP. All other ward stay events have feasible time intervals indicating when they can be scheduled (e.g., the discharge \( v_{{s_{1} }}^{\text{dis}} \) can be scheduled from day 3 to day 6, see Fig. 1). The number of days between admission and discharge on a ward forms the length of stay (LOS) on that ward. For every ward stay, the LOS is constrained by a minimum and a maximum number of days. During hospitalization, each ward stay requires a bed resource and it is assumed that there are no gap days between two adjacent ward stays.

On the second level of the CP representation, a treatment t corresponds to a surgery or any other clinical service to be performed to cure a disease. A CP contains a set \( {\mathcal{T}} \) of different treatments. Each of these treatments lasts at most 1 day and can only be performed if the required amount of all necessary resource types (e.g., surgeons, special rooms, theater nurses or the patient) is available. To facilitate scheduling, treatments are clustered into treatment groups; the treatments within the same group \( g \) have to be scheduled at the same day (see e.g., \( t_{2} \) and \( t_{3} \) in Fig. 1). Some treatment types may occur in multiple groups which means that they have to be performed once per group (\( t_{2} \), for example, occurs in two groups). To ensure medically correct schedules, each treatment group \( g \) has a feasible time interval \( \left[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\delta }_{g} ;\bar{\delta }_{g} } \right] \) relative to the first admission event. In Fig. 1, this interval corresponds to the length of the bar associated with the treatment group (e.g., \( g_{2} \) has the feasible interval [2;3]). In addition, a medically correct order can be enforced by precedence constraints imposing a minimum and a maximum time lag \( \left[ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\gamma }_{{g,g^{\prime} }} ;\bar{\gamma }_{{g,g^{\prime}}} } \right] \) between two related treatment groups \( g \) and \( g^{\prime} \) (e.g., in Fig. 1, \( g_{5} \) needs to fall into the interval [1;3] relative to the scheduled day of \( g_{4} \)). Moreover, a group can be associated with a certain ward stay \( s \) which means that the group can only be scheduled during that ward stay (e.g., g₁ and g₂ from Fig. 1 can only be scheduled during the first ward stay). Note that by grouping treatments as described, many CP-related constraints are aggregated and in some cases even considered implicitly. On the one hand, this contributes to a tractable size of the MILP models presented in the next section, on the other hand, the modeling itself is facilitated by the grouping.

The pathway-scheduling problem considered in this paper consists of determining the patient’s admission and discharge days, the start and end days of the ward stays and the days on which treatments are performed. The scheduling accounts for precedence relations between treatments and considers all critical hospital resources such as beds, medical staff as well as treatment and operating rooms. Bed resources are considered on the level of rooms, accounting for the requirement of gender separation. Treatments are associated with resource requirements. It is assumed that for each requirement there is a set of eligible resources and a given amount of resource time needed for the treatment. Each resource, in turn, is associated with a time capacity for each given day. Identical resources may be considered in an aggregated way; however, to avoid disaggregation problems, important complex resources such as operating rooms are considered individually.

With respect to the level of detail considered, the pathway-scheduling problem addressed in this paper is situated between the problems considered in Gartner and Kolisch (2014) and in Burdett and Kozan (2018): both the problems considered in Gartner and Kolisch (2014) and in this paper schedule treatments on the time-aggregated level of days, but in contrast to the problem addressed here, Gartner and Kolisch (2014) do not consider multiple ward stays, bed assignment to gender-separated rooms and resource eligibility constraints. Burdett and Kozan (2018), in contrast, consider multiple ward stays and resource eligibility constraints such that the level of detail for representing resources is similar to our work. However, the problem addressed in Burdett and Kozan (2018) deals with the exact timing of treatments instead of only determining the day on which a treatment is performed.

Gartner and Kolisch (2014) point out that the pathway-scheduling problem they address is related to the resource-constrained project scheduling problem (RCPSP), with the important difference that treatments are assumed to take a fraction of a the time unit (in this case: a day) while in project scheduling, activities are typically assumed to take multiple units of time. Using the terminology from Artigues et al. (2015), the model presented by Gartner and Kolisch (2014) can be characterized as a time-indexed formulation, that is, the main decision variables for scheduling activities are binary variables with a day index. The authors assume that each resource requirement is associated with a single set of aggregated resources. As a result, no treatment-to-resource assignment is needed and the resource capacity constraint can be formulated using the time-indexed treatment scheduling variables. The resulting model instances are fairly compact and can be solved to optimality by standard MILP solvers even for realistically sized instances.

Using the analogy to RCPSP, extending the problem addressed in Gartner and Kolisch (2014) by the consideration of treatment-specific resource eligibility is very similar to the extension of the RCPSP to a project staffing and scheduling problem in which resources are considered as flexible or multi-skilled and each task is associated with a set of eligible resources. As discussed in Correia and Saldanha-da-Gama (2015), this setting adds a whole new dimension to the RCPSP since tasks are not only scheduled but also explicitly assigned to resources. Incorporating resource eligibility in MILP formulations for the RCPSP typically results in additional variables and constraints, see, e.g., the formulation proposed in Correia and Saldanha-da-Gama (2015) and, as also discussed therein, makes the problems much harder to solve. Note that the modeling framework for project staffing and scheduling problems proposed in Correia and Saldanha-da-Gama (2015) is based on natural-date variables, that is, on variables representing start times of tasks. Our formulation presented below employs both natural-date variables (e.g., for the start day of ward stays) and time-indexed variables (e.g., for resource assignments). Note that Burdett and Kozan (2018) do not provide a MILP formulation of their very detailed CP scheduling problem—their solution approach uses constructive heuristics and metaheuristics.

Instead of resorting to metaheuristic approaches to deal with the computational complexity of the problem considered in this paper, similar to Schimmelpfeng et al. (2012), we employ a two-stage MILP approach which can be viewed as a constructional hierarchical decomposition in the terminology of hierarchical planning, see, e.g., (Schneeweiss 1998). The first stage determines the “cornerstones” of the clinical pathway, that is, the patient admission and discharge dates as well as the dates for the complex key treatments of each clinical pathway. Considering the first-stage decisions as fixed instructions, the second stage solves the full problem sketched above.

To obtain a high-quality solution for the full problem, the first-stage model anticipates major aspects of the full planning problem using anticipation model components obtained by the means of aggregation and relaxation. While the first stage does not determine the ward stays, it anticipates ward stay scheduling under consideration of the gender separation requirement on the level of aggregated room types. Furthermore, while it only schedules complex treatments (under consideration of all required treatment resources), to make this scheduling consistent with the pathway constraints involving all treatments, the first-stage model also involves all remaining treatment groups (neglecting the respective resource requirements). Before presenting the MILP formulations for the first-stage and the second-stage model, we give a short overview of the notational conventions used in the presentation. A full list of all symbols used in the models is given in the Appendix; in addition, all symbols are explained in the description of the models.

The research presented in this paper is based on a partnership with a German University Hospital providing us both with a real-world dataset and with an opportunity to discuss our assumptions and results with domain experts such as the case manager of the department of urology considered in our investigation. In 2011, the case study hospital had around 36,000 admissions divided into around 25,000 elective and 11,000 emergency inpatients. Figure 2 shows the amount of elective admissions on each ward in 2011. The department of urology (HA2200) has the highest number of cases; Fig. 3 shows the distribution of these cases grouped by month of admission.

We agreed with the partner hospital to base our analysis and our experiments on the peak month March 2011 exhibiting the highest number of cases. In close collaboration with the case manager, we prepared and validated the input data required for our approach including two sets objective function weights representing two different planning scenarios. The remainder of this section describes and illustrates these input data: Sect. 5.1 deals with the cases and their CP information automatically extracted by the pathway-mining approach sketched in Sect. 3. Section 5.2 describes how the data regarding resource requirements and resource capacities were obtained. Finally, Sect. 5.3 explains the planning scenarios used for the computational experiments.

The real-world data described in the previous section forms the basis of a series of computational experiments with our hierarchical approach. The first set of experiments, discussed in Sect. 6.1, aims at assessing the hierarchical approach proposed in this paper. The second sets of experiments aim at discussing the results of the two scenarios in detail.

For the experiments, the MILP models presented in Sect. 4 were implemented AMPL; all treatments exhibiting a duration of more than 30 min (about 50% of the treatments) were considered to form the set \( {\mathcal{G}}_{p}^{\text{res}} \) of treatment groups to be scheduled in the first-stage model. The model instances were solved with Gurobi 6.5 on an Intel i7-3770 CPU with 3.40 GHz and 8.00 GB RAM using 6 threads. For solving the aggregated first-stage model, the relative MIP gap tolerance was set to 1%, the time limit was set to 2 h and the MIP search strategy was set to focus on improving bounds. The second-stage model was solved using default Gurobi parameter settings.

This paper presents a hierarchical MILP approach for CP scheduling aiming at practical applicability in several ways. The CP information including the pathway constraints can be automatically extracted from standardized hospital billing data. The data-driven character of our approach substantially reduces the amount of work to be performed to obtain the CP information needed for scheduling. Moreover, the CP scheduling approach considers all relevant resources on an adequate level of detail; in particular, it models bed assignment on the level of rooms and allows considering treatment resources individually to avoid disaggregation problems of complex resources such as operating rooms. Furthermore, it considers several practically relevant aspects such as multiple ward stays per hospitalization, gender-separated rooms and eligibility of resources for treatments (e.g., special equipment in operating rooms needed for a certain surgery or special qualifications of nurses). To support a broad range of application scenarios and hospital-specific objective structures, our approach employs a multi-criteria objective function accounting for both patient- and hospital-related objectives. Since the detailed representation of practically relevant aspects yields complex large-scale model instances, we propose a carefully designed hierarchical two-stage approach involving anticipation components aligning the first-stage solution with aspects relevant to the second-stage problem.

The experimental results based a case study with real-world data involving a planning horizon of 30 days, 1088 treatments and 302 ward stays of 286 patients show that our approach is capable of obtaining high-quality solutions within a reasonable amount of time: even the most complex instances in which the admission days of the patients can be freely chosen can be solved within less than 90 min. Furthermore, the detailed evaluation shows that our model is capable of considering different scenarios such as achieving a smooth allocation of resources over the planning horizon and establishing a high resource allocation in the beginning of the horizon.

The results presented in this paper offer multiple opportunities for future research: The robustness of the schedules obtained with our approach could be assessed by a simulation study accounting for sources of uncertainty such as such as emergency patients, stochastic treatment times and short-term resource unavailability. Moreover, evaluating our approach in additional settings would be instrumental for understanding in how far the results presented in this paper can be generalized. From a practical perspective, the main goal of our efforts is to embed our model into the information systems of our partner university hospital to provide decision support for hospital-wide scheduling of clinical pathways. While we are aware that this goal is presently out of reach mainly due to the present organizational structure in hospitals and due to a lack of integrated information systems, we believe that providing an approach that is data-driven and considers many practically relevant aspects is a step in the right direction.