WIXLIB

2simulation results that have been obtained, thereby limiting theirof the time, for no more than 8 hours per day;”value. Prior work on resource scheduling has not accounted for accurately models resource interactions, and the resourcethe detailed models of resources, and constraints on those rescheduling interplay in simultaneously scheduling all resources necessary to model complex, human-intensive systems.sources, accounting for all relevant constraints; andQueuing models, for example, have only partially addressed allows flexibility in which system properties are optimized,variations in resource load [13], [16], [19], [20], [21], and canincluding often conflicting measures.not apply to the flow of complex systems [6], [9], [14]. In viewWhile our technique is general and applies broadly to resourceof these concerns, our work has focused on the development dependent systems, for exposition and evaluation, we focus inand application of discrete-event simulations that account for this paper on healthcare systems, and, in particular, on hospi(1) detailed process models that include specifications of how to tal emergency departments (EDs). EDs, like many resourcedeal with such complications as concurrency and responding to dependent systems have significant constraints on their resourceexceptional conditions, (2) detailed specifications of the charac- use, and variability in system requirements. For example,teristics of resources (including human resources) and the ways EDs commonly have five-fold variation in patient arrival ratesin which their efforts are applied to process performance, and throughout a 24-hour period, and staffing and resource schedul(3) specifications of how system load can be expected to vary ing decisions need to be responsive to such variation whileover time.simultaneously considering the impact on conflicting objectives,Specifically, this paper presents a novel approach for creat- such as patient waiting time, utilization of the doctors and nurses,ing precise and detailed discrete-event simulations of complex, delays in care, and staffing costs.human-intensive systems and their performance in resourceWe evaluate our scheduling approach by applying it to deconstrained environments. Our approach consists of three steps. tailed models of EDs. The approach identifies several interestingFirst, the approach uses discrete-event simulation to compute findings. First, staffing composed of variable-length shifts thatresource requirements, such as how many of each resource are are allowed to overlap requires less staff salaries, and enablesnecessary to be present at each time in the discrete-event simu- greater staff utilization. Second, staffing composed of long,lation to meet user-specified resource utilization requirements. single-length shifts that do not overlap (i.e., start at the sameSecond, our approach uses deterministic integer linear program- time), results in fewer patient handoffs (the transitioning of aming (ILP) to produce a resource schedule that satisfies those patient’s care to a new nurse or doctor) but incurs significant deresource requirements and user-specified constraints on resource viations from desired utilization ranges. Allowing flexible shiftutilization. Third, our approach again uses the discrete-event start times significantly reduces this problem. Further, while thesimulation to compute how the resource schedule affects statisti- increase in handoffs incurred by overlapping shifts increases thecal estimates of the system’s runtime properties. Our approach patient length of stay, that increase is only marginal.combines the rigor of mathematical programming with the comOur approach enables not only computing resource schedplex detail and realism of a discrete-event simulation. While ules, but also exploring how constraints, requirements on theprevious projects have developed and applied discrete-event sim- resources, and allocation policies impact critical system propulation based on detailed models of processes and resources, our erties. In the ED domain, the approach enables exploring, in awork is unique in the breadth and depth of detail in the models, principled manner, the effects of doctor and nurse assignmentand the incorporation of resource constraints. As a result, our policies, patient admittance policies, shift scheduling policies,approach more accurately models human-intensive systems, par- requirements on a single doctor and nurse handling all of a paticularly under resource-constrained conditions, and allows for tient’s procedures, on the length of stay of the patient, patientprecise measurements of system properties and developing re- handoffs, hospital financial efficiency, etc.source requirements and schedules that optimize a wide varietyThe rest of the paper is organized as follows. Section 2of objectives.provides a detailed review of the relevant research. Section 3The main contributions of our work are a novel approach for presents the methodological details of our simulation optimizausing discrete-event simulation and integer programming to ana- tion approach, first overviewing the discrete-event simulation enlyze complex, human-intensive systems and develop resource gine, then describing the integer linear programming formulationschedules in resource-constrained environments, and an evalu- and the scheduling algorithm, and finally, using the simulationation of this approach in the healthcare domain. Our approach optimization framework. Section 4 evaluates our approach byis mathematically rigorous and precise. Unlike prior work, our applying it to the ED scenario and (1) computing the hourly staffapproach:utilization, and (2) the interplay between utilization, staffing incorporates constraints on the resources, and their capabil- costs, length of stay, and handoffs. Finally, Section 5 summaities, use, and allocation policies;rizes our contributions and future research directions. handles the complex realism of real-world, resourceconstrained systems, including multiplicity of resources,time-varying events that trigger resource requirements, de- 2 R ELATED W ORKtailed processes of resource use, and empirically derived, The problem of scheduling resources in complex environmentsstochastic time distributions of durations of process steps; has been extensively studied, with a considerable focus on hos accounts for a desired, target resource utilization rangespital emergency department operations. This section describesand constraints on resources scheduling, such as “resources this prior work, and its limitations. Overall, despite the largeof a given type may only be utilized between 60% and 75% number of these prior studies, in our view, none of them has

SHIN et al.: DISCRETE-EVENT SIMULATION AND INTEGER LINEAR PROGRAMMING FOR CONSTRAINT-AWARE RESOURCE SCHEDULINGattempted to model all of the relevant aspects of the schedulingproblem simultaneously, and in sufficient detail.Bergh et al. [10] provide a comprehensive literature surveyof personnel scheduling problems. They examined 291 relevantarticles published from 2004 to 2012, and found that 93 of thesepapers are related to healthcare. Their work indicates that thestaffing problem in healthcare has been widely studied, but thatmany issues remain to be addressed adequately. These issuesinclude: (1) Lack of integration of the dynamic complexityof the staffing, such as demand forecasting, hiring and firing,machine scheduling, and multiple hospital locations. (2) Lack ofintegration of the details of the staff, such as differences in skills,flexibility in contracts, and breaks. (3) Lack of considerationfor the staffing and equipment constraints. (4) Not handlinguncertainty sources, such as nondeterminism in decision making,in scheduling, and in the demand. (5) Insufficient testing of therobustness of solutions to noise, uncertainty, schedule flexibility,etc. (6) Consistent lack of implementation and empirical studyof effects of the proposed algorithms. (7) Lack of scientificcomparison between the approaches.Analytical approaches are widely used in studying ED staffing,since closed form expressions are relatively easy to calculate andrequire less data than simulation approaches. Green et al. [14]show how queuing models work effectively to create staffing forvarious patient arrival rates in an ED. Their work focuses on thetime lag between a patient’s arrival and their actual treatment.While a useful rough-cut approach, this work simplifies the EDcare process considerably, and only calculates the physicianschedules. By contrast, our approach accounts for the fact thatpatients with different acuities have different care needs, that thepatient care process consist of multiple steps, and that nurse andother resources’ schedules also affect lag times.Cochran et al. [6] introduce a multi-class queuing networkanalysis for the capacity planning of both beds and staff. Theirapproach incorporates five types of patients characterized byresource utilization and priority, non-exponential service timedistributions, and nine patient care areas. Based on their queuingnetwork, they can determine staff level for each area to satisfya quality measurement, such as the number of patient walkouts. This work does not take into account the need to schedulephysicians, nurses, and equipment simultaneously, and insteaduses statistical service time distributions, which we believe is aless accurate scheduling method than our approach.Li et al. [18] propose an analytical framework that modelsthe complexity of an ED by incorporating a variety of flowcontrols, such as split, re-entrant, closed, and parallel queueing.The paper presents a method for redistributing limited resourcesand mitigating bottlenecks. However, the approach proposedby Li et al. does not go as far as our approach in modeling thecomplexities of the ED. For example, their approach does notmodel constraints that patients need to be cared for by the samephysician and nurse — at least until the end of that physician’sand nurse’s shifts.Many researchers have noted the need to model multiple,complex constraints to schedule ED resources accurately. Somehave even stressed the need to model variations in numbers ofworking hours per week, days-off regulations, and staff salaries.Carter et al. [5], for example, address the problem of scheduling3ED physicians in the presence of real-world constraints from sixhospitals in the greater Montreal, Canada area. They attemptto create schedules that improve the quality of patient care,while satisfying physicians’ vacation schedule requirements andassuring that there is a minimum of 16 hours between any pairof a physician’s shifts. However, this work neither considers thesimultaneous scheduling of other resources, such as nurses andclerical assistants, nor more complicated sets of constraints, andit is unclear if it can be extended to handle those two commonfeatures of EDs.As with our approach, Brunner et al. [3], [4] study the possibility of scheduling flexible shifts for physicians. Their work allowsfull flexibility of shift starting times and shifts lengths, and includes the assignment of breaks and the use of planned overtime,while conforming to constraints defined as part of general laboragreements. Ferrand et al. [12] provide a method to build cyclicphysician schedules that can be repeated throughout the year.Their schedules can incorporate holidays, work assignments,and vacation requests. Stolletz et al. [27] introduce an optimization technique to schedule physicians with flexible shifts. Theirapproach supports balancing the work times and the number ofon-call service assignments over all physicians. Kazemian etal. [17] introduce a deterministic integer-programming-basedhealthcare provider shift design to minimize patient handoffs.While considering complex shift constraints, unlike our work,all of these approaches rely on relatively coarse approximationsof ED processes, and ignore the scheduling of nurses and clerical workers. These factors can greatly affect key ED measures,such as patient waiting time and staff utilization, which puts intoquestion the applicability of these approaches in the real world.Understandably, it is difficult to incorporate the full rangeof the complex issues arising in ED resource scheduling intoanalytical models. Hence, discrete-event simulation has beenwidely used in studying ED resource allocation [1], [7], [11],[22], [23], [25], [26]. Wang et al. [29] use a simulation modelto identify potential changes in operational policies to reducepatients’ length of stay. They suggest reassignment of nursejobs, combining registration with triage, adding float nurses,mandatory requirement of physician’s visit within 30 min, andthe simultaneous improvement of durations of the most sensitiveprocedures to decrease the length of stay. Zeng et al. [31] usea simulation model to study the ED of a community hospital.Based on their sensitivity analysis, they suggest that addingnurses and CT scanners can reduce patient waiting times andlength of stay. They also suggest that a team nursing policy(creating pooled capacities) can significantly improve ED efficiency. Brenner et al. [2] use simulation to identify bottlenecksand investigate the optimal numbers of human and equipmentresources.In contrast to our work, these discrete-event simulations donot model time-varying arrival rates, which are particularly important to the accuracy of staffing models. We use a combinationof integer linear programming and discrete-event simulation tosupport resource scheduling in the presence of time-varyingarrival rates. Sinreich et al. [8] also propose the combinationof discrete-event simulation and integer programming to studystaff scheduling, using simulation to first identify the bottleneckresource and the required number of units of this resource, and

4then reschedule the start times of the bottleneck resource’s shifts have not considered variable arrival rates. Some support minimalto better fit the resource requirements. Iterating the steps of (or no) resource utilization constraints. Some have failed toidentifying a bottleneck resource and optimizing the resource’s consider the effects of one resource type on another. Some relyshift start times can approximate the optimal staffing of the re- on coarse process models that poorly describe the patient caresources. This paper also presents an algorithm for transferring process, or simplistic resource models that poorly describe theshifts between similar resources, such as fast-track physicians complexity of the involved resources. Our work builds on theseand surgical physicians, to improve staffing of the bottleneck earlier efforts by addressing these shortcomings. In our work, weresource. However, in scheduling one resource at a time, this combine unusually detailed models of processes and resources,approach does not, for example, take into consideration complex a highly flexible approach to specifying constraints, variableinteractions between resources. By contrast, our work sched- arrival rates, and flexibility in human resource shift policies.ules multiple resources simultaneously, accounting for interactions between resources, and procedures that require multiple, 3 A PPROACHconstrained resources. Additionally, unlike Sinreich et al.’s apAs indicated above, our work centers on using a powerful capaproach, our work allows more flexibility in shifts than fixed,bility for simulating the operations of a hospital ED. We begin8-hour shifts.this section with a detailed explanation of this simulation capabilIzady et al. [15] propose a heuristic iterative approach to deterity, focusing first on our approaches to specifying the ED processmining the minimal hour-by-hour staff levels needed in an ED.and the ED resources, and then focusing on incorporating intoTheir approach combines a queueing model of non-stationaryour simulations various constraints and context conditions.infinite server networks, the square root staffing law, and simulation to achieve the UK government target that 98% of patientsshould be discharged, transferred, or admitted within 4 hours of 3.1 ED Process Modelingtheir arrivals. Their technique first calculates required staffing Our approach falls broadly under the heading of model-basedlevels using an offered load analysis [21] and the square root simulation, centering on the use of a detailed model of the prostaffing law [16] with non-stationary infinite server networks. cess by which patients are treated in an example ED. We usedThen, the technique uses simulation to test if the derived staffing the Little-JIL language to create this model. Little-JIL processsatisfies the government target. If it does not, the technique definitions are based upon the notion of functional decomposireruns the algorithm by adjusting the target delay probability of tion of a high level process into a hierarchy of steps. Little-JILa resource. While this approach incorporates multiple types of has well-defined semantics based upon finite state machine defiresources, interactions between resources, and different patient nitions, and is supported by a tool suite that includes a graphicalrouting based on the patient types, it takes into consideration editor that renders process definitions as visualizations such asonly a limited number of constraints that typically characterize is shown in Figure 1ED operations. For example, their model does not allow conThe central semantic element of a Little-JIL definition is thesideration of ED operations for which a patient must be cared step. Steps are connected by edges to parents (above) and chilfor by the same doctor and nurse that were assigned when the dren (below), with edges also specifying the flow of argumentspatient was first placed in a bed. In addition, this technique between parents and children. Parent steps both define scopes,does not support analysis of staff utilization under time varying and also specify the flow of control between children. The legarrival rates. By contrast, our approach handles both detailed end in Figure 1 indicates three different control flow possibilities:constraints and varying arrival rates.sequential (children performed in left-to-right order), parallelZeltyn et al. [30] use a simulation model of an ED to propose (children performed in any order, possibly concurrently), andstaffing levels over several different time horizons ranging from choice (only one of the children selected for performance). Eachseveral hours to several months. This work presents the modified step also incorporates a specification of needed resources (e.g.offered-load approximation staffing algorithm. The approach doctor, nurse, x-ray machine) to be allocated at run time (seefirst simulates ED models hypothesizing the availability of infi- Figure 3). It is useful to note that these specifications can setnite resources to estimate the workloads of busy resources, and up contentions that can further constrain execution order, forthen uses these estimates to calculate staffing demands through example by making concurrent performance either possible oroffered load analysis, finally evaluating the through simulation. impossible.The simulation-based offered load analyses show significant imOur ED process model was developed based on the adviceprovements over a commonly used, rough cut capacity-planning of a domain expert with extensive experience as an emergencytechnique [28], as measured by waiting time to be first seen by a physician and ED manager at the Baystate Medical Center, inphysician. However, by contrast to our approach, this work only Springfield, MA, USA. Figure 1 illustrates one small part ofon finding staffing demand levels, and has not used to study the this very detailed process definition, namely the patient testinginfluence of variability in shift starting times and shift lengths. process for an acuity-level-four patient. Thus, Figure 1 specifiesIn addition, this work does not provide insight into resource that AL4Test is a parallel step, which means that a lab testutilization levels.process, AL4LabProc, can be performed in parallel with theIn summary, previous work has made various simplifying other tests, although contention for needed resources (in thisand restrictive assumptions in studying how resource utilization case the patient) may make concurrency impossible. As noted inapproaches affect such key quality measures as patient waiting the legend of Figure 1, steps may have prerequisites that may betime and resource utilization levels. Some of these techniques used by our simulations to specify the relative frequency with

SHIN et al.: DISCRETE-EVENT SIMULATION AND INTEGER LINEAR PROGRAMMING FOR CONSTRAINT-AWARE RESOURCE SCHEDULING5also makes it easy to represent places where agents (especiallyhuman agents) are able to use their judgment to make choices,and what these choices are. As just noted, Figure 3 shows therepresentation of the doctor‘s ability to choose either a CT or anX-Ray for the patient. In addition the choice step was useful inconcisely and precisely defining the way in which patients aretriaged by a triage nurse (TrRN). In this case, the TrRN assignseach patient a bed-placement triage level (an integer between1 and 5), which is an output from the step performed by theTrRN. This assigned triage level is then used as an input to a bedallocation step, which uses the TrRN‘s judgment to determinewhether a bed is to be allocated now, or whether the allocationis to be deferred.Concurrency: Some steps in some of the treatment processescan be performed in parallel, and, indeed, further concurrencyarises because the entire treatment process is performed once foreach patient in the ED. This creates the potential for contentionfor resources such as MDs, RNs, and X-Ray machines, andmakes the clear and precise specification of the exact nature ofthe concurrency particularly important. The Little-JIL parallelstep makes it quite easy to specify this concurrency, and supportsa very clear visual depiction of the concurrency that seemsreadily accessible to our ED domain experts.Fig. 1. The Little-JIL definition of the patient testing process,Exception Management: Emergency Department operationswhich is part of the care an acuity-level-four patient undergoes in rarely follow a straight path through predefined sequences ofan EDsteps. Instead exceptional and non-nominal situations arise continually. Thus, for example, the lack of needed resources (e.g.beds, nurses) may necessitate changes in treatment sequences orwhich exceptions should be thrown, or which of the alternatives substitution of resources, and treatment procedures that provespecified as the children of a choice steps is the one that should ineffective may necessitate new diagnostic procedures and diagbe selected. Thus, the pre-requisite on AL4LabProc means that noses. The Little-JIL exception management facilities, featuring92% of acuity-level-four patients require the lab test. For the scoped handling of typed exceptions has proven to be particother tests, a nurse checks a patient’s ECG first, RNECG, and then ularly effective in defining clearly and precisely even difficulta doctor checks the ECG result, MDCkECG, because AL4ECGProc exception management scenarios.controls its child steps sequentially. After the ECG test, a nurseOur full detailed process definition contains 164 steps (ofgives a medication to the patient, RNMedHi, and then the patient which Figure 3 depicts only a small part). While this seems to bewill be transferred to either the CT or the x-ray room. This a large number of steps, our view is that it is a relatively modestbehavior is represented by the AL4XrayOrCTOrNothing choice number in view of the size and complexity of the ED processstep which means only one of its child steps will be executed, that is defined.with the choice being made by the agent who performs the parentstep.The use of Little-JIL to define the Baystate ED process has 3.2 ED Resource Modelingmade it quite easy to define and represent visually some chal- While the clear and precise representation of ED process stepslenging, yet key, features of the process. Thus, for example:and artifact flows is clearly a key challenge in this work, ourAllowing For Process Variation: The Little-JIL choice step view is that the clear and precise representation of resources is

Constraint-Aware Resource Scheduling Seung Yeob Shin, Hari Balasubramanian, Yuriy Brun,Philip L. Henneman, Leon J. Osterweil . on the state of the art by enabling using detailed resource and constraint specifications effectively to support analysis and decision-making about complex processes in domains that currently rely largely on trial .