Asymptotically optimal staffing of service systems with joint QoS constraints

Abstract

We consider the problem of staffing large-scale service systems with multiple customer classes and multiple dedicated server pools under joint quality-of-service (QoS) constraints. We first analyze the case in which arrival rates are deterministic and the QoS metric is the probability a customer is queued, given by the Erlang-C formula. We use the Janssen–Van Leeuwaarden–Zwart bounds to obtain asymptotically optimal solutions to this problem. The second model considered is one in which the arrival rates are not completely known in advance (before the server staffing levels are chosen), but rather are known via a probability distribution. In this case, we provide asymptotically optimal solutions to the resulting stochastic integer program, leveraging results obtained for the case of deterministic arrivals.

Appendix

Proof of Lemma 3

To show $UB(\beta ,\lambda )$ is strictly decreasing in $\lambda$, it suffices to show the denominator of (8), $\rho +\gamma \left( \frac{\Phi (a)}{\phi (a)}+\frac{2}{3\sqrt{n}}\right)$, is strictly increasing in $\lambda$ for any $\beta >0$. First note that

$$\begin{aligned} \rho +\gamma \left( \frac{2}{3\sqrt{n}}\right) =\frac{3\lambda +2\beta \sqrt{\lambda }}{3\left( \lambda +\beta \sqrt{\lambda }\right) } \end{aligned}$$

is strictly increasing in $\lambda$ for any $\beta >0$, by straightforward differentiation.

Thus, we only need to prove that $\frac{\gamma \Phi (a)}{\phi (a)}$ is non-decreasing in $\lambda$ for any $\beta , \lambda >0$. The derivative of $\frac{\gamma \Phi (a)}{\phi (a)}$ with respect to $\lambda$ is

$$\begin{aligned} \frac{\beta ^2}{4 (\lambda +\beta \sqrt{\lambda })\sqrt{\lambda +\beta \sqrt{\lambda }}}\frac{\Phi (a)}{\phi (a)}+\beta \sqrt{\frac{\lambda }{\lambda +\beta \sqrt{\lambda }}}\frac{[\phi (a)+\Phi (a)a]\frac{\partial a}{\partial \lambda }}{\phi (a)}. \end{aligned}$$

It is easily seen that the expression above is positive if

$$\begin{aligned} \frac{\partial a}{\partial \lambda }=\frac{-\frac{\beta }{\sqrt{\lambda }}+\left( 1+\frac{\beta }{2\sqrt{\lambda }}\right) \ln \left( 1+\frac{\beta }{\sqrt{\lambda }}\right) }{\sqrt{-2\left( \beta \sqrt{\lambda }+\lambda \right) \left( 1-\frac{\lambda }{\beta \sqrt{\lambda }+\lambda }+\ln \left( \frac{\lambda }{\beta \sqrt{\lambda }+\lambda }\right) \right) }} \end{aligned}$$

(45)

is also positive for any $\beta , \lambda > 0$. The denominator of (45) is strictly positive and the positivity of the numerator is again easily established by differentiation, establishing the lemma. $\square$

Proof of Lemma 4

With

$$\begin{aligned} g(\beta ,\lambda )=\frac{\gamma }{(12n-1)}=\frac{\beta \sqrt{\lambda /\left( \lambda +\beta \sqrt{\lambda }\right) }}{12\left( \lambda +\beta \sqrt{\lambda }\right) -1}, \end{aligned}$$

we have that $g(\beta ,\lambda )>0$ and is continuous in $(\beta ,\lambda )$ for all $\beta >0, \lambda >10.$ One can verify directly that

$$\begin{aligned} \widehat{\beta }=\frac{-1+12\lambda +\sqrt{1-120\lambda +1296\lambda ^2}}{24\sqrt{\lambda }} \end{aligned}$$

is the only positive critical point of $g(\beta ,\lambda )$ as a function of $\beta$. Also, we have $g(0,\lambda )=0$, $\lim _{\beta \rightarrow \infty }g(\beta ,\lambda )=0$, and $g(\widehat{\beta },\lambda )>0$, $\forall \lambda >10$. Thus $\widehat{\beta }$ is the global maximizer of $g\left( \beta ,\lambda \right)$ for any $\lambda >10$. Since $\lim _{\lambda \rightarrow \infty }g(\widehat{\beta },\lambda )=0,$ we have $\lim _{\lambda \rightarrow \infty }\sup _{\beta >0}g(\beta ,\lambda )=0.$ $\square$

Proof of Lemma 5

To show that $\rho \phi (a)+\gamma \Phi (a)$ is strictly increasing in $\beta$ for any sufficiently large $\lambda$, it suffices to demonstrate that $\rho \phi (a)+\gamma \Phi (a)$ is strictly increasing in $n$ for any sufficiently large $\lambda$, since $\beta$ and $n$ satisfy a linear relationship with a positive slope. Let $h(n,\lambda )=\rho \phi (a)+\gamma \Phi (a)$. We have

$$\begin{aligned} \frac{\partial h(n,\lambda )}{\partial n}=\frac{-\lambda \phi (a)}{n^2}+\Phi (a)\frac{n+\lambda }{2n\sqrt{n}}+\frac{\lambda \phi (a)\ln \left( \frac{\lambda }{n}\right) }{n}-\frac{(n-\lambda )\phi (a)\ln \left( \frac{\lambda }{n}\right) }{a\sqrt{n}}. \end{aligned}$$

(46)

First note that

$$\begin{aligned} \frac{-\lambda \phi (a)}{n^2}+\Phi (a)\frac{n+\lambda }{2n\sqrt{n}}>\frac{-\lambda \phi (a)+n\Phi (a)}{n^2}, \end{aligned}$$

since $\textit{n}>\lambda \ge 1$.

Also since

$$\begin{aligned} \frac{-\lambda \phi (a)+n\Phi (a)}{n^2}\ge \frac{-\lambda \phi (0)+n\Phi (0)}{n^2}> 0, \end{aligned}$$

the first two terms in (46) are positive. It remains then to show that the last two terms in (46) are positive, which is equivalent to $\lambda a \le \sqrt{n}(n-\lambda )$, after some algebra. As shown by Eq. (50) in [11],

$$\begin{aligned} a=\beta -\frac{1}{6}\beta ^{2}\frac{1}{\sqrt{\lambda }}+O\left( 1/\lambda \right) . \end{aligned}$$

So we have $0<a<\beta$ for sufficiently large $\lambda$. Thus

$$\begin{aligned} \lambda a<\lambda \beta =\sqrt{\lambda }(n-\lambda )<\sqrt{n}(n-\lambda ), \end{aligned}$$

since $\lambda <n$. $\square$

Proof of Lemma 6

All the four terms in (10a) are non-negative for all $\beta >0$, $\lambda \ge 1$. Thus it suffices to show that $h(\beta ,\lambda )=\rho \phi (a)+\gamma \Phi (a)$ is uniformly bounded away from 0 for all sufficiently large $\lambda$ and $\beta >0$, since $\phi (\cdot )$ is positive and bounded. From Lemma 5, we know $h(\beta ,\lambda )$ is strictly increasing in $\beta$ for all sufficiently large $\lambda$ and $h(0,\lambda )=\phi (0)>0$. Thus we have that $h(\beta ,\lambda )$ is uniformly bounded away from 0 for all sufficiently large $\lambda$ and all $\beta >0$. $\square$

Proof of Lemma 7

Let $UB_{n}(n,\lambda )=UB(\frac{n-\lambda }{\sqrt{\lambda }},\lambda )$. Since $n=\lambda +\beta \sqrt{\lambda }$, to show $UB({\beta ,\lambda })$ is strictly decreasing in $\beta$ for any $\lambda >0$, it is enough to verify that $UB_{n}(n,\lambda )$ is strictly decreasing in $n$, or equivalently that

$$\begin{aligned}{}[UB_{n}(n,\lambda )]^{-1}= \frac{\lambda }{n}+\frac{n-\lambda }{\sqrt{n}}\left( \frac{\Phi (a)}{\phi (a)}+\frac{2}{3\sqrt{n}}\right) \end{aligned}$$

is strictly increasing in $n$ for any $\lambda$, where $a$ is given in (5). This property can be established by straightforward differentiation. $\square$

Proof of Lemma 11

We prove that

$$\begin{aligned} \prod _{i=1}^{L}\left( 1-UB( \beta _{i},\lambda _{i}^m)\right) -\prod _{i=1}^{L}\left( 1-\tilde{\alpha }\left( \beta _{i},\lambda _{i}^m\right) \right) \end{aligned}$$

converges uniformly to 0 in $\beta$ as $m \rightarrow \infty$, via induction. Let $\underline{UB}(\beta _i,\lambda _i^m)$ denote $1-UB(\beta _i,\lambda _i^m)$ and let $\underline{\tilde{\alpha }}(\beta _i,\lambda _i^m)$ denote $1-\tilde{\alpha }\left( \beta _{i},\lambda _{i}^m\right)$.

First,

$$\begin{aligned}&\lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left( \underline{UB}(\beta _{1},\lambda _{1}^m)\underline{UB}(\beta _{2},\lambda _{2}^m)-\underline{\tilde{\alpha }}(\beta _{1},\lambda _{1}^m)\underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)\right) \\&\quad =\lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \underline{UB}(\beta _{1},\lambda _{1}^m)\left( \underline{UB}(\beta _{2},\lambda _{2}^m)-\underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)\right) \right. \\&\qquad +\left. \left( \underline{UB}(\beta _{1},\lambda _{1}^m)-\underline{\tilde{\alpha }}(\beta _{1},\lambda _{1}^m)\right) \underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)\right\} \\&\quad \le \lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \underline{UB}(\beta _{1},\lambda _{1}^m)\left( \underline{UB}(\beta _{2},\lambda _{2}^m)-\underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)\right) \right\} \\&\qquad +\lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \left( \underline{UB}(\beta _{1},\lambda _{1}^m)-\underline{\tilde{\alpha }}(\beta _{1},\lambda _{1}^m)\right) \underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)\right\} , \end{aligned}$$

where the inequality holds because both terms are positive. The latter two terms above converge to 0 by applying Theorem 8 and the fact that the Erlang-C formula and the JVLZ upper bound have range (0, 1]. Hence $\underline{UB}(\beta _{1},\lambda _{1}^m)\underline{UB}(\beta _{2},\lambda _{2}^m)-\underline{\tilde{\alpha }}(\beta _{1},\lambda _{1}^m)\underline{\tilde{\alpha }}(\beta _{2},\lambda _{2}^m)$ converges uniformly to 0 in $\beta =(\beta _{1},\beta _{2})$.

To apply the induction step, assume $\forall K\in \{2,3,\ldots ,L-1\}$,

$$\begin{aligned} \prod _{i=1}^{K}\left( 1-UB( \beta _{i},\lambda _{i}^m)\right) -\prod _{i=1}^{K}\left( 1-\tilde{\alpha }\left( \beta _{i},\lambda _{i}^m\right) \right) \end{aligned}$$

converges uniformly to 0 in $\beta$. Some algebra yields the following:

$$\begin{aligned}&\!\!\!\lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \prod _{i=1}^{K+1}\left( 1-UB( \beta _{i},\lambda _{i}^m)\right) -\prod _{i=1}^{K+1}\left( 1-\tilde{\alpha }\left( \beta _{i},\lambda _{i}^m\right) \right) \right\} \\&\!\!\!\quad \le \lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \left( \prod _{i=1}^{K}\left( 1-UB( \beta _{i},\lambda _{i}^m)\right) \right) \left( \underline{UB}(\beta _{K+1},\lambda _{K+1}^m)-\underline{\tilde{\alpha }}(\beta _{K+1},\lambda _{K+1}^m)\right) \right\} \\&\!\!\!\qquad + \lim _{m\rightarrow \infty }\sup _{\beta \ge 0}\left\{ \left( \prod _{i=1}^{K}\left( 1\!-\!UB( \beta _{i},\lambda _{i}^m)\right) \!-\! \prod _{i=1}^{K}\left( 1\!-\!\tilde{\alpha }\left( \beta _{i},\lambda _{i}^m\right) \right) \right) \underline{\tilde{\alpha }}(\beta _{K+1},\lambda _{K+1}^m)\right\} \!. \end{aligned}$$

As before, Theorem 8 implies convergence of the latter two terms, which establishes uniform convergence for the $K+1$ case, completing the induction. $\square$

Proof of Lemma 15

The inequality $\beta _{\lambda }^{G}\ge \beta _{\lambda }^{F}$ for all $\lambda >0$ is immediate from the definitions of these quantities and the fact that $\tilde{\alpha }(\beta ,\lambda ) \le UB(\beta ,\lambda )$ for all $\lambda , \beta >0$.

Denote the Halfin-Whitt approximation defined in (3) in Sect. 2 as $\alpha _{HW}(\cdot )$, and its inverse function as $\alpha _{HW}^{-1}(\cdot )$. The function $\alpha _{HW}(\cdot )$ is strictly decreasing and this implies that $\alpha _{HW}^{-1}(\cdot )$ is strictly decreasing. For any $\lambda >0$, we denote the inverse of $UB(\cdot ,\lambda )$ as $UB^{-1}_{\lambda }(\cdot )$. $UB(\cdot ,\lambda )$ is strictly decreasing for any $\lambda >0$, and this implies that $UB^{-1}_{\lambda }(\cdot )$ is strictly decreasing for any $\lambda >0$. By Janssen et al. [11], we have

$$\begin{aligned} \lim _{\lambda \rightarrow \infty }UB(\beta ,\lambda )=\alpha _{HW}(\beta ), \; \forall \beta >0. \end{aligned}$$

Together with the monotonicity of $UB(\beta ,\lambda )$ in $\lambda$ for any $\beta >0$, we have

$$\begin{aligned} \lim _{\lambda \rightarrow \infty }UB^{-1}_{\lambda }(x)=\alpha ^{-1}_{HW}(x), \; \forall x>0. \end{aligned}$$

Since $\lim _{\lambda \rightarrow \infty }\epsilon _{\lambda }=\epsilon >0$, there exists $l,u>0$, such that $0<l \le \epsilon _{\lambda }\le u$ when $\lambda$ is large enough. Also, since $\alpha _{HW}^{-1}(\cdot )$ is a continuous function, by Theorem 14 we have

$$\begin{aligned} \lim _{\lambda \rightarrow \infty }\sup _{x>0}|UB^{-1}_{\lambda }(x)-\alpha _{HW}^{-1}(x)|=0. \end{aligned}$$

This gives

$$\begin{aligned} \lim _{\lambda \rightarrow \infty }UB^{-1}_{\lambda }(\epsilon _{\lambda })=\alpha _{HW}^{-1}(\epsilon ), \end{aligned}$$

which implies that $\lim _{\lambda \rightarrow \infty } \beta _{\lambda }^{G}$ exists and we denote it by $\beta ^{*}$. Then analogous to the proof of Theorem 10 in Sect. 3, we can show that the limit of $\beta ^{F}_{\lambda }$ exists and $\lim _{\lambda \rightarrow \infty }\beta _{\lambda }^{G}=\lim _{\lambda \rightarrow \infty }\beta _{\lambda }^{F}=\beta ^{*}.$ $\square$