OPERATIONS RESEARCHVol. 62, No. 2, March–April 2014, pp. 462–482ISSN 0030-364X (print) � ISSN 1526-5463 (online) http://dx.doi.org/10.1287/opre.2014.1258

© 2014 INFORMS

When to Use Speedup: An Examination ofService Systems with Returns

Carri W. ChanDecision, Risk, and Operations, Columbia Business School, New York, New York 10027, cwchan@columbia.edu

Galit Yom-TovIndustrial Engineering and Management, Technion–Israel Institute of Technology, Haifa 32000, Israel, gality@tx.technion.ac.il

Gabriel EscobarDivision of Research, Kaiser Permanente, Oakland, California 94612, gabriel.escobar@kp.org

In a number of service systems, there can be substantial latitude to vary service rates. However, although speeding upservice rate during periods of congestion may address a present congestion issue, it may actually exacerbate the problem byincreasing the need for rework. We introduce a state-dependent queuing network where service times and return probabilitiesdepend on the “overloaded” and “underloaded” state of the system. We use a fluid model to examine how different definitionsof “overload” affect the long-term behavior of the system and provide insight into the impact of using speedup. We identifyscenarios where speedup can be helpful to temporarily alleviate congestion and increase access to service. For such scenarios,we provide approximations for the likelihood of speedup to service. We also identify scenarios where speedup should never beused; moreover, in such a situation, an interesting bi-stability arises, such that the system shifts randomly between twoequilibria states. Hence, our analysis sheds light on the potential benefits and pitfalls of using speedup when the subsequentreturns may be unavoidable.

Subject classifications : speedup; state-dependent queues; Erlang-R; fluid models; return to service; bi-stability.Area of review : Stochastic Models.History : Received July 2012; revisions received April 2013, July 2013, November 2013; accepted December 2013.

1. IntroductionWe consider a queuing system where the service timeof customers can be reduced at the expense of increasedlikelihood of the need to return to service. We refer tothe mechanism of increasing the service rate of customersas speedup. The speedup phenomenon can arise in a numberof settings such as the Intensive Care Unit (ICU) (KC andTerwiesch 2012), production lines (Powell and Schultz 2004),email contact centers (Hasija et al. 2010), and general servicesystems (Ata and Shneorson 2006). The reduction in qualityof service due to speedup manifests itself through the needfor rework, which we refer to as customer returns. Thiswork aims to understand the dynamics of a queuing systemwhere speedup is used and the subsequent customer returnsmay be unavoidable.

We define the speedup dynamics by an operational control,in the form of a threshold, that specifies whether the system isconsidered to be overloaded. Hence, service rates and returnprobabilities are endogenous to the operational speedupcontrol. We introduce a new multiserver queuing modelwhere the parameters that define the system dynamics arecongestion dependent; hence, they depend on the systemstate. We examine these state-dependent dynamics using afluid approximation. In doing so, we are able to characterizethe system’s stability conditions and long-term behavior.

A number of works have considered the impact of cus-tomer returns. For instance, Yom-Tov and Mandelbaum(2014), de Véricourt and Jennings (2008), and Yankovicand Green (2011) consider staffing and resource provision-ing in (healthcare) service systems with customer returns.de Vericourt and Zhou (2005) and Zhan and Ward (2014)consider routing in call centers where customers may callback. None of these works consider how the likelihood ofreturn depends on the service rate, which may be altereddepending on system congestion. In this work, we considerthe impact of “speedup” on these customer behaviors.

Also, there have been works that consider state-dependentdynamics (e.g., Armony and Maglaras 2004, Glazebrookand Whitaker 1992, Maglaras and Zeevi 2003, Powell andSchultz 2004); however, to the best of our knowledge, ourwork is the first that considers both state-dependent servicetimes in addition to state-dependent return probabilities.Combining these two effects reveals new phenomena thathave not been previously observed when considering eachdynamic separately. More specifically, we show an interestingbi-stability; i.e., the presence of two equilibria, can arise andidentify conditions under which speedup is detrimental inthe long run.

A number of works consider congestion-dependent servicetimes. Whitt (1990) and Boxma and Vlasiou (2007) consider

462

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 463

the steady-state behavior of state-dependent queues wherethe service times may increase or decrease with delay. Froma control standpoint, Ata and Shneorson (2006) and Anandet al. (2011) consider the quality-speed trade-off of anM /M /1 queue and find that speedup can be beneficial. Bekkerand Borst (2006) and Bekker and Boxma (2007) consider thesteady-state distribution and optimal control of single-serverqueues with state-dependent service rates. These worksdo not consider returns to service. In contrast, our workexamines a multiserver model that includes customer returnsto service, as well as the increase in return probability dueto speedup.

Mandelbaum and Pats (1998) and Mandelbaum et al.(1998) consider state-dependent queuing networks with state-dependent routing. The focus of these works is to developtheoretical support for fluid and diffusion approximations ofthe network dynamics. These works assume state-dependentfunctions that are continuous and cannot be applied to ourmodel, which includes discontinuities in the state-dependentdynamics. These discontinuities require a different analyticapproach: in this work we utilize fluid approximations andFilippov analysis (Filippov 1988).

We show that speedup—a mechanism that seems toalleviate congestion and increase access to service in amyopic manner—may create more congestion and exacerbatethe situation in the long run under certain conditions. Moreprecisely, we show that in some situations, speedup can be auseful operational tool to navigate periods of high congestion.In other instances, speedup will increase congestion becauseof the additional load of returning customers. A surprisingbi-stability arises, resulting in system dynamics that can bemisleading about whether speedup can help. Therefore, weseek to understand system dynamics under speedup and usethis to develop insight into the benefits and pitfalls of usingspeedup. In analyzing our state-dependent model, we makethe following key contributions:

• We introduce a new queuing model (§2) that, to thebest of our knowledge, is the first such model to incorpo-rate (1) congestion-dependent service times in addition to(2) congestion-dependent return probabilities. The interplaybetween speedup and customer returns is a phenomenonthat has not yet been considered in the literature from ananalytic viewpoint.

• We specify conditions for when the queues of ourstate-dependent queuing system grow without bound (Theo-rem 4.2). We show that in some cases, speedup can make astable system unstable; in other cases, speedup is necessaryto maintain stability.

• We identify the long-term queuing dynamics and equi-libria for our state-dependent queuing system (§4). We findthat in some cases (Case 1), management can specify thedesired system congestion and effective offered load byappropriately tuning the speedup threshold (N ∗). Addition-ally, this implies that congestion is invariant to changes inthe number of servers. This analysis provides a possibleexplanation for the observation of “supply-sensitive demand”in healthcare; i.e., demand increases with supply.

• We also find that in some cases (Case 2) an interestingbi-stability arises: the long-term dynamics can convergeto one of two states, depending on the initial condition.Using simulation, we demonstrate that the stochastic systemwill oscillate randomly between the two equilibria. Thisphenomenon demonstrates that although speedup may appearto reduce congestion in some instances (Case 1), its use maybe extremely detrimental in other scenarios (Case 2). In suchcases, other mechanisms may be necessary to navigateperiods of congestion.

The rest of the paper is structured as follows: In §2, wepresent our queuing system that captures the main essenceof a system with speedup and its influence on customerreturns. We start by examining a system without speedupin §3. This provides a baseline for exploring the behavior ofour system with speedup in §4. In §5, we extend our modelto account for factors often seen in various service settings:multiclass customers and time-varying arrivals. We showthat in both extensions, the main insights from our originalmodel, such as the bi-stability effect, still hold. Finally, weconclude in §6.

2. Queuing ModelWe now formally introduce our state-dependent queuingmodel that captures new and returning customers as well asthe effect occupancy levels and queue lengths may have onservice times and returns.

We consider a queuing network with two stations asdepicted in Figure 1. Following the terminology of Yom-Tovand Mandelbaum (2014), we distinguish between two cus-tomer states: Needy and Content. Needy customers requireservice at Station 1 and are either in service or waiting tobegin service. When a Needy customer completes service atStation 1, he will either leave the system or transition intothe Content state. Content customers are customers whocurrently are being served at Station 2, but upon completionof service, they will transition back (return) to the Needystate and require additional service at Station 1. Station 1

Figure 1. System model.

Needy(N-servers)rate-�(Ql)

1 – p(Ql)

p(Ql)

1

2

Arrivalsrate �

Content(∞-server)

rate-�

Exit

Notes. Station 1 represents the N servers where Needy customers areserved. Station 2 represents the servers where Content customers are served.

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup464 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

represents a limited resource station with N servers. Station 2represents an unlimited resource with an infinite number ofservers. The service rate and return probability for Needycustomers are state dependent and will be defined in thenext subsection.

2.1. Stochastic Model

We now describe our stochastic model as a continuoustime Markov chain (CTMC), where all of the dynamics areMarkovian. Let �= 4�4t51 t ¾ 05 be a two-dimensionalstochastic queuing process, where �4t5= 4�14t51�24t55:�14t5 is the number of Needy customers at Station 1 attime t and �24t5 is the number of Content customers atStation 2. We suppress the dependence on t when it isunderstood from the context of the discussion.

New Needy customers arrive to the system accordingto a Poisson random process with rate �. Station 1 has Nservers and an unbounded buffer. If a customer is beingtreated in one of the N servers at Station 1, his service rate,�4�15, depends on the number of Needy customers, �1.Customers discharged from Station 1 will return to Station 1with probability p4�4�155.

We distinguish between two service rates: when thesystem is considered overloaded, then Station 1 operatesunder congested dynamics, with higher service and returnprobabilities than the nominal operation. When Station 1 isnot considered overloaded, then the servers operate normally,with nominal service rates and return probabilities. LetN ∗ ¾ 0 be a control variable that determines the operationof Station 1. We refer to N ∗ as the speedup threshold. Thesystem is considered to be overloaded when the number ofNeedy customers is greater than the speedup threshold, i.e.,when �1 ¾N ∗. Note that if N ∗ ¶N , speedup will beginbefore a queue forms.

Let �L and �H (�H >�L) define the service rate duringunderloaded and overloaded periods, i.e., when the occupancylevel is low and high, respectively. The state dependentservice rates are given by

�4�15=

{

�L1 if �1 <N ∗1

�H 1 if �1 ¾N ∗0(1)

Once a customer completes service at Station 1, he exitsthe system with probability 1 −p4�4�155 and never requiresadditional service at Station 1. With probability p4�4�155the customer enters the Content state. Content customerstransition into the Needy state according to an exponentialrandom variable with constant rate �. Thus, this stationactually models the delay between completion of initialservice at Station 1 and the subsequent request for additionalservice. Note that the return probability, p4�4�155, dependson the service rate of the customer at discharge: whenspeedup is used, the return probability increases. Let pL

and pH (pH > pL) denote the return probability duringunderloaded and overloaded periods:

p4�4�155=

{

pL1 if �1 <N ∗1

pH 1 if �1 ¾N ∗0(2)

Thus, during their stay in the system, customers start in theNeedy state and then alternate between Needy and Contentstates until they depart the system. When a customer becomesNeedy and a server at Station 1 is available, he immediatelybegins service. However, if there are no available servers,customers must wait in a queue for an available one. Thequeuing policy is FCFS (First Come First Served).

Remark 2.1. One could also consider return probabilitiesthat depend on the mean congestion in Station 1 duringservice (e.g., to capture how much work was “sped up”).Doing so would require substantial notational overhead tokeep track of the congestion each customer experienced, andwe leave such exploration for future work.

Remark 2.2. Note that in practice, �2, which only tracksContent customers who eventually transition back to theNeedy state, may be an unobservable quantity since weusually do not know which customers will return to servicea priori. As such, we restrict our control to depend onlyon �1.

The queuing system we analyze is a CTMC, which, underconditions for stability (to be described later), has a long-termdistribution. We can derive the equations for the equilibriumdistribution (see Appendix B) and numerically evaluate oruse simulation to compute desired performance measures.However, these methods fail to provide some insights intothe behavior of the system, which a fluid analysis can.

2.2. The Fluid Model

In order to enable tractable analysis of the system dynamicsof our state-dependent system, we introduce a deterministicfluid approximation to the stochastic model presented in§2.1. The fluid model is meant to provide insight into theuse of speedup (some of which is unintuitive, as will beseen in §4.2).

We denote the fluid function of our queuing network byQ= 8Q4t51 t¾ 09. Here Q4t5= 4Q14t51Q24t55, where Q1

and Q2 are the fluid content of Needy and Content customersat time t. We derive the fluid formula directly. We assumethat arrivals and departures occur deterministically at thespecified rates and also regard the number of customersand servers as continuous quantities. Thus, the fluid arrivesdeterministically and continuously at constant rate �. Fluidis served in station 1 deterministically at rate �4Q154Q1 ∧N5,where ∧ denotes the minimum function so that 4Q1 ∧N5 isthe number of occupied servers in station 1. A p4Q15 fractionof the fluid is transferred to station 2 after leaving station 1;the rest of the fluid exits the system. The fluid in station 2is served deterministically and continuously at rate �Q2.The service rate function, �4 · 5, and the return probabilityfunction, p4 · 5, are discontinuous in the amount of fluidcontent of the Needy customers, Q14t5. These functions aregiven by (1) and (2), respectively.

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 465

The dynamics of our model can be captured by the follow-ing ordinary differential equations (ODE) with discontinuousright-hand sides:

Q̇14t5= �+ �Q24t5− 18Q14t5<N ∗9�L4Q14t5∧N5

− 18Q14t5¾N ∗9�H4Q14t5∧N51

Q̇24t5= −�Q24t5+ 18Q14t5<N ∗9pL�L4Q14t5∧N5

+ 18Q14t5¾N ∗9pH�H4Q14t5∧N50

(3)

This discontinuous ODE is discontinuous in Q but continuousin t. From (3), it is easy to see that the derivative values,Q̇, that specify the flow dynamics are discontinuous atQ14t5=N ∗. We will analyze the long-term behavior of thisfluid system, i.e., the behavior as t → �. Let q̄ = 4q̄11 q̄25be the long-term values such that:

q̄ ≡ limt→�

6Q4t5 �Q405= q07

Note that these limits may be infinite, may depend onthe initial condition q0, or may not exist. For notationalsimplicity, henceforth we will omit the dependence on theinitial condition and specify explicitly if the limit dependson it.

2.3. Definitions

In our analysis of the long-term behavior of our fluid system,we will require a few definitions. Consider a dynamicsystem that is dictated by the ODE q̇ = F 4q5, q ∈�n

+. In our

system, n= 2 to capture the Needy and Content customers.We denote by ê4q01 t5 the flow at time t, given initialcondition q0. Then the flow dynamics over time are definedat time t by 4d/dt5ê4q01 t5= F 4ê4q01 t55, ê4q0105= q0.The system is considered to be unstable if the fluid contentof customers in the system grows without bound over time.Formally,

Definition 2.1 (Unstable System). We say that a systemdefined by the ODE q̇ = F 4q5 is unstable if for any initialcondition, q0

limt→�

6Q14t5+Q24t57→ �

In cases where the system is not unstable, we wish toexamine the behavior of the system and assess whether thereis a limit to which the fluid system might converge overtime. The following definitions for equilibria can be foundin di Bernardo et al. (2008).

Definition 2.2 (Equilibrium [or Fixed Point]). A pointq̄ is an equilibrium of the ODE q̇ = F 4q5 if

ê4q̄1 t5=ê4q̄1051 for all t0

The simplest form of equilibrium q̄ is one that satisfiesF 4q̄5= 0. Following di Bernardo et al. (2008), we call a

pseudo-equilibrium an equilibrium that arises on the regionof discontinuity in the ODE (e.g., on the switching boundaryè≡ 8Q2 Q1 =N ∗9 of (3)). This type of equilibrium is anequilibrium since a trajectory starting as that point will staythere, but it is different from standard equilibria becausethe derivatives may not be zero. This form of equilibriumhappens when the forces that push the trajectory to thispoint are equal from all directions. Technical details ofpseudo-equilibria are given in the appendix.

Note that even if an equilibrium, q̄, exists, it is notnecessarily true that the system will converge to it as t → �.Moreover, the limiting behavior may depend on the initialcondition q0 ∈�2

+. Hence, we further differentiate between

types of equilibria. An equilibrium is called Lyapunov stableif trajectories starting nearby to the equilibrium remainnearby for all time. This type of equilibrium is often referredto as a Locally Stable Equilibrium. Without loss of generality,we assume the equilibrium is at the origin; that is, ê401 t5=

ê40105 for all t.

Definition 2.3 ((Lyapunov) Locally Stable Equilib-rium). The origin is said to be (Lyapunov) locally stable iffor any � > 0, there exists a �> 0 such that if

�q0�<� ⇒ �ê4q01 t5�< �1 ∀ t > 0

We refer to an equilibrium as Globally Stable if for everystarting point it will converge to the same stable equilibriumdefined by Definition 2.3.

Definition 2.4 (Globally Stable (in the Sense ofLyapunov) Equilibrium). The origin is said to be globallystable (in the sense of Lyapunov) if the following twoconditions hold:

1. It is locally stable.2. For all initial conditions, q0: limt→� ê4q01 t5= 0.

Note that these definitions of stability do not mean thatthere exists a t0 such that Q4t5 = q̄ for all t > t0. Theysimply require that for every � > 0, there exists a t0 suchthat for all t > t0, Q4t5 is within � of q̄; in the case oflocal stability, this is only true if the trajectory starts closeenough to the equilibrium. We will actually see instances (forpseudo-equilibria) where the fluid oscillates with arbitrarilysmall fluctuations around the equilibrium point. Finally, weremark that there could exist long-term behavior that is notcaptured by Definitions 2.1 through 2.4; e.g., a trajectorycould remain finite but not converge to any single state.

3. A System Without SpeedupFor comparison purposes, we first consider a system wherespeedup is never used. In this case, the fluid equations canbe simplified to

Q̇14t5= �+ �Q24t5−�L4Q14t5∧N51

Q̇24t5= −�Q24t5+pL�L4Q14t5∧N50(4)

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup466 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

This is the fluid model of an Erlang-R queue (Yom-Tovand Mandelbaum 2014). The queues grow without bound ifN <�/441 −pL5�L5; otherwise, the system converges to aglobally stable equilibrium, q̄. More formally,

Theorem 3.1. The dynamics of the fluid system describedin (4) can be summarized as

1. The system is unstable if N <�/441 −pL5�L5.2. If N > �/441 − pL5�L5, the fluid converges to the

following globally stable equilibrium:

limt→�

Q4t5= q̄ =

(

�

41 −pL5�L

1�pL

41 −pL5�

)

0

The proof of this result can be found in the appendix. Wenote that if N = �/441 −pL5�L5, there are an uncountablenumber of equilibria. As an example, if the initial conditionis such that 4q051 ¾N and 4q052 = 4�pL5/441 −pL5�5, thenthe fluid content stays at the initial condition, so Q4t5= q0

for all t.

4. Analysis of System DynamicsIn this section, we analyze the long-term dynamics of thefluid model presented in §2.2. The main challenge is thediscontinuity at Q1 =N ∗. The long-term dynamics are highlydependent on system parameters for arrival rate, servicetimes, and return probabilities as well as the control variablefor when to begin speedup, N ∗.

To start, we leverage results from Filippov (1988) toestablish the existence of a solution to our ODE.

Theorem 4.1. There exists a solution of the problem definedby the ODE (3) for any initial condition q0 = Q405 ∈

601Qmax7× 601Qmax7 where Qmax <� is an arbitrary finiteconstant.

This is a result of Theorem 1 on page 77, Chapter 2,Section 7 of Filippov (1988). The details of leveraging thisresult can be found in the appendix.

We define the following parameters, that will be useful indescribing the system dynamics:

qL =

(

�

41 −pL5�L

1pL�

41 −pL5�

)

1

qH =

(

�

41 −pH5�H

1pH�

41 −pH5�

)

1

�=4N ∗ ∧N5− qH

1

qL1 − qH

1

0

(5)

One can think of qL and qH as the offered load atStation 1 and 2 under low and high occupancy dynamics.This interpretation is clear when considering the systemeither (i) always works under underloaded dynamics and sonever speeds up (i.e., the system analyzed in §3) or (ii) neverworks under underloaded dynamics and so always speeds up.

We begin our analysis with the question of when oursystem is unstable. The proof is given in the appendix.

Theorem 4.2. The instability conditions for the fluid systemin (3) are broken into two cases.

1. qH1 < qL

1 .• The system is unstable if N < qH

1 .• The system is unstable if N < qL

1 and N ∗ = � (i.e.,speedup is never used)

2. qH1 ¾ qL

1 .• The system is unstable if N < qL

1 .• The system is unstable if N < qH

1 and N ∗ < qL1 .

We will show in Theorem 4.3 that when the conditions ofTheorem 4.2 are not satisfied, the system will converge to afinite equilibrium.

Note that the stability of the system depends on bothsystem parameters 4qH

1 1 qL1 1N5 and the decision variable,

i.e., the speedup threshold 4N ∗5. Consequently, there arecases in which the system can be stabilized only if speedupis applied (e.g., under Case 1 if qH

1 < N ¶ qL1 ); in such

cases using speedup reduces the offered load so that it isnot necessary to acquire additional servers to ensure thatthe queues do not grow without bound. On the other hand,there are cases where an otherwise stable system becomesunstable because of utilizing speedup (e.g., under Case 2 ifN ∗ < qL

1 <N < qH1 ).

We now consider the long-term dynamics of our system.In the results that follow, we assume that N is large enoughsuch that the queues in our system do not explode, i.e., theconditions of Theorem 4.2 are violated. Moreover, becauseof the potential for an uncountable number of equilibriaof our fluid equations (as described in §3), we make thefollowing assumption:

Assumption 4.1. The number of servers, N , is such thatthe effective system load is strictly less than 1; i.e.,

N > 4qL1 ∧ qH

1 50

We then consider how the various system parametersimpact the system. In particular, we identify scenarios wherethere is a unique, globally stable equilibrium as well asother scenarios where there may be multiple locally stableequilibria.

Theorem 4.3. Given N and N ∗ such that Assumption 4.1holds and the conditions of Theorem 4.2 are violated, thelong-term dynamics of the fluid system in (3) can be brokenin two cases with additional subcases:1. qH

1 < qL1 .

1.1. If N ∗ ¶ qH1 , then qH is a globally stable equilibrium.

1.2. If qH1 <N ∗ ∧N < qL

1 , then 4N ∗1�qL2 + 41 −�5qH

2 5is a globally stable pseudo-equilibrium.

1.3. If qL1 ¶N ∗ ∧N , then qL is a globally stable equili-

brium.2. qH

1 ¾ qL1 .

2.1. qH1 <N

2.1.1. If N ∗ < qL1 , then qH is a globally stable

equilibrium.

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 467

Figure 2. Phase portrait for Case 1.1 (N ∗ ¶N ): Dark lines represent points where the derivative is zero in one of thedimensions.

N*

N*N

NQ1 Q1

Q2

(a)

qH

qL

Q2

(b) dtdQ2(t)

, ,= 0dt

dQ1(t)= 0

2.1.2. If qL1 ¶N ∗ ¶ qH

1 , then qL and qH are locallystable equilibria. In addition, when qL

1 6= qH1 ,

then 4N ∗1�qL2 + 41 − �5qH

2 5 is a pseudo-equilibrium.

2.1.3. If qH1 <N ∗, then qL is a globally stable equi-

librium.2.2. qH

1 ¾ N > qL1 and N ∗ > qL

1 . Then qL is a locallystable equilibrium and 4N ∗1�qL

2 + 41 −�5qH2 5 is a

pseudo-equilibrium.

The proof follows by Filippov and Lyapunov techniquesand is given in the appendix. We demonstrate the intuitionbehind the result for Case 1 via the phase portrait ofeach subcase with N ∗ ¶N . (The case for N ∗ >N followssimilarly.) In Figure 2(a), we see the phase portrait when theequilibrium is at qH—the arrows represent the magnitudeand direction of the derivative at each state, and the solidlines represent points where the derivative is zero in one ofthe dimensions. Hence, the trajectory of the queuing systemis pulled toward and along these lines. Figure 2(b) breaks

Figure 3. Phase portraits for Case 1.2 and Case 1.3 (N ∗ ¶N ).

N*N* NN

(1.2) (1.3)

Q2 Q2

Q1Q1

qH

qHqL

qL

dtdQ2(t)

, ,= 0dt

dQ1(t)= 0

(N*, �q2L + (1 – �)q2

H)

down the phase portrait in Figure 2(a) to present a clearerview of the relationship between the different parameters.The dashed lines are a virtual continuation of the derivativelines. It is not necessarily the case that q̇1 = 0 or q̇2 = 0along these lines because the system dynamics change whencrossing the N ∗ threshold. If the dynamics did not change,qL would be an equilibrium. However, because of the changein dynamics due to the speedup threshold, qL is not anactual equilibrium in this case. Thus, we refer to qL as aninadmissable equilibrium. Intuitively, when Q1 <N ∗, thesystem does not speed up and the trajectory is attracted tothe point, qL. Before reaching qL, the number of Needycustomers grows so that Q1 ¾N ∗ and speedup is used. Atthis point, the system dynamics switch to the overloadeddynamics and the trajectory is attracted to the point qH .Because N ∗ ¶ qH <N in Case 1.1, the derivatives at qH ,q̇1 = q̇2 = 0. We thus refer to qH as an admissible point andcan conclude it is the equilibrium point of the system.

This intuition can be extended to Case 1.2 and 1.3. Thestripped down phase portraits for these cases are in Figure 3,

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup468 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

which depict the pull of two points that attract trajectories:qL and qH . Each point represents the equilibrium whenthe system never or always speeds up. The relationshipbetween qL, qH , and the speedup threshold N ∗ dictateswhether the equilibrium is at qH (Case 1.1), qL (Case 1.3),or N ∗, in which case the trajectories oscillate across theswitching boundary between the speedup/no-speedup regions(Case 1.2). Similar phase portraits can be generated forCase 2.

To understand the impact of different parameters on theequilibrium values, we use bifurcation diagrams. Bifurcationdiagrams are often used to show the possible long-termvalues (equilibria or periodic orbits) of a dynamical systemas a function of a parameter that may dictate the system’sbehavior. In our case, our main interest is in understand-ing how the speedup threshold, N ∗, affects the equilibria(in §5.2 we will see cases where the long-term values areactually periodic orbits). To examine the influence of N ∗,we assume that all other parameters, including the numberof servers, are fixed. For consistency, we consider the casewhere N ∗ ¶N . The case of N ∗ >N follows very similarly,assuming Assumption 4.1 holds. Figure 4(a) summarizes theequilibria for Case 1 as a function of N ∗. The long-termnumber of Needy customers, q̄1, increases with N ∗, whereasthe number of Content customers, q̄2, decreases with N ∗.When N ∗ is larger than qL

1 , no speedup is applied; whenN ∗ is smaller than qH

1 , speedup is applied most of the time.Finally, in the middle range (qH

1 ¶ N ∗ ¶ qL1 ), speedup is

applied a fraction of the time (therefore only some of thecustomers will be sped up). This graph demonstrates that N ∗

is not only the threshold of speedup but also the equilibriumof the system. From Theorems 3.1 and 4.2, we recognizethat, in Case 1, N > qL

1 guarantees the queue does not growwithout bound irrespective of whether or not speedup isused. However, by utilizing speedup, we can achieve along-term backlog of q̄1 < qL

1 and maintain finite queueswith fewer servers. Hence, in Case 1, utilizing speedup(i.e., reducing N ∗) increases access to service by reducingthe overall workload on Station 1, despite the increase inreadmission likelihood.

Figure 4. Bifurcation diagram as the speedup threshold, N ∗, varies.

N*

N* N*

N*q1H

q1H

q1H

q2H

q2H

q2L

q2L

q1Hq1

L

q1L

q1L

q1, q2

q1, q2

q1

q1

q2 q2

q1L

(a) Case 1 (b) Case 2.1

Case 1.1global

equilibriumat qH

Case 2.1.1global

equilibriumat qH

Case 1.2global

equilibrium at

Case 1.3global

equilibriumat qL

Case 2.1.3global

equilibriumat qL

(N*, �q2H

+ (1–�)q2L)

Case 2.1.2three equilibria at qH, qL and

(N*, �q2H

+ (1–�)q2L)

Figure 4(b) summarizes the equilibria for Case 2.1 as afunction of the parameter N ∗. In this case, both the numberof Needy and Content customers is higher when utilizingspeedup compared to never using it. Although speedupmay seem like a reasonable action to take during periodsof congestion, it is a myopic action that can exacerbatecongestion issues in the long run. Hence, unlike Case 1, it isundesirable to utilize speedup because it can increase theoverall load on Station 1, which is already congested.

At the extremes (high/low N ∗) when speedup is alwaysor never used, the basic insights from Case 1 and Case 2are not surprising. However, because systems may elect tooperate at intermediary values where speedup is used someof the time (Case 1.2 and Case 2.1.2), it is important tofurther understand the dynamics in these regions.

4.1. Case 1.2: qL1 >qH

1

We now discuss a number of interesting insights that can beextracted by our analysis of Case 1.2. Recall that in thiscase, speedup can increase access to service.

We first examine the impact of the number of servers,N , on the system dynamics. Fix an occupancy threshold,0 ¶ r at which speedup begins; hence, N ∗ = rN . Figure 5demonstrates the long-term behavior as we vary the numberof servers, but maintain the speedup threshold at N ∗ = rN .This introduces an interesting phenomenon where addingmore servers does not seem to reduce congestion. Morespecifically, as the number of servers, N , increases, theoccupancy level at Station 1, Q1/N , remains at r . This isbecause N ∗ is not only the threshold of speedup but also theresulting equilibrium of the system. Hence, Station 1 stillseems “busy” even with the addition of servers. Thoughadding servers doesn’t appear to reduce congestion, it doesresult in fewer customers who are sped up. Our analysissuggests that large additions may be required before therewill be any noticeable change in occupancy levels.

We now delve further into the behavior of the system inCase 1.2, where it oscillates frequently between overloadedand underloaded regions. Note that these fluctuations arearbitrarily small such that the fluid state remains close to

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 469

Figure 5. Bifurcation diagram of Case 1 as the num-ber of servers, N , varies; speedup begins atoccupancy level r ¶ 1.

N

rN

q1H

q1H

q1H

r

q2H

q2L

q1Lq1

L

q1L

q1, q2

q1

q2

Unstable Case 1.1global

equilibriumat qH

Case 1.2global

equilibrium at

Case 1.3global

equilibriumat qL

(N*, �q2L + (1–�)q2

H)

r

Note. The diagram is similar for r > 1.

the globally stable pseudo-equilibrium. Hence, althoughthe derivatives are nonzero, the system is arbitrarily closeto the equilibrium point. As a consequence of the proofof Theorem 4.3, we can establish the proportion of timespent in overload and underload when the system oscillatesbetween these two regions.

Figure 6. Case 1 (qH1 ¶N ∗ ¶ qL

1 ): Simulation vs. fluid.

50454035

N*30252015

50454035

N*

30252015

N*40 50 60 70 80 90 100 110 120 130 140 15030

N*

40 50 60 70 80 90 100 110 120 130 140 15030

0.0

0.2

0.4

0.6

0.8

1.0

Spee

dup

prop

ortio

n of

tim

e

0

5

10

15

20

25

30

35

40

0

20

40

60

80

100

120

140

Num

ber

of c

usto

mer

s

Num

ber

of c

usto

mer

s

0.0

0.2

0.4

0.6

0.8

1.0

Spee

dup

prop

ortio

n of

tim

e

SimulationFluid

(a) N = 50: P(speedup) as a function of N* (b) N = 150: P(speedup) as a function of N*

(c) N = 50: Q1 as a function of N* (d) N = 150: Q1 as a function of N*

Corollary 4.1. If the fluid system is stable and qH1 ¶

N ∗ ∧N ¶ qL1 , then the proportion of time the fluid process

spends speeding up is given by

limT→�

1T

∫ T

018Q14t5¾N ∗9

=�+ �q̄2 −�L4q̄1 ∧N5

4�H −�L54q̄1 ∧N5

=�+ �4�qL

2 + 41 −�5qH2 5−�L4N

∗ ∧N5

4�H −�L54N∗ ∧N5

0 (6)

This corollary is based on Filippov’s convex method(Filippov 1988) that provides expressions for the proportionof time a trajectory spends above the switching boundary.This proportion—from the fluid model—can be used as anapproximation for the probability of speedup in our originalstochastic model, i.e.,

P4speedup5≡ P4�14t5¾N ∗5≈ limT→�

1T

∫ T

018Q14t5¾N ∗90

We simulate the long-term behavior of our original stochas-tic system and compare it to our fluid approximation. Fig-ures 6(a) and 6(b) shows the probability of speedup as wevary N ∗ for both the simulation and the fluid approxima-tion. We use parameters that satisfy the criteria for Case 1:

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup470 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

(a) A small system with N = 50 servers and �L = 000164,�H = 000224, pL = 000667, pH = 000973, �= 0001611 and(b) a large system with N = 150 servers and �L = 0001,�H = 0002, pL = 005, pH = 006, �= 0001. We observe thatfor large N the fluid is very accurate; this accuracy degradesas the size of the system decreases and when N ∗ is close toqH

1 or qL1 . This is due to the nonsmooth dynamics of the

fluid approximation when N ∗ is relatively large or small.This phenomenon also arises when considering the expectednumber of Needy customers, E6�17, as seen in Figures 6(c)and 6(d). Upon further investigation, we noticed that thefluid model provides a more accurate estimate for the modeof �1, i.e., the most frequently observed value of �1. �1

typically does not have a symmetric distribution, so E6�17is not necessarily equal to the mode of �1. As the systemgets larger, the symmetry of the distribution increases, sothe fluid approximation improves.

We next examine the variation of our stochastic processwith respect to the fluid approximation. Figures 7(a) and 7(c)show a sample path of the system in Case 1.2, and Fig-ures 7(b) and 7(d) show the long-term distribution of �(using the same parameters as before for the small andlarge systems). In this case, the equilibrium of the fluidmodel is exactly q̄1 =N ∗. When considering the stochasticmodel, we observe the distribution for �14t5 has an unusualshape—similar to a bilateral exponential distribution—thatis tight around the threshold N ∗ and can be observed as

Figure 7. Case 1 simulation: qH1 ¶N ∗ ¶ qL

1 .

(a) A single sample path for N = 50 (b) Steady state distribution of ñ1(t) and ñ2(t) for N = 50

0 50 100 150 200 250 300 350 400 450 5000

20

40

60

80

100

120

Num

ber

of c

usto

mer

sN

umbe

r of

cus

tom

ers

Time

Time (days)

Sim Q1

Fluid Q1

Sim Q2

Fluid Q2

Sim Q1

Fluid Q1

Sim Q2

Fluid Q2

(c) A single sample path for N = 150

0 50 100 1500

0.05

0.10

0.15

0.20

Number of customers

000

5

5

10

10

15

15

20

20

25

25

30

30

35

35

40

40

45 10 20 30 40 50

Number of customers

Rel

ativ

e fr

eque

ncy

0

0.05

0.10

0.15

0.25

0.20

Rel

ativ

e fr

eque

ncy

Q1

Q2

Q1

Q2

(d) Steady state distribution of ñ1(t) and ñ2(t) for N = 150

rapid changes in the sample path. On the other hand, �24t5exhibits the typical Poisson distribution (this is more visiblein the larger system). The rapid changes in �14t5 suggesta very strong pull toward the equilibrium from above andbelow the equilibrium N ∗ for Needy customers. This obser-vation suggests that the methodology considered in Perry andWhitt (2011), which also observes tight drifts for a differentqueuing system, could be used to generate an approximationfor the distribution of �1.

4.1.1. Approximating � Under Case 1.2. Followingideas from Perry and Whitt (2011), we develop an approxi-mation to our original stochastic process �1 while operatingunder Case 1.2 conditions. Such an approximation providesinsight into the behavior of the variation of the queue lengthprocess, which the fluid system does not allow. We developthe approximation as a heuristic. We consider an approxima-tion with a very simple structure: a two-sided birth-deathprocess with constant rates on each side. Because of thissimple structure, we are able to easily derive approximationsfor the steady-state distribution of �1 as well as provide anapproximation for the probability of speedup in our originalstochastic model, P4�1 ¾N ∗5. Although the approximationfor P4speedup5 from this approach is the same as the onedeveloped in Corollary 4.1 using the Filippov method forthe fluid model, we now also have more detailed insight intothe distribution of the number of Needy customers in our

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 471

original stochastic model than when considering the resultsof the fluid analysis alone.

Define a CTMC process Q̃= 4Q̃4t51 t ¾ 05 ∈�. Let �+

and �+ be the birth and death rates of Q̃4t5 when Q̃4t5¾ q̄1

and �− and �− be the birth and death rates when Q̃4t5 < q̄1.Our approximation defines these rates as

�+ = �+ �q̄21 �+ =�H4q̄1 ∧N51

�− = �+ �q̄21 �− =�L4q̄1 ∧N50(7)

Because of the constant birth and death rates, the processQ̃4t5 evolves as an M /M /1 queue in each of the regionsQ̃4t5¾ q̄1 and Q̃4t5 < q̄1. This allows us to easily determinethe steady state probability of being in state i:

P4Q̃ = q̄1 − 15=41 −�+/�+541 −�−/�−5

1 − 4�+/�+54�−/�−5

P4Q̃ = i5=

(

�−

�−

)−4i−q̄1+15

×P4Q̃ = q̄1 − 151

if i < q̄1 − 11

(

�+

�+

)i−q̄1+1

×P4Q̃ = q̄1 − 151

if i > q̄1 − 10

(8)

The intuition behind this process construction is as follows:The stochastic process � we are trying to approximate hasstate-dependent drifts depending on the number of customersin service; however, we observed in Figure 7(c) that thenumber of Needy customers is almost deterministic andequal to q̄1 =N ∗. Hence, we remove the state dependencyand instead use constant drifts in the process Q̃, similar to asingle-server queue rather than the N -server queue we areapproximating. The death rates differ on each side becauseof speedup; speedup is used when Q̃¾ q̄1, whereas speedupis not used when Q̃ < q̄1. As a result, the rates of Q̃ are thesame as the process � if the number of customers werefixed �= q̄ = 4N ∗1�qL

2 + 41 −�5qH2 5. This is irrespective

of what the actual queue length � is and allows us to derivesimple expressions for the distribution of Q̃, as given in (8).

Previously, we used the fluid model to provide an approxi-mation for the probability of speedup in our original stochas-tic system. We now consider a different approximation

Figure 8. Case 1: Simulation vs. approximation based on two-sided M /M /1 queue.

(a) 75%

0.20

0.15

0.10

0.05

070 80 90 100 110 120 130

Number of customers

70 80 90 100 110 120 130

Number of customers

70 80 90 100 110 120 130

Number of customers

Rel

ativ

e fr

eque

ncy

0.20

0.15

0.10

0.05

0

Rel

ativ

e fr

eque

ncy

0.20

0.15

0.10

0.05

0

Rel

ativ

e fr

eque

ncy

(b) 50%

SimulationApproximation

(c) 25%

approach, which uses the process Q̃4t5 to approximate �14t5;thus, we measure when Q̃4t5 is equal to or greater than N ∗.Therefore,

P4�1¾N ∗5≈P4Q̃¾ q̄15=�∑

i=q̄1

(

�+

�+

)i−q̄+1

×P4Q̃= q̄1 −15

=�+/�+41−�−/�−5

1−4�+/�+54�−/�−50

Using (7), and noting that �+ = �−, gives:

P4speedup5= P4�1 ¾N ∗5

≈�+ −�−

�+ −�−=

�+ �q̄2 −�L4q̄1 ∧N5

4�H −�L54q̄1 ∧N50

This is exactly the same approximation as from Corollary 4.1.Figure 8 compares the steady-state distribution of our

approximation, Q̃, to the simulated distribution of the originalprocess �1 in various cases. As expected, the fit is very goodwhen N ∗ is such that we expect the speedup probabilityshould be close to 50%. As we deviate from that valueof N ∗ (e.g., when the speedup probability is close to 25%or 75%), the fit degrades. Earlier, we observed in Figure 4(a)that the fluid model provides a very accurate approximationwhen P4speedup5 is close to 50%, but its accuracy degradesas N ∗ approaches qL

1 or qH1 (equivalently, as P4speedup5

approaches 0 or 1). We expect this inaccuracy to also ariseas we consider our approximation for the whole distributionfor �1. Because the shape of the distribution is still quiteaccurate in the latter cases suggests that with improvedapproximations for q̄, the approximation for the distributionof �1 could also improve.

4.2. Case 2.1.2: qL1 ¶ qH

1

We now examine the analogous scenario in Case 2—Case 2.1.2—and consider the insights our fluid analysisprovides for our original stochastic system. There arethree equilibria in Case 2.1.2. However, the equilibrium4N ∗1�qL

2 + 41 −�5qH2 5 is not stable. That is, if the fluid

starts there, it stays there; however, even small deviations inthe initial conditions from the equilibrium will drive the

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup472 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

system away from it. Hence, it is unlikely to be observedin our original stochastic system. The other two equilibria,qH and qL, are locally stable. Hence, whether speedup canalleviate congestion at Station 1 or whether it will lead toworse congestion resulting in perpetual overload (even ifthe system could be operated in underload without usingspeedup) will depend on the initial condition. In the stochas-tic model, the behavior of the queues will depend on thedistance between qH and qL. If they are very far from eachother, the steady state of the stochastic system will primarilydepend on the initial condition. By starting near qL, speedupwill not need to be used; however, starting near qH willrequire that speedup is always used. Even if qL and qH arefar away from each other, there exists sample paths suchthat the number of Needy customers will increase (decrease),thereby effectively increasing (decreasing) the system loadand transitioning to state qH (qL). For example, a transitionfrom qL to qH may occur because of a “burst” of arrivals.Because of stochastic fluctuations, it is possible that thestochastic queue will oscillate between qH and qL. If thesetwo equilibria are very far apart, the transition times in thestochastic system could be very long—long enough thatsuch transitions are never observed in practice. However, ifthe equilibria are close to one another, small bursts will besufficient to cause the stochastic system to transition and soit may oscillate between the two equilibria frequently. As anexample, we chose to demonstrate a scenario where bothlocally stable equilibrium coexist.

Figure 9(a) presents a sample path of the stochasticstate �4t5= 4�14t51�24t55, under Case 2.1.2. We observeshifting from one equilibrium to the second one in themiddle of the run, after approximately 220 days.2 Thesystem begins around the qL equilibrium and shifts to theqH equilibrium. When examining the distribution of �4t5 inFigure 9(b), we observe the two equilibria at qL = 42419065and qH = 440154045. Interestingly, there is another peakat �1 =N ∗ = 35. This peak does not indicate the pseudo-equilibrium but rather is a product of the system shifting fromone region to the next. During the transition, when the fluid

Figure 9. Case 2.1.2 simulation.

0 100 200 300 400 500 00

0.01

0.02

0.03

0.04

0.05

0.06

0.07

10 20 30 40

Rel

ativ

e fr

eque

ncy

50 60 70 800

10

20

30

40

50

60

70

80

Num

ber

of c

usto

mer

s

Time (days) Q

Sim Q1

Sim Q2

(a) Sample path of Case 2.1.2 (b) ñ1 and ñ2 distributions

Q1 distributionQ2 distribution

flow encounters the switching boundary è (where Q1 =N ∗),the flow slides along the switching boundary. Therefore, fora significant part of the time, Q1 is constant and equal N ∗,while Q2 changes. This behavior is described as a slidingmode in the dynamical systems literature and occurs when4�L4N

∗ ∧N5−�5/�¶Q2 ¶ 4�H4N∗ ∧N5−�5/�, which

corresponds to 1804 ¶ Q2 ¶ 4604 in our example. Moredetails can be found in the appendix. Although this slidingmotion is a phenomenon of the fluid system, we can see thatit still provides important insight into the behavior of thestochastic system.

The fluid analysis allowed us to identify these two oper-ating modes. Gibbens et al. (1990) also used fixed pointanalysis of a deterministic system to demonstrate the exis-tence of bi-stability, albeit in communication networkswithout feedback. Recognizing such behavior can exist willhelp avoid poor speedup decision making.

5. Model ExtensionsThus far, the focus of this work has been on the modelpresented in §2. We now consider a number of extensions toour stylized model that capture additional dynamics that canarise in various service settings. In particular, we look at theimpact of including prioritization of customers and time-varying arrival rates. In both cases, we find that although onecan garner some additional insights from analyzing theseextensions, the primary insights from our original analysiscarry over to these extended models.

5.1. New vs. Return Customers

In this section, we consider differentiating between returnand first time customers. Return customers may warranthigher priority in order to limit the total time customersspend in the system (e.g., Huang et al. 2012). In addition,their service rates may differ, as seen in Durbin and Kopel(1993). We now examine the dynamics of our queuingmodel where the service rates and return probabilitiesdepend not only on congestion but also on whether the

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 473

customer is new versus returning. We assume that returningcustomers have preemptive priority over new customers.Again, we use fluid analysis to generate insights about ourstochastic model. �F 1L (�R1L) denotes the service rate forfirst-time (return) Needy customers when the system isconsidered underloaded, and �F 1H (�R1H ) represents thesame when the system is considered overloaded. Similarly,pF 1L (pR1L) denotes the probability of return for first-time(return) Needy customers when the system is consideredunderloaded, and pF 1H (pR1H ) represents the same when thesystem is considered overloaded. Denote by QF

1 and QR1

the fluid content of first-time and return Needy customers,respectively. Thus, when QF

1 + QR1 ¾ N ∗, the system is

considered overloaded and speedup is used. Because wegive preemptive priority to return customers, capacity willfirst be allocated to them (QR

1 ∧N ); any remaining servicecapacity, 4N −QR

1 5+, is allocated to the first-time Needy

customers. The modified ODE under consideration is now

Q̇F1 = �−4QF

1 ∧4N −QR1 5

+5[

�F 1L18QF1 +QR

1 <N ∗9

+�F 1H18QF1 +QR

1 ¾N ∗9

]

1

Q̇R1 = �Q2 −4QR

1 ∧N5[

�R1L18QF1 +QR

1 <N ∗9

+�R1H18QF1 +QR

1 ¾N ∗9

]

1

Q̇2 = −�Q2 +(

QF1 ∧4N −QR

1 5+)

·[

pF 1L�F 1L18QF1 +QR

1 <N ∗9+pF 1H�F 1H18QF1 +QR

1 ¾N ∗9

]

+4QR1 ∧N5

·[

pR1L�R1L18QF1 +QR

1 <N ∗9+pR1H�R1H18QF1 +QR

1 ¾N ∗9

]

0

(9)

For this model, we utilize numerical approaches becusethe increased complexity of this model introduces additionalchallenges, making it cumbersome to employ the generalizedLyapunov analysis used to prove Theorem 4.3. Similar to ouroriginal model, we find that this extended fluid model alsohas two cases: one with a single globally stable equilibriumand another with bi-stability.

We translate the insight generated from the numericalanalysis of the fluid model to a stochastic model via simula-tion of a system with N = 45 servers and speedup thresholdN ∗ = 35. We use the following parameters in this exam-ple: �F 1L = 0001, �F 1H = 0002, �R1L = 00015, �R1H = 0002,pF 1L = 0005, pR1L = 0006, pF 1H = 007, pR1H = 0085, �= 0015,�= 000125. Figure 10 shows the result of a single trace ofthis extended model. We see there exists a bi-stability effectin which the system transitions, after nearly five months,from a “bad” equilibrium, where the system is always underspeedup, to a “good” equilibrium, where speedup is hardlyused. Note that under the “good” equilibrium, most of thecustomers are new customers and there are very few returncustomers; however, under the “bad” equilibrium, most of thecustomers are returning customers. Similar to our originalmodel in §2, we see that in this case, utilizing speedup canresult in even more congestion. We see again that when sucha bi-stability exists, other mechanisms, such as admissioncontrol, may be more effective in navigating periods of highcongestion.

Figure 10. Simulation: New vs. return customers.

0 50 100 150 200 250 300 3500

20

40

No.

of

cust

omer

s

Q1 (new)

Fluid

0 50 100 150 200 250 300 3500

20

40

60Q1 (return)

Fluid

0 50 100 150 200 250 300 3500

50

100

t (days)

Q2

Fluid

No.

of

cust

omer

sN

o. o

f cu

stom

ers

5.2. Time Varying Arrivals

Another marked property of service systems is that customers’arrivals are often time varying (e.g., Gans et al. 2003, Greenet al. 2006, Yom-Tov and Mandelbaum 2014). We nowexplore the implications of having time-varying arrivals.

As discussed in Yom-Tov and Mandelbaum (2014) for aclosely related queuing system (with returns but no speedup),the impact of time-varying arrivals depends on the relation-ship of the period and amplitude of the arrival rate versusthe service duration. Time variation can substantially impactthe dynamics of our queuing system, especially when thescale of the service time is long but of the same order asthe time variation. Here, we discover speedup control cansometimes smooth the time variability. A complete analysisof the time-variability case is beyond the scope of thispaper, and there is currently little theory to support analysisof time-varying Filippov systems. Therefore, most of theobservations we present here are based on numerical andsimulation analysis.

We now consider a queuing system with the same stochas-tic dynamics as the system described in §2, except that thearrival process no longer has constant rate. We now modelthe arrival rate as a nonhomogeneous Poisson process withtime-varying arrival rate �4t5. We again use fluid modelsto provide insight for the stochastic model. Accordingly,we can modify our original ODE in Equation (3) to derivean ODE to describe the fluid dynamics of this system withtime-varying arrival rate as follows:

Q̇14t5= �4t5+ �Q24t5− 18Q14t5<N ∗9�L4Q14t5∧N5

− 18Q14t5¾N ∗9�H4Q14t5∧N51

Q̇24t5= −�Q24t5+ 18Q14t5<N ∗9pL�L4Q14t5∧N5

+ 18Q14t5¾N ∗9pH�H4Q14t5∧N50

(10)

In our analysis of this modified system, we find thedistinction between Case 1 and 2 still exists. In Case 1 we

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup474 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

have a distinct solution to the ODE, whereas in Case 2 thesystem is quite chaotic (i.e., very dependent on the specificstarting point and the phase of the arrival rate). Hence, weconcentrate on Case 1. In this case, the solution may notbe an equilibrium point as it was before but could be anorbit, which is a periodic function that the trajectory followsover time. This orbit, which we denote by q̄4t5, is closelyrelated to the solution of a (time-varying) ODE that alwaysor never uses speedup. We define qH4t5 as the solution forthe following ODE when speedup is always used.

q̇H1 4t5= �4t5+ �qH

2 4t5−�HqH1 4t51

q̇H2 4t5= −�qH

2 4t5+pH�HqH1 4t50

(11)

We similarly define qL4t5 as the solution for the ODE whenspeedup is never used. A complete analysis of such an ODEis given in Yom-Tov and Mandelbaum (2014). If the arrivalrate is periodic (as is the case in many service systems),qH 4t5 and qL4t5 are cyclic functions that exhibit similar timevariation that lags after the arrival rate function �4t5. Thisorbit’s period is the same as the period of the arrival rates,though the phase is shifted. Since we are in Case 1, one canview never using speedup as a worst case scenario; i.e., theaverage number of customers is the highest possible. In asense, qL4t5 is an upper bound for the long-term dynamicsof our fluid system: consider two trajectories that start at thesame initial point. One follows the dynamics described by(11) and the other follows the dynamics described by (10).The fluid content of Needy customers in the latter willalways be larger. Hence, qL

1 4t5 is an upper bounding functionfor q̄1. Similarly, qH

1 4t5 is a lower bounding function for q̄1.We start by considering a sinusoidal arrival process:

�4t5= 14805× 41+0012 sin42�t/f 55, t ¾ 0. The period f is24 hours, �L = 10474, �H = 20018, pL = 00667, pH = 00973,�= 10445, N = 150. Using numeric analysis, we find thatin Case 1, the orbit function q̄ is a function that duringvarious points of its cycle (determined by the cycle of timevariability in the arrival process) will follow either the upperbounding function, qL4t5, or the lower bounding function,qH

1 4t5, or stay along the speedup threshold, N ∗.Figure 11 presents some typical fluid approximations

and simulated sample paths of our stochastic system underdifferent threshold values. In Figure 11(a), the trajectoryconverges to the orbit qH4t5 where speedup is always used.Because of the periodic nature of the arrival process, we seethat the trajectory on the fluid model follows a cyclic orbitwith the same period as the arrival process. In Figure 11(e),the trajectory converges to N ∗. This is similar to the pseudo-equilibrium in Case 1.2 without periodic arrivals, where qH

and qL reside on opposite sides of the speedup threshold,N ∗, so that the trajectory is pulled rapidly back and forthmaking N ∗ an equilibrium. What is interesting in the caseof time-varying arrival rates is that this behavior creates anontime-varying equilibrium, N ∗. We see that using speedupimproves access to service at Station 1 by reducing theoffered load. It also has another benefit in that it also has the

power to remove time-variation and smooth the occupancylevel at Station 1. Thus, although �4t5 and, consequently,qH4t5 and qL4t5 are periodic functions with a period of 24hours, the fluid content of Needy customers is time-invariantand fixed at N ∗. Another possible trajectory of the fluidcontent is depicted in Figure 11(d). The orbit function, q̄4t5,can follow two of the trajectories: it follows qH 4t5, but whenit hits the speedup threshold, N ∗, it stays there until thearrival rate falls again, at which point it returns to trackingqH4t5. Thus, there is some smoothing of the occupancylevel at Station 1 (when Q14t5=N ∗); however, because thespeedup threshold is higher than in Figure 11(e), it is notheld constant for all time and the trajectory exhibits some(but not all) of the time variation of qH4t5. Figures 11(b)through 11(f) present simulated sample paths of the fluidsystems depicted in Figures 11(a) through 11(e). We see thatthe fluid approximation is quite accurate in describing thetime-varying system dynamics.

Although we see some very interesting dynamics arisewhen incorporating time variation into our model, we focusedon a numeric setting that allows us to observe the nuances.We also wish examine the impact of time-varying arrivalsin the ICU setting. In the ICU—unlike the ED setting inYom-Tov and Mandelbaum (2014) and Green et al. (2006)—the length of stay (LOS) is quite long compared to thetime variability. Specifically, the arrival rate varies at thetime scale of hours, while ICU LOS is typically threeto four days, spanning a few arrival rate cycles. Becauseof this discrepancy in the time scale of variation versusservice time, Yom-Tov and Mandelbaum (2014) suggeststhat the impact of time variation is likely to be small. Wealso find this to be true when considering our system withspeedup. In Figures 13(a) and 13(b), we present the fluidapproximation and simulated sample path of �1 usingidentical parameters as in Figures 7(a) and 7(b), except thearrival rate is according to the empirical time-varying arrivalrates depicted in Figure 12. We observe the system stillvaries around the chosen threshold, and it is difficult toascertain substantial differences from Figure 7(a). Althoughwe find that in this setting incorporating daily variability doesnot significantly alter the system dynamics, we can see in theprevious analysis that the dynamics can change dramaticallywhen incorporating time-varying arrivals. We leave furtherexploration of this type of time-varying, state-dependentqueuing system for future research.

6. ConclusionsIn this work, we consider a queuing model where servicerates and return probabilities increase when the system isoverloaded. We analyze the dynamics of this state-dependentqueuing model to gain insight into the impact speedup andreturns have on system dynamics. The model presented hereprovides insights into the pros and cons of using speedup ina service system where customers may return to service.

We find that there are two main parameter regimes thatdefine whether speedup can be a beneficial or detrimental

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 475

Figure 11. Fluid approximations and sample paths for time-varying arrivals with different threshold under Case 1conditions.

0 1 2 3 4 50

20

40

60

80

100

120

140

160

180

Time (days)

0 1 2 3 4 5

Time (days)

Num

ber

of c

usto

mer

s

0

20

40

60

80

100

120

140

160

180

Num

ber

of c

usto

mer

s

q1(t)q2(t)

qL(t)qH(t)

�(t)

(a) Equilibrium is q1H(t) (r = 0.85): Fluid

(b) Equilibrium is q1H(t) (r = 0.85): Sample path

0 1 2 3 4 5 00

50

100

150

2 4 6 8 100

20

40

60

80

100

120

140

160

180

Time (days) Time (days)

Num

ber

of c

usto

mer

s

00

50

100

150

2 4 6 8 10

Time (days)

0 2 4 6 8 10

Time (days)

Num

ber

of c

usto

mer

s

0

50

100

150

Num

ber

of c

usto

mer

s

Num

ber

of c

usto

mer

s

(e) Equilibrium is N* (r = 0.62): Fluid

(f) Equilibrium is N* (r = 0.62): Sample path

(c) Equilibrium is a mix between N*

and qH(t) (r = 0.75): Fluid

(d) Equilibrium is a mix between N* and qH(t)(r = 0.75): Sample path

Simulation

Simulation

Fluid

Fluid

Simulation

Fluid

q1(t)

q2(t)

qL(t)

qH(t)

�(t)

q1(t)

q2(t)

qL(t)qH(t)�(t)

operational tool to help alleviate temporary congestion. Suchanalysis provides tools to enable practitioners to assess thepotential benefits and pitfalls of different speedup policies.We find that in some cases speedup can be beneficial tohelp alleviate congestion. In such situations, the amount ofcongestion and frequency of speedup can be specified viathe speedup threshold, N ∗. In other cases, the use of speedup

can exacerbate congestion. Moreover, an interesting bi-stability can arise, which demonstrates the potential problemsassociated with using speedup.

We demonstrate via simulation that the fluid approximationto our state-dependent queuing system can be very accurate.However, there are scenarios where the accuracy suffers—particularly in small systems and/or when speedup is used

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup476 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

Figure 12. Time-varying arrival rate to ICU (in number of patients/hour).

0 6 12 18 240.2

0.4

0.6

0.8

1.0

Time (hours)A

rriv

al r

ate

Figure 13. Time-varying ICU: Fluid approximation and sample path.

0 5 10 15 20 250

10

20

30

40

Time (days)

Num

ber o

f pat

ient

s

q1q2

qL

qH

(a) Fluid approximation

0 5 10 15 20 25 30 35 40 450

10

20

30

40Q

1

Time (days)

(b) Sample path

around 25% or 75% of the time. In this work, we derivedthe fluid directly. Establishing a proof of the limit in afunctional weak law of large numbers sense introducesseveral technical challenges due to the discontinuity of theODE. However, it would be useful to be able to show sucha result. Additionally, it would be interesting to considerrefinements to the fluid approximation.

Finally, we consider two important extensions for ourmodel: (i) differing dynamics for new and returning cus-tomers and (ii) time-varying arrivals. This analysis providessome additional insights but also suggests that our originalstylized model has value in shedding light on the much morecomplex reality. We observe, for example, that in the ICUapplication one need not explicitly consider time-varyingdynamics. Instead, one may draw important conclusions onthe impact of using speedup from the time-stationary model.Nevertheless, we find the time-varying dynamics can be veryinteresting in its own right and plan to investigate it furtherin future work.

Appendix A. Miscellaneous Proofs

Proof of Theorem 3.1. 1. We begin with the instability result.Recall for instability, we must have the total fluid content of jobs inthe system grow without bound. That is, we consider QT =Q1 +Q2.The dynamics of QT can be summarized as

Q̇T = Q̇1 + Q̇2 = �− 41 −pL5�L4Q1 ∧N50

If the system is unstable, then limt→� QT 4t5/t > 0. We integrateand solve for QT 4t5. We have

limt→�

QT 4t5

t= �− 41 −pL5�L lim

t→�

1t

∫ t

04Q14�5∧N5d�

¾ �− 41 −pL5�L limt→�

1t

∫ t

0N d�

= �− 41 −pL5�LN > 01

if N <�

41 −pL5�L

0 (A1)

2. For the stability and equilibrium result, we first show thatq̄ = 4�/441 − pL5�L51 4�pL5/441 − pL5�55 is a globally stableequilibrium. The stability result follows from the finiteness of q̄.To show global stability, we use the following Lyapunov function:

V 4Q5= �Q1 − q̄1� + �Q2 − q̄2�0

We must show that for all Q 6= q̄, V̇ 4Q5 < 0. To do this, we mustexamine a few cases:

(a) Q1 > q̄11Q2 > q̄2.

V̇ 4Q5= Q̇1 + Q̇2 = �− 41 −pL5�L4Q1 ∧N5

< �− 41 −pL5�Lq̄1 = 00

(b) Q1 < q̄11Q2 < q̄2.

V̇ 4Q5= −Q̇1 − Q̇2 = −�+ 41 −pL5�L4Q1 ∧N5

<−�+ 41 −pL5�Lq̄1 = 00

(c) Q1 > q̄11Q2 < q̄2.

V̇ 4Q5= Q̇1 − Q̇2 = �+ 2�Q2 − 41 +pL5�L4Q1 ∧N5

< �+ 2�q̄2 − 41 +pL5�Lq̄1 = 00

(d) Q1 < q̄11Q2 > q̄2.

V̇ 4Q5= −Q̇1 + Q̇2 = −�− 2�Q2 + 41 +pL5�L4Q1 ∧N5

<−�− 2�q̄2 + 41 +pL5�Lq̄1 = 00

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 477

(e) Q1 = q̄11Q2 > q̄2.

V̇ 4Q5=Q̇2 =−�Q2 +pL�L4Q1 ∧N5<−�q̄2 +pL�Lq̄1 =00

(f) Q1 = q̄11Q2 < q̄2.

V̇ 4Q5=−Q̇2 =�Q2 −pL�L4Q1 ∧N5<�q̄2 −pL�Lq̄1 =00

(g) Q1 > q̄11Q2 = q̄2.

V̇ 4Q5=Q̇1 =�+�Q2 −�L4Q1 ∧N5<�+�q̄2 −�Lq̄1 =00

(h) Q1 < q̄11Q2 = q̄2.

V̇ 4Q5= −Q̇1 = −�− �Q2 +�L4Q1 ∧N5

<−�− �q̄2 +�Lq̄1 = 00 �

A.1. Proofs for Ordinary Differential Equationswith Discontinuities

Our system is a piecewise-smooth set of ordinary differentialequations. As such, it fits in to the framework of Filippov (1988).In our analysis, we use Lyapunov techniques as well the methodsoutlined in di Bernardo et al. (2008).

Primitives

To begin, we represent our dynamic system by the followingdifferential equation using the Filippov convex method. Moredetails of this method can be found in di Bernardo et al. (2008)and Filippov (1988). The basic premise is to divide the statespace into regions where the ODE is smooth and continuous inorder to leverage existing results of smooth dynamical systems.A separate region, the switching boundary,3 is defined as thestates of discontinuity in the ODE. The approach is to transformthe differential equation into a differential inclusion, where thedifferential function is now a set-valued function. Additionally,Filippov (1988) proves that solutions to the original discontinuousdifferential equation coincide with solutions to the appropriatelydefined differential inclusion. In what follows, we will discuss firsthow to transform Equation (3) into the appropriate differentialinclusion. Next we will demonstrate the desired results for thedifferential inclusion, which will imply the result holds for theoriginal differential equation. Note that in our case, the differentialequation (and subsequently the differential inclusion) does notdepend on t but only on Q.

To start, we separate the state space, �2+ into two regions, DL

and DH , and the switching boundary, è, between them as follows:

DL = 8Q2 Q1 <N ∗91 DH = 8Q2 Q1 >N ∗91

è= 8Q2 Q1 =N ∗90

In the regions DL and DH , the ODE is smooth. However, theODE is discontinuous at the switching boundary è. The Filippovmethodology overcomes this by transforming the differentialequation into a differential inclusion by using a convex combinationof the smooth flows defined in DL and DH on the switchingboundary, è. We define the fluid function Fi4Q5, Q ∈Di, as thesmooth ODE in these regions:

FL4Q5=

(

�+ �Q2 −�L4Q1 ∧N5

−�Q2 +pL�L4Q1 ∧N5

)

1

FH 4Q5=

(

�+ �Q2 −�H 4Q1 ∧N5

−�Q2 +pH�H 4Q1 ∧N5

)

0

Note that even though the ODE is nondifferentiable at Q1 =N , asis customary, it is still considered smooth, and not discontinuous,at this point. The real challenge comes at the switching boundary,i.e., when Q1 =N ∗. Now, our ODE Q̇ = F 4Q5 can be representedvia a Filippov ODE (a.k.a. a differential inclusion):

Q̇∈F4Q5=

FL4Q51 if Q∈DL1

FH 4Q51 if Q∈DH 1

841−�5FL4Q5

+�FH 4Q5 �0¶�¶191 if Q∈è0

(A2)

Proof of Theorem 4.1. We start by stating the existence resultin Filippov (1988) in terms of our notation. The result is fora differential inclusion; however, the Filippov method utilizesthe fact that solutions of the differential inclusion coincide withsolutions of the original discontinuous differential equation. Hence,if our differential inclusion satisfies the conditions of the followingtheorem, this will imply existence of a solution to our ODE (3).

Theorem A.1 (Theorem 1, Chapter 2, Section 7 of Filippov1988). Let F4Q5 be a differential inclusion that satisfies thefollowing conditions in the domain G:

1. F4Q5 is nonempty for all Q ∈G.2. F4Q5 is bounded and closed for all Q ∈G.3. F4Q5 is convex for all Q ∈G.4. The function F is upper semicontinuous in Q.

Then for any point q0 ∈G, there exists a solution of the problem

Q̇ ∈F4Q51 Q405= q00

We will consider the domain G = 601Qmax7 × 601Qmax7 forsome arbitrary finite constant, Qmax <�. Now, we just have todemonstrate that the conditions hold for all Q ∈G. It is easy to seethat conditions 1–4 hold for all Q ∈DL ∪DH , as in these regionsF is a continuous real-valued function (rather than a set-valuedfunction). Thus, F4Q5 is a single point, which is bounded aboveby max8� + �Qmax1pH�H 4Qmax ∧ N59 and bounded below bymin8�−�H 4Qmax ∧N51−�Qmax9. Any continuous function is alsoupper semicontinuous, so the fourth condition follows.

It remains to show the four conditions hold for any Q on theswitching boundary, è. By the same argument as for Q ∈DL ∪DH ,F4Q5 is bounded for any Q ∈è. By definition of F in (A2), F4Q5is closed and convex for Q ∈è because it is a convex combinationof FH and FL. Since both of these functions are nonempty, sois F. Finally, to show F is upper semicontinuous on è, we needto show that F is upper semicontinuous for every Q ∈ è. Theset-valued function F2 è→ Y ⊂�2

+ is upper semicontinuous at apoint Q ∈è provided that for each open set V in Y containingF4Q5, there is an open set U in è containing Q such that ifQ′ ∈ U , then F4Q′5 ⊆ V . By the definition of the inclusion,for an Q ∈ è, F4Q5 = 841 − �5FL4Q5+ �FH 4Q5 � 0 ¶ � ¶ 19.Consider an open set V that contains F4Q5: there exists an� > 0 such that for every f ∈ F4Q5, f + � ∈ V . Now by thecontinuity of FH and FL, there exists � > 0 such that if �Q′ −Q�< �,then �FH 4Q5− FH 4Q

′5�< �/2 and �FL4Q5− FL4Q′5�< �/2. Thus,

�641 −�5FL4Q5+�FH 4Q57− 641 −�5FL4Q′5+�FH 4Q

′57� < �for all 0 ¶ � ¶ 1. Hence, F4Q′5⊂ V , and we have derived thenecessary open set U = 8Q′ � �Q′ −Q�< �9∩è (recall that theintersection of two open sets is open). This demonstrates that F isupper semicontinuous in è. All conditions hold on the switchingboundary. Therefore, there exists a solution to the differentialinclusion and subsequently our ODE. �

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup478 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

Proof of Theorem 4.2. We consider each of the two cases.1. 6qH

1 < qL1 7.

(a) We first consider the case where N < qH1 . Similar to the

instability proof of Theorem 3.1, we consider the total number ofjobs in the system and show that limt→� QT 4t5/t > 0. We have that

Q̇T = Q̇1 + Q̇2 = �− 18Q14t5<N ∗941 −pL5�L4Q1 ∧N5

− 18Q14t5¾N ∗941 −pH 5�H 4Q1 ∧N50

We integrate both sides, divide by t and take the limit as t → �:

limt→�

QT 4t5

t=�− lim

t→�

1t

∫ t

04Q14�5∧N5

·[

41−pL5�L18Q14�5<N ∗9+41−pH 5�H18Q14�5¾N ∗9

]

d�

>�−41−pH 5�H limt→�

1t

∫ t

04Q14�5∧N5d�

¾�−41−pH 5�H limt→�

1t

∫ t

0N d�

=�−41−pH 5�HN >�−41−pH 5�HqH1 =00

The first inequality is because in this case qH1 < qL

1 , which impliesthat 41 − pL5�L < 41 − pH 5�H . The last inequality comes from theassumption that N <�/441 −pH 5�H 5= qH

1 . Hence, the system isunstable if N < qH

1 .(b) We next consider the case where N < qL

1 and N ∗ = � (i.e.,speedup is never used). This is simply the result of Theorem 3.1.

2. 6qH1 ¾ qL

1 7.(a) We first consider the case where N < qL

1 . Using the sameargument as before, we now have

limt→�

QT 4t5

t=�− lim

t→�

1t

∫ t

04Q14�5∧N5

·[

41−pL5�L18Q14�5<N ∗9+41−pH 5�H18Q14�5¾N ∗9

]

d�

¾�−41−pL5�L limt→�

1t

∫ t

04Q14�5∧N5d�

¾�−41−pL5�L limt→�

1t

∫ t

0N d�

=�−41−pL5�LN >00

The first inequality is because qH1 ¾ qL

1 . The last inequality comesfrom the assumption that N <�/441 −pL5�L5= qL

1 . Hence, thesystem is unstable if N < qL

1 .(b) Now we consider the case where N < qH

1 and N ∗ <qL1 .

Again, we focus on the total workload in the original system. Wehave that

limt→�

QT 4t5

t=�− lim

t→�

1t

∫ t

04Q14�5∧N5

·[

41−pL5�L18Q14�5<N ∗9+41−pH 5�H18Q14�5¾N ∗9

]

d�

>�− limt→�

1t

∫ t

0

[

N ∗41−pL5�L18Q14�5<N ∗9

+qH1 41−pH 5�H18Q14�5¾N ∗9

]

d�

>�− limt→�

1t

∫ t

0

[

qL1 41−pL5�L18Q14�5<N ∗9

+qH1 41−pH 5�H18Q14�5¾N ∗9

]

d�

=�− limt→�

1t

∫ t

0�d�=00

The inequalities come from the assumptions that N < qH1 and

N ∗ < qL1 . Hence, the system is unstable. �

Proof of Theorem 4.3. Defining equilibria points and the ODEflow. Our theorem distinguishes between seven cases and threeequilibria points. We start by identifying these points and theconditions under which they arise as equilibria; we then provestability. To do so, we refer back to the primitives defined earlierfor Filippov ODEs, which transform the original ODE into adifferential inclusion.

We start by examining each region, DH and DL. If the solutiontrajectory never leaves a region Di once it enters the region, thenthe solution can be characterized with standard methods for regularcontinuous ODEs (Guckenheimer and Holmes 2002). Therefore,we first define the equilibria of FL4Q5 and FH 4Q5. That is, weconsider the long-term behavior of a system with dynamics that aredefined by the continuous ODE FL4Q5 (FH 4Q5) across the entirestate space in the case where speedup is never (always) used. Weassume there is no switching boundary or speedup threshold. Bythe methods of di Bernardo et al. (2008), if a locally or globallystable equilibrium, q̄L (q̄H ), of the continuous ODE FL4Q5 (FH 4Q5)is in DL (DH ), then this directly translates into local stability ofq̄L (q̄H ) in the original discontinuous ODE.

Lemma A.1. If qL1 <N , then the continuous ODE FL has a globally

stable equilibrium at qL. If qL ∈ DL and qL1 < N , then qL is

a locally stable equilibrium in the original discontinuous ODEdefined in (3).

Proof. The first part comes from Theorem 3.1. The second part istypical for piecewise-smooth ODEs and follows from Guckenheimerand Holmes (2002) and our stability assumption. Intuitively, by thestability of qL in the continuous ODE defined by FL, there exists asmall ball around qL such that trajectories that start within the ballwill converge to qL and stay there. If qL is in DL, then one canalso select a small ball around qL such that (1) trajectories thatstart within the ball will converge to qL and (2) the ball is entirelycontained in DL. Then starting a trajectory in this small ball, butletting the system dynamics be defined according to our original,discontinuous ODE in (3), the trajectory will stay in the ball, whichmeans they will stay in DL and follow the same dynamics as thecontinuous ODE FL, since it won’t hit the switching boundary, è,or enter the other region, DH . Thus, qL is locally stable. �Lemma A.2. If qH

1 < N , then the continuous ODE FH has aglobally stable equilibrium at qH . If qH ∈DH and qH

1 <N , thenqH is a locally stable equilibrium in the original discontinuousODE defined in (3).

Proof. The results can be derived with the same techniques as inthe proof for Theorem 3.1 and Lemma A.1.

Lemma A.1 proves the existence of a locally stable equilibriumat qL in Cases 1.3, 2.1.2, 2.1.3, and 2.2 because qL ∈DL holds inthese cases, as demonstrated for Case 1.3 in Figure 3. Similarly,Lemma A.2 proves the existence of a locally stable equilibriumat qH in Cases 1.1, 2.1.1, and 2.1.2. We will later use Lyaponovtechniques to prove the global stability of these equilibria in theappropriate cases.

Next, we analyze the dynamics of the system on the switchingboundary, è, and identify our third equilibrium that lies in thisspace. To do this, we look at the forces on either side of theswitching boundary. Specifically, we look at the component of Finormal to è, which we denote by Li. These measures are oftenreferred to as the Lie derivatives.

LL = �+ �Q2 −�L4N∗ ∧N51

LH = �+ �Q2 −�H 4N∗ ∧N50

(A3)

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 479

Figure A.1. Example of a sliding motion.

0 2 4 6 8 10

× 104

0

100

200

300

400

500

Time

Q1

Q2

We have the following three cases to consider:1. LL < 0 and LH < 0: a flow that hits è will transition from

DH to DL. If the flow is already in DL, it will stay in DL. Because�L <�H , for all 8Q ∈è2 Q2 < 4�L4N

∗ ∧N5−�5/�9, both LL andLH are negative, and the transition will be from DH to DL;

2. LL > 0 and LH > 0: a flow that hits è will transition fromDL to DH . If the flow is already in DH , it will stay in DH . For all8Q ∈è2 Q2 > 4�H 4N

∗ ∧N5−�5/�9, both LL and LH are positive,and the transition will be from DL to DH .

3. LLLH < 0: a flow that hits è will stay on è—potentiallyforever. The flow is said to be in a sliding mode, in which Q1

is constant and equal to N ∗ while only Q2 changes. Figure A.1illustrates an example of a sliding mode flow where N ∗ = 200. If4�L4N

∗ ∧N5−�5/�¶Q2 ¶ 4�H 4N∗ ∧N5−�5/�, we have that

LL < 0 and LH > 0, so then the ODE is in a sliding mode on theswitching boundary è. The importance of this sliding mode isthere could be an additional equilibrium inside the sliding set. Thispoint is typically not a fixed point in the standard sense since theODE is nonzero at that point. However, it is still an equilibriumby Definition 2.2 because if a flow starts at that point, it staysthere. In some cases, this special equilibrium is a unique and stableequilibrium. We call this type of equilibrium a pseudo-equilibriumas in di Bernardo et al. (2008).

Definition A.1. We call a point q̄ a pseudo-equilibrium if it isan equilibrium of the sliding flow; i.e., for some scalar 0 < � < 1,

Fs = 41 − �5FL4q̄5+ �FH 4q̄5= 01 q̄ ∈è0 (A4)

Note the similarities to the Filippov ODE (A2). When theconvex combination is active in (A2), i.e., � ∈ 40115, there existsan equilibrium on the switching boundary è and � = �.

Lemma A.3. The point 4N ∗1�qL2 + 41 − �5qH

2 5 is a pseudo-equilibrium in Cases 1.2 and 2.1.2.

Proof. Solving (A4) yields

� =�− 41 −pL5�L4N

∗ ∧N5

41 −pH 5�H 4N∗ ∧N5− 41 −pL5�L4N

∗ ∧N50 (A5)

We have that 0 < � < 1 if the following three conditions holdsimultaneously:

(a) �− 41 −pL5�L4N∗ ∧N5> 0 ⇒ N ∗ ∧N < qL

1 ,

(b) 41−pH 5�H 4N∗ ∧N5− 41−pL5�L4N

∗ ∧N5 > 0 ⇒ qH1 < qL

1 ,and

(c) � − 41 − pL5�L4N∗ ∧ N5 < 41 − pH 5�H 4N

∗ ∧ N5 −

41 −pL5�L4N∗ ∧N5 ⇒ qH

1 <N ∗ ∧N .These are exactly the conditions of Case 1.2, which means

that in this case there exists a pseudo-equilibrium on the switch-ing boundary è. Substituting � from (A5) into (A4) gives theresulting equilibrium: 4N ∗1 444N ∗ ∧N5 − qH

1 5/4qL1 − qH

1 55qL2 +

44qL1 − 4N ∗ ∧N55/4qL

1 − qH1 55q

H2 5. We will show later that in

this case this point is a globally stable equilibrium. By defining�= 44N ∗ ∧N5−qH

1 5/4qL1 −qH

1 5, we can express the equilibrium as4N ∗1�qL

2 − 41 −�5qH2 5. Note that under the above three conditions

(Case 1.2) 0 <�< 1.Another scenario where 0 < � < 1 is if the following three

conditions hold simultaneously:(a) �− 41 −pL5�L4N

∗ ∧N5< 0 ⇒N ∗ ∧N > qL1 ,

(b) 41 − pH 5�H 4N∗ ∧N5 − 41 − pL5�L4N

∗ ∧N5 < 0 ⇒

qH1 > qL

1 , and(c) � − 41 − pL5�L4N

∗ ∧N5 > 41 − pH 5�H 4N∗ ∧N5 −

41 −pL5�L4N∗ ∧N5⇒ qH

1 >N ∗ ∧N .These are exactly the conditions of Cases 2.1.2 (for qL

1 6= qH1 )

and 2.2, which means that in these cases there also exists apseudo-equilibrium on the switching boundary è. Again thispseudo-equilibrium is 4N ∗1�qL

2 + 41 −�5qH2 5. Experiments show

that this point is not stable. If we start the system at that point itwill stay there, but very small changes from that point will bringus to one of the other two equilibria of the system. �

Locally Stable Equilibria. Combining the results of Lemmas A.1through A.3 yields our (Lyapunov/local) stability results forCase 2.1.2 and 2.2 and the existence of the third equilibrium inCase 2.1.2.

Globally Stable Equilibria. We continue by proving the globalstability results (Cases 1.1 through 1.3, 2.1.1, and 2.1.3). To showglobal stability in the sense of Lyapunov, we need to identify aLyapunov function and prove that for all Q ∈�2

+\8q̄9, the derivativeof the Lyaponov function is strictly negative. We use the followingLyapunov function:

V 4Q5= �Q1 − q̄1� + �Q2 − q̄2� (A6)

where q̄ is the specified equilibrium. We use the Filippov method-ology as describe earlier, which redefines the ODE as a differentialinclusion so that on the switching boundary, è, is the convexcombination of the surrounding smooth ODEs in (A2) for F4Q5.We continue to use this definition of our ODE and utilize thegeneralized Lyapunov theory for set valued functions. Using theapproach in Shevitz and Paden (1994), we need to show that theset value map for our generalized Lyapunov derivative is negativefor all states not equal to the equilibrium in order to establishglobal stability.

We have two cases to consider for our set value map, generalizedLyapunov derivative:

1. 6Q1 6=N ∗7.

˙̃V 4Q5=

V̇ 4Q51 Q1 6= q̄11 Q2 6= q̄23

Q̇11 Q1 > q̄11 Q2 = q̄23

−Q̇11 Q1 < q̄11 Q2 = q̄23

Q̇21 Q1 = q̄11 Q2 > q̄23

−Q̇21 Q1 = q̄11 Q2 < q̄20

(A7)

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup480 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

2. 6Q1 =N ∗7. In this case, the flow is on the switching boundary,è.

˙̃V 4Q5=

�V̇ L4Q5+ 41 −�5V̇ H 4Q51

� ∈ 601171 Q1 6= q̄11 Q2 6= q̄23

�Q̇L1 + 41 −�5Q̇H

1 1

� ∈ 601171 Q1 > q̄11 Q2 = q̄23

−�Q̇L1 − 41 −�5Q̇H

1 1

� ∈ 601171 Q1 < q̄11 Q2 = q̄23

�Q̇L2 + 41 −�5Q̇H

2 1

� ∈ 601171 Q1 = q̄11 Q2 > q̄23

−�Q̇L2 − 41 −�5Q̇H

2 1

� ∈ 601171 Q1 = q̄11 Q2 < q̄20

(A8)

where V L and V H correspond to the Lyapunov function whenQ1 <N ∗ and Q1 >N ∗, respectively.

In what follows, we will use this generalized Lyapunov theory toprove the global stability in Theorem 4.3. Because of the immenseamount of algebra involved in this proof, we only include herethe proof for Case 1.2 while noting the rest of the cases (1.1, 1.3,2.1.1, and 2.1.3) will follow similarly. We need to show that for allQ 6= q̄, ˙̃V 4Q5 < 0.

Case 1.2. qH1 < 4N ∗ ∧ N5 < qL

1 : Define the stability point asq̄ = 4q̄14N

∗51 q̄24N∗55 = 4N ∗1�qL

2 + 41 − �5qH2 5, where � =

44N ∗ ∧N5− qH1 5/4q

L1 − qH

1 5. We will suppress the dependenceon the control factor, N ∗, for notational compactness. Note thatq̄1 ∧N ∈ 4qH

1 1 qL1 5 and q̄2 ∈ 4qL

2 1 qH2 5. Moreover, by Assumption 4.1,

N > qH1 . There are a number of subcases to consider within each

of our two cases:(i) 6Q1 6=N ∗7

(a) Q1 > q̄1 =N ∗, Q2 > q̄2.

˙̃V 4Q5= V̇ 4Q5= Q̇1 + Q̇2

= �+ �Q2 −�H 4Q1 ∧N5− �Q2 +pH�H 4Q1 ∧N5

= �− 41 −pH 5�H 4Q1 ∧N5

< �− 41 −pH 5�H 4q̄1 ∧ qH1 5= �− 41 −pH 5�Hq

H1 = 00

(b) Q1 < q̄1 =N ∗, Q2 < q̄2.

˙̃V 4Q5= V̇ 4Q5=−Q̇1 −Q̇2

=−�−�Q2 +�L4Q1 ∧N5+�Q2 −pL�L4Q1 ∧N5

=−�+41−pL5�L4Q1 ∧N5<−�+41−pL5�LqL1 =00

(c) Q1 < q̄1 =N ∗, Q2 > q̄2.

˙̃V 4Q5= V̇ 4Q5= −Q̇1 + Q̇2

= −�− �Q2 +�L4Q1 ∧N5− �Q2 +pL�L4Q1 ∧N5

= −�− 2�Q2 + 41 +pL5�L4Q1 ∧N5

<−�− 2�q̄2 + 41 +pL5�L4q̄1 ∧N5

<−�− 2�qL2 + 41 +pL5�Lq

L1 = 00

(d) Q1 > q̄1 =N ∗, Q2 < q̄2.˙̃V 4Q5= V̇ 4Q5= Q̇1 − Q̇2

= �+ �Q2 −�H 4Q1 ∧N5+ �Q2 −pH�H 4Q1 ∧N5

= �+ 2�Q2 − 41 +pH 5�H 4Q1 ∧N5

< �+ 2�q̄2 − 41 +pH 5�H 4q̄1 ∧ qH1 5

¶ �+ 2�qH2 − 41 +pH 5�Hq

H1 = 00

(e) Q1 > q̄1 =N ∗, Q2 = q̄2.˙̃V 4Q5=Q̇1 =�+�Q2 −�H4Q1 ∧N5<�+�q̄2 −�H4q̄1 ∧qH

1 5

¶�+�qH2 −�Hq

H1 =00

(f) Q1 < q̄1 =N ∗, Q2 = q̄2.˙̃V 4Q5= −Q̇1 = −�− �Q2 +�L4Q1 ∧N5

<−�− �qL2 +�Lq

L1 = 00

(ii) 6Q1 = N ∗7. We want to show that for all � ∈ 60117,˙̃V 4Q5 < 0:

(a) Q1 = q̄1 =N ∗, Q2 > q̄2.˙̃V 4Q5=�Q̇L

2 +41−�5Q̇H2

=�6−�Q2 +pL�L4Q1 ∧N57

+41−�56−�Q2 +pH�H 4Q1 ∧N57

<�6−�q̄2 +pL�L4q̄1 ∧N57

+41−�56−�q̄2 +pH�H 4q̄1 ∧N57

<�6−�qL2 +pL�Lq

L1 7

+41−�56−�q̄2 +pH�H 4q̄1 ∧N57

=41−�56−�q̄2 +pH�H 4q̄1 ∧N57

=41−�5

[

pH�H 4N∗∧N5−�

(

4N ∗ ∧N5−qH1

qL1 −qH

1

qL2

+qL

1 −4N ∗ ∧N5

qL1 −qH

1

qH2

)]

=41−�5

[

pH�H 4N∗∧N5

−�

(

4N ∗ ∧N54qL2 −qH

2 5−qH1 qL

2 +qL1 q

H2

qL1 −qH

1

)]

=41−�5

[

pH�H 4N∗∧N5

−4N ∗ ∧N54pL−pH 5�L�H −�4pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

=41−�5

[

pH�H 4N∗∧N5−4N ∗

∧N5

·4pL−pH 5�L�H −4�/4N ∗ ∧N554pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

<41−�5

[

pH�H 4N∗∧N5−4N ∗

∧N5

·4pL−pH 5�L�H −4�/qH

1 54pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

=41−�5

[

pH�H 4N∗∧N5−4N ∗

∧N5

·4pL−pH5�L�H −41−pH5�H4pL�L−pH�H5

41−pH5�H −41−pL5�L

]

=01

∀�0

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use SpeedupOperations Research 62(2), pp. 462–482, © 2014 INFORMS 481

(b) Q1 = q̄1 =N ∗, Q2 < q̄2.

˙̃V 4Q5=−�Q̇L2 −41−�5Q̇H

2

=�6�Q2−pL�L4Q1 ∧N57+41−�56�Q2−pH�H 4Q1 ∧N57

<�6�q̄2 −pL�L4q̄1 ∧N57+41−�56�q̄2 −pH�HqH1 7

¶�6�q̄2 −pL�L4q̄1 ∧N57+41−�56�qH2 −pH�Hq

H1 7

=�6�q̄2 −pL�L4q̄1 ∧N57

=41−�5

[

−pL�L4N∗∧N5

+�

(

4N ∗ ∧N5−qH1

qL1 −qH

1

qL2 +

qL1 −4N ∗ ∧N5

qL1 −qH

1

qH2

)]

=41−�5

[

pH�H 4N∗∧N5

−�

(

4N ∗ ∧N54qL2 −qH

2 5−qH1 qL

2 +qL1 q

H2

qL1 −qH

1

)]

=41−�5

[

−pL�L4N∗∧N5

+4N ∗ ∧N54pL−pH 5�L�H −�4pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

=41−�5

[

−pL�L4N∗∧N5+4N ∗

∧N5

·4pL−pH 5�L�H −4�/4N ∗ ∧N554pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

<41−�5

[

−pL�L4N∗∧N5+4N ∗

∧N5

·4pL−pH 5�L�H −4�/qL

1 54pL�L−pH�H 5

41−pH 5�H −41−pL5�L

]

=41−�5

[

−pL�L4N∗∧N5+4N ∗

∧N5

·4pL−pH5�L�H −41−pL5�L4pL�L−pH�H5

41−pH5�H −41−pL5�L

]

=01

∀�0

This concludes the proof for the global stability of Case 1.2. �

Appendix B. Markov Chain Performance Measures

P4speedup5

=�40105(

41 −ph5�h

41 −pl5�l

)T−1∑

j

1j!

(

�pl

41 −pl5�

)j

·

( N∑

i=T

1i!

(

�

41 −ph5�h

)i

+

�∑

i=N+1

1N !N i−N

(

�

41 −ph5�h

)i )

1

P4Wait > 05

=�40105(

41 −ph5�h

41 −pl5�l

)T−1∑

j

1j!

(

�pl

41 −pl5�

)j

·

�∑

i=N+1

1N !N i−N

(

�

41 −ph5�h

)i

1

�40105=[

∑

j

1j!

(

�pl

41−pl5�

)j(T−1∑

i=0

1i!

(

�

41−pl5�l

)i

+

(

41−ph5�h

41−pl5�l

)T−1 N∑

i=T

1i!

(

�

41−ph5�h

)i

+

(

41−ph5�h

41−pl5�l

)T−1 �∑

i=N+1

1N !N i−N

(

�

41−ph5�h

)i)]−1

0

(B1)

Endnotes1. These parameters were inspired by an ICU application.2. The timing for such shift is unpredictable: we have simulationruns where the shift occurs within a few days and others that takemuch longer.3. The switching boundary is also often referred to as a discontinu-ity set, discontinuity boundary, or switching manifold.

AcknowledgmentsThe authors thank the anonymous reviewers, an associate editor,and the area editor for their valuable suggestions. The authorsare grateful to Mor Armony, Linda Green, and Ward Whitt fortheir support and feedback during the course of this research.The authors also thank Marla Gardner and John Greene for theirhelp in preparing the ICU data. This research was conductedwhile the second author was a postdoctoral researcher at ColumbiaUniversity—she would like to gratefully acknowledge the wonderfulhospitality of this institution.

A previous version of this paper placed second in the INFORMS2012 JFIG best paper competition under the title “When toUse Speedup: An Examination of Intensive Care Units withReadmissions.”

ReferencesAnand K, Pac MF, Veeraraghavan S (2011) Quality-speed conundrum:

Trade-offs in customer-intensive services. Management Sci. 57(1):40–56.

Armony M, Maglaras C (2004) Contact centers with a call-back option andreal-time delay information. Oper. Res. 52(4):527–545.

Ata B, Shneorson S (2006) Dynamic control of an M/M/1 service sys-tem with adjustable arrival and service rates. Management Sci. 52:1778–1791.

Bekker R, Borst SC (2006) Optimal admission control in queues withworkload-dependent service rates. Probab. Engrg. Informational Sci.20:543–570.

Bekker R, Boxma OJ (2007) An M /G/1 queue with adaptable service speed.Stochastic Models 23:373–396.

Boxma OJ, Vlasiou M (2007) On queues with service and interarrival timesdepending on waiting times. Queuing Systems 56:121–132.

de Véricourt F, Jennings OB (2008) Dimensioning large-scale membershipservices. Oper. Res. 56(1):173–187.

de Vericourt F, Zhou Y-P (2005) Managing response time in a call-routingproblem with service failure. Oper. Res. 53(6):968–981.

di Bernardo M, Budd CJ, Champneys AR, Kowalczyk P (2008) Piecewise-Smooth Dynamical Systems: Theory and Applications (Springer,London).

Durbin CG, Kopel RF (1993) A case-control study of patients readmitted tothe intensive care unit. Critical Care Medicine 21:1547–1553.

Filippov AF (1988) Differential Equations with Discontinuous RighthandSides (Kluwer Academic Publishers, Dordrecht, The Netherlands).

Gans N, Koole G, Mandelbaum A (2003) Telephone call centers: Tuto-rial, review, and research prospects. Manufacturing Service Oper.Management 5(2):79–141.

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.

Chan, Yom-Tov, and Escobar: When to Use Speedup482 Operations Research 62(2), pp. 462–482, © 2014 INFORMS

Gibbens RJ, Hunt PJ, Kelly FP (1990) Bistability in communicationnetworks. Disorder in Physical Systems (Oxford University Press,New York), 113–128.

Glazebrook KD, Whitaker LR (1992) Single-machine stochastic schedulingwith dependent processing times. Adv. Appl. Probab. 24:635–652.

Green LV, Soares J, Giglio JF, Green RA (2006) Using queuing theory toincrease the effectiveness of emergency department provider staffing.Academic Emergency Medicine 13:61–68.

Guckenheimer J, Holmes P (2002) Nonlinear Oscillations, DynamicalSystems, and Bifurcations of Vector Fields (Springer).

Hasija S, Pinker E, Shumsky RA (2010) OM practice—Work expands to fillthe time available: Capacity estimation and staffing under Parkinson’slaw. Manufacturing Service Oper. Management 12(1):1–18.

Huang J, Carmeli B, Mandelbaum A (2012) Control of patient flow inemergency departments, or multiclass queues with deadlines andfeedback. Working paper, Technion, Israel.

KC D, Terwiesch C (2012) An econometric analysis of patient flows in thecardiac intensive care unit. Manufacturing Service Oper. Management14(1):50–65.

Maglaras C, Zeevi A (2003) Pricing and capacity sizing for systemswith shared resources: Approximate solutions and scaling relations.Management Sci. 49(8):1018–1038.

Mandelbaum A, Pats G (1998) State-dependent stochastic networks. Part I:Approximations and applications with continuous diffusion limits. Ann.Appl. Probab. 8:569–646.

Mandelbaum A, Massey W, Reiman M (1998) Strong approximations forMarkovian service networks. Queuing Systems 30:149–201.

Perry O, Whitt W (2011) An ODE for an overloaded X model involving astochastic averaging principle. Stochastic Systems 1:17–66.

Powell SG, Schultz KL (2004) Throughput in serial lines with state-dependent behavior. Management Sci. 50(8):1095–1105.

Shevitz D, Paden B (1994) Lyapunov stability theory of nonsmooth systems.IEEE Trans. Automatic Control 39(9):1910–1914.

Whitt W (1990) Queues with service times and interarrival times dependinglinearly and randomly upon waiting times. Queueing Systems 6:335–352.

Yankovic N, Green LV (2011) Identifying good nursing levels: A queuingapproach. Oper. Res. 59(4):942–955.

Yom-Tov G, Mandelbaum A (2014) Erlang-R: A time-varying queue withreentrant customers, in support of healthcare staffing. ManufacturingService Oper. Management 16. Forthcoming.

Zhan D, Ward AR (2014) Routing to minimize waiting and callbacks in largecall centers. Manufacturing Service Oper. Management. Forthcoming.

Carri W. Chan is an assistant professor in the Division ofDecision, Risk, and Operations at Columbia Business School. Herresearch interests include modeling of complex stochastic systems,efficient algorithmic design for queuing systems, and dynamiccontrol of stochastic processing systems. Her current focus ison problems related to healthcare operations management with aparticular emphasis on considering how to improve patient flowthrough hospital intensive care units.

Galit Yom-Tov is a research fellow in the William DavidsonFaculty of Industrial Engineering and Management at the Technion–Israel Institute of Technology and is a member of the SEELabat the Technion. At the heart of her research are service systemsoperations. Her research focuses on what data obtained from variousservice systems, such as call centers and hospitals, can teach usabout customer and agent behavior and how queuing models canhelp understand the operational implications of such behavior.

Gabriel Escobar is a physician and a health services researcher.He is the Regional Director for Hospital Operations Research forthe Permanente Medical Group, Inc., and Director of the SystemsResearch Initiative at Kaiser Permanente Northern California’sDivision of Research. His research interests include severity of illnessscoring, risk adjustment, and the use of modern electronic medicalrecord systems for research and the improvement of patient safety.

Dow

nloa

ded

from

info

rms.

org

by [

128.

59.2

22.1

07]

on 1

2 Ju

ly 2

016,

at 1

2:20

. Fo

r pe

rson

al u

se o

nly,

all

righ

ts r

eser

ved.