# Emergency Department Staffing: A Separated Continuous Linear Programming Approach

Authors: Xiaoqing Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The emergency department (ED) overcrowding is becoming serious in recent years. The shortage of ED staff is considered to be a common factor to contribute to the ED overcrowding. In this paper, we present a new model to address the ED staffing from a macroscopic perspective. The model is a kind of optimization model called separated continuous linear programming (SCLP). By using the efficient algorithm for SCLP, we can get the ED staffing level which minimizes the total cost of the patients and the ED.


---

## Body

## 1. Introduction

Emergency medical service is an important part of medical and health care systems. Its quality of service and availability directly affect the quality of health care. In recent years, the emergency department (ED) in many hospitals has experienced overcrowding [1, 2], and patients, health care workers, and hospitals in which the ED exists are adversely affected.ED overcrowding leads to the delay in the assessment and treatment of patients [3], including the delay in hospitalization. Long residence time in ED adds additional pain, burden on patients and sometimes even leads to the unexpected death.ED overcrowding makes health care workers overworked [4] and greatly influences their enthusiasm for work and efficiency in work, the chances of medical errors and medical disputes increasing. At the same time, ED overcrowding also affects the normal operation of the entire hospital in which the ED exists, leading to a longer hospitalization time for the emergency patients and lowering the capability of the hospital to meet the need for hospitalization of other nonurgent patients.Many problems lead to ED overcrowding; one of them is the shortage of physicians to meet the fast-growing demand for ED. There are several reasons for the shortage of physicians; one of them is the high operational cost of ED. Physician salaries represent a large part of the operational cost in ED and there is not enough motivation for the hospital to improving their service by increasing the amount of physicians in ED in the past. The increasing degree of ED overcrowding in recent years introduces so many troubles to the hospitals and the management authority in hospitals found that they have no other choice but trying to find effective methods to alleviate ED overcrowding. Obviously, improving the quality of ED staffing decision is one approach. The management authority wants to know the least amount of physicians ED needs to provide improved quality of service, so that the degree of ED overcrowding can be alleviated to an acceptable level.In recent years, research efforts are made to improve the ED staffing. This paper provides a new approach to balance the waiting cost of the patients and the operational cost of the EDs. The objective is to find an appropriate amount of physicians and their scheduling which can meet the ED demand with the least total cost of the patients and the EDs. The advantage of our approach is that the time needed to find the ED staffing level is shorter compared with the existing methodologies. Also, we do not make strong assumptions on the distribution of the arrival rate and the distribution of the service time of the demand to ED.The paper is organized as follows. In Section2, we provide a literature review on ED staffing; we also give a brief introduction to separated continuous linear programming (SCLP) on which our approach is based. In Section 3, we describe the emergency service process that we focus on. In Section 4 we construct an SCLP model to minimize the total cost of patients and the ED given a specific ED staffing level. We then solve the SCLP model with varying staffing level in ED and finally find the appropriate staffing level which results in the least total cost of patients and the ED among the possible staffing levels. In Section 5, we summarize what we get and point out some future research directions.


## 2.  The Literature Review

### 2.1.  Literature on ED Staffing

There are two main research methodologies to tackle the staffing in ED. One is simulation and the other is the stochastic models based on the queueing theory.The most commonly used research method for ED staffing is simulation [5]. The reason is that the ED of a modern hospital is a highly complex system and it is difficult to use the analytic model to describe the dynamic ED reality accurately. Simulation offers a natural framework to address this issue within. Simulation models often possess high validity because they track true system behavior fairly accurately, but they yield fewer analytic inference than that of analytic models because they take both input parameters and decisions as fixed. A lot of experiments need to be performed before an approximate optimal solution can be found, and the gap between the approximation optimal solution and the true optimal solution is unknown. Also, the approximate optimal solution obtained is just a numerical solution and we have no knowledge on the interactions among ED staffing and other managerial decisions, thus makeing it difficult to pinpoint the relationship between the staffing level and the quality of service in ED.On the other hand, although analytic models can never capture all characteristics of an actual ED process, stochastic models, based on queuing theory, are more appropriate for capturing the volatile and inherently nondeterministic ED reality, and they can be invaluable in providing managerial insight that greatly improves performance of the ED process [6]. Although the operation in ED is very complex, many researchers try to focus on the most important parts of the ED process and build simpler stochastic queueing models to study the ED staffing. These models strive to seek a balance between the tractability and validity and get some valuable results [5, 7–9].There are three important characteristics of the demand of EDs. Firstly, the arrival rate of the patients has significant variation over the time-of-the-day, day-of-the-week, and month-of-the year, that is, time-varying arrival rate. Secondly, the patients are prioritized into emergent, urgent, and nonurgent categories by use of triage upon arrival, that is, multiclass customers. Thirdly, the patients usually visit the physician several times during their sojourn time in the ED before they are discharged or hospitalized, that is, customer feedback.Zeltyn et al. [5] use simulation-based models to address the ED staffing with time-varying demand. They incorporate the offered-load technique and classical square-root safety-staffing principle which are based on the M/M/s queueing model. The staffing recommendations they provided are implemented by a large Israeli hospital and get the satisfactory results.Green et al. [8] use the M/M/s queueing model as part of a Lag stationary independent period by period (SIPP) approach to determine how to vary staffing level to meet changing demand in an urban hospital ED in the United States. Their staffing recommendations have been implemented in that ED and as a result the proportion of patients who left without being seen (LWBS) decreases significantly.Recently, Yom-Tov and Mandelbaum [9] analyze a queueing model that they call Erlang-R, where the “R” stands for ReEntrant customers, to accommodate the phenomenon that the patients return to physician several times during their sojourn within the ED. They propose time-varying square-root staffing policy which is based on the modified-offered-load and Erlang-R model. They use simulations to verify that their staffing recommendations work well in the ED settings.One of the problems for the queueing model approach is that some special distributions for patient arrival and service process, such as the Poisson arrival and exponential service time, and some working discipline, such as First-Come-First-Serve (FCFS), need to be assumed in order to get the explicit closed-form expression for some quality measures (e.g., the fraction of patients who LWBS in an ED) on the ED service. But these assumptions do not always agree with reality.The purpose of the present paper is to introduce models for dynamic ED staffing without explicitly calculating the quantities of interest like patients' waiting time, the fraction of patients who LWBS, and so forth, and rather developing models directed towards using efficient algorithms to handle these quantities. We do this by looking at the ED system from a macroscopic perspective and use fluid network to approximate the overloaded ED system. From our knowledge, there is no other work tackling the ED staffing by using this approach.


### 2.2.  A Brief Introduction to SCLP

Linear programming (LP) is probably the most successful mathematical model in terms of its extremely wide range of industrial applications and its superb speed and capacity in solving very large size problems. For this reason, LP has been pushed and extended to an ever-broadening frontier. One of such frontier extensions is the so-calledseparated continuous linear programming (SCLP) which was first introduced by Anderson [10] who used it to model the job-shop scheduling problem. The following is the SCLP due to Weiss [11]:
(1)(SCLP)max∫0T‍[(γ+(T-t)c)′u(t)+d′x(t)]dts.t.∫0t‍Gu(s)ds+Fx(t)≤α+ta,000000Hu(t)≤b,000000u(t)≥0,x(t)≥0,t∈[0,T],
where u(t), x(t) are decision variables and are assumed to be bounded measurable functions with the measure of the break-point set being 0. γ,c,d,α,a,b are vectors, G,F,H are matrices. ′ denotes the transpose operation. The word “separated” refers to the fact that there are two kinds of constraints in SCLP: the constraints involving integration and the instantaneous constraints [10].SCLP has in recent years attracted considerable research attention in the field of stochastic networks, a part of queueing theory. The multiclass stochastic network is a system consists of different classes (types) of jobs which need to be processed and a set of servers which process the jobs. Jobs arrive to the system randomly. Each server can process one or more classes of jobs and the processing time for every job is different for different class of jobs. The jobs in the same class have the same characteristics such as arrival rate and service requirements. After one job is processed in one server, it may leave the network instantaneously or may become another class of job and go to another server for processing. The multiclass stochastic network is a very useful model for many real systems.For each multiclass stochastic network, there is a corresponding deterministic fluid network, which takes only the first-order data (means and rates) from the stochastic model and assumes that the jobs circulating in the network are continuous flows instead of discrete units. With appropriate scaling, the fluid network is a limit of the stochastic network, in the sense of strong law of large numbers (refer to, e.g., [12]). Furthermore, the fluid model has played a central role in studying the stability of stochastic networks [13]. Because of these developments, the real-time control (dynamic scheduling) of a stochastic network, which is itself a quite intractable problem, can be turned into the control of a corresponding fluid network, and the latter problem takes exactly the form of SCLP. We will show in Section 4 that the problem of finding the dynamic control of the patient flow, subproblem of optimizing the ED staffing, can be formulated as an SCLP (see (20) in Section 4).The dual of SCLP is the following problem:(2)(SCLP*)min∫0T‍[(α+(T-t)a)′p(t)+b′q(t)]dts.t.∫0t‍G′p(s)ds+H′q(t)-(γ+tc)≥0,000000F′p(t)-d≥0,000000p(t)≥0,q(t)≥0,t∈[0,T],
where the dual variables, p(t) and q(t), are bounded measurable functions.There exists the rich literature on duality theory and algorithms for solving SCLP. Interested reader may refer to [14] for the detailed review on the research results on SCLP. Specifically, Wang [15] suggested an algorithm which is a polynomial approximation scheme for solving SCLP. Because that algorithm is very efficient in terms of the computing time, we choose that algorithm to solve the model we propose in this paper. In the next Section 2.3, we will explain in detail how that algorithm works.


### 2.3. An Approximation Algorithm for SCLP

Before explaining the algorithm in [15], we first introduce some notations and conventions which we will use in the remaining part of this paper.(i)
By default, all vectors are column vectors. One exception is when we denote the solutions to the SCLP as(u,x), we mean (u′,x′)′.(ii)
π={t0,…,tm} denotes a partition of [0,T] into m segments:
(3)0=t0<t1<⋯<tm=T.
We use πm to denote π when all the interval lengths in π are the same.(iii)
Given a partitionπ={t0,…,tm} and a vector f^:=(f^(t0),f^(t1),…,f^(tm)), where f^(·) is a right continuous function, the following (continuous) function
(4)f(t)=(ti-tti-ti-1)f^(ti-1)+(t-ti-1ti-ti-1)f^(ti),fort∈[ti-1,ti],i=1,…,m
is called a piecewise linear extension of f^, whereas the following (right-continuous) function
(5)f(t)={f^(ti-1),t∈[ti-1,ti),fori=1,…,mf^(tm-1),t=T,
is called a piecewise constant extension of f^.(iv)
For problem(P), we use v(P) to denote the optimal objective value of (P).We start with introducing the following discretization of(SCLP) based on a partition of [0,T], π={t0,…,tm}:
(6)(LP1(π))max∑i=1m‍((γ+(T-ti+ti-12)c)′u^(ti-1)0000000000+d′[x^(ti)+x^(ti-1)]ti-ti-12(γ+(T-ti+ti-12)c)′)s.t.α+tia-[Gu^(t0)+⋯+Gu^(ti-1)00000000000000+Fx^(ti)]≥0,000000000000000i=1,2,…,m;000000(ti-ti-1)b-Hu^(ti-1)≥0,0000000000000000000i=1,…,m;000000u^(ti-1)≥0,x^(ti)≥0,0000000000000000i=1,…,m.
In addition, assume that
(7)α-Fx^(t0)≥0,x^(t0)≥0.The following Lemma and the algorithm presented later in this subsection are adapted from [15].Lemma 1.
Suppose that(u^,x^) is a feasible solution to (LP1(π)), with
(8)u^=(u^(t0),…,u^(tm-1)),x^=(x^(t1),…,x^(tm)).
Let u(t) be the piecewise constant extension of (u^(t0)/(t1-t0),…,u^(tm-1)/(tm-tm-1)), and let x(t) be the piecewise linear extension of (x^(t0),x^). Then, (u(t),x(t)) is a feasible solution to (SCLP), and the objective value of (u^,x^) in (6) is the same as that of (u(t),x(t)) in (1).The same discretization applies to(SCLP*), the dual problem. Specifically, corresponding to the partition π={t0,…,tm}, we have
(9)(LP2(π))min∑i=1m((α+(T-ti+ti-12)a)′p^(ti-1)‍0000000000+b′[q^(ti)+q^(ti-1)]ti-ti-12(α+(T-ti+ti-12)a)′)s.t.G′p^(t0)+G′p^(t1)+⋯+G′p^(ti-1)+H′q^(ti)-(γ+tic)≥0,00000000000000000i=1,…,m;00000F′p^(ti-1)-(ti-ti-1)d≥0,000000000000000000i=1,…,m;00000p^(ti-1)≥0,q^(ti)≥0,0000000000000000i=1,…,m.
In addition, assume that
(10)H′q^(t0)-γ≥0,q^(t0)≥0.We need the following assumption.Assumption 2.
The following two linear programming problems have optimal solutions:(11)(LP1)maxc′u+d′xs.t.α+Ta-Gu-Fx≥0,000000Tb-Hu≥0000000u≥0,x≥0,(LP2)mina′p+b′qs.t.G′p+H′q-(γ+Tc)≥0,000000F′p-Td≥0,000000p≥0,q≥0.Algorithm 3.
Letδ be the predefined precision between the objective value of the solution requested and v(SCLP).
Step  1. Check if Assumption 2 is satisfied. If yes, go to Step 2; otherwise, stop.
Step  2. Solving (T/2m)(v(LP1)-v(LP2)+b′q^(t0)-d′x^(t0))≤δ to get m (number of intervals in partition πm), find the optimal solution (u^*,x^*) for (LP1(πm)). Use the extension of this solution to construct a feasible solution for (SCLP). Stop.Note that the method to construct a feasible solution for(SCLP) from the extension of a feasible solution for (LP1(πm)) is mentioned in Lemma 1.To getm, we need to first solve the two linear programs (LP1) and (LP2). In addition, we also need to determine x^(t0) and q^(t0). This can be accomplished by solving the following two linear programs:
(12)maxd′x^(t0)s.t.α-Fx^(t0)≥0,000000x^(t0)≥0,minb′q^(t0)s.t.H′q^(t0)-γ≥0,000000q^(t0)≥0.After gettingm, we solve the linear program (LP1(πm)) to get a feasible solution for (SCLP) which satisfies the pre-defined precision δ.In summary, the previous Algorithm3 amounts to solving five linear programming problems: (LP1), (LP2), (12), and (LP1(πm)). Linear programs are known to be polynomially solvable. Hence, this algorithm is a polynomial-time algorithm.


## 2.1.  Literature on ED Staffing

There are two main research methodologies to tackle the staffing in ED. One is simulation and the other is the stochastic models based on the queueing theory.The most commonly used research method for ED staffing is simulation [5]. The reason is that the ED of a modern hospital is a highly complex system and it is difficult to use the analytic model to describe the dynamic ED reality accurately. Simulation offers a natural framework to address this issue within. Simulation models often possess high validity because they track true system behavior fairly accurately, but they yield fewer analytic inference than that of analytic models because they take both input parameters and decisions as fixed. A lot of experiments need to be performed before an approximate optimal solution can be found, and the gap between the approximation optimal solution and the true optimal solution is unknown. Also, the approximate optimal solution obtained is just a numerical solution and we have no knowledge on the interactions among ED staffing and other managerial decisions, thus makeing it difficult to pinpoint the relationship between the staffing level and the quality of service in ED.On the other hand, although analytic models can never capture all characteristics of an actual ED process, stochastic models, based on queuing theory, are more appropriate for capturing the volatile and inherently nondeterministic ED reality, and they can be invaluable in providing managerial insight that greatly improves performance of the ED process [6]. Although the operation in ED is very complex, many researchers try to focus on the most important parts of the ED process and build simpler stochastic queueing models to study the ED staffing. These models strive to seek a balance between the tractability and validity and get some valuable results [5, 7–9].There are three important characteristics of the demand of EDs. Firstly, the arrival rate of the patients has significant variation over the time-of-the-day, day-of-the-week, and month-of-the year, that is, time-varying arrival rate. Secondly, the patients are prioritized into emergent, urgent, and nonurgent categories by use of triage upon arrival, that is, multiclass customers. Thirdly, the patients usually visit the physician several times during their sojourn time in the ED before they are discharged or hospitalized, that is, customer feedback.Zeltyn et al. [5] use simulation-based models to address the ED staffing with time-varying demand. They incorporate the offered-load technique and classical square-root safety-staffing principle which are based on the M/M/s queueing model. The staffing recommendations they provided are implemented by a large Israeli hospital and get the satisfactory results.Green et al. [8] use the M/M/s queueing model as part of a Lag stationary independent period by period (SIPP) approach to determine how to vary staffing level to meet changing demand in an urban hospital ED in the United States. Their staffing recommendations have been implemented in that ED and as a result the proportion of patients who left without being seen (LWBS) decreases significantly.Recently, Yom-Tov and Mandelbaum [9] analyze a queueing model that they call Erlang-R, where the “R” stands for ReEntrant customers, to accommodate the phenomenon that the patients return to physician several times during their sojourn within the ED. They propose time-varying square-root staffing policy which is based on the modified-offered-load and Erlang-R model. They use simulations to verify that their staffing recommendations work well in the ED settings.One of the problems for the queueing model approach is that some special distributions for patient arrival and service process, such as the Poisson arrival and exponential service time, and some working discipline, such as First-Come-First-Serve (FCFS), need to be assumed in order to get the explicit closed-form expression for some quality measures (e.g., the fraction of patients who LWBS in an ED) on the ED service. But these assumptions do not always agree with reality.The purpose of the present paper is to introduce models for dynamic ED staffing without explicitly calculating the quantities of interest like patients' waiting time, the fraction of patients who LWBS, and so forth, and rather developing models directed towards using efficient algorithms to handle these quantities. We do this by looking at the ED system from a macroscopic perspective and use fluid network to approximate the overloaded ED system. From our knowledge, there is no other work tackling the ED staffing by using this approach.


## 2.2.  A Brief Introduction to SCLP

Linear programming (LP) is probably the most successful mathematical model in terms of its extremely wide range of industrial applications and its superb speed and capacity in solving very large size problems. For this reason, LP has been pushed and extended to an ever-broadening frontier. One of such frontier extensions is the so-calledseparated continuous linear programming (SCLP) which was first introduced by Anderson [10] who used it to model the job-shop scheduling problem. The following is the SCLP due to Weiss [11]:
(1)(SCLP)max∫0T‍[(γ+(T-t)c)′u(t)+d′x(t)]dts.t.∫0t‍Gu(s)ds+Fx(t)≤α+ta,000000Hu(t)≤b,000000u(t)≥0,x(t)≥0,t∈[0,T],
where u(t), x(t) are decision variables and are assumed to be bounded measurable functions with the measure of the break-point set being 0. γ,c,d,α,a,b are vectors, G,F,H are matrices. ′ denotes the transpose operation. The word “separated” refers to the fact that there are two kinds of constraints in SCLP: the constraints involving integration and the instantaneous constraints [10].SCLP has in recent years attracted considerable research attention in the field of stochastic networks, a part of queueing theory. The multiclass stochastic network is a system consists of different classes (types) of jobs which need to be processed and a set of servers which process the jobs. Jobs arrive to the system randomly. Each server can process one or more classes of jobs and the processing time for every job is different for different class of jobs. The jobs in the same class have the same characteristics such as arrival rate and service requirements. After one job is processed in one server, it may leave the network instantaneously or may become another class of job and go to another server for processing. The multiclass stochastic network is a very useful model for many real systems.For each multiclass stochastic network, there is a corresponding deterministic fluid network, which takes only the first-order data (means and rates) from the stochastic model and assumes that the jobs circulating in the network are continuous flows instead of discrete units. With appropriate scaling, the fluid network is a limit of the stochastic network, in the sense of strong law of large numbers (refer to, e.g., [12]). Furthermore, the fluid model has played a central role in studying the stability of stochastic networks [13]. Because of these developments, the real-time control (dynamic scheduling) of a stochastic network, which is itself a quite intractable problem, can be turned into the control of a corresponding fluid network, and the latter problem takes exactly the form of SCLP. We will show in Section 4 that the problem of finding the dynamic control of the patient flow, subproblem of optimizing the ED staffing, can be formulated as an SCLP (see (20) in Section 4).The dual of SCLP is the following problem:(2)(SCLP*)min∫0T‍[(α+(T-t)a)′p(t)+b′q(t)]dts.t.∫0t‍G′p(s)ds+H′q(t)-(γ+tc)≥0,000000F′p(t)-d≥0,000000p(t)≥0,q(t)≥0,t∈[0,T],
where the dual variables, p(t) and q(t), are bounded measurable functions.There exists the rich literature on duality theory and algorithms for solving SCLP. Interested reader may refer to [14] for the detailed review on the research results on SCLP. Specifically, Wang [15] suggested an algorithm which is a polynomial approximation scheme for solving SCLP. Because that algorithm is very efficient in terms of the computing time, we choose that algorithm to solve the model we propose in this paper. In the next Section 2.3, we will explain in detail how that algorithm works.


## 2.3. An Approximation Algorithm for SCLP

Before explaining the algorithm in [15], we first introduce some notations and conventions which we will use in the remaining part of this paper.(i)
By default, all vectors are column vectors. One exception is when we denote the solutions to the SCLP as(u,x), we mean (u′,x′)′.(ii)
π={t0,…,tm} denotes a partition of [0,T] into m segments:
(3)0=t0<t1<⋯<tm=T.
We use πm to denote π when all the interval lengths in π are the same.(iii)
Given a partitionπ={t0,…,tm} and a vector f^:=(f^(t0),f^(t1),…,f^(tm)), where f^(·) is a right continuous function, the following (continuous) function
(4)f(t)=(ti-tti-ti-1)f^(ti-1)+(t-ti-1ti-ti-1)f^(ti),fort∈[ti-1,ti],i=1,…,m
is called a piecewise linear extension of f^, whereas the following (right-continuous) function
(5)f(t)={f^(ti-1),t∈[ti-1,ti),fori=1,…,mf^(tm-1),t=T,
is called a piecewise constant extension of f^.(iv)
For problem(P), we use v(P) to denote the optimal objective value of (P).We start with introducing the following discretization of(SCLP) based on a partition of [0,T], π={t0,…,tm}:
(6)(LP1(π))max∑i=1m‍((γ+(T-ti+ti-12)c)′u^(ti-1)0000000000+d′[x^(ti)+x^(ti-1)]ti-ti-12(γ+(T-ti+ti-12)c)′)s.t.α+tia-[Gu^(t0)+⋯+Gu^(ti-1)00000000000000+Fx^(ti)]≥0,000000000000000i=1,2,…,m;000000(ti-ti-1)b-Hu^(ti-1)≥0,0000000000000000000i=1,…,m;000000u^(ti-1)≥0,x^(ti)≥0,0000000000000000i=1,…,m.
In addition, assume that
(7)α-Fx^(t0)≥0,x^(t0)≥0.The following Lemma and the algorithm presented later in this subsection are adapted from [15].Lemma 1.
Suppose that(u^,x^) is a feasible solution to (LP1(π)), with
(8)u^=(u^(t0),…,u^(tm-1)),x^=(x^(t1),…,x^(tm)).
Let u(t) be the piecewise constant extension of (u^(t0)/(t1-t0),…,u^(tm-1)/(tm-tm-1)), and let x(t) be the piecewise linear extension of (x^(t0),x^). Then, (u(t),x(t)) is a feasible solution to (SCLP), and the objective value of (u^,x^) in (6) is the same as that of (u(t),x(t)) in (1).The same discretization applies to(SCLP*), the dual problem. Specifically, corresponding to the partition π={t0,…,tm}, we have
(9)(LP2(π))min∑i=1m((α+(T-ti+ti-12)a)′p^(ti-1)‍0000000000+b′[q^(ti)+q^(ti-1)]ti-ti-12(α+(T-ti+ti-12)a)′)s.t.G′p^(t0)+G′p^(t1)+⋯+G′p^(ti-1)+H′q^(ti)-(γ+tic)≥0,00000000000000000i=1,…,m;00000F′p^(ti-1)-(ti-ti-1)d≥0,000000000000000000i=1,…,m;00000p^(ti-1)≥0,q^(ti)≥0,0000000000000000i=1,…,m.
In addition, assume that
(10)H′q^(t0)-γ≥0,q^(t0)≥0.We need the following assumption.Assumption 2.
The following two linear programming problems have optimal solutions:(11)(LP1)maxc′u+d′xs.t.α+Ta-Gu-Fx≥0,000000Tb-Hu≥0000000u≥0,x≥0,(LP2)mina′p+b′qs.t.G′p+H′q-(γ+Tc)≥0,000000F′p-Td≥0,000000p≥0,q≥0.Algorithm 3.
Letδ be the predefined precision between the objective value of the solution requested and v(SCLP).
Step  1. Check if Assumption 2 is satisfied. If yes, go to Step 2; otherwise, stop.
Step  2. Solving (T/2m)(v(LP1)-v(LP2)+b′q^(t0)-d′x^(t0))≤δ to get m (number of intervals in partition πm), find the optimal solution (u^*,x^*) for (LP1(πm)). Use the extension of this solution to construct a feasible solution for (SCLP). Stop.Note that the method to construct a feasible solution for(SCLP) from the extension of a feasible solution for (LP1(πm)) is mentioned in Lemma 1.To getm, we need to first solve the two linear programs (LP1) and (LP2). In addition, we also need to determine x^(t0) and q^(t0). This can be accomplished by solving the following two linear programs:
(12)maxd′x^(t0)s.t.α-Fx^(t0)≥0,000000x^(t0)≥0,minb′q^(t0)s.t.H′q^(t0)-γ≥0,000000q^(t0)≥0.After gettingm, we solve the linear program (LP1(πm)) to get a feasible solution for (SCLP) which satisfies the pre-defined precision δ.In summary, the previous Algorithm3 amounts to solving five linear programming problems: (LP1), (LP2), (12), and (LP1(πm)). Linear programs are known to be polynomially solvable. Hence, this algorithm is a polynomial-time algorithm.


## 3. The Emergency Treatment Process

The treatment process in ED constitutes a multiclass stochastic queueing network with feedback. In this network, patients arrive at the ED randomly. The critically ill patients get the medical service immediately after arrival. The other patients are assigned different priority to see the physician for the first time after triage. The service (treatment) time for each patient is random, and there are several possible outcomes after the patient sees the physician, including revisiting the physician after examination and/or testing, going to the emergency observation room (ER) within the ED (under the care of another group of physicians and nurses) or leaving ED (going home with medicine, moving to ward or dead). In the last two cases, we say the patientleaves the system. Figure 1 illustrates a simplified version of such an emergency treatment process in a typical ED which we will focus on in this paper.Figure 1
The emergency treatment process in a typical ED.In Figure1, Server 1 represents physicians for treatment (hereafter, doctors); Server 2 represents the physicians for examination and testing (hereafter, testing staff). The patients arriving at the ED from outside are classified into n classes after triage based on patients' health condition. The patients in the same class are assigned the same priority which is represented by the time deadline to see the doctor for the first time [16]; for example, class 2 patients are told after triage that they will see the doctor within 30 minutes; “30 minutes” here is the time deadline for class 2 patients and is the measure for the quality of service in a specific ED. Patients within each class are served on an FCFS basis. The critically ill patients will not queue in the network, the effect they impose on the network is occupying some critical resources, such as the physicians and the beds, during some time intervals.The patients queueing before Server 1 and waiting for their first time to see the doctor are said in theirfirst stage. After seeing the doctor, the patients either leave the system or enter their second stage—queueing before Server 2 and waiting for examination and/or testing. Upon getting their examination and/or testing results, the patients enter their third stage—queueing before Server 1 and waiting to see the doctor again. The patients leave the system (discharged or hospitalized) after they see the doctor for the second time.The physicians and nurses who are in charge of the service within the ER are usually another group of staff. Their staffing is not the subject of this paper and we do not include the service process within the ER in Figure1.


## 4. Mathematical Model for ED Staffing

We consider the ED staffing within a time interval[0,T]. The criterion for the appropriate ED staffing level is that the total cost for patients and the ED within the time interval [0,T] is minimized. This criterion includes the quality of service requirement in ED by explicitly considering the waiting cost of patients. By balancing the cost of patients and that of the ED, we want to find an ED staffing level to cope with the time-varying demand for the ED service, which can balance the quality of service requirement and the utilization of the ED staff.We address the ED staffing problem by two steps. In the first step, we construct the queueing model to determine the appropriate scheduling policy for patients to minimize the waiting cost of patients given a specific ED staffing level. The queueing model is an SCLP and we can solve it efficiently by using the algorithm described in Section2.3. In the second step, by varying the ED staffing level in the SCLP, we can find the least staffing level for the ED which minimize the total cost of patients and the ED for the time interval [0,T].In building the analytic model of the ED system, one needs to decide how detailed does the description of the system have to be? The more microscopic the model is, the more accuracy is achieved, but on the other hand, usually the harder it is to handle analytically [17]. In this paper, we choose to view the ED system in a more macroscopic way. We use the deterministic fluid model to describe the performance of the overloaded ED systems. The use of the fluid model in overloaded system is justified in a number of papers, for example, in Whitt [18, 19]. The patients who left without being seen are ignored, and the ED systems try hard to accommodate the patients who wait until seeing the physicians.In the ED process that we focus on, the arrival rate of the patients and the service time of the patients are random variables; instead of assuming that the arrival rate or the service time obeys some particular distributions (as those in the previous papers [5, 7–9]), we only take the first moments (means of the arrival rate and the service time) to describe these randomness.Specifically, the corresponding fluid network for the ED treatment process in Figure1 is as follows: the patients in the ED are regarded as continuous fluid instead of individual person. The arrival rate and the service time of the fluid in each server are deterministic. After visiting Server 1, the fluid proceeds to Sever 2 with deterministic percentage (probability). The fluid which do not proceed to Server 2 exits the network. After visiting Server 2, the fluid continues to visit Server 1 again. The fluid exits the network after visiting Server 1 in the second time.Letλi(t) denote the arrival rate of class i patients from outside at time t. The mean service time for class i patients in their stage 1 is ηi. After receiving service from Server 1, the class i patients will enter their second stage and queue before Server 2 with probability pi, or leave the system with probability 1-pi. The mean service time for class i patients in their second stage is γi. After receiving service from Server 2, the class i patients enter their third stage and queue before Server 1 again, and the mean service time for them is μi.The service capacity of each doctor or testing staff is 1. Letsj denote the number of doctors or testing staff in Server j and let bj(t) denote the service capability of Server j at time t for patients in the queues. If the critically ill patients show during [0,T], they will occupy some capacity of Server j and subsequently bj(t) becomes kjsj, kj∈[0,1), where the value of kj depends on the condition of the critically ill patients. If no critically ill patients show during [0,T], bj(t) is simply sj.Letωij denote the waiting cost of class i patients in their jth stage (including the cost for the waiting time and the cost of patients' health condition changes due to the long waiting time, e.g., the additional financial cost). ωi1 should be big enough to reflect the cost for different class patients in order to guarantee that each patient in his first stage can get service within the time deadline the ED promises. Usually a senior physician in an ED can tell the approximate waiting cost for a specific class of patients in their specific stage and we can use this piece of information to determine the value of ωij's. Let cj denote the service cost for each doctor or each testing staff in Server j. The estimation of the ED's operational cost is relatively straightforward because the salaries paid to the physicians constitute most of the ED operational cost. So we can use the physicians' salaries to represent the service cost of an ED.Letaij denote the amount of class i patients in their jth stage at time 0.The following is the fluid model which determines the optimal scheduling policy for patients with the objective of minimizing the waiting cost of patients given a specific ED staffing level:(13)Model1:Q(s1,s2)=min∑i=1n‍∑j=13‍(∫0T‍ωijxij(t))dt+c1s1+c2s2(14)s.t.xi1(t)=ai1+∫0t‍λi(s)ds-∫0t‍ui1(s)ds,i=1,…,n,(15)xi2(t)=ai2+pi∫0t‍ui1(s)ds-∫0t‍ui2(s)ds,i=1,…,n,(16)xi3(t)=ai3+pi∫0t‍ui2(s)ds-∫0t‍ui3(s)ds,i=1,…,n,(17)∑i=1n‍(ηiui1(t)+μiui3(t))≤b1(t),(18)∑i=1n‍γiui2(t)≤b2(t),(19)uij(t),xij(t)≥0,i=1,…,n,j=1,2,3,t∈[0,T],
where xij(t) is the state variable and represents the amount of class i patients in their jth stage at time t, uij(t) is the control variable and represents the service rate for class i patients in their jth stage at time t, i=1,…,n, j=1,2,3.  s1, s2 are the numbers of doctors in Server 1 and testing staff in Server 2, respectively.The objective of (13) is minimizing the total cost for patients and the ED within the time interval [0,T].The first three sets of constraints describe the dynamic of the ED service process, that is; how the state variablesxij(t) are changing with the changing of the control variables uij(t).The constraint (14) states that the amount of class i patients in their first stage at time t is equal to the summation of the amount of class i patients in their first stage at time 0 and the amount of class i patients arrived from outside lessing the amount of class i patients serviced by Server 1 and exit their first stage during time interval [0,t].The constraint (15) states that the amount of class i patients in their second stage at time t is equal to the summation of the amount of class i patients in their second stage at time 0 and the amount of class i patients who enter their second stage lessing the amount of class i patients serviced by Server 2 and enter their third stage during time interval [0,t].The constraint (16) states that the amount of class i patients in their third stage at time t is equal to the summation of the amount of class i patients in their third stage at time 0 and the amount of class i patients who enter their third stage lessing the amount of class i patients serviced by Server 1 and exit their third stage during time interval [0,t].The next two sets of constraints are the service capacity constraints. The constraint (17) states that the total capacity consumed by the patients in their first and third stages cannot exceed the available capacity of Server 1, and the constraint (18) states that the total capacity consumed by the patients in their second stage cannot exceed the available capacity of Server 2.Although there are time-varying parameters in Model 1, that is,λi(t), bj(t), we can assume that within the sufficient short time interval, for example, within one hour, those parameters can be regarded as constants. This assumption is justified by the statistical analysis of the ED treatment process [9]. Because of this, we can choose a sufficient small T and replace λi(t), bj(t) with λi, kjsj, respectively, when t∈[0,T]. Here, kj can be specified based on the statistical information on the type and arrival rate of critically ill patients during [0,T]. With these simplifications, Model 1 reduces to the following SCLP problem:(20)max∫0T‍[(-ω11-ω12-ω13⋯-ωn1-ωn2-ωn3)′x(t)]dt+c1s1+c2s2s.t.∫0t‍(-1p1-1p1-1⋱-1pn-1pn-1)u(s)ds+(-1-1-1⋱-1-1-1)x(t)=(-a11-a12-a13⋮-an1-an2-an3)+t(-λ100⋮-λn00),0000000(η10μ1⋱ηn0μn0γ10⋱0γn0)u(t)≤(k1s1k2s2),0000000u(t)≥0,x(t)≥0,t∈[0,T],where
(21)u(t)=(u11u12u13⋮un1un2un3),x(t)=(x11x12x13⋮xn1xn2xn3),
and all the blank entries in the matrices in (20) are 0.We can use algorithm described in Section2.3 to solve (20) efficiently.Then we solve the following problem to get the optimal ED staffing level:(22)Model2minQ(s1,s2)s.t.s1≥1,s2≥1,s1,s2areintegers,
where(23)Q(s1,s2)=min∫0T‍[(-ω11-ω12-ω13⋯-ωn1-ωn2-ωn3)′x(t)]dt+c1s1+c2s2.Note that Q(s1,s2) is just the objective of Model 1.From our experience in some large hospital,sj's are usually single-digit numbers, so we can solve Model 2 efficiently by enumerating all the possible combination of s1 and s2.In summary, we can get the optimal ED staffing level by solving Model 1 and Model 2, which amounts to solving several instances of (20). As (20) is an SCLP, we can solve it in polynomial time; thus, we can get the optimized ED staffing level very quickly.


## 5.  Conclusion and Future Work

In this paper, we propose a new approach to address the ED staffing. Our approach consists of two steps. In the first step, we construct the fluid model (Model 1 or (20)) to determine the optimal scheduling policy for patients in the ED to minimize the waiting cost of patients given a specific ED staffing level. The model is an SCLP and can be solved efficiently by utilizing the algorithm suggested by Wang [15]. Then, in the second step, we solve Model 2 to get the appropriate ED staffing level which minimizes the total cost of patients and the ED.Our approach accommodates the three characteristics of the demand in EDs, that is, time-varying arrival rate, multiclasses customer, and customer feedback. Comparing with other existing approaches on ED staffing, our approach is more efficient to get the appropriate staffing level.There are still some interesting problems that need explore. In this paper, we assume that the waiting costs of the patients are the linear functions of the queue lengths before Servers. How to determine the amount of ED physicians if the cost functions are other type of functions, for example, convex and increasing function of the queue lengths, is still unknown.Also, in this paper, we only consider how to determine the amount of ED physicians who are in charge of the patients arrived from outside. In reality, there is another decision to make; that is, how to determine the amount of physicians who are in charge of the patients in ER. Although this issue is usually translated into determining the appropriate amount of beds in ER in most of the literature, directly handling this issue is still meaningful if there is some cooperation between these physicians and the physicians who are in charge of patients arrived from outside.



---

*Source: 680152-2013-10-28.xml*