Balancing admission control, speedup, and waiting in service systems

Admission control and service rate speedup may be used during periods of congestion to minimize customer waiting in different service settings. In a healthcare setting, this can mean sending patients to alternative care facilities that may take more time and/or provide less ideal treatment. While waiting can be detrimental to patient outcomes, strategies used to control congestion can also be costly. In this work, we examine a multi-server queueing system that considers both admission control and speedup. We use dynamic programming to characterize properties of the optimal control and find that in some instances the optimal policy has a simple form of a threshold policy. Leveraging this insight, we examine a queueing system where speedup is used when the number of customers (patients) in the system exceeds some threshold and admission control is used when that number exceeds some (potentially different) threshold. Using a fluid model and a stochastic loss model, we develop a methodology to derive approximations for the probability that speedup will be applied, the probability that admission control will be applied and the expected queue length customers experience. We use the approximations as the basis for a greedy heuristic to derive a near optimal solution to the original stochastic optimization problem. We use simulation to demonstrate the quality of these approximations and find that they can be quite accurate and robust. This analysis can provide insight to managers deciding how to balance admission control and speedup in service settings: when and to what extent to use each.

1. Due to numeric issues, in order to calculate the expected queue length for large systems we used Stirling’s formula \(\left( i! \sim \left( \frac{i}{e}\right) ^i\sqrt{2 \pi i} \right) \) [27] to calculate E[Q].

2. The exhaustive search was computationally intensive, requiring nearly two weeks to complete on an Intel Xeon E5-2470, 2.3Ghz, 16 core CPU. Thus, providing more granularity was computationally limiting.

3. Given the computational complexity of this simulation, in which we must keep track of the number of customers in the system upon arrival for each customer, the number of repetitions is limited to 40.

4. We do not need to consider the second case because \(N_a\) is our equilibrium and our Lyapunov function is equal to 0 when \(X = N_a\).

5. We do not need to consider the third case because \(N_s\) is our equilibrium and our Lyapunov function is equal to 0 when \(X = N_s\).

Authors and Affiliations

1. Technion—Israel Institute of Technology, Haifa, Israel

   Galit B. Yom-Tov

2. Columbia Business School, New York, NY, USA

   Carri W. Chan

Corresponding author

Correspondence to Galit B. Yom-Tov.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix 1: Miscellaneous proofs for a stochastic system

Proof of Theorem 1

The proof of this theorem requires an intermediate result on the differential discounted cost, \(\varDelta \).

Proposition 2

(Differential Monotonicity) The differential discounted-cost function, \(\varDelta ({\mathbb {X}})\), is non-decreasing in the number of jobs, \({\mathbb {X}}\). That is, let \({\bar{{\mathbb {X}}}} > {\mathbb {X}}\); then

Proof

The proof is via the value iteration method and induction. We generate a sequence of functions \(J_k\) starting with \(J_0({\mathbb {X}}) = 0\) for all \({\mathbb {X}}\ge 0\). Then, for each \(k> 0\), we have

Additionally, for \({\mathbb {X}}> 0\), we have

For \(k\ge 0\) and \({\mathbb {X}}>0\), let

where \(\varDelta _k(0) = 0\). Using value iteration, we have that \(J({\mathbb {X}}) = \lim _{k\rightarrow \infty } J_k({\mathbb {X}})\). It follows that \(\varDelta ({\mathbb {X}}) = \lim _{k\rightarrow \infty } \varDelta _k({\mathbb {X}})\). If we can show that \(\varDelta _k({\mathbb {X}})\) is non-decreasing in \({\mathbb {X}}\) for every k, then the proposition is true. To do this, we use induction. The base case is trivially true for \(k = 0\), where \(\varDelta _0({\mathbb {X}}) = 0\) for all \({\mathbb {X}}\).

We will assume that the assertion is true for k and will show that it is also true for \(k+1\). We denote \(u_k({\mathbb {X}}+1) = (\lambda _k({\mathbb {X}}+1),\mu _k({\mathbb {X}}+1)) = \mathop {\hbox {arg min}}\limits _{\lambda ,\mu } \{ \phi (\lambda ) + \lambda \varDelta _k({\mathbb {X}}+1) +\xi (\mu ) - ({\mathbb {X}}\wedge N)\mu \varDelta _k({\mathbb {X}})\}\) as the strategy used in iteration \(k+1\).

where the last inequality comes from the fact that we can use the policy \(u_{k+1}({\mathbb {X}}+1)\) at iteration \(k+1\) in state \({\mathbb {X}}\) and incur cost of at least \(J_{k+1}({\mathbb {X}})\). Similarly, we can use the policy \(u_{k+1}({\mathbb {X}}-1)\) in state \({\mathbb {X}}\) at iteration \(k+1\) and incur cost of at least \(J_{k+1}({\mathbb {X}})\):

Combining equations (16) and (17), for \({\mathbb {X}}\ge 1\) we have that

For the differential function when \({\mathbb {X}}= 1\), we will use a suboptimal policy in state 0 so that the arrival and service rates are the same as those used in state 1 (\(\lambda _k(1)\) and \(\mu _k(1)\)) so that

where the first inequality follows from the induction hypothesis. This completes the proof that for all \({\mathbb {X}}\) and k, \(\varDelta _{k+1}({\mathbb {X}}+1)\ge \varDelta _{k+1}({\mathbb {X}})\), and so is also true in the limit as \(k \rightarrow \infty \). \(\square \)

Now, we consider the Bellman equation, where the arrival rate and service rate decisions can be separated:

• Admission Control:  We first consider the optimization of the arrival rate. Our goal is to find \(\lambda ^*({\mathbb {X}})\) such that

  $$\begin{aligned} \lambda ^*({\mathbb {X}}) = \mathop {\hbox {arg min}}\limits _{\lambda } \{ \phi (\lambda ) + \lambda \varDelta ({\mathbb {X}}+1)\}. \end{aligned}$$

  By Proposition 2, we have that \(\varDelta ({\mathbb {X}})\) is non-decreasing in \({\mathbb {X}}\). By assumption, \(\phi (\lambda )\) is non-increasing in \(\lambda \). Hence, \(\lambda ^*\) is also non-increasing in \({\mathbb {X}}\).

• Speedup:  We now consider the optimization of the service rate. Our goal is to find \(\mu ^*({\mathbb {X}})\) such that

  $$\begin{aligned} \mu ^*({\mathbb {X}}) = \mathop {\hbox {arg min}}\limits _{\mu } \{\xi (\mu ) - ({\mathbb {X}}\wedge N)\mu \varDelta ({\mathbb {X}})\}. \end{aligned}$$

  By Proposition 2, we have that \(x\varDelta ({\mathbb {X}})\) is non-decreasing in \({\mathbb {X}}\). By assumption, \(\xi (\mu )\) is non-decreasing in \(\mu \). Hence, \(\mu ^*\) is also non-decreasing in \({\mathbb {X}}\). \(\square \)

Proof of Theorem 2

We again turn back to Bellman’s equation:

• Admission Control:  We first consider the optimization of the arrival rate. Our goal is to find \(\lambda ^*({\mathbb {X}})\) such that

  $$\begin{aligned} \lambda ^*({\mathbb {X}}) = \mathop {\hbox {arg min}}\limits _{\lambda \in [\lambda _L,\lambda _H]} \{ \phi (\lambda ) + \lambda \varDelta ({\mathbb {X}}+1)\}. \end{aligned}$$

  Consider a fixed \({\mathbb {X}}\). Then \(\varDelta ({\mathbb {X}}+1)\) is some non-negative constant. By assumption, \(\phi (\lambda )\) is concave; hence, the portion of the cost function associated with the arrival rate

  $$\begin{aligned} \phi (\lambda ) + \lambda \varDelta ({\mathbb {X}}+1) \end{aligned}$$

  is concave. Since we are minimizing a concave function over a finite interval, the optimal admission rate must be on the boundary. Therefore, we must have that \(\lambda ^*({\mathbb {X}}) = \lambda _L\) or \(\lambda ^*({\mathbb {X}}) = \lambda _H\).

• Speedup:  We now consider the optimization of the service rate. Our goal is to find \(\mu ^*({\mathbb {X}})\) such that

  $$\begin{aligned} \mu ^*({\mathbb {X}}) = \mathop {\hbox {arg min}}\limits _{\mu } \{\xi (\mu ) - ({\mathbb {X}}\wedge N)\mu \varDelta ({\mathbb {X}})\}. \end{aligned}$$

  Consider a fixed \({\mathbb {X}}\). Then \(({\mathbb {X}}\wedge N)\varDelta ({\mathbb {X}})\) is some non-negative constant. By assumption, \(\xi (\mu )\) is linear; hence, the portion of the cost function associated with the arrival rate

  $$\begin{aligned} \xi (\mu ) -({\mathbb {X}}\wedge N)\mu \varDelta ({\mathbb {X}}) \end{aligned}$$

  is linear. Since we are minimizing a linear function over a finite interval, the optimal service rate must be on the boundary. Therefore, we must have that \(\mu ^*({\mathbb {X}}) = \mu _L\) or \(\mu ^*({\mathbb {X}}) = \mu _H\).

Proof of Proposition 1

This is a direct result of Proposition 4.3.3 in Bertsekas [12] on Blackwell optimal policies. Note that the results of Theorem 2 (and Proposition 2) are independent of the exact value of the discount factor, \(\beta \). Because there exists a Blackwell optimal policy, it must satisfy the structural properties derived in Theorem 2. Additionally, because a Blackwell optimal policy is also optimal for the average-cost problem, the properties hold for the average-cost problem.

Appendix 2: Proofs for a fluid system

Our system is a piecewise-smooth set of ordinary differential equations. We will take a similar approach to that in Chan et al. [18]; however, our system has two regions of discontinuity, \(X=N_a\) and \(X=N_s\), and is one-dimensional. Still, we can utilize generalized Lyapunov techniques for discontinuous differential equations as outlined in Filippov [24] and di Bernardo et al. [11]. The main idea behind the Filippov [24] approach is to use a smoothed version of the ODE at the points of discontinuity by using a convex combination of the surrounding smooth ODEs. We will demonstrate this for the case where \(N_a < N_s\) and note that the remaining cases (\(N_a = N_s\) and \(N_a > N_s\)) follow similarly.

We first partition the state space into 3 distinct regions and 2 switching boundaries:

We can consider the differential equations under policies that either 1) never use either admission control or speedup, 2) always use admission control and speedup, 3) always use admission control, but never use speedup, and, finally, 4) never use admission control, but always use speedup:

1. 1.

    [Never use either admission control or speedup]: \({\dot{X}}^{HL}(t) \triangleq \lambda _H - \mu _L (X(t) \wedge N)\).

2. 2.

    [Always use admission control and speedup]: \({\dot{X}}^{LH}(t) \triangleq \lambda _L - \mu _H (X(t) \wedge N)\).

3. 3.

    [Always use admission control. Never use speedup]: \({\dot{X}}^{LL}(t) \triangleq \lambda _L - \mu _L (X(t) \wedge N)\).

4. 4.

    [Never use admission control. Always use speedup]: \({\dot{X}}^{HH}(t) \triangleq \lambda _H - \mu _H (X(t) \wedge N)\).

We can now define the fluid function \(F_i(X), X\in {\mathcal {D}}_i\), as the smooth ODE in each region:

We can now define our discontinuous ODE, \({\dot{X}} = F(X)\), as a differential inclusion:

We now have the primitives necessary to prove the remaining results for the fluid system.

Proof of Theorem 3

This result follows directly from the existence result in Filippov [24]. We restate it here for completeness.

Theorem 5

(Theorem 1, Chapter 2, Section 7 of [24]) Let \({\mathcal {F}}(X)\) be a differential inclusion that satisfies the following conditions in the domain G:

1. 1.

   \({\mathcal {F}}(X)\) is non-empty for all \(X\in G\).

2. 2.

   \({\mathcal {F}}(X)\) is bounded and closed for all \(X\in G\).

3. 3.

   \({\mathcal {F}}(X)\) is convex for all \(X\in G\).

4. 4.

   The function \({\mathcal {F}}\) is upper semicontinuous in X.

Then, for any point \(x_0\in G\), there exists a solution of the problem

Thus, to prove existence of a solution to our ODE, we need to verify whether our differential inclusion (18) satisfies the four conditions of the theorem.

It is trivial to see that the four conditions are satisfied when the system state is not on a switching boundary, i.e., when \(X \in {\mathcal {D}}_1 \cup {\mathcal {D}}_2 \cup {\mathcal {D}}_3\). This is because \({\mathcal {F}}(X)\) is a single point that is bounded above by \(\lambda _H\) and below by \(\lambda _L - \mu _H N\). Because the differential inclusion is defined by a continuous function in these regions, it is also upper semicontinuous in the regions.

What remains is to demonstrate that the four conditions are satisfied in \(\varSigma _{12}\) and \(\varSigma _{23}\). For any \(X \in \varSigma _{ij}\), the differential inclusion is given by the convex combination of a single, bounded point. Thus, it is easy to see that conditions 1–3 are satisfied.

We need to prove that the ODE is upper semicontinuous for all \(X\in \varSigma _{12} \cup \varSigma _{23}\). We do this by construction and start with \(X\in \varSigma _{12}\). The case for \(X\in \varSigma _{23}\) follows similarly. Consider an open set V such that \({\mathcal {F}}(X) \subset V\). Then, there must exist an \(\epsilon > 0\) such that, for any \(f\in {\mathcal {F}}(X)\), \(f+\epsilon \in {\mathcal {F}}(X)\). Now consider \(X \in \varSigma _{12}\) and some \(\epsilon > 0\). Because \(F_1\) and \(F_2\) are continuous functions, there exists a \(\delta > 0\) such that \(|X-X'|<\delta \), \(|F_1(X) - F_1(X')| < \epsilon /2\), and \(|F_2(X) - F_2(X')| < \epsilon /2\). Thus,

This implies that \({\mathcal {F}}(X')\subset V\). Thus, we have constructed the necessary open set, \(X':|X-X'|<\delta \), \(X\in \varSigma _{12}\), to demonstrate that \({\mathcal {F}}(X)\) is upper semicontinuous on \(\varSigma _{12}\).

Since all four conditions hold for all \(X\in G = [0,X_{max}]\), a solution to our ODE exists. \(\square \)

Proof of Theorem 4

To show globally asymptotic stability, we need to identify a Lyapunov function and prove that, for all \( X\ge 0, X\not = {\bar{x}}\), the derivative of the Lyapunov function is strictly negative. We use the following Lyapunov function:

where \({\bar{x}}\) is the specified equilibrium. The main challenge here is that the ODE (6) is discontinuous. Hence, we need to use a generalized Lyapunov theory that utilizes Filippov solutions as done in Shevitz and Paden [37]. We use the Filippov methodology, which redefines the ODE at the points of discontinuity, \(N_a\) and \(N_s\), as the set-valued function that is now equal to the convex combination of the surrounding smooth ODEs in (6) and (18). To establish globally asymptotic stability, we need to show that the set-value map for our generalized Lyapunov derivative is negative for all states not equal to the equilibrium [37].

We now define the set-value map for our generalized Lyapunov derivative. This requires considering a number of cases that differ in terms of whether and where the flow X is found on the point of discontinuity.

1. 1.

    \([X\not = N_a, N_s]\).

   $$\begin{aligned} \dot{{\tilde{V}}}(X) = \left\{ \begin{array}{ll} {\dot{X}}, &{} X > {\bar{x}}; \\ -{\dot{X}}, &{} X < {\bar{x}}. \end{array} \right. \end{aligned}$$

   (20)
2. 2.

    \([X = N_a \not = N_s]\). In this case, the flow is on a point of discontinuity, \(N_a\); thus, the set-value map is defined as the convex combination of the surrounding smooth ODEs.

   $$\begin{aligned} \dot{{\tilde{V}}}(X) = \left\{ \begin{array}{ll} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{HH},\psi \in [0,1], &{} {X> {\bar{x}}\hbox { and }X> N_s;} \\ \psi {\dot{X}}^{LL} +(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} {X> {\bar{x}}\hbox { and }X< N_s;} \\ -\psi {\dot{X}}^{LH} -(1-\psi ){\dot{X}}^{HH},\psi \in [0,1], &{} {X< {\bar{x}}\hbox { and }X > N_s;} \\ -\psi {\dot{X}}^{LL} -(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} {X< {\bar{x}}\hbox { and }X < N_s.} \end{array} \right. \end{aligned}$$

   (21)
3. 3.

    \([X = N_s \not = N_a]\). In this case, the flow is on a different point of discontinuity, \(N_s\). We take a similar approach to that of before;

   $$\begin{aligned} \dot{{\tilde{V}}}(X) = \left\{ \begin{array}{ll} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{LL},\psi \in [0,1], &{} {X> {\bar{x}}\hbox { and }X> N_a;} \\ \psi {\dot{X}}^{HH} +(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} {X> {\bar{x}}\hbox { and }X< N_a;} \\ -\psi {\dot{X}}^{LH} -(1-\psi ){\dot{X}}^{LL},\psi \in [0,1], &{} {X< {\bar{x}}\hbox { and }X > N_a;} \\ -\psi {\dot{X}}^{HH} -(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} {X< {\bar{x}}\hbox { and }X < N_a.} \end{array} \right. \end{aligned}$$

   (22)
4. 4.

    \([X= N_s = N_a]\). In this case, the flow is on the (only) point of discontinuity, \(N_a = N_s\).

   $$\begin{aligned} \dot{{\tilde{V}}}(X) = \left\{ \begin{array}{ll} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} X > {\bar{x}}; \\ -\psi {\dot{X}}^{LH} -(1-\psi ){\dot{X}}^{HL},\psi \in [0,1], &{} X < {\bar{x}}. \end{array} \right. \end{aligned}$$

   (23)

The parameter \(\psi \) is used to generate the convex combination of smooth ODEs. In order to prove global asymptotic stability, we must have \(\dot{{\tilde{V}}}(X) < 0\) for all \(X \ge 0\), \(X \not = {\bar{x}}\), and all \(\psi \in [0,1]\). Due to the amount of algebra involved in this proof, we include here only the proof for Case 1, ACF (\(N_a < N_s\)), while noting that the proofs for Case 2, SCF, and Case 3, SASC, follow similarly. For this proof, it is helpful to recall that, by Assumption 2, \(N>x^{HL} = \lambda _H/\mu _L\). Also, we do not need to consider the fourth case, \(X = N_a = N_s\), because we are currently examining the case where \(N_a <N_s\).

• Case 1.1 \(x^{HL}\le N_a \): In this case, the equilibrium is \({\bar{x}} = x^{HL}\). We need to examine the three cases (i) \(X \not = N_a,N_s\), (ii) \(X=N_a\), and (iii) \(X = N_s\). There are a number of subcases to consider within each case:

  1. (i)

     \([X \not = N_a,N_s]\)

     1. (a)

        \(X >{\bar{x}} = x^{HL}\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} {\dot{X}} = \mathbb {1}_{\{X<N_a\}}\lambda _H + \mathbb {1}_{\{X \ge N_a\}}\lambda _L \\&- \left( \mathbb {1}_{\{X<N_s\}}\mu _L +\mathbb {1}_{\{X \ge N_s\}}\mu _H\right) (X\wedge N)\\\le & {} \lambda _H - \mu _L(X\wedge N) < \lambda _H - \mu _L{\bar{x}} = \lambda _H - \mu _Lx^{HL} = 0. \end{aligned}$$
     2. (b)

        \(X < {\bar{x}} = x^{HL}\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -{\dot{X}} = -\lambda _H+ \mu _L (X\wedge N) < -\lambda _H + \mu _L{\bar{x}} \\= & {} -\lambda _H + \mu _Lx^{HL}= 0. \end{aligned}$$
  2. (ii)

     \([X = N_a \not = N_s]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     2. (b)

        \(X > {\bar{x}}\) and \(X < N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} \psi {\dot{X}}^{LL} +(1-\psi ){\dot{X}}^{HL}=\psi [\lambda _L - \mu _L(X\wedge N)] \\&+ (1-\psi )[\lambda _H - \mu _L(X\wedge N)] \le \lambda _H - \mu _L(X\wedge N)\\< & {} \lambda _H -\mu _L{\bar{x}} = \lambda _H -\mu _Lx^{HL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
     3. (c)

        \(X < {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_s\). This case cannot occur because \(X <{\bar{x}} = x^{HL} \le N_a\).

  3. (iii)

     \([X = N_s \not = N_a]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{LL}=\psi [\lambda _L - \mu _H(X\wedge N)] \\&+ (1-\psi )[\lambda _L - \mu _L(X\wedge N)] \\\le & {} \lambda _L - \mu _L(X\wedge N)< \lambda _H -\mu _L(X\wedge N) \\< & {} \lambda _H -\mu _Lx^{HL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
     2. (b)

        \(X > {\bar{x}}\) and \(X < N_a\). This case cannot occur because \(X = N_s > N_a\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_a\). This case cannot occur because \(X <{\bar{x}} = x^{HL} \le N_a\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_a\). This case cannot occur because \(X = N_s > N_a\).

• Case 1.2 \(x^{LL} \le N_a \le x^{HL}\):  In this case, the equilibrium is \({\bar{x}} = N_a\). We need to examine the two cases (i) \(X \not = N_a,N_s\) and^{Footnote 4} (ii) \(X = N_s\). There are a number of subcases to consider within each of our two cases:

  1. (i)

     \([X \not = N_a,N_s]\)

     1. (a)

        \(X >{\bar{x}} = N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} {\dot{X}} = \lambda _L - \left( \mathbb {1}_{\{X<N_s\}}\mu _L +\mathbb {1}_{\{X \ge N_s\}}\mu _H\right) (X\wedge N) \\\le & {} \lambda _L - \mu _L(X\wedge N) < \lambda _L - \mu _Lx^{LL} = 0. \end{aligned}$$
     2. (b)

        \(X< {\bar{x}} = N_a < N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -{\dot{X}} = -\lambda _H + \mu _L(X\wedge N) \\< & {} -\lambda _H + \mu _L{\bar{x}} \le -\lambda _H + \mu _Lx^{HL}= 0. \end{aligned}$$
  2. (ii)

     \([X = N_s \not = N_a]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{LL} \\= & {} \psi [\lambda _L - \mu _H(X\wedge N)] + (1-\psi )[\lambda _L - \mu _L(X\wedge N)] \\\le & {} \lambda _L - \mu _L(X\wedge N) < \lambda _L - \mu _L{\bar{x}} \le \lambda _L -\mu _Lx^{LL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
     2. (b)

        \(X > {\bar{x}}\) and \(X < N_a\). This case cannot occur because \({\bar{x}} = N_a\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_a\). This case cannot occur because \({\bar{x}} = N_a\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_a\). This case cannot occur because \(X = N_s > N_a\).

• Case 1.3 \(N_a \le x^{LL} \le N_s\): In this case, the equilibrium is \({\bar{x}} = x^{LL}\). We need to examine the three cases (i) \(X \not = N_a,N_s\), (ii) \(X=N_a\), and (iii) \(X = N_s\). There are a number of subcases to consider within each case:

  1. (i)

     \([X \not = N_a,N_s]\)

     1. (a)

        \(X >{\bar{x}} = x^{LL} \ge N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} {\dot{X}} = \lambda _L - \left( \mathbb {1}_{\{X<N_s\}}\mu _L +\mathbb {1}_{\{X \ge N_s\}}\mu _H\right) (X\wedge N)\\\le & {} \lambda _L - \mu _L(X\wedge N) < \lambda _L - \mu _Lx^{LL} = 0. \end{aligned}$$
     2. (b)

        \(X < {\bar{x}} = x^{LL} \le N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -{\dot{X}} = -\mathbb {1}_{\{X<N_a\}}\lambda _H - \mathbb {1}_{\{X \ge N_a\}}\lambda _L + \mu _L(X\wedge N) \\\le & {} -\lambda _L + \mu _L(X\wedge N) < -\lambda _L + \mu _Lx^{LL}= 0. \end{aligned}$$
  2. (ii)

     \([X = N_a \not = N_s]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     2. (b)

        \(X > {\bar{x}}\) and \(X < N_s\). This case cannot occur because \(X = N_a \le x^{LL} = {\bar{x}}\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -\psi {\dot{X}}^{LL} -(1-\psi ){\dot{X}}^{HL} \\= & {} -\psi [\lambda _L - \mu _L(X\wedge N)] - (1-\psi )[\lambda _H - \mu _L(X\wedge N)] \\\le & {} -\lambda _L + \mu _L(X\wedge N) < -\lambda _L +\mu _L{\bar{x}} \\= & {} -\lambda _L +\mu _Lx^{LL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
  3. (iii)

     \([X = N_s \not = N_a]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} \psi {\dot{X}}^{LH} +(1-\psi ){\dot{X}}^{LL} \\= & {} \psi [\lambda _L - \mu _H(X\wedge N)] + (1-\psi )[\lambda _L - \mu _L(X\wedge N)] \\\le & {} \lambda _L - \mu _L(X\wedge N) < \lambda _L -\mu _Lx^{LL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
     2. (b)

        \(X > {\bar{x}}\) and \(X < N_a\). This case cannot occur because \(X = N_s > N_a\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_a\). This case cannot occur because \(X =N_s \ge x^{LL} = {\bar{x}}\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_a\). This case cannot occur because \(X = N_s > N_a\).

• Case 1.4 \(x^{LH} \le N_s \le x^{LL}\): In this case, the equilibrium is \({\bar{x}} = N_s\). We need to examine the two cases (i) \(X \not = N_a,N_s\) and^{Footnote 5} (ii) \(X = N_a\). There are a number of subcases to consider within each of our two cases:

  1. (i)

     \([X \not = N_a,N_s]\)

     1. (a)

        \(X>{\bar{x}} = N_s>N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} {\dot{X}} = \lambda _L - \mu _H(X\wedge N) < \lambda _L - \mu _H{\bar{x}} \le \lambda _L -\mu _Hx^{LH} = 0. \end{aligned}$$
     2. (b)

        \(X < {\bar{x}} = N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -{\dot{X}} = -\mathbb {1}_{\{X<N_a\}}\lambda _H - \mathbb {1}_{\{X \ge N_a\}}\lambda _L + \mu _L(X\wedge N) \\\le & {} -\lambda _L + \mu _L(X\wedge N) < -\lambda _L + \mu _L{\bar{x}} \le -\lambda _L +\mu _Lx^{LL}= 0. \end{aligned}$$
  2. (ii)

     \([X = N_a \not = N_s]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     2. (b)

        \(X > {\bar{x}}\) and \(X < N_s\). This case cannot occur because \(X>{\bar{x}} = N_s\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -\psi {\dot{X}}^{LL} -(1-\psi ){\dot{X}}^{HL} \\= & {} -\psi [\lambda _L - \mu _L(X\wedge N)] - (1-\psi )[\lambda _H - \mu _L(X\wedge N)] \\\le & {} -\lambda _L + \mu _L(X\wedge N) < -\lambda _L +\mu _L{\bar{x}} \\\le & {} -\lambda _L +\mu _Lx^{LL} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$

• Case 1.5 \(N_s \le x^{LH} \): In this case, the equilibrium is \({\bar{x}} = x^{LH}\). We need to examine the three cases (i) \(X \not = N_a,N_s\), (ii) \(X=N_a\), and (iii) \(X = N_s\). There are a number of subcases to consider within each case:

  1. (i)

     \([X \not = N_a,N_s]\)

     1. (a)

        \(X>{\bar{x}}\ge N_s > N_a\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} {\dot{X}} = \lambda _L -\mu _H (X\wedge N) <\lambda _L -\mu _H {\bar{x}} = \lambda _L - \mu _Hx^{LH} = 0. \end{aligned}$$
     2. (b)

        \(X < {\bar{x}}\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -{\dot{X}} = -\mathbb {1}_{\{X<N_a\}}\lambda _H - \mathbb {1}_{\{X \ge N_a\}}\lambda _L \\&+ \left( \mathbb {1}_{\{X<N_s\}}\mu _L +\mathbb {1}_{\{X \ge N_s\}}\mu _H\right) (X\wedge N) \\\le & {} -\lambda _L + \mu _H(X\wedge N) <-\lambda _L + \mu _H{\bar{x}}=\lambda _L - \mu _Hx^{LH} = 0. \end{aligned}$$
  2. (ii)

     \([X = N_a \not = N_s]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     2. (b)

        \(X > {\bar{x}}\) and \(X < N_s\). This case cannot occur because \(X = N_a< N_s \le x^{LH} = {\bar{x}}\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_s\). This case cannot occur because \(X = N_a < N_s\).

     4. (d)

        \(X < {\bar{x}}\) and \(X < N_s\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -\psi {\dot{X}}^{LL} -(1-\psi ){\dot{X}}^{HL} \\= & {} -\psi [\lambda _L - \mu _L(X\wedge N)] -(1-\psi )[\lambda _H - \mu _L(X\wedge N)] \\\le & {} -\lambda _L + \mu _L(X\wedge N)< -\lambda _L +\mu _Lx^{LH} \\< & {} -\lambda _L +\mu _Lx^{LL}= 0, ~\forall \psi \in [0,1]. \end{aligned}$$
  3. (iii)

     \([X = N_s \not = N_a]\) We want to show that, for all \(\psi \in [0,1]\), \(\dot{{\tilde{V}}}(X) < 0\):

     1. (a)

        \(X > {\bar{x}}\) and \(X > N_a\). This case cannot occur because \({\bar{x}} = x^{LH} \ge N_s =X\).

     2. (b)

        \(X > {\bar{x}}\) and \(X < N_a\). This case cannot occur because \({\bar{x}} = x^{LH} \ge N_s > N_a\).

     3. (c)

        \(X < {\bar{x}}\) and \(X > N_a\). This case cannot occur because \({\bar{x}} = x^{LH} \ge N_s = X\).

        $$\begin{aligned} \dot{{\tilde{V}}}(X)= & {} -\psi {\dot{X}}^{LH} -(1-\psi ){\dot{X}}^{LL}\\= & {} -\psi [\lambda _L - \mu _H(X\wedge N)] - (1-\psi )[\lambda _L - \mu _L(X\wedge N)] \\\le & {} -\lambda _L + \mu _H(X\wedge N) \\< & {} \lambda _L -\mu _H x^{LH} = 0, ~\forall \psi \in [0,1]. \end{aligned}$$
     4. (d)

        \(X < {\bar{x}}\) and \(X < N_a\). This case cannot occur because \({\bar{x}} = x^{LH} \ge N_s = X > N_a\).

This concludes the proof for the global asymptotic stability of Case 1. \(\square \)

Appendix 3: Distribution fitting

Figure 13 shows fittings of distributions to simulated data under Case 3.3 (Fig. 13(a)), Case 3.2 (Fig. 13(b)), and Case 3.1 (Fig. 13(c)).

Fitting distributions to simulated data

Full size image

Appendix 4: Scaling

Table 10 shows how the performance metrics scale with the system size in the efficiency driven (ED) regime (i.e., \(N=x^{HL}+2\)) as a function of the threshold. We include the following scenarios: 1—no threshold (i.e., \(N_a,N_s=\infty \)); 2—threshold between \(x^{HL}\) and N; 3—threshold is \(O(x^{HL})\) above \(x^{HL}\) (i.e., \(N_a>>N\)). Table 11 shows how the performance metrics scale with the system size in the quality and efficiency drive regime (i.e., \(N=x^{HL}+0.5\sqrt{x^{HL}}\)) as a function of the threshold. We include the following scenarios: 1—no threshold (i.e., \(N_a,N_s=\infty \)); 2—threshold between \(x^{HL}\) and N; 3—threshold is \(O(\sqrt{x^{HL}})\) above \(x^{HL}\) (i.e., \(N_a>N\)). We observe that if the threshold is \(O(x^{HL})\), then E[Q] goes to infinity while P(Admission) and P(Speedup) are 0, and P(Wait) is between 0 and 1. On the other hand, if the threshold is within the low-cost policy set we defined in Sect. 6, all performance levels go to 0 in O(1), except P(Wait).

Reprints and permissions