# Optimal control of admission to a multiserver queue with two arrival streams

J.P.C. Blanc, P.R. de Waal, Philippe Nain, D. Towsley

► To cite this version:

J.P.C. Blanc, P.R. de Waal, Philippe Nain, D. Towsley. Optimal control of admission to a multiserver queue with two arrival streams. IEEE Transactions on Automatic Control, 1992, 37 (6), pp.785-797. 10.1109/9.256332. hal-04356582

HAL Id: hal-04356582

https://inria.hal.science/hal-04356582v1

Submitted on 20 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
OPTIMAL CONTROL OF ADMISSION TO A
MULTI-SERVER QUEUE WITH TWO ARRIVAL
STREAMS

J. P. C. Blanc*, P. R. de Waal†, P. Nain‡, D. Towsley§

June 26, 1993

Abstract

The problem of finding an optimal admission policy to an M/M/c queue with one controlled and one uncontrolled arrival stream is addressed in this paper. There are two streams of customers (customers of class 1 and 2) that are generated according to independent Poisson processes with constant arrival rates. The service time probability distribution is exponential and does not depend on the class of the customers. Upon arrival a class 1 customer may be admitted or rejected, while incoming class 2 customers are always admitted. A state-dependent reward is earned each time a new class 1 customer enters the system. When the discount factor is small, we show that there exists a stationary admission policy of a threshold type that maximizes the expected total discounted reward over an infinite horizon. A similar result is also obtained when considering the long-run average reward criterion. The proof relies on a new device that consists of a partial construction of the solution of the dynamic programming equation. Applications arising from teletraffic analysis are proposed.

**Keywords:** Control of Queues; Optimal Control of Admission; Markov Decision Processes; Dynamic Programming; Deadlines.

<footnote>* Tilburg University, Faculty of Economics, P.O. Box 90153, 5000 LE Tilburg, The Netherlands.</footnote>

<footnote>†CWI, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands. This author was supported by the Technology Foundation (STW).</footnote>

<footnote>‡INRIA, B.P. 109, 06565 Valbonne Cedex, France.</footnote>

<footnote>§Department of Computer and Information Science, University of Massachusetts, Amherst, MA 01003, USA. This author was supported in part by ONR under contract N00014-87-K-0304 and NSF under grant ASC-8802764.</footnote>
# 1 Introduction

We consider an M/M/c queueing system fed by two independent Poisson streams of customers with intensities $\lambda_1$ and $\lambda_2$. Customers of stream $i$ will be referred to as class $i$ customers, $i = 1, 2$. The buffer has unlimited capacity and the order of service is irrelevant as long as the service discipline is not anticipative. The customer service demands are independent and exponentially distributed random variables with finite mean $1/\mu$.

Customers of stream 1 are controlled, in the sense that an arriving class 1 customer can be either accepted in the system or rejected on the basis of past and current queue-length information. Customers of stream 2 are not controlled; all are required to enter the queue. A reward $g(k + 1)$ is earned each time a class 1 customer is admitted when the queue-length is $k$. Our objective is twofold: we want to find *admission policies* for class 1 customers that maximize (1) the average discounted reward gained over an infinite horizon, and (2) the long-run average reward over an infinite horizon.

Throughout the years, many authors have studied flow control problems in the context of queueing systems, and a comprehensive discussion can be found in the survey paper by Stidham [22]. A standard approach in the control of queueing systems consists of formulating the optimization problem at hand as a Markov decision problem (see e.g., Serfozo [21], Lin and Kumar [14]) or a semi-Markov decision problem (see e.g., Lippman [16]), from which the functional equation of dynamic programming can be derived (Bertsekas [4], Heyman and Sobel [10], Ross [20]). Then, the so-called policy improvement algorithm (see e.g., Lin and Kumar [14]) or the value iteration algorithm (see for instance Hajek [9], Johansen and Stidham [12], Ephremides et al. [8], Ma and Makowski [17]) may be used to determine the optimal policy (e.g., threshold policy, switching curve). An alternative approach to dynamic programming is to convert the Markov decision problem to a linear program (Heyman and Sobel [10], Ross [20]) and to use results from the theory of linear programming to determine the structure of the optimal policy (see e.g., Hordijk and Spieskma [11], Rosberg et al. [18], Ross and Chen [19]). In some cases, direct arguments arising from performance analysis techniques may also yield the optimal policy (Lazar [13]).

The contributions of this paper are the following: first, we establish the optimality of threshold policies for fairly general reward functions (in particular, $g$ need not to be convex/concave); second, these results are obtained in the presence of a non-controlled input stream which makes the optimization problem more involved; third, we propose a new device for extracting information from the optimality equation since we have not been able to apply any of the classical techniques listed above; last, we show that our model has interesting applications in teletraffic analysis.

In Section 2 the problem is cast in the Markov decision process framework. Section 3 addresses the discounted reward control problem in the case where $\lambda_2 = 0$, which will turn out to be much simpler to analyse than the case where $\lambda_2 > 0$ (Section 4). In both cases, we show the existence of an optimal threshold policy for small discount factors. The optimality of a threshold policy for the long-run average reward problem is proved in Section 5. Extensions of our results
to negative/non-geometrically decreasing reward functions are discussed in Section 6. Section 7 contains two applications arising from teletraffic analysis.

## 2 The Model

The optimization problem described in Section 1 is now formulated as a Markov decision problem. This formulation closely follows that of Lippman in [15]. Let $\mathbb{N} := \{0, 1, 2, \dots\}$, $N^* := \mathbb{N} - \{0\}$ and $\mathbb{R}_+ := (0, +\infty)$.

Let $t_n$ be the time when the $n$-th event occurs (arrival or departure). Assume that $t_1 = 0$. Let $U_n \in \{0, 1\}$ be the $n$-th decision to be made at time $t_n$ (the $n$-th decision epoch). If $t_n$ corresponds to the arrival of a class 1 customer, then the controller may decide either to accept ($U_n = 1$) or to reject ($U_n = 0$) this new customer; otherwise, the decision is irrelevant since only class 1 customers are controlled. In that case, we shall assume by convention that $U_n = 0$.

Let $Q(t)$ be the total number of customers in the system at time $t$, including the customers in service, if any. We assume that the sample paths of the process $\{Q(t), t \ge 0\}$ are right-continuous. At time $t_n$ the state of the system is represented by $Z_n = (Q(t_n), X_n) \in \mathbb{S} := \mathbb{N} \times \{0, 1\}$, where $X_n$ is the number of class 1 customers seeking admittance.

When in state $(k, 1)$ a reward $g(k+1)$ is earned if the customer seeking admittance is accepted. Let $\mu_k$ be the departure rate when there are $k$ customers in the system, $k \in \mathbb{N}$. Observe that $\mu_k = \mu \min(k, c)$ for all $k \in \mathbb{N}$ (cf. Remark 2.1). We assume that the reward function $g: \mathbb{N}^* \to \mathbb{R}_+$ satisfies the following conditions:

$$ \mu_k g(k) \le \mu_{k+1} g(k+1), \quad \text{for } k = 1, 2, \dots, c-1; \qquad (2.1) $$

$$ g(k+1) \le \Psi g(k), \quad \text{for } k = c, c+1, \dots, \qquad (2.2) $$

with $\Psi \in (0, 1)$. Observe from (2.1) and (2.2) that $g$ is uniformly bounded in $\mathbb{N}^*$ (say by a constant $G$).

Let us briefly discuss the conditions (2.1) and (2.2). Condition (2.1) is satisfied (in particular) if $g$ is nondecreasing in $[1, c]$. Condition (2.2) implies that $g$ is geometrically decreasing, with the corollary that $\lim_{k \uparrow \infty} g(k) = 0$. It is also worth noting that the restrictions we place on $g$ are particularly weak when $c = 1$ (M/M/1 queue), since in that case we only require that $g$ be geometrically decreasing. In particular, no convexity assumption is required. The more general case when $g$ is nonincreasing in $[c, \infty)$ (i.e., $\Psi = 1$) will be discussed in Section 6.2.

The process $Z := \{Z_n, n \ge 1\}$ is a Markov decision process with state space $\mathbb{S}$ (Ross [20]). An *admission policy* is any mapping $u: \mathbb{S} \to \{0, 1\}$, where $u(z) = 1$ (resp. $u(z) = 0$) indicates that the decision is to admit (resp. reject) the new customer when the system is in state $z \in \mathbb{S}$. We only consider stationary policies since it is well known that nothing is gained by considering more general
policies (e.g., randomized, non-stationary, history dependent policies; for instance see Lippman [16] or Ross [20]). The set of all admission policies will be denoted by $\mathcal{U}$.

Our objective is twofold. First, we want to maximize over $\mathcal{U}$.

$$V_{\alpha}(z; u) := E_u \left[ \sum_{n \ge 1} e^{-\alpha t_n} r(Z_n; U_n) \mid Z_1 = z \right], \quad \alpha > 0, \qquad (2.3)$$

the expected total $\alpha$-discounted reward gained over an infinite horizon for every initial state $z \in \mathbf{S}$, where $r(z; a) := g(k+1) \mathbf{1}(a = 1, x = 1)$ with $z = (k, x)$. It is easily seen from (2.3) that $V_{\alpha}(z; u)$ is uniformly bounded on $\mathbf{S} \times \mathcal{U}$ (by $K_{\alpha} := (\alpha + \lambda_1) G / \alpha$) for every $\alpha > 0$. Let $V_{\alpha}^{*}(z) := \sup_{u \in \mathcal{U}} V_{\alpha}(z; u)$.

Second, we want to find an admission policy that maximizes over $\mathcal{U}$.

$$W(z; u) := \liminf_{T \uparrow \infty} \frac{1}{T} E_u \left[ \sum_{\{n: 0 \le t_n < T\}} r(Z_n; U_n) \mid Z_1 = z \right], \qquad (2.4)$$

the long-run average reward gained over an infinite horizon, for every initial state $z \in \mathbf{S}$. Observe that $0 \le W(z, u) \le \lambda_1 G$ for all $(z, u) \in \mathbf{S} \times \mathcal{U}$.

Theorem 2.1 gives the Dynamic Programming (DP) equation that is satisfied by the optimal value function $V_{\alpha}^{*}$. The proof of this result can be found in Lippman [16, Theorem 1].

**Theorem 2.1** Let $A_{k,1} := \{0,1\}$ and $A_{k,0} := \{0\}$ be the action spaces when in state $(k, 1)$ and $(k, 0)$, respectively. Then, for every $\alpha > 0$, $V_{\alpha}^{*}$ is the unique uniformly bounded solution in $\mathbf{S}$ to the DP equation

$$V_{\alpha}^{*}(z) = \max_{a \in A_{k,x}} \left\{ r(z; a) + \frac{\theta_{z}(a)}{\alpha + \theta_{z}(a)} \sum_{z' \in \mathbf{S}} Q(z' \mid z; a) V_{\alpha}^{*}(z') \right\}, \quad z = (k, x) \in \mathbf{S}, \qquad (2.5)$$

where $Q(\bullet | z; a)$ and $\theta_z(a)$ are the one-step probability transition of the process $\mathbf{Z}$ and the transition rate out of state $z$ respectively, given that the current state is $z$ and that action $a$ is chosen. Furthermore, the control which selects an action maximizing the right-hand side of (2.5) for all $z \in \mathbf{S}$ is optimal.

It is easily obtained from (2.5) (see Blanc et al. [3] for details) that

$$(\alpha + \lambda + \mu_k) V_{\alpha}^{*}((k, 0)) = \lambda_1 V_{\alpha}^{*}((k, 1)) + \lambda_2 V_{\alpha}^{*}((k + 1, 0)) + \mu_k V_{\alpha}^{*}((k - 1, 0)) \mathbf{1}\{k \ge 1\}; (2.6)$$

$$V_{\alpha}^{*}((k, 1)) = \max\{g(k + 1) + V_{\alpha}^{*}((k + 1, 0)); V_{\alpha}^{*}((k, 0))\}, \qquad (2.7)$$

for all $k \in \mathbb{N}$, where $\lambda := \lambda_1 + \lambda_2$.

For $k \in \mathbb{N}$, define

$$x_{\alpha}^{*}(k) := \begin{cases} V_{\alpha}^{*}((k, 0)), & k = 0; \\ V_{\alpha}^{*}((k, 0)) - V_{\alpha}^{*}((k - 1, 0)), & k \ge 1. \end{cases} \qquad (2.8)$$
As a consequence of the last statement of Theorem 2.1 and (2.7), the optimal action $u_{\alpha}^{*}(k, 1) \equiv u_{\alpha}^{*}(k)$ when the state of the system is $(k, 1)$ is given by

$$u_{\alpha}^{*}(k) = \mathbf{1}\{x_{\alpha}^{*}(k+1) + g(k+1) > 0\}, k \in \mathbb{N}. \quad (2.9)$$

Further, it follows from (2.6) and (2.7) that for every $\alpha > 0$ the function $x_{\alpha}^{*}$ is the unique bounded solution of the DP equation

$$-\alpha \sum_{i=0}^{k} x_{\alpha}^{*}(i) + \lambda_{1} u_{\alpha}^{*}(k) (x_{\alpha}^{*}(k+1) + g(k+1)) + \lambda_{2} x_{\alpha}^{*}(k+1) - \mu_{k} x_{\alpha}^{*}(k) \mathbf{1}\{k \ge 1\} = 0, k \in \mathbb{N}. \quad (2.10)$$

**Remark 2.1** All the results in this paper are seen to hold if $\mu_1, \mu_2, \dots, \mu_{c-1}$ are arbitrary numbers satisfying (2.1). The assumption that $\mu_k = \mu k$ for $k = 1, 2, \dots, c-1$ is only made for sake of notational convenience.

## 3 Discounted Reward Problem: the Single-Stream Case

This section is devoted to the analysis of the single-stream discounted problem (i.e., $\lambda_2 = 0$). In that case, the DP equation (2.10) reduces to

$$-\alpha \sum_{i=0}^{k} x_{\alpha}^{*}(i) + \lambda_{1} u_{\alpha}^{*}(k) (x_{\alpha}^{*}(k+1) + g(k+1)) - \mu_{k} x_{\alpha}^{*}(k) \mathbf{1}\{k \ge 1\} = 0, k \in \mathbb{N}, \alpha > 0. \quad (3.1)$$

The main result of this section is:

**Proposition 3.1** The optimal $\alpha$-discounted admission policy $u_{\alpha}^{*}$ is such that

1. $u_{\alpha}^{*}(k) = 1$ for $k = 0, 1, \dots, c-1, \alpha > 0$;

2. if $0 < \alpha < \alpha_0 := \mu(1 - \Psi)/\Psi$ and if there is an $l < \infty$ such that $u_{\alpha}^{*}(l) = 0$, then $u_{\alpha}^{*}(k) = 0$ for $k \ge l$.

Proposition 3.1 shows that for small discount factors the optimal $\alpha$-discounted policy is of threshold type, with a threshold greater or equal to $c$.

**Proof of Proposition 3.1.** We first prove 1. by induction on $k$. Substituting $k = 0$ and $k = 1$ into equation (3.1) yields

$$-\alpha x_{\alpha}^{*}(0) + \lambda_{1} u_{\alpha}^{*}(0) (x_{\alpha}^{*}(1) + g(1)) = 0, \quad (3.2)$$

$$-\alpha(x_{\alpha}^{*}(0) + x_{\alpha}^{*}(1)) + \lambda_{1}u_{\alpha}^{*}(1)(x_{\alpha}^{*}(2) + g(2)) - \mu_{1}x_{\alpha}^{*}(1) = 0. \quad (3.3)$$
Subtracting (3.2) from (3.3) yields

$$ \lambda_1 u_{\alpha}^{*}(1) (x_{\alpha}^{*}(2) + g(2)) - \lambda_1 u_{\alpha}^{*}(0) (x_{\alpha}^{*}(1) + g(1)) = (\alpha + \mu_1) x_{\alpha}^{*}(1). $$

If we assume that $u_{\alpha}^{*}(0) = 0$, then since $u_{\alpha}^{*}(1)(x_{\alpha}^{*}(2) + g(2)) \ge 0$ (see (2.9)) we can write

$$ (\alpha + \mu_1) x_{\alpha}^{*}(1) \ge 0. \quad (3.4) $$

However, because $u_{\alpha}^{*}(0) = 0$, it follows that $0 \ge x_{\alpha}^{*}(1) + g(1) > x_{\alpha}^{*}(1)$. But according to (3.4), $x_{\alpha}^{*}(1)$ is nonnegative which results in a contradiction and therefore $u_{\alpha}^{*}(0) = 1$.

Assume now that $u_{\alpha}^{*}(0) = u_{\alpha}^{*}(1) = \dots = u_{\alpha}^{*}(l-1) = 1$ for $l < c$ and let us show that $u_{\alpha}^{*}(l) = 1$. Substituting $k = l$ and $k = l+1$ into equation (3.1) and subtracting the first equation from the second one, yields

$$ \lambda_1 u_{\alpha}^{*}(l+1)(x_{\alpha}^{*}(l+2) + g(l+2)) - \lambda_1 u_{\alpha}^{*}(l)(x_{\alpha}^{*}(l+1) + g(l+1)) = (\alpha + \mu_{l+1})x_{\alpha}^{*}(l+1) - \mu_l x_{\alpha}^{*}(l). \quad (3.5) $$

If we assume that $u_{\alpha}^{*}(l) = 0$, we then deduce from (2.9) and (3.5) that

$$ (\alpha + \mu_{l+1}) x_{\alpha}^{*}(l+1) - \mu_l x_{\alpha}^{*}(l) \ge 0, $$

since $u_{\alpha}^{*}(l+1)(x_{\alpha}^{*}(l+2) + g(l+2)) \ge 0$, or equivalently that

$$ (\alpha + \mu_{l+1})(x_{\alpha}^{*}(l+1) + g(l+1)) - \mu_l(x_{\alpha}^{*}(l) + g(l)) - g(l+1)(\alpha + \mu_{l+1}) + \mu_l g(l) \ge 0. \quad (3.6) $$

By noting now that $x_{\alpha}^{*}(l+1) + g(l+1) \le 0$ (since $u_{\alpha}^{*}(l) = 0$ by assumption), $-(x_{\alpha}^{*}(l) + g(l)) < 0$ (since $u_{\alpha}^{*}(l-1) = 1$ by assumption) and $-g(l+1)\mu_{l+1} + \mu_l g(l) \le 0$ from (2.1), we see that the left-hand side of equation (3.6) is strictly negative, which gives a contradiction. Therefore $u_{\alpha}^{*}(l) = 1$.

We also prove 2. by induction. Fix $\alpha$ such that $0 < \alpha < \alpha_0$. Let $l \ge c$ be such that $u_{\alpha}^{*}(l) = 0$. This implies that $x_{\alpha}^{*}(l+1) \le -g(l+1)$.

Define $x: \mathbb{N} \to \mathbb{R}$ as

$$ x(k) = \begin{cases} x_{\alpha}^{*}(k), & k = 0, 1, \dots, l; \\ -\alpha \sum_{i=0}^{k-1} x(i)/(\alpha + \mu), & k \ge l+1. \end{cases} \quad (3.7) $$

Note that the expression for $x(k)$ for the case $k > l$ is the recursion obtained from (3.1) by setting $u_{\alpha}^{*}(k) = 0$ for $k > l$ (i.e., always reject an arriving class 1 customer when the queue-length exceeds $l$).

We prove that $x(k) \le -g(k)$ for $k > l$ by induction on $k$.

*Basis step.* Let $k = l+1$. From the definition of $x$ we have

$$ x(l+1) = -\alpha \sum_{i=0}^{l} x(i)/(\alpha + \mu), $$
$$
\begin{align*}
&= -\alpha \sum_{i=0}^{l} x_{\alpha}^{*}(i) / (\alpha + \mu), \\
&= (\alpha x_{\alpha}^{*}(l+1) - \lambda_{1} u_{\alpha}^{*}(l+1) (x_{\alpha}^{*}(l+2) + g(l+2)) + \mu x_{\alpha}^{*}(l+1)) / (\alpha + \mu), \\
&\leq x_{\alpha}^{*}(l+1), \\
&\leq -g(l+1).
\end{align*}
$$

The last two steps follow from the fact that $u_{\alpha}^{*}(k)(x_{\alpha}^{*}(k+1)+g(k+1)) \ge 0$ for all $k \in \mathbb{N}$ (cf. (2.9))
and the fact that $u_{\alpha}^{*}(l) = 0$.

Inductive step. We assume that $x(k') \le -g(k')$ for $k' = l+1, l+2, \dots, k$. We show that $x(k+1) \le -g(k+1)$. We have, cf. (3.7),

$$
\begin{align*}
x(k+1) &= \left[ -\alpha x(k) - \alpha \sum_{i=1}^{k-1} x(i) \right] / (\alpha + \mu), \\
&= (-\alpha x(k) + (\alpha + \mu)x(k)) / (\alpha + \mu), \\
&= \mu x(k) / (\alpha + \mu), \tag{3.8} \\
&\le -\mu g(k) / (\alpha + \mu), \\
&\le -g(k+1),
\end{align*}
$$

by the induction hypothesis, the assumptions on $g$ and the condition on $\alpha$. In particular, (3.8)
shows that $|x(k)| = (\mu/(\alpha + \mu))^{k-l} |x_{\alpha}^{*}(l)| \le 2K_{\alpha}$ for all $k \ge l+1$, where the bound follows from
the definition (2.8) together with the uniform bound on $V_{\alpha}^{*}$ (see Section 2).

We have thus found a uniformly bounded function $x$ that when substituted for $x_{\alpha}^{*}$ in equation (3.1)
satisfies that equation. Therefore, $x^{*} = x$ since (3.1) has only one uniformly bounded solution,
which in turns implies that $x_{\alpha}^{*}(k) + g(k) \le 0$ for $k > l$ and $\alpha \in (0, \alpha_{0})$. This concludes the proof.

The next result tells us that this threshold is finite.

**Proposition 3.2** For every $\alpha \in (0, \alpha_0)$, the smallest integer $l$ such that $u_{\alpha}^*(l) = 0$ is finite. Moreover, $l$ is uniformly bounded in $\alpha$ for all $\alpha$ small enough.

An immediate corollary of Propositions 3.1 and 3.2 is that for every fixed $\alpha \in (0, \alpha_0)$ the integer
$\inf\{l \ge c : u_{\alpha}^*(l) = 0\}$ is the optimal threshold.

**Proof of Proposition 3.2.** The proof follows from Lemma 4.3 in Section 4 by letting $\lambda_2 = 0$ (see also Remark 4.2). A direct proof is also available in de Waal [7, Lemma 4.5.4]. ■

The methodology used in the proof of Proposition 3.1 does not fall into any of the categories that
were reported in Section 1. This method — first proposed by de Waal [6, 7]— is based on the
construction of an intermediate function (say $f$) that we suspect to be the optimal policy (here $f(\cdot) = x(\cdot)$, cf. (3.7)). If we can show that $f$ is bounded and solves the DP equation, then the existence of a unique bounded solution to the DP equation enables us to conclude that $f$ is indeed the optimal value function. This method has also been applied with success by Altman and Nain [1] for controlling the vacations of the server in a Markovian queue. Therefore, we remark that the importance of the result lies not as much in the optimality of threshold policies but rather in the method of proof.

The next section shows that this method also applies to the case where $\lambda_2 > 0$, although this case differs from the single-stream case in an essential way: in the two-stream case, the number of customers in the system is *never* bounded from above regardless of the admission policy for class 1 customers. This fact makes the analysis of the two-stream case much more involved.

# 4 Discounted Reward Problem: the Two-Stream Case

This section presents the analysis of the discounted problem with two streams of customers. Recall that only the stream of class 1 customers is controlled. Again, our objective is to find an admission policy that maximizes the discounted cost function (2.3).

We first introduce some notation and state some preliminary results. Let

$$ \beta_1 := \frac{\alpha + \mu + \lambda_2 - \sqrt{(\alpha + \mu + \lambda_2)^2 - 4 \lambda_2 \mu}}{2 \lambda_2}, \quad (4.1) $$

be the smallest zero of the polynomial (in $t$) $\lambda_2 t^2 - (\alpha + \mu + \lambda_2) t + \mu$. Denote by $\beta_2$ the other root and observe that $0 < \beta_1 < 1 < \beta_2$ for all $\alpha > 0$. Assume now that $\lambda_2 < \mu$. By noting that $\beta_1 = 1$ when $\alpha = 0$ and that the mapping $\alpha \to \beta_1$ is strictly decreasing in $[0, +\infty)$, we see that there exists $\alpha_1 > 0$ such that

$$ \beta_1 > \Psi, \quad (4.2) $$

for $\alpha \in (0, \alpha_1)$, where $\Psi$ was introduced in (2.2).

In the remainder of this section, we shall assume that the reward function $g$ satisfies the following additional conditions (see Remark 4.1)

$$ g(k) \ge g(k+1), \quad \text{for } k = 1, 2, \dots, c-1. \quad (4.3) $$

The following result holds (see Remark 4.2):

**Proposition 4.1** Assume that $\lambda_2 < \mu$ and fix $\alpha \in (0, \alpha_1)$. If there exists a finite integer $m \ge 0$ (that clearly depends on $\alpha$) such that the set of equations

$$ 0 = -\alpha \sum_{i=0}^{k} y(i) + \lambda_1 (y(k+1) + g(k+1)) + \lambda_2 y(k+1) - \mu_k y(k), \quad 0 \le k < m + c; \quad (4.4) $$
$$0 = -\alpha \sum_{i=0}^{m+c} y(i) + \lambda_2 y(m+c+1) - \mu y(m+c); \qquad (4.5)$$

$$0 = y(m+c+1) - \beta_1 y(m+c), \qquad (4.6)$$

has a solution that satisfies

$$y(k) + g(k) > 0, \quad \text{for } 1 \le k \le m+c; \qquad (4.7)$$

$$y(m+c+1) + g(m+c+1) \le 0, \qquad (4.8)$$

then $u_{\alpha}^{*}(k) = 1\{k < m + c\}$ for $k \in \mathbb{N}$.

**Proof.** Let $m \ge 0$ be such that $(y(k))_{k=0}^{m+c+1}$ satisfies (4.4)-(4.8). Define $x : \mathbb{N} \to \mathbb{R}$ as

$$x(k) = \begin{cases} y(k), & k = 0, 1, \dots, l; \\ \beta_1 x(k-1), & k \ge l+1, \end{cases} \qquad (4.9)$$

with $l := m + c$ (see the comments below).

We prove that $x(k) + g(k) \le 0$ for $k > l$ by induction on $k$.

*Basis step.* Let $k = l + 1$. From the definition of $x$ we have

$$\begin{aligned} x(l+1) &= \beta_1 y(l), \\ &= y(l+1), \quad \text{from (4.6)}, \\ &\le -g(l+1), \end{aligned}$$

from (4.8).

*Inductive step.* We assume that $x(k') + g(k') \le 0$ for $k' = l + 1, l + 2, \dots, k$. We show that $x(k+1) + g(k+1) \le 0$. We have, cf. (4.9),

$$\begin{aligned} x(k+1) &= \beta_1 x(k), \\ &\le -\beta_1 g(k), \quad \text{from the induction hypothesis,} \\ &\le -\Psi g(k), \quad \text{from (4.2)}, \\ &\le -g(k+1), \end{aligned}$$

from (2.2). Consequently,

$$x(k) + g(k) \le 0, \quad \text{for } k > l. \qquad (4.10)$$

By combining this result together with the definition of $y(k)$ for $0 \le k \le m+c+1$ and the definition of $\beta_1$, it is easily seen that $x$ satisfies the DP equation (2.10).

On the other hand, a direct inspection of (4.9) indicates that $|x(k)| \le \max_{0 \le i \le k}\{|y(i)|\}$ for all $k \in \mathbb{N}$ (use $\beta_1 \in (0, 1)$). Consequently, $x = x^*$ since (2.10) has a unique uniformly bounded solution on $\mathbb{N}$, which in turn implies that $x_{\alpha}^*(k) + g(k) > 0$ for $1 \le k \le m + c$ (cf. (4.7), (4.9a)) and
$x_{\alpha}^{*}(k) + g(k) \le 0$ for $k \ge m + c + 1$ (cf. (4.10)). This concludes the proof.

<figure><img src="image_2.png" /></figure>

**Proposition 4.1** contains an existence result which makes it already quite interesting. Indeed, if one can show (for instance, numerically) that the finite system of equations (4.4)-(4.6) has a solution that satisfies (4.7)-(4.8), then Proposition 4.1 says that the optimal discounted policy is a threshold policy. In other words, the infinite system of equations (2.9)-(2.10) has been reduced to a finite one.

Let us now comment on the definition of $x$ in (4.9) since this is the key point of our method. Assume that $u_{\alpha}^{*}(k) = 0$ for all $k \ge l \ge c$. Then, equation (2.10) reduces to

$$ - \alpha \sum_{i=0}^{k} x_{\alpha}^{*}(i) + \lambda_{2} x_{\alpha}^{*}(k+1) - \mu x_{\alpha}^{*}(k) \mathbf{1}\{k \ge 1\} = 0, \quad (4.11) $$

for $k \ge l$. Substituting $k$ for $k + 1$ in (4.11), then subtracting (4.11) from this new equation, yields for $k \ge l$

$$ \lambda_{2} x_{\alpha}^{*}(k+2) - (\alpha + \lambda_{2} + \mu) x_{\alpha}^{*}(k+1) + \mu x_{\alpha}^{*}(k) = 0. \quad (4.12) $$

It is known that the general solution to the second-order difference equation defined by (4.12) is

$$ x_{\alpha}^{*}(k) = a \beta_{1}^{k} + b \beta_{2}^{k}, \quad (4.13) $$

for $k \ge l$, where we recall that $\beta_1$ and $\beta_2$ are the roots of the (characteristic) equation $\lambda_2 t^2 - (\alpha + \mu + \lambda_2)t + \mu = 0$. The coefficients $a$ and $b$ are easily identified by plugging (4.13) into (4.12) (see Blanc et al. [3]). Because $x_{\alpha}^{*}$ must be uniformly bounded on $\mathbb{N}$, (4.13) and $\beta_2 > 1$ necessarily imply that $b = 0$, or equivalently, that $x_{\alpha}^{*}(l+1) = \beta_1 x_{\alpha}^{*}(l)$. This last relation in turn entails that $a = x_{\alpha}^{*}(l)/\beta_1^l$. In other words, if the optimal policy is such that $u_{\alpha}^{*}(k) = 0$ for all $k \ge l \ge c$, then necessarily

$$ x_{\alpha}^{*}(k) = \beta_{1} x_{\alpha}^{*}(k-1), $$

for $k \ge l + 1$, which is nothing but the definition of $x(k)$ given in (4.9) for $k \ge l + 1$.

It could be tempting to replace $y(k)$ in (4.9a) by $x_{\alpha}^{*}(k)$ in direct analogy with the definition (3.7a) of $x$ in the single-stream case. However, we are not allowed to do it because there is a priori no reason why the extra condition (4.6) should hold for $x_{\alpha}^{*}$.

The next step towards the optimality of a threshold policy is to establish the existence of a solution to (4.4)-(4.8). This is done in the following proposition.

**Proposition 4.2** Let $\alpha \in (0, \alpha_1)$. Then, there exists a finite integer $m = m^*, m^* \ge 0$, such that the unique solution to the set of equations (4.4)-(4.6) satisfies the constraints (4.7), (4.8). Further, $m^*$ is uniformly bounded as $\alpha \downarrow 0$.

The proof of Proposition 4.2 relies upon the following three lemmas, of which proofs are given in the Appendix. We introduce the following notation: for any $m \ge 0$, $(x_{m+c}(k))_{k=0}^{m+c+1}$ will denote
the unique solution to the set of equations (4.4)-(4.6) (the uniqueness of the solution is discussed at the beginning of the Appendix).

**Lemma 4.1** The unique solution $(x_c(k))_{k=0}^{c+1}$ to the set of equations (4.4)-(4.6) when $m = 0$ is such that

$$x_c(k) + g(k) > 0, \quad \text{for } 1 \le k \le c. \qquad (4.14)$$

**Lemma 4.2** Let $C_m, m \ge 0$, be the condition on the model parameters $\lambda_1, \lambda_2, \mu, c, \alpha, (g(k))_{k=1}^{m+1+c}$, which is equivalent to $x_{m+c}(m+1+c)+g(m+1+c) \le 0$. If none of the conditions $C_0, C_1, \dots, C_{m-1}$ holds, $m \ge 1$, then $x_{m+c}(k) + g(k) > 0$ for $k = 1, 2, \dots, m+c$.

**Lemma 4.3** Let $\alpha \in (0, \alpha_1)$. Then, there exists $m, 0 \le m < +\infty$, such that $x_{m+c}(m + c + 1) + g(m + c + 1) \le 0$. Moreover, $m$ is uniformly bounded as $\alpha \downarrow 0$.

**Proof of Proposition 4.2.** Let $m^*$ be the smallest nonnegative integer such that $x_{m^*+c}(m^* + c + 1) + g(m^* + c + 1) \le 0$, where the existence of $m^*$ is ensured by Lemma 4.3. If $m^* = 0$ then the proposition follows from Lemma 4.1, whereas if $m^* > 0$ the proposition follows from Lemma 4.2. The second part follows from the second statement of Lemma 4.3. ■

Combining Propositions 4.1 and 4.2 yields the following final result:

**Proposition 4.3** Assume $\lambda_2 < \mu$. Let $g$ be a reward function such that conditions (2.1), (2.2), (4.3) hold simultaneously. Then, for every $\alpha \in (0, \alpha_1)$, there exists $m_\alpha^* < \infty$ such that $u_\alpha^*(k) = 1\{k < m_\alpha^* + c\}$ for all $k \in \mathbb{N}$. Moreover, there exists $\alpha_2, 0 < \alpha_2 < \alpha_1$, and a constant $M > 0$ such that $m_\alpha^* \in [0, M]$ for all $\alpha \in (0, \alpha_2)$.

Before concluding this section, let us briefly address the numerical computation of the optimal threshold $m_\alpha^* + c$. The standard way for computing $m_\alpha^*$ is to solve the system of equations (4.4)-(4.6) for $m = 0, 1, 2, \dots$ until we end up with a value of $m$ such that the constraints (4.7)-(4.8) are met. Then, $m_\alpha^* = m$. However, it is much more efficient both in terms of computation time and memory space savings to determine $m_\alpha^*$ from the inequality (A.50) in the Appendix by using the recursions (A.22) and (A.23). More precisely, for every $\alpha \in (0, \alpha_1)$, $m_\alpha^*$ will be the smallest integer such that (A.50) holds.

**Remark 4.1** The assumption that $g$ is nonincreasing in $[1, c]$ is only used in the proof of Lemma 4.1. We conjecture that Lemma 4.1 holds without this extra assumption on $g$ (we have only checked it for $c = 2$ and $c = 3$, which implies, in particular, that Proposition 4.3 holds for $c \le 3$ without this assumption).
**Remark 4.2** Proposition 4.1 still holds if $\lambda_2 = 0$ provided that $\beta_1$ is replaced by $\lim_{\lambda_2 \downarrow 0} \beta_1 = \mu/(\alpha + \mu)$. Moreover, when $\lambda_2 = 0$ Lemma 4.1 holds without the extra assumption (4.3) (see the comment at the end of the proof of Lemma 4.1), which in turn implies (see Remark 4.1) that the same is true for Proposition 4.1.

# 5 The Average Reward Control Problem

In this section, we shall discuss the long-run average reward control problem. Since $V_\alpha(z; u)$ is well defined for all $z \in S$, $u \in U$ (see Section 2), we know from a Tauberian theorem (Widder [23, pp. 181-182]) that

$$W(z; u) \le \liminf_{\alpha \downarrow 0} \alpha V_{\alpha}(z; u), \quad (5.1)$$

for all $z \in S$, $u \in U$. Further, if $W(z; u)$ exists as a limit, then $\lim_{\alpha \downarrow 0} \alpha V_\alpha(z; u)$ exists as well, and

$$W(z; u) = \lim_{\alpha \downarrow 0} \alpha V_{\alpha}(z; u), \quad (5.2)$$

for all $z \in S$, $u \in U$.

Assume first that $0 < \lambda_2 < \mu$ and that the assumptions in Proposition 4.3 are fulfilled. Let $z$ be fixed in $S$. For every $\alpha \in (0, \alpha_2)$, we have from Proposition 4.3 that

$$u_{\alpha}^{*}(j) = 1\{j \le m_{\alpha}^{*} + c\}, \\ 
\alpha V_{\alpha}(z; u) \le \alpha V_{\alpha}(z; u_{\alpha}^{*}), \quad (5.3)$$

for $j \ge 0$ with $0 \le m_{\alpha}^{*} < +\infty$. Consequently, for $\alpha \in (0, \alpha_2)$,

for all $u \in U$.

Let $\{\alpha_i\}_{i=1}^\infty$ be a sequence in $(0, \alpha_2)$ such that $\alpha_i \downarrow 0$ as $i \uparrow \infty$. Since $m_\alpha^* \in [0, M]$ for $\alpha \in (0, \alpha_2)$ by Proposition 4.3, and since $m_\alpha^*$ is an integer, there exists $J < +\infty$ and a subsequence of $\{\alpha_i\}_{i=1}^\infty$, denoted as $\{\alpha_j\}_{j=1}^\infty$, such that $m_{\alpha_j}^*$ is a constant (denoted as $m^*$) for all $j \ge J$. Define $u^*(j) := 1\{j < m^* + c\}, j \ge 0$.

If we now take the limit in (5.3) along $\alpha_j, j \uparrow \infty$, we get from (5.1) that for every policy $u \in U$

$$W(z; u) \le \liminf_{j \uparrow \infty} \alpha_j V_{\alpha}(z; u^*). \quad (5.4)$$

By observing now that $Z$ (see Section 2) is an ergodic Markov chain when the threshold policy $u^*$ is used, we may deduce from Chung [5, Section I.15] that $W(z; u)$ exists as a limit. Hence, cf. (5.2), (5.4), $W(z; u) \le W(z; u^*)$ for all $z \in S$, $u \in U$.

For $\lambda_2 = 0$, the same result can be shown by using Propositions 3.1 and 3.2. However, (4.3) is not needed in that case.
For $\lambda_2 \ge \mu$, it should be clear from $\lim_{k \uparrow \infty} g(k) = 0$, cf. (2.2), that $W(z; u) = 0$ for all $u \in \mathcal{U}$.

The results of this section are collected in the following proposition:

**Proposition 5.1** If $\lambda_2 = 0$, then there exists a threshold policy with finite threshold that is average optimal over the set $\mathcal{U}$ of all admission policies. The same result holds if $0 < \lambda_2 < \mu$ provided that $g$ is nonincreasing in $[1, c]$. If $\lambda_2 \ge \mu$, then all admission policies are average optimal.

# 6 Extensions of the Model

Two extensions of the definition of a reward function will be discussed in this section.

## 6.1 Negative rewards

Let $g: \mathbb{N}^* \to \mathbb{R}$ be a mapping such that (2.1) holds, and further

$$g(k+1) \le \Psi g(k), \quad \text{for } k = c, c+1, \dots, C-1; \qquad (6.1)$$

$$g(k) \ge 0, \quad \text{for } k = 1, 2, \dots, C-1; \qquad (6.2)$$

$$g(k) \le 0, \quad \text{for } k \ge C. \qquad (6.3)$$

where $C$ is an arbitrary constant greater than or equal to $c$. The above conditions generalize (2.1)-(2.2) since they reduce to (2.1)-(2.2) when $C = \infty$.

We also assume that Assumptions 2 and 3 in Lippman [15] are satisfied (these assumptions ensure the validity of Theorem 2.1 for non-uniformly bounded rewards).

Then, it is easily seen (cf. Remark 6.1) that the results contained in Sections 3-5 still hold if (2.2) is replaced by the new set of conditions (6.1)-(6.3).

**Remark 6.1** The second statement of the proof of Proposition 3.1 is obtained by noting from (3.7) that $x(k) \le 0$ for all $k \ge 1$. This implies, in particular, that $x(k) + g(k) \le 0$ for all $k \ge C$, from which we deduce that the optimal threshold lies in $[c, C - 1]$. When $\lambda_2 > 0$, the latter result follows from (A.54).

## 6.2 Non-geometrically decreasing rewards

Let $g: \mathbb{N}^* \to \mathbb{R}_+$ be a mapping that satisfies both conditions (2.1)-(2.2) with $\Psi = 1$. Further, we assume that there exists $\Delta \ge 0$ such that

$$\sup_{k \in \mathbb{N}^*} kg(k) \le \Delta. \qquad (6.4)$$
**Proposition 6.1** *Proposition 5.1 holds under the foregoing assumptions.*

**Proof.** Let $\epsilon \in [0, 1)$ and $z \in \mathbf{S}$. Define $g_{\epsilon} : \mathbb{N}^* \to \mathbb{R}_+$ such that

$$ g_{\epsilon}(k) := \begin{cases} g(k), & \text{for } k = 1, 2, \dots, c; \\ g(k)(1-\epsilon)^k, & \text{for } k \ge c+1. \end{cases} \qquad (6.5) $$

Let $W_{\epsilon}(z, u)$ be the long-run average reward gained over an infinite horizon when the reward function $g_{\epsilon}$ is used (cf. (2.4)). Observe that $W_{\epsilon}(z, u)$ is uniformly bounded on $[0, 1) \times \mathbf{S} \times \mathcal{U}$ (by $\lambda_1 \mathcal{G}$) and that $W_0(z, u) = W(z, u)$.

Since $g_{\epsilon}$ satisfies conditions (2.1)-(2.2), we may deduce from Proposition 5.1 (provided that $g$ is nonincreasing in $[1, c]$) that there exists an integer $l_{\epsilon}$, $c \le l_{\epsilon} < \infty$, such that

$$ W_{\epsilon}(z; u_{l_{\epsilon}}) \ge W_{\epsilon}(z; u), \qquad (6.6) $$

for all $u \in \mathcal{U}$, where $u_{l_{\epsilon}}(k) := \mathbf{1}(k < l_{\epsilon})$, $k \in \mathbb{N}$.

Assume that for every policy $u \in \mathcal{U}$, the mapping $\epsilon \to W_{\epsilon}(z, u)$ is right-continuous at $\epsilon = 0$. Call this assumption **H**. Let $\{\epsilon_i\}_i$ be a sequence in $(0, 1)$ such that $\epsilon_i \downarrow 0$ when $i \uparrow \infty$. Since $l_{\epsilon}$ lies in a compact set for $\epsilon$ small enough (see (A.54)), there exists a subsequence $\{\epsilon_j\}_j$ of $\{\epsilon_i\}_i$ and an integer $J$ such that $l_{\epsilon_j} = l$ for all $j > J$. Consequently, for $j > J$,

$$ W_{\epsilon_j}(z, u_l) \ge W_{\epsilon_j}(z, u), \qquad (6.7) $$

for every $u \in \mathcal{U}$. Letting now $j$ go to $\infty$ in (6.7), we have from assumption **H**

$$ W(z, u_l) \ge W(z, u), $$

for every $u \in \mathcal{U}$, which proves Proposition 6.1.

It remains to show that assumption **H** is valid. Let $u$ be an arbitrary policy in $\mathcal{U}$. The following will be shown: there exists $\delta_{\epsilon} > 0$ such that $\delta_{\epsilon}$ converges to 0 when $\epsilon$ goes to 0, and such that

$$ W(z, u) - \delta_{\epsilon} \le W_{\epsilon}(z, u) \le W(z, u), \qquad (6.8) $$

for $\epsilon \in [0, 1)$, from which **H** will follow.

First, observe from (6.5) that the second inequality in (6.8) is trivially true since $\epsilon \to W_{\epsilon}(z, u)$ is nonincreasing in $[0, 1)$. Let us show that the first inequality is also true.

We have (with $Z_1 = z$)

$$ W_{\epsilon}(z, u) \ge $$

$$ \liminf_{T \uparrow \infty} E_u \left[ \frac{1}{T} \sum_{\{n: 0 \le t_n < T\}} \left\{ g(Q(t_n) + 1) + g(Q(t_n) + 1) \left( (1 - \epsilon)^{Q(t_n)+1} - 1 \right) \right\} \mathbf{1}(X_n = 1, U_n = 1) \right], $$
$$ 
\begin{aligned}
&\geq \liminf_{T \uparrow \infty} \left\{ E_u \left[ \frac{1}{T} \sum_{\{n: 0 \leq t_n < T\}} r(Z_n; U_n) \right] - D\epsilon E_u \left[ \frac{1}{T} \sum_{n: 0 \leq t_n < T} 1 \right] \right\}, \\
&= W(z, u) - \delta_{\epsilon},
\end{aligned} 
\quad (6.9) $$

where (6.9) follows from (6.4) and from the inequality $(1 - (1 - \epsilon)^i)/i \leq \epsilon$ for $\epsilon \in (0, 1)$, $i \in \mathbb{N}^*$. ■

Proposition 6.1 yields the following interesting corollary:

**Corollary 6.1** Assume that $c = 1$ and that condition (6.4) holds. Then, for any nonincreasing reward function $g: \mathbb{N}^* \to \mathbb{R}_+$, there exists a threshold policy that is average optimal.

# 7 Applications

In this section, we present two applications of our results arising from the context of teletraffic analysis.

## Example 1.

Assume that a deadline $D_n > 0$ on service time completion is associated with the $n$-th arriving customer of class 1, $n \geq 1$. More precisely, if the $n$-th customer has arrived at time $t$, then we want this customer to be served by time $t + D_n$. Customers that miss their deadline are not discarded, meaning that once a class 1 customer gets accepted in the system then it is served. This is a typical situation in many data networks where high level protocols are concerned with admission while low level protocols are concerned with scheduling and transmission. In many cases, the lower level protocols do not have access to deadline information whereas the high level protocols do.

This model can also serve as an elaborate version of the queueing model for call request processing in a telephone exchange as presented in de Waal [7, Chapter 4]. Customers of type 1 represent the requests from subscribers that are connected locally to the switch, while customers of type 2 represent call requests that are forwarded from other switches. The latter are always admitted to the exchange because of the processing time that is already spent on them at the forwarding switch. The deadline of type 1 customers corresponds to the limited patience of the subscribers when they are waiting for the completion of their call.

We assume that $\{D_n\}_n$ is a sequence of i.i.d. random variables, independent of the input and service times processes. The reward function $g$ is defined to be the probability that a new class 1 customer meets its deadline given there are $k$ customers in the system, including itself, upon its arrival. With this definition, it is seen that the long-run average reward gained over an infinite horizon (see 2.4) provides a measure of the goodput of the system, that is the completion rate of class 1 customers that complete service before their deadline.

With the definition of $g$ in mind, we observe that (2.1) holds since $g(k) = P(D < S)$ for $k < c$,
where S (resp. D) denotes a generic random variable for the service time (resp. deadline) of a customer.

In the case that $P(D \le x) = 1 - \exp(-\gamma x)$ for $x \ge 0$, $\gamma > 0$ (exponentially distributed deadlines), an easy computation shows that

$$g(k) = \begin{cases} \mu/(\mu + \gamma), & k = 1, 2, \dots, c; \\ (\mu/(\mu + \gamma))(c\mu/(c\mu + \gamma))^{k-c}, & k = c+1, c+2, \dots. \end{cases}$$

It is also easy to see that the above expression for $g(k)$ satisfies both conditions (2.1) and (2.2) with $\Psi = c\mu/(c\mu + \gamma)$.

In the general case where the deadline distribution function is arbitrary, then $g(k)$ cannot be computed in closed form. However, many interesting deadline distribution functions are such that condition (2.2) is met. More precisely, we have the following result:

**Proposition 7.1** *The mapping g satisfies condition (2.2) if one of the three following conditions is fulfilled:*

1. the deadlines are deterministic;

2. the deadlines have a failure rate that is bounded away from 0 by a strictly positive constant;

3. the deadlines have an Erlang distribution.

The proof of Proposition 7.1 can be found in de Waal [7]. Note that condition 2 in Proposition 7.1 is satisfied by a large class of distributions, including the exponential distribution, subsets of the class of Gamma distributions, and truncated normal distributions (see Barlow and Proschan [2], Sec. 5). The mapping $g$ also satisfies the condition (2.2) if the deadline distribution is a finite mixture of distribution functions that satisfy any of the conditions of Proposition 7.1.

If one of the conditions of Proposition 7.1 is satisfied, then the goodput of the system is maximized by rejecting a class 1 customer if the queue size exceeds a (finite) threshold upon its arrival. This follows from Proposition 5.1.

**Example 2.** A classical problem in teletraffic analysis is to find a trade-off between response times and throughput. Let us illustrate this phenomena through the following simple model.

Define $g(k) := r - w(k)$, $k \ge 1$, where $r > 1/\mu$ and where $w(k)$ is the mean sojourn time of a customer that enters the system when the queue-length is $k-1$. Consequently, we must find a trade-off between accepting all the customers which would imply high throughput but high response times, and rejecting most of the customers which would yield low response times but also low throughput.

For the long-run average reward criterion this formulation is equivalent to the one where a reward is gained for every admitted customer and holding costs are payed per time unit for every waiting
customer (cf. the Dynamic Flow Models in Stidham [22]). The formulations differ in the sense that
in our model the total expected holding costs of each customer are incurred at the moment of his
arrival.

Let us show that the reward function *g* satisfies conditions (2.1), (6.1)-(6.3). Because *w*(*k*) = 1/μ for *k* = 1, 2, ..., *c*, we see that condition (2.1) is satisfied. Define *C* := inf{*k* ≥ 1, *g*(*k*) ≤ 0} (note that *C* ≥ *c* + 1 since *g*(*c*) = *r* − 1/μ > 0). Since *w*(*k*) is nondecreasing in *k*, we immediately deduce that condition (6.3) holds, and that condition (6.1) also holds with Ψ := max<sub>*c*≤*k*≤*C*−2</sub> *g*(*k*+1)/*g*(*k*).

Therefore, the results in Sections 3-5 apply to this model, which shows the existence of optimal threshold policies both for the discounted and the long-run average reward criteria.

**Acknowledgements.** The authors acknowledge the support of the European Research Consortium for Informatics and Mathematics (ERCIM). They are also grateful to a referee and to the Associate Editor A. Shwartz for their useful comments and suggestions. Many thanks also to P. Mussi for a useful discussion during the course of this work.

A Appendix

We first introduce some notation and establish some intermediate results.

Define the matrices

$$
M_k^j(a_0, b_0, c_0) :=
\begin{pmatrix}
a_0 & \alpha & \alpha & \cdots & \alpha & \alpha & b_0 \\
-\mu_j & \alpha + \lambda & \alpha & \cdots & \alpha & \alpha & b_0 \\
0 & -\mu_{j+1} & \alpha + \lambda & & & & \\
0 & 0 & -\mu_{j+2} & & & & \\
& & & \vdots & \vdots & \vdots & \\
& & & \alpha & & & \\
0 & 0 & 0 & -\mu_{k-1} & \alpha + \lambda & b_0 \\
0 & 0 & 0 & \cdots & 0 & -\mu_k & c_0
\end{pmatrix},
\quad (A.1)
$$

for $1 \le j < k$, and

$$
M_k^k(a_0, b_0, c_0) := \begin{pmatrix} a_0 & b_0 \\ -\mu_k & c_0 \end{pmatrix}, \quad (A.2)
$$

for $k \ge 1$, where $a_0$, $b_0$ and $c_0$ are arbitrary constants (recall that $\mu_j = \mu \min(j, c)$)

Let $|M|$ be the determinant of any matrix $M$, with the convention that $|x| = x$ if $x$ is a scalar number. It is easily seen by using an induction argument that

$$
|M_k^j(a_0, b_0, c_0)| > 0, \tag{A.3}
$$

when $a_0 > 0, b_0 > 0$ and $c_0 > 0$, for $1 \le j \le k$.
Let us show that the set of equations (4.4)-(4.6) has a unique solution for all $m \ge 0$. Let $x_{m+c}(k) := y(k)$, $k = 0, 1, \dots, m + c + 1$, in Proposition 4.1.

By substituting (4.6) into (4.5), by eliminating $x_{m+c}(0)$ from (4.4) by using (4.5), and finally by using the definition of $\beta_1$, we obtain the matrix equation:

$$A_{m+c} \mathbf{x}_{m+c} = -\lambda_1 \mathbf{g}_{m+c}, \quad (A.4)$$

where

$$\mathbf{x}_{m+c} := (x_{m+c}(1), \dots, x_{m+c}(m+c))^T;$$

$$\mathbf{g}_{m+c} := (g(1), \dots, g(m+c))^T;$$

$$A_{m+c} := \begin{cases} M_{m+c-1}^1 (\alpha + \lambda, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } m+c > 1; \\ \lambda_1 + c\mu/\beta_1, & \text{if } m+c = 1. \end{cases}$$

By noting that $c\mu/\beta_1 - \lambda_2 > 0$ (since $\beta_1 < 1$, cf. (4.1) for $\alpha > 0$, and $\lambda_2 < c\mu$) we see from (A.3) that $|A_{m+c}| > 0$ for $m \ge 0$. Therefore, the set of equations (4.4)-(4.6) has a unique solution for all $m \ge 0$.

We start with the proof of Lemma 4.1.

## Proof of Lemma 4.1

For $m = 0$ rewrite the equation (A.4) as

$$A_c[\mathbf{x}_c + \mathbf{g}_c] = [A_c - \lambda_1 I_c] \mathbf{g}_c := \mathbf{h}_c,$$

where $I_c$ stands for the identity matrix and $\mathbf{h}_c := (h_c(1), \dots, h_c(c))^T$. It follows readily that

$$h_c(k) = -\mu_{k-1} g(k-1) \mathbf{1}\{k > 1\} + \alpha \sum_{i=k}^{c-1} g(i) + \lambda_2 g(k) + \left(\frac{c\mu}{\beta_1} - \lambda_2\right) g(c), \quad (A.5)$$

for $k = 1, 2, \dots, c$.

By developing the determinant which forms the numerator of $x_c(j) + g(j)$ to the $j$-th column we get after a tedious but easy computation

$$(x_c(j) + g(j)) |A_c| = |A_c^{j+1}| \sum_{k=1}^{j} h_c(k) |\Lambda_{k-1}| \frac{(j-1)!}{(k-1)!} \mu^{j-k} \\ - \sum_{k=1}^{j} |\Lambda_{k-1}| \frac{(j-1)!}{(k-1)!} \mu^{j-k} \sum_{i=j+1}^{c} h_c(i) \lambda^{i-j-1} |V_c^i|, \quad (A.6)$$

for $j = 1, 2, \dots, c$, where
$$
\begin{align*}
A_c^j &:= \begin{cases}
M_{c-1}^j (\alpha + \lambda, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } 1 \le j \le c-1; \\
\lambda_1 + c\mu/\beta_1, & \text{if } j = c; \\
1, & \text{if } j = c+1;
\end{cases} \\
V_c^j &:= \begin{cases}
M_{c-1}^j (\alpha, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } 1 \le j \le c-1; \\
c\mu/\beta_1 - \lambda_2, & \text{if } j = c;
\end{cases} \\
\Lambda_k &:= \begin{cases}
M_{k-1}^1 (\alpha + \lambda, \alpha, \alpha + \lambda), & \text{if } k > 1; \\
\alpha + \lambda, & \text{if } k = 1; \\
1, & \text{if } k = 0.
\end{cases} \tag{A.7}
\end{align*}
$$

With the above definitions the following recursions can easily be established for $j = 1, 2, \dots, c-1$,

$$
|A_c^j| = (\alpha + \lambda) |A_c^{j+1}| + j\mu |V_c^{j+1}|, \quad (A.8)
$$

$$
|V_c^j| = \alpha |A_c^{j+1}| + j\mu |V_c^{j+1}|. \tag{A.9}
$$

Repeated application of the recursions (A.8) and (A.9) leads to

$$
|A_c^{j+1}| = \lambda^{c-j} + \sum_{i=j+1}^{c} \lambda^{i-j-1} |V_c^i|, \quad j = 0, 1, \dots, c-1. \quad (A.10)
$$

Introducing (A.10) into (A.6) finally yields for $j = 1, 2, \dots, c$,

$$
(x_c(j) + g(j)) |A_c| = \sum_{k=1}^{j} \frac{(j-1)!}{(k-1)!} |\Lambda_{k-1}| \mu^{j-k} \left\{ h_c(k) \lambda^{c-j} + \sum_{i=j+1}^{c} [h_c(k) - h_c(i)] \lambda^{i-j-1} |V_c^i| \right\}.
$$

As we have seen before $|A_c| > 0$, $|\Lambda_{k-1}| > 0$ for $k = 0, 1, \dots, c-1$, $|V_c^i| > 0$ for $i = 1, 2, \dots, c$. Further, the assumptions on $g$ imply that (a) $h_c(k) > 0$ for $k = 1, 2, \dots, c$ and that (b) $h_c(k) - h_c(i) > 0$ for $k < i$. Hence, $x_c(j) + g(j) > 0$ for $j = 1, 2, \dots, c$, which concludes the proof of Lemma 4.1 (if $\lambda_2 = 0$ then it is easily seen that (a) and (b) are satisfied without the additional assumption (4.3)).

<figure><img src="image_3.png" /></figure>

**Proof of Lemma 4.2.**

Let us show that the lemma is true if

$$
x_{m+c}(0) > x_{m-1+c}(0), \tag{A.11}
$$

when condition $C_{m-1}, m \ge 1$, is not satisfied. We use an induction argument.

First notice that, cf. (4.4), (4.5),

$$
x_{m+c}(k) = \frac{\alpha \sum_{i=0}^{k-1} x_{m+c}(i) - \lambda_1 g(k) + \mu_{k-1} x_{m+c}(k-1)}{\lambda}, \quad 1 \le k \le m+c; (A.12)
$$

$$
x_{m+c}(m+c+1) = \frac{\alpha \sum_{i=0}^{m+c} x_{m+c}(i) + \mu_{m+c} x_{m+c}(m+c)}{\lambda_2}, \quad (A.13)
$$
for all $m \ge 0$, $c \ge 1$.

*Basis step.* Assume that $C_0$ is not satisfied and let us show that $x_{1+c}(k)+g(k) > 0$ for $1 \le k \le 1+c$. 

¿From (A.12) and the inequality (A.11) (with $m = 1$), it is readily seen that

$$x_{1+c}(k) > x_c(k), \quad \text{for } 0 \le k \le c, \qquad (A.14)$$

which implies from Lemma 4.1 that $x_{1+c}(k) + g(k) > x_c(k) + g(k) > 0$ for $k = 1, 2, \dots, c$.

Further, cf. (A.12), (A.13), (A.14),

$$\begin{align*}
x_{1+c}(1+c) &= \frac{\alpha \sum_{i=0}^{c} x_{1+c}(i) - \lambda_1 g(1+c) + \mu_c x_{1+c}(c)}{\lambda}, \\
&> \frac{\alpha \sum_{i=0}^{c} x_c(i) - \lambda_1 g(1+c) + \mu_c x_c(c)}{\lambda}, \\
&= \frac{\lambda_2 x_c(1+c) - \lambda_1 g(1+c)}{\lambda},
\end{align*}$$

and so

$$x_{1+c}(1+c) + g(1+c) > \frac{\lambda_2}{\lambda} (x_c(1+c) + g(1+c)) > 0,$$

from the assumption on $C_0$.

*Inductive step.* Assume that none of the conditions $C_0, C_1, \dots, C_{m-2}, m \ge 2$, is satisfied and that

$$x_{m-1+c}(k) + g(k) > 0, \quad \text{for } 1 \le k \le m-1+c. \qquad (A.15)$$

Let us show that $x_{m+c}(k) + g(k) > 0$ for $1 \le k \le m + c$ if $C_{m-1}$ is not satisfied. It is easily seen from (A.11), (A.12), (A.13), that

$$x_{m+c}(k) > x_{m-1+c}(k), \quad \text{for } 1 \le k \le m-1+c; \qquad (A.16)$$

$$x_{m+c}(m+c) > \frac{\lambda_2 x_{m-1+c}(m+c) - \lambda_1 g(m+c)}{\lambda}. \qquad (A.17)$$

Consequently, $x_{m+c}(k) + g(k) > 0$ for $1 \le k \le m - 1 + c$ from (A.15) and (A.16), and $x_{m+c}(m + c) + g(m + c) > 0$ from (A.17) and the assumption on $C_{m-1}$.

We are therefore left to prove that (A.11) holds if the condition $C_{m-1}$ is not satisfied, $m \ge 1$. More precisely, we shall show that

$$[x_{m+c}(0) - x_{m-1+c}(0)] |A_{m+c}| = \frac{\lambda_1}{\alpha} \lambda^{m-1+c} \left( \frac{c\mu}{\beta_1} - \lambda_2 \right) [x_{m-1+c}(m+c) + g(m+c)], \quad (A.18)$$

for all $m \ge 1$, if $C_{m-1}$ is not satisfied (i.e., $x_{m-1+c}(m+c) + g(m+c) > 0$), which will prove (A.11) since $|A_{m+c}| > 0$ and $c\mu/\beta_1 - \lambda_2 > 0$. The proof decomposes into 3 steps:

**Step 1:** Computation of $x_{m-1+c}(m+c) + g(m+c)$
Recall the definition of $\Lambda_k$ (cf. (A.7)). Let

$$ Y_k := \begin{cases} M_{k-1}^1(\alpha + \lambda, \mu_k, \mu_k), & \text{if } k > 1; \\ \mu, & \text{if } k = 1; \\ 0, & \text{if } k = 0. \end{cases} \qquad (A.19) $$

With these definitions, we easily obtain that

$$ |\Lambda_k| = (\alpha + \lambda) |\Lambda_{k-1}| + \alpha |Y_{k-1}|; \qquad (A.20) $$

$$ |Y_k| = \mu_k (|\Lambda_{k-1}| + |Y_{k-1}|), \qquad (A.21) $$

for $k \ge 1$, from which we deduce that

$$ \lambda \mu_k |\Lambda_{k-1}| = \mu_k |\Lambda_k| - \alpha |Y_k|; \qquad (A.22) $$

$$ \lambda \mu_k |Y_{k-1}| = (\alpha + \lambda) |Y_k| - \mu_k |\Lambda_k|, \qquad (A.23) $$

for $k \ge 1$.

By means of the recursion

$$ x_{m+c}(m+c) |A_{m+c}| = -\lambda_1 g(m+c) |\Lambda_{m-1+c}| + \mu_{m-1+c} x_{m+c-1}(m-1+c) |A_{m-1+c}|, \quad m \ge 0, $$

that follows from (A.4) we obtain for $m \ge 0$,

$$ x_{m+c}(m+c) |A_{m+c}| = -\lambda_1 \sum_{j=1}^{m+c} g(j) |\Lambda_{j-1}| \prod_{i=j}^{m-1+c} \mu_i, \qquad (A.24) $$

$$ = -\lambda_1 (c\mu)^m \sum_{j=1}^{c-1} g(j) \frac{(c-1)!}{(j-1)!} \mu^{c-j} |\Lambda_{j-1}| $$

$$ - \lambda_1 \sum_{j=0}^{m} g(j+c)(c\mu)^{m-j} |\Lambda_{c+j-1}|, \qquad (A.25) $$

where by convention we have assumed that $\sum_{j=1}^0 \cdot = 0$.

Next, we introduce the new quantities

$$ \tilde{A}_{m+1} := \begin{cases} M_{m+c-1}^c (\alpha + \lambda, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } m \ge 1; \\ \lambda_1 + c\mu/\beta_1, & \text{if } m = 0; \end{cases} $$

$$ \tilde{V}_{m+1} := \begin{cases} M_{m+c-1}^c (\alpha, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } m \ge 1; \\ c\mu/\beta_1 - \lambda_2, & \text{if } m = 0. \end{cases} $$

Then, for $m \ge 0$, $c \ge 1$,

$$ |A_{m+c}| = |\Lambda_{c-1}| |\tilde{A}_{m+1}| + |Y_{c-1}| |\tilde{V}_{m+1}|. \qquad (A.26) $$

For $c = 1$, the proof of (A.26) is trivial by noting that $\tilde{A}_{m+1} = A_{m+1}$ when $c = 1$, $\Lambda_0 = 1$ (cf. (A.7)) and $Y_0 = 0$ (cf. (A.19)). For $c \ge 2$, the proof follows from Lemma A.1.
For these new matrices, it is easily seen that for $m \ge 0$,

$$|\tilde{A}_{m+1}| = (\alpha + \lambda) |\tilde{A}_m| + c\mu |\tilde{V}_m|; \qquad (A.27)$$

$$|\tilde{V}_{m+1}| = \alpha |\tilde{A}_m| + c\mu |\tilde{V}_m|, \qquad (A.28)$$

from which it follows that for $m \ge 0$,

$$|\tilde{V}_{m+1}| = |\tilde{A}_{m+1}| - \lambda |\tilde{A}_m|; \qquad (A.29)$$

$$|\tilde{A}_{m+2}| = (\alpha + \lambda + c\mu) |\tilde{A}_{m+1}| - c\mu \lambda |\tilde{A}_m|, \qquad (A.30)$$

provided $|\tilde{A}_0| = 1$ and $|\tilde{V}_0| = 1 - \lambda_2\beta_1/(c\mu)$.

Further, (A.26) and (A.29) imply that for $m \ge 0$,

$$|A_{m+c}| = (|\Lambda_{c-1}| + |Y_{c-1}|) |\tilde{A}_{m+1}| - \lambda |Y_{c-1}| |\tilde{A}_m|. \qquad (A.31)$$

Introducing the matrix

$$\tilde{A}_{m+1} = \begin{cases} M_{m+c-1}^c (\alpha + \lambda, \alpha, \alpha + \lambda), & \text{if } m \ge 1; \\ \alpha + \lambda, & \text{if } m = 0, \end{cases}$$

we have similarly to (A.31)

$$|\Lambda_{m+c}| = (|\Lambda_{c-1}| + |Y_{c-1}|) |\tilde{A}_{m+1}| - \lambda |Y_{c-1}| |\tilde{A}_m|, \qquad (A.32)$$

for $m \ge 0$, with the convention that $|\tilde{A}_0| = 1$.

Using (A.32), (A.25) and the relation $x_{m-1+c}(m+c) = \beta_1 x_{m-1+c}(m-1+c)$, cf. (4.6), we finally obtain for $m \ge 1$,

$$\begin{align*} [x_{m-1+c}(m+c) + g(m+c)] |A_{m-1+c}| = & \\ g(m+c) |A_{m-1+c}| - \lambda_1 \beta_1 (c\mu)^{m-1} \sum_{j=1}^{c-1} g(j) \frac{(c-1)!}{(j-1)!} \mu^{c-j} |\Lambda_{j-1}| - & \\ \lambda_1 \beta_1 \sum_{j=0}^{m-1} g(j+c)(c\mu)^{m-1-j} [(|\Lambda_{c-1}| + |Y_{c-1}|) |\tilde{A}_j| - \lambda |Y_{c-1}| |\tilde{A}_{j-1}|] . & \end{align*} \qquad (A.33)$$

**Step 2:** Computation of $x_{m+c}(0) - x_{m-1+c}(0)$

In order to describe $x_{m+c}(0)$, we introduce the matrix

$$V_{m+c}^j := \begin{cases} M_{m+c-1}^j (\alpha, c\mu/\beta_1 - \lambda_2, \lambda_1 + c\mu/\beta_1), & \text{if } 1 \le j < m+c; \\ c\mu/\beta_1 - \lambda_2, & \text{if } j = m+c. \end{cases}$$
By straightforward manipulations with the determinants, it can be shown that

$$x_{m+c}(1) |A_{m+c}| = -\lambda_1 g(1) \frac{|A_{m+c}| - |V_{m+c}^1|}{\lambda} + \lambda_1 \sum_{j=2}^{m+c} g(j) \lambda^{j-2} |V_{m+c}^j|, \quad m \ge 0.$$

From this relation, it follows readily by using (A.12) with $k=1$ that

$$x_{m+c}(0) |A_{m+c}| = \frac{\lambda_1}{\alpha} \sum_{j=1}^{m+c} g(j) \lambda^{j-1} |V_{m+c}^j|, \quad m \ge 0. \quad (A.34)$$

From the definitions of the matrices $V_{m+c}^j$ and $\tilde{V}_{m+1+c-j}$ we have

$$V_{m+c}^j = \tilde{V}_{m+1+c-j}, \quad (A.35)$$

for $c \le j \le m+c$. Further, by applying again Lemma A.1 to $V_{m+c}^j$ it is easily seen that

$$|V_{m+c}^j| = |W_{c-1}^j| |\tilde{A}_{m+1}| + |Z_{c-1}^j| |\tilde{V}_{m+1}|, \quad (A.36)$$

for $1 \le j \le c-1$, $m \ge 0$, where

$$W_{c-1}^j := \begin{cases} M_{c-2}^j(\alpha, \alpha, \alpha + \lambda), & \text{if } 1 \le j \le c-2; \\ \alpha, & \text{if } j = c-1; \end{cases}$$

$$Z_{c-1}^j := \begin{cases} M_{c-2}^j(\alpha, \mu_{c-1}, \mu_{c-1}), & \text{if } 1 \le j \le c-2; \\ \mu_{c-1}, & \text{if } j = c-1. \end{cases}$$

These matrices satisfy the recursions

$$|W_c^j| = (\alpha + \lambda) |W_{c-1}^j| + \alpha |Z_{c-1}^j|; \quad (A.37)$$

$$|Z_c^j| = c\mu (|W_{c-1}^j| + |Z_{c-1}^j|), \quad (A.38)$$

for $j = 1, 2, \dots, c-1$, $c \ge 2$, while $|W_c^c| = \alpha$ and $|Z_c^c| = c\mu$ for $c \ge 1$. With the aid of relations (A.35) and (A.36) we may rewrite (A.34) as

$$\begin{aligned} x_{m+c}(0) |A_{m+c}| = & \frac{\lambda_1}{\alpha} \sum_{j=1}^{c-1} g(j) \lambda^{j-1} [|W_{c-1}^j| |\tilde{A}_{m+1}| + |Z_{c-1}^j| |\tilde{V}_{m+1}|] \\ & + \frac{\lambda_1}{\alpha} \sum_{j=0}^{m} g(c+j) \lambda^{c+j-1} |\tilde{V}_{m+1-j}|, \quad m \ge 0. \end{aligned} \quad (A.39)$$

Hence, for $m \ge 1$,

$$\frac{\alpha}{\lambda_1} [x_{m+c}(0) - x_{m-1+c}(0)] |A_{m+c}| |A_{m-1+c}| =$$
$$ \begin{aligned} & \left( |\tilde{A}_{m+1}| |A_{m-1+c}| - |\tilde{A}_m| |A_{m+c}| \right) \sum_{j=1}^{c-1} g(j) \lambda^{j-1} |W_{c-1}^j| \\ & + \left( |\tilde{V}_{m+1}| |A_{m-1+c}| - |\tilde{V}_m| |A_{m+c}| \right) \sum_{j=1}^{c-1} g(j) \lambda^{j-1} |Z_{c-1}^j| \\ & + g(m+c) \lambda^{m-1+c} |\tilde{V}_1| |A_{m-1+c}| \\ & + \sum_{j=0}^{m-1} g(j+c) \lambda^{j-1+c} \left( |\tilde{V}_{m+1-j}| |A_{m-1+c}| - |\tilde{V}_{m-j}| |A_{m+c}| \right). \end{aligned} \quad (A.40) $$

It can be shown by induction on $m$ (and by using (A.30)) that for $m > 1$ and $j = 1, 2, \dots, m-1$ or $m = 1$ and $j = 0$,

$$ |\tilde{A}_{m+1}| |\tilde{V}_{m-j}| - |\tilde{A}_m| |\tilde{V}_{m+1-j}| = \lambda_1 \beta_1 (c\mu)^{m-1-j} \lambda^{m-j} |\tilde{V}_1| |\tilde{\Lambda}_j|. \quad (A.41) $$

By applying (A.26) and (A.41) to the first two terms in the right-hand side of (A.40), as well as (A.29) and (A.41) to the last one, it is straightforward to reduce (A.40) for $m \ge 1$ to

$$ \begin{aligned} \frac{\alpha}{\lambda_1} [x_{m+c}(0) - x_{m-1+c}(0)] |A_{m+c}| |A_{m-1+c}| = & \\ \lambda_1 \beta_1 (c\mu)^{m-1} \lambda^m |\tilde{V}_1| \sum_{j=1}^{c-1} g(j) \lambda^{j-1} \left( |Y_{c-1}| |W_{c-1}^j| - |\Lambda_{c-1}| |Z_{c-1}^j| \right) + & \\ g(m+c) \lambda^{m-1+c} |\tilde{V}_1| |A_{m-1+c}| + \sum_{j=0}^{m-1} g(j+c) \lambda_1 \beta_1 (c\mu)^{m-1-j} \lambda^{m-1+c} |\tilde{V}_1| \times & \\ \left( \lambda |Y_{c-1}| |\tilde{\Lambda}_{j-1}| - [|\Lambda_{c-1}| + |Y_{c-1}|] |\tilde{\Lambda}_j| \right). & \end{aligned} \quad (A.42) $$

### Step 3: Proof of (A.18)

We are now in position to prove (A.18). For $c = 1$, it is seen from (A.33) and (A.42) that (A.18) is true.

For $c \ge 2$, it follows from (A.33) and (A.42) that the relation

$$ \sum_{j=1}^{c-1} g(j) \lambda^{j-1} \left( |Y_{c-1}| |W_{c-1}^j| - |\Lambda_{c-1}| |Z_{c-1}^j| \right) = -\lambda^{c-1} \sum_{j=1}^{c-1} g(j) \frac{(c-1)!}{(j-1)!} \mu^{c-j} |\Lambda_{j-1}|, \quad (A.43) $$

has to be proved in order to establish (A.18).

For $c = 2$, this relation reads

$$ |Y_1| |W_1^1| - |\Lambda_1| |Z_1^1| = -\lambda \mu |\Lambda_0|, $$

which is true since $|Y_1| = \mu$, $|\Lambda_0| = 1$, $|\Lambda_1| = \alpha + \lambda$, $|W_1^1| = \alpha$ and $|Z_1^1| = \mu$.
Now suppose that (A.43) holds for some fixed $c$, $c \ge 2$. Then,

$$ 
\begin{aligned}
\lambda^c \sum_{j=1}^{c} g(j) \frac{c!}{(j-1)!} \mu^{c+1-j} |\Lambda_{j-1}| = & \lambda^c g(c) c\mu |\Lambda_{c-1}| \\
& + \lambda c\mu \sum_{j=1}^{c-1} g(j) \lambda^{j-1} (|\Lambda_{c-1}| |Z_{c-1}^j| - |Y_{c-1}| |W_{c-1}^j|).
\end{aligned} 
\quad (A.44) 
$$

On the other hand, using the recursions (A.20), (A.21), (A.37) and (A.38), it follows that

$$ 
\begin{aligned}
\sum_{j=1}^{c} g(j) \lambda^{j-1} (|\Lambda_c| |Z_c^j| - |Y_c| |W_c^j|) = & \lambda^{c-1} g(c) (c\mu |\Lambda_c| - \alpha |Y_c|) + \\
& \lambda c\mu \sum_{j=1}^{c-1} g(j) \lambda^{j-1} (|\Lambda_{c-1}| |Z_{c-1}^j| - |Y_{c-1}| |W_{c-1}^j|).
\end{aligned} 
\quad (A.45) 
$$

Finally, by using (A.22) with $k=c$, it is seen that (A.44) and (A.45) are equivalent, so that (A.43) holds for $c$ instead of $c-1$, which concludes the proof. ■

The notation introduced in the proof of Lemma 4.3 will be used in the remainder of this appendix.

### Proof of Lemma 4.3.

By using (A.24) and the identity $x_{m+c}(m+c+1) = \beta_1 x_{m+c}(m+c)$, it follows that the condition $C_m, m \ge 0$, can be expressed as

$$ g(m+1+c) \le \frac{\lambda_1 \beta_1}{c\mu} \sum_{j=1}^{m+c} g(j) \frac{|\Lambda_{j-1}|}{|A_{m+c}|} \prod_{i=j}^{m+c} \mu_i. \quad (A.46) $$

On the other hand, it is easily seen from the definition of the matrices $A_{m+c}$, $Y_{m+c}$ and $\Lambda_{m+c}$ that for $m \ge 0$

$$ |A_{m+c}| = \left(\lambda_1 + \frac{c\mu}{\beta_1}\right) |\Lambda_{m-1+c}| + \left(\frac{c\mu}{\beta_1} - \lambda_2\right) |Y_{m-1+c}|, \quad (A.47) $$

which implies, together with (A.20) and (A.21), that for $m \ge 1$

$$ |A_{m+c}| = \lambda_1 |\Lambda_{m-1+c}| + \frac{c\mu}{\beta_1} |A_{m-1+c}|. \quad (A.48) $$

Repeated applications of (A.48) give for $m \ge 1$

$$ |A_{m+c}| = \left(\frac{c\mu}{\beta_1}\right)^m |A_c| + \lambda_1 \sum_{j=c+1}^{m+c} \left(\frac{c\mu}{\beta_1}\right)^{m+c-j} |\Lambda_{j-1}|. \quad (A.49) $$

Note that (A.49) trivially holds for $m=0$.
With (A.49) it is easily seen that (A.46) is equivalent to

$$ g(m+1+c) \left[ \left( \frac{c\mu}{\beta_1} \right)^m |A_c| + \lambda_1 \sum_{j=c+1}^{m+c} \left( \frac{c\mu}{\beta_1} \right)^{m+c-j} |\Lambda_{j-1}| \right] \\ \leq \lambda_1 \beta_1 \sum_{j=1}^{c} \mu^{m+c-j} c^m \frac{(c-1)!}{(j-1)!} |\Lambda_{j-1}| g(j) + \lambda_1 \beta_1 \sum_{j=c+1}^{m+c} (c\mu)^{m+c-j} |\Lambda_{j-1}| g(j), \quad (A.50) $$

for $m \ge 0$.

Because $\alpha$ is such that

$$ \Psi < \beta_1 < 1, \quad (A.51) $$

and generally (see (2.2))

$$ g(m+1+c) \le \Psi^{m+1-j+c} g(j), \quad (A.52) $$

for $j \ge c$, it follows that for all $m > 0$,

$$ g(m+1+c) \sum_{j=c+1}^{m+c} \left(\frac{c\mu}{\beta_1}\right)^{m+c-j} |\Lambda_{j-1}| < \beta_1 \sum_{j=c+1}^{m+c} (c\mu)^{m+c-j} |\Lambda_{j-1}| g(j). \quad (A.53) $$

Further, (A.51) and (A.52) implies that

$$ \lim_{m \uparrow \infty} \frac{g(m)}{\beta_1^m} = 0, $$

so that there must exist an $M$ (that clearly depends on $\alpha$), $0 \le M < +\infty$, such that for all $m \ge M$,

$$ \frac{g(m+1+c)}{\beta_1^m} |A_c| \le \lambda_1 \beta_1 \sum_{j=1}^{c} \mu^{c-j} \frac{(c-1)!}{(j-1)!} |\Lambda_{j-1}| g(j). \quad (A.54) $$

By combining (A.50), (A.53) and (A.54), we finally see that $C_m$ is satisfied for all $m \ge M$.

The proof is concluded by observing that such an $M$ also exists for $\alpha = 0$, since $\beta_1 = 1$ if $\alpha = 0$, cf. Section 4, and since $\lim_{m\uparrow\infty} g(m) = 0$. ■

**Lemma A.1** Let $c \ge 2$ and define

$$ \tilde{A}_{m+1}(b_0, c_0) := \begin{cases} M_{m+c-1}^c(\alpha + \lambda, b_0, c_0), & \text{if } m \ge 1; \\ c_0, & \text{if } m = 0; \end{cases} $$

$$ \tilde{V}_{m+1}(b_0, c_0) := \begin{cases} M_{m+c-1}^c(\alpha, b_0, c_0), & \text{if } m \ge 1; \\ b_0, & \text{if } m = 0; \end{cases} $$

$$ W_{c-1}^j(a_0) := \begin{cases} M_{c-2}^j(a_0, \alpha, \alpha + \lambda), & \text{if } 1 \le j \le c-2; \\ a_0, & \text{if } j = c-1; \end{cases} $$

$$ Z_{c-1}^j(a_0) := \begin{cases} M_{c-2}^j(a_0, \mu_{c-1}, \mu_{c-1}), & \text{if } 1 \le j \le c-2; \\ \mu_{c-1}, & \text{if } j = c-1. \end{cases} $$
Then,

$$|M_{m+c-1}^j| = |W_{c-1}^j(a_0)| |\tilde{A}_{m+1}(b_0, c_0)| + |Z_{c-1}^j(a_0)| |\tilde{V}_{m+1}(b_0, c_0)|, \quad (A.55)$$

for $1 \le j \le c - 1$, $m \ge 0$, and for any constants $a_0$, $b_0$ and $c_0$.

**Proof.** The proof is easily obtained by induction on $m$ (see Blanc et al. [3]).

<figure><img src="image_4.png" /></figure>

## References

[1] E. Altman and P. Nain, “Optimality of a threshold policy in the M/M/1 queue with repeated vacations.” INRIA Report no. 1419, Apr. 1991. Submitted to *Operat. Res.*

[2] R. E. Barlow and F. Proschan, *Statistical Theory of Reliability and Life Testing*. Holt, Rinehart and Winston, Inc., New York, 1975.

[3] J. P. C. Blanc, P. de Waal, P. Nain, and D. Towsley, “A new device for the synthesis problem of optimal control of admission to an M/M/c queue,” INRIA Report no. 1310, Oct. 1990.

[4] D. P. Bertsekas, *Dynamic Programming: Deterministic and Stochastic Models*. Prentice-Hall, Englewoods Cliffs, New Jersey, 1987.

[5] K. L. Chung, *Markov Chains with Stationary Transition Probabilities*. 2nd. Ed., Springer Verlag, New York, 1967.

[6] P. R. de Waal, “Performance analysis and optimal control of an M/M/1/k queueing system with impatient customers,” in *Proc. Messung, Modellierung und Bewertung von Rechensystemen 4. GI/ITG-Fachtagung*, pp. 28-40, U. Herzog and M. Paterok, Eds., Springer-Verlag, Berlin, 1987.

[7] P. R. de Waal, “Overload Control of Telephone Exchanges”, PhD. thesis, CWI, Amsterdam, 1990.

[8] A. Ephremides, P. Varaiya, and J. Walrand, “A simple dynamic routing problem”, *IEEE Trans. Automat. Contr.*, vol. AC-25, no. 4, pp. 690-693, 1980.

[9] B. Hajek, “Optimal control of two interacting service stations,” *IEEE Trans. Automat. Contr.*, vol. AC-29, no. 6, pp. 491-498, 1984.

[10] D. P. Heyman and M. J. Sobel, *Stochastic Models in Operations Research*, Vol II. McGraw-Hill, New York, 1982.

[11] A. Hordijk and F. M. Spieskma, “Constrained admission control to a queueing system,” *Adv. Appl. Prob.*, vol. 21, pp. 409-431, 1989.

[12] S. G. Johansen and S. S. Stidham, “Control of arrivals to a stochastic input-output system,” *Adv. Appl. Prob.*, vol. 12, pp. 972-999, 1980.
[13] A. A. Lazar, "Optimal flow control of an M/M/m queue," JACM, vol. 31, no. 1, pp. 86-98, 1984.

[14] W. Lin and P. R. Kumar, "Optimal control of a queueing system with two heterogeneous servers," IEEE Trans. Automat. Contr., vol. AC-29, no. 8, pp. 696-703, 1984.

[15] S. A. Lippman, "Applying a new device in the optimization of exponential queueing systems," Operat. Res., vol. 23, no. 4, pp. 687-710, 1975.

[16] S. A. Lippman, "On dynamic programming with unbounded rewards," Management Sci., vol. 21, no. 11, pp. 1225-1233, 1975.

[17] D.-J. Ma and A. M. Makowski, "Optimality results for a simple flow control problem," in Proc. 26th Conf. on Decision Contr., pp. 1852-1857, Los Angeles CA, Dec. 1987.

[18] Z. Rosberg, P. Varaiya, and J. Walrand, "Optimal control of service in tandem queues," IEEE Trans. Automat. Contr., vol. AC-27, no. 3, pp. 600-610, 1982.

[19] K. W. Ross and B. Chen, "Optimal scheduling of interactive and noninteractive traffic in telecommunication systems," IEEE Trans. Automat. Contr., vol. AC-33, no. 2, pp. 261-267, 1988.

[20] S. M. Ross, Applied Probability Models with Optimization Applications. Holden-Day, San Francisco, 1970.

[21] R. Serfozo, "Optimal control of random walks, birth and death processes, and queues," Adv. Appl. Prob., vol. 13, pp. 61-83, 1981.

[22] S. S. Stidham, "Optimal control of admission to a queueing system," IEEE Trans. Automat. Contr., vol. AC-30, no. 8, pp. 705-713, 1985.

[23] D. V. Widder, The Laplace Transform. Princeton University Press, Princeton, 1941.