# Optimal control of the M/G/1 queue with repeated vacations of the server

Eitan Altman, Philippe Nain

► To cite this version:

Eitan Altman, Philippe Nain. Optimal control of the M/G/1 queue with repeated vacations of the server. IEEE Transactions on Automatic Control, 1993, 38 (12), pp.1766-1775. 10.1109/9.250556. hal-04360077

HAL Id: hal-04360077

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

Submitted on 21 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 THE M/G/1 QUEUE WITH REPEATED VACATIONS OF THE SERVER *

Eitan ALTMAN and Philippe NAIN

INRIA

B.P. 93

06902 Sophia Antipolis Cédex, France

altman@sophia.inria.fr nain@sophia.inria.fr

December 1993

## Abstract

We consider a M/G/1 queue where the server may take repeated vacations. Whenever a busy period terminates the server takes a vacation of random duration. At the end of each vacation the server may either take a new vacation or resume service; if the queue is found empty the server always takes a new vacation. The cost structure includes a holding cost per unit of time and per customer in the system and a cost each time the server is turned on. One discounted cost criterion and two average cost criteria are investigated. We show that the vacation policy that minimizes the discounted cost criterion over all policies (randomized, history dependent, etc.) converges to a threshold policy as the discount factor goes to zero. This result relies on a non standard use of the value iteration algorithm of dynamic programming and is used to prove that both average cost problems are minimized by a threshold policy

## 1 Introduction

We consider a M/G/1 queue where the server may take repeated vacations. Let $\lambda > 0$ be the intensity of the Poisson arrival process and let $0 < b < \infty$ and $b^{(2)} < \infty$ be the first and second moment of the service time distribution $B(\cdot)$, respectively. We shall assume throughout this paper that $\rho := \lambda b < 1$. Whenever a busy period terminates (i.e., when the queue empties) the server takes a vacation whose duration is distributed like a generic random variable (r.v.) $D$ with Laplace-Stieltjes Transform (LST) $\hat{d}(\cdot)$, first moment $0 < d < \infty$ and second moment $d^{(2)} < \infty$. The durations of the vacation periods are assumed to be mutually independent r.v.'s independent of

<footnote>*Work partially supported by the France-Israel Scientific Cooperation in Computer Science and Engineering under Grant 3321190.</footnote>
the arrival and service processes. At each vacation completion time (or decision epoch) the control policy specifies whether the server should take a new vacation of random duration D (action v) or resume service (action s); if the queue is found empty the server always takes a new vacation. The service discipline is arbitrary as long as it is work conserving. The cost structure includes a holding cost of 1 per unit of time and per customer in the system and a constant cost $\gamma > 0$ each time the server is turned on.

In this paper we shall adopt the definition of a control policy used in the Semi-Markov Decision Process (SMDP) setting (see [?, ?] among others). A control policy u is a sequence of decision rules $u_1, u_2, \dots$ where the nth decision rule $u_n$ selects an action in $\{s, v\}$ after completion of the nth vacation. More precisely, $u_n$ is a conditional probability on the set $\{s, v\}$ given the history $h_n = (x_1, a_1, \tau_2, \dots, x_{n-1}, a_{n-1}, \tau_n, x_n)$ of the system up to and including the n-th decision epoch, where $x_j, a_j$ and $\tau_j$ represent the queue-length at the jth decision epoch, the action made at the jth decision epoch and the time that elapses between the j-1st and the jth decision, respectively. Let $\mathcal{U}$ be the set of all control policies such that $u_n(v|h_n) = 1$ if $x_n = 0$ for all $n \ge 1$. As usual a policy in $\mathcal{U}$ is said to be a stationary policy if there exists a measurable mapping $f$ from $\{0, 1, 2, \dots\}$ into $\{s, v\}$ such that $u_n(a|h_n) = \mathbf{1}(f(x_n) = a)$ for all $a \in \{s, v\}, n \ge 1$. For every stationary policy $u \in \mathcal{U}$ the notation $u(x)$ will stand for the action to be chosen when the system is in state $x$. In particular, a stationary policy $u \in \mathcal{U}$ such that $u(x) = v$ for $0 \le x < l$ and $u(x) = s$ for $x \ge l, l \ge 1$, is called a threshold policy with threshold $l$ and is denoted by $u_l$.

Given that policy u is used and that $x$ customers are present in the system at time 0 there exists a probability space $(\Omega, \mathcal{F}, P_x^u)$ that simultaneously carries the queue-length process $\{X(t), t \ge 0\}$, the action process $\{A_n, n \ge 1\}$ where $A_n \in \{s, v\}$ is the nth action taken, and the vacation completion time process $\{t_n, n \ge 1\}$, $0 \le t_1 < t_2 < \dots$ a.s., where $t_n$ is the time when the nth vacation ends (nth decision epoch). In the following we shall assume that the first decision is made at time 0 (i.e., $t_1 = 0$). The construction of $P_x^u$ is a standard exercise that will not be addressed in this paper (see [?]).

Let $X_n := X(t_n)$ be the queue-length at the nth decision epoch $t_n, n \ge 1$. We now introduce the three control problems that will be successively considered in this paper:

**Problem P0(α).** Find $u \in \mathcal{U}$ that minimizes ($\alpha > 0$)

$$W_{\alpha}(x, u) := E_x^u \left[ \sum_{n \ge 1} e^{-\alpha t_n} C(X_n, A_n) \right], \quad x = 0, 1, 2, \dots; \qquad (1.1)$$

**Problem P1.** Find $u \in \mathcal{U}$ that minimizes

$$\Phi(x, u) := \overline{\lim}_{t \to \infty} \frac{1}{t} E_x^u \left[ \sum_{n=1}^{N(t)} C(X_n, A_n) \right], \quad x = 0, 1, 2, \dots; \qquad (1.2)$$
Problem **P2**. Find $u \in \mathcal{U}$ that minimizes

$$V(x, u) := \varlimsup_{t \to \infty} \frac{1}{t} E_x^u \left[ \int_0^t X(\xi) \, d\xi + \gamma \sum_{n=1}^{N(t)} \mathbf{1}(A_n = s) \right], \quad x = 0, 1, 2, \dots \quad (1.3)$$

where $E_x^u$ is the expectation operator associated with the probability measure $P_x^u$ and $N(t) := \sup\{n \ge 1 : 0 \le t_n < t\}$ is the number of decision epochs in $[0, t)$.

In (??)-(??) the quantity $C(x, a)$ is defined to be the cumulative expected cost incurred by the system between two consecutive decision epochs, say $t_n$ and $t_{n+1}$, given that the queue-length is $x$ at time $t_n$ and that action $a$ is chosen at time $t_n$. Since the arrival process is Poisson we observe that the evolution of the queue-length process in $[t_n, t_{n+1})$, given that $X_n = x$ and $A_n = a$, does not depend on $n$. So, letting $n = 1$ we see that

$$C(x, a) = E_x^u \left[ \int_0^{t_2} X(\xi) \, d\xi \right] + \gamma \mathbf{1}(a = s), \quad x \in \mathbb{N}. \quad (1.4)$$

A closed-form expression for $C(x, a)$ is given in Section ??.

The cost functions (??) and (??) are the total expected $\alpha$-discounted cost and the long-run expected average cost associated with the one-step cost function $C$, respectively. On the other hand, (??) gives the long-run average cost corresponding to the original system. So, in a way, (??) is the “natural” cost criterion associated with the cost structure introduced at the beginning of this section. However, solving directly for problem **P2** is a difficult task for this problem cannot be formulated as a SMDP control problem in contrast with problems **P0**($\alpha$) and **P1**. Therefore, in a first step our approach will consist in solving successively problems **P0**($\alpha$) and **P1** by using tools from SMDP theory. In a second step, we shall invoke renewal theory to show that both cost functions (??) and (??) agree over the broad class of so-called regenerative policies (see the definition in Section ??). This will finally yield the solution to problem **P2**.

We now summarize the main contributions of this paper. The first set of results (Propositions ??-??) addresses the problem **P0**($\alpha$) for small values of the discount factor $\alpha$. We show that there exists $L \in \mathbb{N}$, $1 \le L \le N_0 := \inf\{k \ge 1 : k > \gamma(1-\rho)/d\}$, such that for every $k \in \mathbb{N}$ there exists $\gamma_k > 0$ such that the optimal action when the queue-length is $x$ is to turn the server off if $0 \le x < L$ and to turn it on if $L \le x \le N_0 + k$ for all $\alpha \in (0, \gamma_k)$. The proof relies on a non-standard use of the value iteration algorithm of the Dynamic Programming (DP) theory [?]. Indeed, the conditions to be propagated involve the entire range of the parameter $\alpha$ and require that they be propagated through the entire family of DP operators. This is in contrast with usual application of the value iteration algorithm where the conditions to be propagated through the DP operator are given for a single value of $\alpha$.

The second contribution (Theorem ??) is to show that the threshold policy $u_L$ solves the average cost problem **P1**. The proof of this result will require a generalization of one of Sennott's conditions for the existence of an average optimal policy [?, ?]. The third contribution (Theorem ??) is to prove
that the threshold policy $u_L$ also minimizes the cost function (??) over the set of all regenerative policies.

The literature on queueing models with vacations is rapidly growing. This is because these models provide an appealing formalism for the study of various discrete event systems ranging from production systems to communication and computer systems (see [?] for a survey paper). Three types of server vacation schemes are commonly encountered in the literature: the scheme with repeated vacations of the server that has just been described above (see also [?, ?, ?, ?, ?]); the scheme where the server may resume service upon the arrival of a new customer (the so-called “removable server”, see [?, pp. 336-337], [?]) and a mixture of those two schemes [?].

Dynamic control and optimization issues for queueing models with server vacations have already received some attention. In [?] a control problem for the M/G/1 queue with a removable server is solved and the optimality of a threshold policy is established. For the same model, the optimal threshold policy out of all threshold policies is computed in [?]. The same analysis is carried out in [?] when batch arrivals are allowed. In [?] the optimality of a threshold policy for the problem P2 is obtained for the M/M/1 queue with exponential repeated vacations.

While we were completing this paper a related study appeared in [?]. The model investigated in [?] is more general than the present model since batch arrivals and system dependent holding cost rates are allowed. However, the analysis developed in the forthcoming sections extends to this model provided that Conditions 1 and 2 in [?, p. 391] are satisfied. In [?] the existence of a threshold policy that minimizes a cost function similar to the cost function (??) is shown. The approach relies on a systematic variation of the parameter $\gamma$ and is completely different from our approach.

The discussion is organized as follows: Section ?? addresses the problem P0($\alpha$) for small values of $\alpha$. In Section ?? we solve the problem P1 while the problem P2 is solved in Section ???. A few words on the notation used in this paper: we denote the set of nonnegative integers by $\mathbb{N}$ and the set of all real numbers by $\mathbb{R}$

## 2 The Discounted Cost Problem

This section addresses the control problem P0($\alpha$) introduced in Section ???. For every fixed $\alpha > 0$, a policy $u \in \mathcal{U}$ is said to be $\alpha$-discounted optimal if $W_{\alpha}(x) = W_{\alpha}(x, u)$ for all $x \in \mathbb{N}$ where

$$W_{\alpha}(x) := \inf_{v \in \mathcal{U}} W_{\alpha}(x, v), \quad n \in \mathbb{N}. \qquad (2.1)$$

Our analysis begins with the observation that the queue-length process embedded at the decision epochs $\{X_n, n \ge 1\}$ is a controlled Markov chain [?] with state space $\mathbb{N}$ and transition probabilities
$P_{xy}(a)$ given by

$$ P_{xy}(a) := \begin{cases} P_V(y) & \text{if } a = s \text{ and } x \ge 1 \\ P_V(y-x) & \text{if } a = v \text{ and } x \le y \\ 0 & \text{if } a = v \text{ and } x > y \end{cases} \qquad (2.2) $$

where $P_V(y)$ stands for the probability of $y$ arrivals during a vacation period.

The LST of the sojourn times of the process $\{X_n, n \ge 1\}$ in state $x$, given that action $a$ has been chosen, is given by $(\alpha > 0)$

$$ \hat{\tau}_{x,a}(\alpha) := \begin{cases} \hat{d}(\alpha) & \text{if } a = v \text{ and } x \in \mathbb{N} \\ \hat{d}(\alpha) [\hat{T}(\alpha)]^x & \text{if } a = s \text{ and } x \ge 1 \end{cases} \qquad (2.3) $$

where $\hat{T}(\alpha)$ stands for the LST of a busy period duration in an M/G/1 queue with arrival intensity $\lambda$ and service time distribution $B(\cdot)$ (observe that $P_{0y}(s)$ and $\hat{\tau}_{0,s}(\alpha)$ need not to be defined since the action $s$ is not permitted when the system is found empty at a decision epoch).

Therefore (see [?, ?]) the cost functions $W_\alpha(x, u)$ and $\Phi(x, u)$ are seen to be the total expected $\alpha$-discounted cost and the long-run expected average cost, respectively, associated with the SMDP $\{X(t), t \ge 0\}$ with state space $\mathbb{N}$, action spaces $\{A_x, x \in \mathbb{N}\}$ with $A_x := \{s, v\}$ if $x \ne 0$ and $A_x := \{v\}$ if $x = 0$, one-step transition probabilities $P_{xy}(a)$, LST of the conditional sojourn times $\hat{\tau}_{x,a}$ and one-step cost function $C$ defined in (2.3), respectively.

We have shown in [?, Appendix A] that for $x \in \mathbb{N}$

$$ C(x, a) = \frac{\lambda d^{(2)}}{2} + x d \mathbf{1}(a = v) + \left( \frac{b}{2(1-\rho)} x^2 + \frac{\lambda b^{(2)} + b(1-\rho)}{2(1-\rho)^2} x + \gamma \right) \mathbf{1}(a = s, x \neq 0). \qquad (2.4) $$

We observe from (2.3) that for each $a \in \{s, v\}$ the cost $C(x, a)$ is not bounded on $\mathbb{N}$. One way of handling unbounded costs is to define a new norm for which the costs are bounded [?]. Adapting the results in [?] to our problem, we define $\mathcal{K}$ to be the set of functions $f: \mathbb{N} \to \mathbb{R}$ such that $||f|| := \sup_{x \in \mathbb{N}} |f(x)| \max(x, 1)^{-2} < \infty$.

Define the Dynamic Programming (DP) operator $T_\alpha: \mathcal{K} \to \mathcal{K}$ by

$$ T_\alpha f(x) := \min_{a \in A_x} \left\{ C(x, a) + \hat{\tau}_{x,a}(\alpha) \sum_{y \in \mathbb{N}} P_{xy}(a) f(y) \right\}, \quad x \in \mathbb{N}. \qquad (2.5) $$

The proof that $T_\alpha(f)$ belongs to the set $\mathcal{K}$ can be found in [?, p. 1228] (the proof that Assumptions 1-3 in [?, p. 1227] hold is straightforward by using the explicit form of $C$ given in (2.3); in particular, the constant $b$ that appears in Assumption 3 in [?] may be chosen to be $1 + \lambda d + \lambda^2 d^{(2)}$).

We have the following results [?, Theorem 1]:
**Proposition 2.1** Fix $\alpha > 0$. For every stationary policy $u \in \mathcal{U}$, $W_\alpha(x, u)$ satisfies the equation

$$W_{\alpha}(x, u) = C(x, u(x)) + \hat{\tau}_{x,u(x)}(\alpha) \sum_{y \in \mathbb{N}} P_{xy}(u(x)) W_{\alpha}(y, u), \quad x \in \mathbb{N}. \qquad (2.6)$$

On the other hand, $W_\alpha(x)$ is (the unique) solution in $\mathcal{K}$ of the DP equation

$$W_{\alpha}(x) = T_{\alpha}W_{\alpha}(x), \quad x \in \mathbb{N} \qquad (2.7)$$

and can be obtained as

$$\lim_{n \to \infty} T_{\alpha}^{n} f(x) = W_{\alpha}(x), \quad x \in \mathbb{N} \qquad (2.8)$$

for every function $f \in \mathcal{K}$, where $T_{\alpha}^{n+1}f := T_{\alpha}[T_{\alpha}^{n}f]$ for $n \ge 1$.

Moreover, any stationary policy that minimizes the right-hand side of (2.7) is $\alpha$-discounted optimal.

Specializing the DP equation (2.7) to our model we see from (2.7), (2.8) and (2.9) that

$$W_{\alpha}(x) = \min \left\{ C(x, v) + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_{V}(y) W_{\alpha}(x+y), C(x, s) + \hat{d}(\alpha) \left[ \hat{T}(\alpha) \right]^{x} \sum_{y \in \mathbb{N}} P_{V}(y) W_{\alpha}(y) \right\} \quad (2.9)$$

for every $x \in \mathbb{N}$. For later use it is convenient to rewrite (2.7) in the form

$$W_{\alpha}(x) = C(x, s) + \hat{d}(\alpha) \left[ \hat{T}(\alpha) \right]^{x} \sum_{y \in \mathbb{N}} P_{V}(y) W_{\alpha}(y) + \min\{\Delta_{\alpha}(x), 0\}, \quad x \in \mathbb{N} \qquad (2.10)$$

where

$$\Delta_{\alpha}(x) := C(x, v) - C(x, s) + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_{V}(y) \left( W_{\alpha}(x+y) - \left[ \hat{T}(\alpha) \right]^{x} W_{\alpha}(y) \right). \qquad (2.11)$$

By Proposition 2.1 the optimal action in state $x$ is to take another vacation if $\Delta_\alpha(x) < 0$ and to resume service if $\Delta_\alpha(x) > 0$, while both actions are optimal when $\Delta_\alpha(x) = 0$. Denote by $u_\alpha^*$ the unique stationary policy that minimizes the right-hand side of (2.7) and that chooses action $v$ in state $x$ if $\Delta_\alpha(x) = 0$ for $x \ge 1$, $\alpha > 0$. The aim of this section is to characterize $u_\alpha^*$ for small values of the discount factor.

We now introduce some properties to be enjoyed by the set of optimal value functions $\{W_\alpha, \alpha > 0\}$ (see Lemma 2.1). We shall say that a set of functions $\{f_\alpha, \alpha > 0\}$ in $\mathcal{K}$ satisfies condition

C1 if for every $x \in \mathbb{N}$, $k \ge 1$, there exists $\alpha_{x,k} > 0$ such that

$$f_{\alpha}(x+r+k) - [\hat{T}(\alpha)]^{k} f_{\alpha}(x+r) \geq C(x+k,s) - C(x,s) \qquad (2.12)$$

for $\alpha \in (0, \alpha_{x,k})$, $r \in \mathbb{N}$;
C2 if for all $\alpha > 0$, $x \in \mathbb{N}$, $k \ge 1$,

$$f_{\alpha}(x+k) - [\hat{T}(\alpha)]^k f_{\alpha}(x) \ge 0. \qquad (2.13)$$

We observe from (2.13) that the set of functions $\{f_{\alpha}, \alpha > 0\}$ with $f_{\alpha}(\cdot) := C(\cdot, s)$ satisfies C1 and C2.

**Lemma 2.1** The set of optimal value functions $\{W_{\alpha}, \alpha > 0\}$ satisfies conditions C1 and C2.

**Proof.** Unless otherwise mentioned $\alpha > 0$, $x \in \mathbb{N}$ and $k \ge 1$ are fixed numbers.

Let $\{f_{\alpha}, \alpha > 0\}$ be an arbitrary set of functions in $\mathcal{K}$ that satisfies C1 and C2. We show that $\{T_{\alpha}f_{\alpha}, \alpha > 0\}$ also satisfies these conditions.

We have from (2.13), (2.14) and (2.15) that for every $r \in \mathbb{N}$

$$ 
\begin{aligned}
& T_{\alpha}f_{\alpha}(x+r+k) - [\hat{T}(\alpha)]^k T_{\alpha}f_{\alpha}(x+r) \\
&= \min \left\{ C(x+r+k,v) + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_V(y)f_{\alpha}(x+r+k+y), \right. \\
& \qquad \left. C(x+r+k,s) + \hat{d}(\alpha) [\hat{T}(\alpha)]^{x+r+k} \sum_{y \in \mathbb{N}} P_V(y)f_{\alpha}(y) \right\} \\
& \quad - [\hat{T}(\alpha)]^k \min \left\{ C(x+r,v) + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_V(y)f_{\alpha}(x+r+y), \right. \\
& \qquad \left. C(x+r,s) + \hat{d}(\alpha) [\hat{T}(\alpha)]^{x+r} \sum_{y \in \mathbb{N}} P_V(y)f_{\alpha}(y) \right\} \\
& \ge \min \left\{ C(x+r+k,v) - [\hat{T}(\alpha)]^k C(x+r,v) \right. \\
& \qquad + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_V(y) (f_{\alpha}(x+r+k+y) - [\hat{T}(\alpha)]^k f_{\alpha}(x+r+y)), \right. \\
& \qquad \left. C(x+r+k,s) - [\hat{T}(\alpha)]^k C(x+r,s) \right\} \qquad (2.14) \\
& \ge \min \left\{ kd + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_V(y) (f_{\alpha}(x+r+k+y) - [\hat{T}(\alpha)]^k f_{\alpha}(x+r+y)), \right. \\
& \qquad \left. C(x+k,s) - C(x,s) \right\}. \qquad (2.15)
\end{aligned}
$$
The inequality (1.1) follows from the inequality $\min(a, b) - \min(c, d) \ge \min(a - c, b - d)$. The first argument in the min in (1.1) follows from

$$C(x + r + k, v) - [\hat{T}(\alpha)]^k C(x + r, v) \ge C(x + r + k, v) - C(x + r, v) = kd \quad (2.16)$$

where the last equality is obtained from (1.1). Finally, the second argument in the min is a consequence of the fact that $C(\cdot, s)$ satisfies C1.

Letting $r = 0$ in (1.1) it is seen that $\{T_\alpha f_\alpha, \alpha > 0\}$ satisfies C2 since $x \to C(x, s)$ is nondecreasing by (1.1) and since $\{f_\alpha, \alpha > 0\}$ satisfies C2 (which implies that the first argument in the min is nonnegative).

Hence, we may deduce by induction that $\{T_\alpha^n f_\alpha, \alpha > 0\}$ satisfies C2 for every $n \ge 1$. Consequently, we have from (1.1)

$$W_\alpha(x + k) - [\hat{T}(\alpha)]^k W_\alpha(x) = \lim_{n \to \infty} [T_\alpha^n f_\alpha(x + k) - [\hat{T}(\alpha)]^k T_\alpha^n f_\alpha(x)] \ge 0 \quad (2.17)$$

which shows that $\{W_\alpha, \alpha > 0\}$ satisfies C2.

It remains to show that the set $\{W_\alpha, \alpha > 0\}$ satisfies C1. Since the mapping $x \to C(x, s)$ is nondecreasing, $\hat{d}(\alpha) \to 1$ as $\alpha \to 0$ and since $kd > 0$, there exists a real number $\beta_{x,k} > 0$ such that for $\alpha \in (0, \beta_{x,k})$

$$kd + \hat{d}(\alpha) (C(x + k, s) - C(x, s)) \ge C(x + k, s) - C(x, s). \quad (2.18)$$

On the other hand, since the set of functions $\{f_\alpha, \alpha > 0\}$ satisfies C1 by assumption, there exists $\alpha_{x,k} > 0$ such that (1.1) holds for $\alpha \in (0, \alpha_{x,k})$. Combining (1.1) and (1.1) we deduce that the right-hand side of inequality (1.1) is equal to $C(x + k, s) - C(x, k)$ for $\alpha \in (0, \gamma_{x,k})$ where $\gamma_{x,k} := \min\{\alpha_{x,k}, \beta_{x,k}\}$. This in turn shows that $\{T_\alpha f_\alpha, \alpha > 0\}$ satisfies C1.

Iterating this procedure we obtain that for every $n \ge 1$,

$$T_\alpha^n f_\alpha(x + r + k) - [\hat{T}(\alpha)]^k T_\alpha^n f_\alpha(x + r) \ge C(x + k, s) - C(x, s)$$

for $\alpha \in (0, \gamma_{x,k})$, $r \in \mathbb{N}$ (note that it is crucial here that $\gamma_{x,k}$ does not depend on $n$) and the proof is concluded as in (1.1). ■

Define

$$N_0 := \inf_{k \in \mathbb{N}} \left\{ k > \gamma \left( \frac{d}{1 - \rho} \right)^{-1} \right\}. \quad (2.19)$$

It is worth observing that the constant $d/(1 - \rho)$ that appears in the definition of $N_0$ is the expected duration between two consecutive vacation completion times if one uses the vacation policy that always turns the server on when the queue is nonempty at the end of a vacation.
We now address the minimization of the right-hand side of the DP equation (??) for $x \ge N_0$ and for small values of $\alpha$.

**Proposition 2.2** There exists a nonincreasing sequence $\{\gamma_k, k \in \mathbb{N}\}$ in $(0, \infty)$ such that for each $k \in \mathbb{N}$, whenever $\alpha \in (0, \gamma_k)$, $u_{\alpha}^*(x) = s$ for $x = N_0, N_0 + 1, \dots, N_0 + k$.

**Proof.** Fix $x \ge N_0$. Owing to (??) it suffices to prove that $\Delta_{\alpha}(x) > 0$ for $\alpha$ small enough.

Since $W_{\alpha}(x+y) - [\hat{T}(\alpha)]^x W_{\alpha}(y)$ is nonnegative for all $\alpha > 0$, $y \in \mathbb{N}$ because $\{W_{\alpha}, \alpha > 0\}$ satisfies C2 by Lemma ??, Fatou's lemma applies to (??) to yield

$$ \begin{aligned} \lim_{\alpha \to 0} \Delta_{\alpha}(x) &\ge C(x, v) - C(x, s) + \sum_{y \in \mathbb{N}} P_V(y) \lim_{\alpha \to 0} (W_{\alpha}(x+y) - [\hat{T}(\alpha)]^x W_{\alpha}(y)) \\ &\ge C(x, v) - C(x, s) + \sum_{y \in \mathbb{N}} P_V(y) (C(x+y, s) - C(y, s)) \end{aligned} \quad (2.20) $$

where the last inequality holds because $\{W_{\alpha}, \alpha > 0\}$ satisfies C1 by Lemma ?? . Using now the expression (??) of the cost $C$ together with the identity $\sum_{y \in \mathbb{N}} y P_V(y) = \lambda d$ (see the definition of $P_V$ in Section ?? ) we readily deduce that the right-hand side of (??) is equal to $xd/(1 - \rho) - \gamma$ which is a strictly positive quantity for all $x \ge N_0$. This concludes the proof. ■

The next result addresses the minimization of the right-hand side of (??) for $x \le N_0$ and for small values of $\alpha$.

**Proposition 2.3** There exists an integer $L$ such that $1 \le L \le N_0$ with the property that for $\alpha$ small enough

$$ u_{\alpha}^{*}(x) = \begin{cases} v & \text{for } x = 0, 1, \dots, L-1 \\ s & \text{for } x = L, L+1, \dots, N_0. \end{cases} \quad (2.21) $$

The proof of Proposition ?? is given in Appendix ?? .

Combining Propositions ?? and ?? we obtain the following

**Corollary 2.1** The sequence of $\alpha$-discounted optimal policies $\{u_{\alpha}^*, \alpha > 0\}$ converges to a threshold policy $u_L$ as $\alpha$ goes to zero with $1 \le L \le N_0$.

## 3 The Problem P1

We show in this section that the threshold policy $u_L$ identified in Section ?? solves the problem P1. The proof of this result will rely on Theorem 2 in [?].
To apply this theorem (see [?, p. 249]) we need to introduce the long-run expected average cost

$$ \Psi(x, u) := \varlimsup_{n \to \infty} \frac{E_x^u \left[ \sum_{i=1}^n C(X_i, A_i) \right]}{E_x^u [t_n]}, \quad x \in \mathbb{N}, u \in \mathcal{U}. \qquad (3.1) $$

The following result is also needed:

**Lemma 3.1** For every $l \ge 1$ we have

$$ \Psi(x, u_l) = \Phi(x, u_l), \quad x \in \mathbb{N} \qquad (3.2) $$

where the cost functions $\Phi(x, u)$ and $\Psi(x, u)$ are defined in (3.2) and (3.3), respectively. Moreover, $\Phi(x, u_l)$ does not depend on $x$ and is finite.

**Proof.** Let $x \in \mathbb{N}$, $l \ge 1$ be fixed integers. Throughout the proof we shall assume that the threshold policy $u_l$ is used. Under policy $u_l$ the queue-length process $\{X(t), t \ge 0\}$ is a delayed regenerative process with regeneration point $S_x := \inf\{n \ge 2 : X_n = x\}$. Hence, we know by Theorem 7.5 in [?] that (3.2) will hold if $E_x^u[S_x] < \infty$.

We have shown in [?] that $E_x^{u_l}[S_x] = \sum_{y \in \mathbb{N}} E_y^{u_l}[t_2] \nu(y)/\nu(x)$ where $\nu(\cdot)$ is the invariant measure of the irreducible, aperiodic, non-null recurrent Markov chain $\{X_n, n \ge 1\}$. Let $U_n$ denote the number of arrivals during the $n$-th vacation period. Because

$$ X_{n+1} = U_n + X_n \mathbf{1}(X_n < l) \le U_n + l \qquad (3.3) $$

for all $n \ge 1$, it is readily seen that $\sum_{y \in \mathbb{N}} E_y^{u_l}[t_2] \nu(y) \le d + (b/(1-\rho))(l + \lambda d)$, which proves that $E_x^u[S_x] < \infty$. As a corollary of this result we know from [?, Remark, p. 161] that $\Phi(x, u_l)$ does not depend on $x$.

It remains to show that $\Phi_l := \Phi(\cdot, u_l) < \infty$. Until the end of the proof we shall assume that $x \ge l$. By applying Theorem 7.5 in [?] we get that $\Phi_l = E_x^{u_l}[Z(S_x)]/E_x^{u_l}[S_x]$ where $Z(t)$ is the total cost incurred in $[0, t)$. Since $E_x^{u_l}[S_x] \ge d > 0$ we must prove that $E_x^{u_l}[Z(S_x)]$ is finite.

It is easily seen from (3.2) that there exist three constants $a_1, a_2, a_3$ such that $C(y, a) \le a_1 + a_2 y + a_3 y^2$ for every $y \in \mathbb{N}$, $a \in \{s, v\}$. Hence, with $N_x := \inf\{n \ge 1 : X_{n+1} = x\}$, we have

$$ E_x^{u_l}[Z(S_x)] = E_x^{u_l} \left[ \sum_{n=1}^{N_x} C(X_n, A_n) \right] \qquad (3.4) $$

$$ = C(x, s) + E_x^{u_l} \left[ \sum_{n=1}^{N_x-1} C(X_{n+1}, A_{n+1}) \right] \\ \le C(x, s) + a_1 E_x^{u_l}[N_x] + a_2 E_x^{u_l} \left[ \sum_{n=1}^{N_x} X_{n+1} \right] + a_3 E_x^{u_l} \left[ \sum_{n=1}^{N_x} X_{n+1}^2 \right] $$

$$ \le C(x, s) + b_1 E_x^{u_l}[N_x] + b_2 E_x^{u_l} \left[ \sum_{n=1}^{N_x} U_n \right] + a_3 E_x^{u_l} \left[ \sum_{n=1}^{N_x} U_n^2 \right] \qquad (3.5) $$
with $b_1 := a_1 + a_2 l + a_3 l^2$, $b_2 := a_2 + 2a_3 l$, in view of (??). Since $x \ge l$ by assumption, we observe that under policy $u_l$ the r.v. $N_x$ is a stopping time for the renewal sequence $\{U_n, n \ge 1\}$. Therefore, Walds' formula [?, p. 377] applies to yield $E_x^{u_l}[\sum_{n=1}^{N_x} U_n^j] = E_x^{u_l}[N_x] E[U_n^j] < \infty$ for $j = 1, 2$, where the boundedness follows from the fact that $E_x^{u_l}[N_x] < \infty$ (cf. [?, Lemma 7.4], where the validity of Condition 1 in [?, p 157] is established in Appendix ??), $E[U_n] = \lambda d < \infty$, and $E[U_n^2] = \lambda^2 d^{(2)} + \lambda d < \infty$. Combining these results with (??) yields $E_x^{u_l}[Z(S_x)] < \infty$ and the proof is complete. ■

We are now in position to solve problem P1.

**Theorem 3.1** There exists an integer $L$, $1 \le L \le N_0$, such that $\Phi(x, u_L) \le \Phi(x, u)$ for every $u \in \mathcal{U}$, $x \in \mathbb{N}$.

**Proof.** If Assumptions 1-5 in [?, p. 250] were to hold then the proof would follow from Theorem 2 in [?] since we have shown in Lemma ?? that $\Psi(x, u_L) = \Phi(x, u_L)$ for all $x \in \mathbb{N}$.

We show in Appendix ?? that Assumptions 1, 3 and 4 in [?] hold for our model. However, Assumption 2 does not hold and it is quite some work to prove that Assumption 5 holds. We shall instead show that Assumption 5 can be replaced by a weaker assumption which turns out to be satisfied by our model.

Assumption 2 is only used in [?] to ensure that $E_x^{u_L}(\tau(X_n, u_L(X_n))) < \infty$ for every $n \ge 1$, $x \in \mathbb{N}$, where $\tau(x, a)$ is the sojourn time in state $x$ given action $a$ is chosen (see Sennott's comment in the proof of Theorem 2). This result is true in our case. Indeed, we have for every $n \ge 1$, $x \in \mathbb{N}$, $a \in A_x$,

$$ 
\begin{aligned}
E_x^{u_L}(\tau(X_n, u_L(X_n))) &= E_x^{u_L}[E_x^{u_L}(\tau(X_n, a) | X_n)] \\
&\le d + \frac{E_x^{u_L}(X_n) b}{1 - \rho} \\
&\le d + \frac{(x + \lambda(n-1)d) b}{1 - \rho} < \infty
\end{aligned}
$$

since $E_x^u(X_n)$ is maximized when using the policy that never turns the server on.

We shall replace Assumption 5 in [?] by the following assumption (we use Sennott's notation):

Assumption 5*: There exists a nonnegative number $M$, such that for every $i \in \mathbb{N}$ there exists $\beta_i > 0$ such that $-M \le h_\alpha(i) := W_\alpha(i) - W_\alpha(N_0)$ for every $i$ and $0 < \alpha < \beta_i$.

We show in Appendix B that Assumption 5* holds. Note that this assumption reduces to Assumption 5 in [?] if $\beta_i$ does not depend on $i$.

Assumption 5 is used by Sennott (see [?], [?, pp. 632-633]) to prove the existence of a sequence
$\{\alpha_n\}$ in $(0, \infty)$ converging to 0 as $n$ goes to $\infty$ such that for all $i \in \mathbb{N}$, $\lim_{n \to \infty} h_{\alpha_n}(i) \geq -M$. We now show that this result is still valid under Assumption 5*.

We know from Assumption 4 in [?] and Assumption 5* above that for every $i \in \mathbb{N}$, $h_{\alpha}(i) \in [-M, M_i]$ for $\alpha \in (0, \min(\alpha_0, \beta_i))$. Therefore, for any sequence $\{\alpha_n\}$ in $(0, \infty)$ converging to 0, there exists a subsequence $\{\alpha_n(0)\}$ of the sequence $\{\alpha_n\}$ such that $\lim_{n \to \infty} h_{\alpha_n(0)}(0)$ exists and is greater than or equal to $-M$. Similarly, there exists a subsequence of $\{\alpha_n(0)\}$ (call it $\{\alpha_n(1)\}$) such that $\lim_{n \to \infty} h_{\alpha_n(1)}(1)$ exists and is greater than or equal to $-M$. Iterating this procedure, we see that for every $i \in \mathbb{N}$ there exists a sequence $\{\alpha_n(i)\} \in (0, \infty)$ converging to 0 with the property that $\{\alpha_n(i)\} \subset \{\alpha_n(i-1)\} \subset \cdots \subset \{\alpha_n(0)\}$ and such that $\lim_{n \to \infty} h_{\alpha_n(i)}(i)$ exists and is greater than or equal to $-M$. Hence, $\lim_{n \to \infty} h_{\alpha_n(n)}(i) \geq -M$ for every $i \in \mathbb{N}$, and Theorem 2 in [?] applies, which concludes the proof. ■

# 4 The Problem P2

We now address the problem P2 introduced in Section ?? . We shall show that the threshold policy $u_L$ solves P2 over a subset $\mathcal{V}$ of the set $\mathcal{U}$ of all vacation policies.

The set $\mathcal{V}$ is defined as follows: $u \in \mathcal{V}$ if $u \in \mathcal{U}$ and if there exists a distinguished state $x_0 \in \mathbb{N}$ and a sequence $\{t'_n\} \subset \{t_n\}$ such that (1) $X(t'_n) = x_0$ for all $n \geq 1$, (2) $\{t'_n\}$ is a renewal process with finite expected cycle length and (3) $\{X(t), t \geq 0\}$ is a delayed regenerative process with respect to the renewal process $\{t'_n\}$. Note that $\mathcal{V} \neq \emptyset$ since $u_l \in \mathcal{V}$ for every $l \geq 1$ as shown in the proof of Lemma ?? .

The following result holds:

**Theorem 4.1** There exists an integer $L$, $1 \leq L \leq N_0$, such that $V(x, u_L) \leq V(x, u)$ for every $u \in \mathcal{V}$, $x \in \mathbb{N}$.

**Proof.** Fix $u \in \mathcal{V}$. We shall first assume that $X(0) = x_0$ (i.e., $t'_1 = 0$) where $x_0$ is the distinguished state associated with the policy $u$. Let $S$ be a generic r.v. distributed as the r.v.'s $t'_{n+1} - t'_n$ and define $N := \inf\{n \geq 1 : X_{n+1} = x_0\}$. We have by Lemma 7.4 in [?] that $E_{x_0}^u[N] < \infty$ since $E_{x_0}^u[S] < \infty$ by definition of the set $\mathcal{V}$.

Since $E_{x_0}^u[S] < \infty$, Theorem 7.5 in [?] applies to the cost $\Phi(x_0, u)$ to give

$$ \Phi(x_0, u) = \frac{E_{x_0}^u Z_N}{E_x^u [S]}, \qquad (4.1) $$

with $Z_n := \sum_{i=1}^n C(X_i, A_i)$, $n \geq 1$. Now, it is easy to see that $\{X_n\}$ is a discrete regenerative process with regeneration time $N$. Hence, by regarding $Z_N$ as the reward earned during the first
cycle, it follows from Theorem 3.16 in [?] that

$$ \lim_{n \to \infty} E_{x_0}^u \left[ \frac{Z_n}{n} \right] = \frac{E_{x_0}^u [Z_N]}{E_{x_0}^u [N]} \quad (4.2) $$

Combining (3.1) and (3.2) gives

$$ \Phi(x_0, u) = \frac{E_{x_0}^u [N]}{E_{x_0}^u [S]} \lim_{n \to \infty} E_{x_0}^u \left[ \frac{Z_n}{n} \right]. \quad (4.3) $$

Let us show that $V(x_0, u)$ (cf. (3.1)) is equal to the right-hand side of (3.2). Consider the renewal reward process $\{(ft'_n, Y_n)\}$ where

$$ Y_n := \int_{t'_n}^{t'_{n+1}} X(\xi) \, d\xi + \gamma \sum_{i=M_n}^{M_{n+1}-1} \mathbf{1}(A_i = s), \quad n \ge 1 $$

is the reward earned during the $n$-th renewal cycle $[t'_n, t'_{n+1})$, and where $M_n$ is such that $t_{M_n} = t'_n$. With $M(t) := \sup\{n \ge 1 : t'_n < t\}$ for $t > 0$ we have, cf. (3.2),

$$ \lim_{t \to \infty} E_{x_0}^u \left[ \frac{1}{t} \sum_{n=1}^{M(t)-1} Y_n \right] \le V(x_0, u) \le \lim_{t \to \infty} E_{x_0}^u \left[ \frac{1}{t} \sum_{n=1}^{M(t)-1} Y_n \right] + \lim_{t \to \infty} E_{x_0}^u \left[ \frac{Y_{M(t)}}{t} \right] \quad (4.4) $$

and it follows again by Theorem 3.16 in [?] (see also the bottom of p. 53 in [?]) that

$$ \begin{align} V(x_0, u) &= E_{x_0}^u \left[ \int_0^S X(\xi) \, d\xi + \gamma \sum_{n=1}^N \mathbf{1}(A_n = s) \right] / E_{x_0}^u [S] \nonumber \\ &= E_{x_0}^u \left[ \sum_{i=1}^N \left( \int_{t_i}^{t_{i+1}} X(\xi) \, d\xi + \gamma \mathbf{1}(A_i = s) \right) \right] / E_{x_0}^u [S] \quad \text{by definition of } S, N, t_i \nonumber \\ &= \frac{E_{x_0}^u [N]}{E_{x_0}^u [S]} \lim_{n \to \infty} E_{x_0}^u \left[ \frac{1}{n} \sum_{i=1}^n \left( \int_{t_i}^{t_{i+1}} X(\xi) \, d\xi + \gamma \mathbf{1}(A_i = s) \right) \right] \tag{4.5} \\ &= \frac{E_{x_0}^u [N]}{E_{x_0}^u [S]} \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n E_{x_0}^u \left[ E_{x_0}^u \left[ \int_{t_i}^{t_{i+1}} X(\xi) \, d\xi + \gamma \mathbf{1}(A_i = s) \mid X_i, A_i \right] \right] \nonumber \\ &= \frac{E_{x_0}^u [N]}{E_{x_0}^u [S]} \lim_{n \to \infty} E_{x_0}^u \left[ \frac{Z_n}{n} \right] \nonumber \\ &= \Phi(x_0, u) \tag{4.6} \end{align} $$

where the derivation of (3.1) is analogous to the derivation of (3.2) by replacing the reward $Z_N$ by the reward $\sum_{i=1}^N \left( \int_{t_i}^{t_{i+1}} X(\xi) d\xi + \gamma \mathbf{1}(A_i = s) \right)$ and where (3.2) follows from (3.1).

Since $\{X(t), t \ge 0\}$ is a delayed regenerative process it follows from (3.2) (see [?, Remark p. 161]) that $V(x, u) = \Psi(x, u)$ for all $x \in \mathbb{N}$. Therefore, by Theorem 3.1, $V(x, u_L) = \Phi(x, u_L) \le \Phi(x, u) =$
$V(x, u)$ for all $x \in \mathbb{N}$ and $u \in \mathcal{V}$.

**Acknowledgments.** We are very grateful to the referees for their thorough work and their constructive comments.

## A Appendix

**Proof of Proposition ??.** It suffices to prove that for $\alpha$ small enough

$$ \Delta_{\alpha}(x) \leq \Delta_{\alpha}(x+1) \quad \text{for } x = 0, 1, \dots, N_0 - 1. \qquad (A.1) $$

Indeed, since $\Delta_{\alpha}(0) = 0$ for all $\alpha > 0$ (cf. (??)) and since $\Delta_{\alpha}(N_0) > 0$ for $\alpha$ small enough (cf. the proof of Proposition ??) we may then conclude from (??) that for $\alpha$ small enough, say $\alpha \in (0, \beta)$, there exists $L_{\alpha} \in \mathbb{N}$, $1 \le L_{\alpha} \le N_0$, such that $\Delta_{\alpha}(x) \le 0$ for $x = 0, 1, \dots, L_{\alpha} - 1$ and $\Delta_{\alpha}(x) > 0$ for $x = L_{\alpha}, L_{\alpha} + 1, \dots, N_0$. Let $\{\alpha_n\}$ be a sequence in $(0, \beta)$ that converges to 0 as $n \to \infty$. Because $L_{\alpha}$ lies in the compact set $[1, N_0]$ there exists a subsequence of $\{\alpha_n\}$ (also denoted by $\{\alpha_n\}$) such that $\lim_{n \to \infty} L_{\alpha_n} = L$ with $1 \le L \le N_0$. Because $L$ is an integer we see that $L_{\alpha} = L$ for $\alpha$ small enough. Remembering now our convention that $u_{\alpha}^*(x) = v$ if $\Delta_{\alpha}(x) = 0$ we immediately deduce from the above that (??) holds for $\alpha$ small enough.

We now turn to the proof of (??)). We have for $x \in \mathbb{N}$, cf. (??), (??),

$$ \Delta_{\alpha}(x+1) - \hat{T}(\alpha)\Delta_{\alpha}(x) = (1 - \hat{T}(\alpha)) \left( dx + \frac{\lambda d^{(2)}}{2} \right) + d - \left( C(x+1, s) - \hat{T}(\alpha) C(x, s) \right) \\ + \hat{d}(\alpha) \sum_{y \in \mathbb{N}} P_V(y) \left( W_{\alpha}(x+1+y) - \hat{T}(\alpha) W_{\alpha}(x+y) \right). \quad (A.2) $$

Letting $\alpha$ go to 0 in (??), we have again by Fatou's lemma that

$$ \begin{aligned} \lim_{\alpha \to 0} \left\{ \Delta_{\alpha}(x+1) - \hat{T}(\alpha) \Delta_{\alpha}(x) \right\} &\ge d - (C(x+1, s) - C(x, s)) \\ &\quad + \sum_{y \in \mathbb{N}} P_V(y) \lim_{\alpha \to 0} \left( W_{\alpha}(x+1+y) - \hat{T}(\alpha) W_{\alpha}(x+y) \right) \\ &= d \end{aligned} \quad (A.3) $$

where (??) follows from the fact that $\{W_{\alpha}, \alpha > 0\}$ satisfies condition C1 by Proposition ?? We deduce from (??) that for $\alpha$ small enough

$$ \Delta_{\alpha}(x+1) - \hat{T}(\alpha)\Delta_{\alpha}(x) \ge d/2, \quad x \in \mathbb{N}. \qquad (A.4) $$

Sifrom (??) that (??) will hold for $\alpha$ small enough if we show that for $\alpha$ small enough

$$ (1 - \hat{T}(\alpha)) \Delta_{\alpha}(x) \le d/2, \quad x = 1, 2, \dots, N_0 - 1. \qquad (A.5) $$
This is done in the remainder of the proof.

It is seen by repeatedly applying (??) that for $\alpha$ small enough

$$ \Delta_{\alpha}(x) \le \frac{\Delta_{\alpha}(N_0)}{[\hat{T}(\alpha)]^{N_0-x}} \le \frac{\Delta_{\alpha}(N_0)}{[\hat{T}(\alpha)]^{N_0}}, \quad x = 1, 2, \dots, N_0 - 1. \quad (A.6) $$

Therefore, for $\alpha$ small enough,

$$ (1 - \hat{T}(\alpha)) \Delta_{\alpha}(x) \le \left( \frac{1 - \hat{T}(\alpha)}{[\hat{T}(\alpha)]^{N_0}} \right) \Delta_{\alpha}(N_0), \quad x = 1, 2, \dots, N_0 - 1. \quad (A.7) $$

Since the coefficient of $\Delta_{\alpha}(N_0)$ in the right-hand side of (??) approaches 0 when $\alpha$ goes to 0, we see from (??) that (??) will hold for $\alpha$ small enough if $\Delta_{\alpha}(N_0)$ is bounded from above by a number that does not depend on $\alpha$. Let us prove that $\Delta_{\alpha}(N_0)$ is bounded from above by a number that does not depend on $\alpha$.

Because $\{W_{\alpha}, \alpha > 0\}$ satisfies C2 by Lemma ?? we have for all $\alpha > 0$, cf. (??),

$$ \begin{aligned} \Delta_{\alpha}(N_0) & \le C(N_0, v) + \sum_{y \in \mathbb{N}} P_V(y) \left( W_{\alpha}(N_0 + y) - [\hat{T}(\alpha)]^{N_0} W_{\alpha}(y) \right), \\ & = C(N_0, v) + \sum_{y \in \mathbb{N}} P_V(y) \left( W_{\alpha}(N_0 + y) - [\hat{T}(\alpha)]^y W_{\alpha}(N_0) \right) \\ & \quad + \sum_{y \in \mathbb{N}} P_V(y) [\hat{T}(\alpha)]^y \left( W_{\alpha}(N_0) - [\hat{T}(\alpha)]^{N_0-y} W_{\alpha}(y) \right). \end{aligned} \quad (A.8) $$

We first compute an upper bound for the first summation in the right-hand side of (??). Let $v_{\alpha} \in \mathcal{U}$ be the policy that serves at the first decision epoch whenever the queue is nonempty and then follows the $\alpha$-optimal policy.

Hence, by definition of $W_{\alpha}(\cdot)$ (cf. (??)) we find for $\alpha > 0$

$$ \begin{aligned} & \sum_{y \in \mathbb{N}} P_V(y) (W_{\alpha}(N_0 + y) - [\hat{T}(\alpha)]^y W_{\alpha}(N_0)) \\ & \le \sum_{y \in \mathbb{N}} P_V(y) (W_{\alpha}(N_0 + y, v_{\alpha}) - [\hat{T}(\alpha)]^y W_{\alpha}(N_0)). \end{aligned} \quad (A.9) $$

For every $y \in \mathbb{N}$, we have by (??) that

$$ \begin{aligned} & W_{\alpha}(N_0 + y, v_{\alpha}) \\ = & C(N_0 + y, s) + \sum_{z \in \mathbb{N}} P_{N_0+y,z}(s) E_{N_0+y}^{v_{\alpha}} \left[ e^{-\alpha t_2} \sum_{n \ge 2} e^{-\alpha(t_n-t_2)} C(X_n, A_n) \mid X_2 = z \right] \\ = & C(N_0 + y, s) + E_{N_0+y}^{v_{\alpha}} \left[ e^{-\alpha t_2} \sum_{z \in \mathbb{N}} P_{N_0+y,z}(s) W_{\alpha}(z) \right] \\ = & C(N_0 + y, s) + \hat{d}(\alpha) \hat{T}(\alpha)^{N_0+y} \sum_{z \in \mathbb{N}} P_V(z) W_{\alpha}(z). \end{aligned} \quad (A.10) $$
On the other hand because $\Delta_{\alpha}(N_0) > 0$ for $\alpha$ small enough (see the proof of Proposition ??) we may deduce from Proposition ?? that the optimal action is to serve in state $N_0$ for $\alpha$ small enough. Hence, cf. (??), we have for small $\alpha$

$$W_{\alpha}(N_0) = C(N_0, s) + \hat{d}(\alpha) \hat{T}(\alpha)^{N_0} \sum_{y \in \mathbb{N}} P_V(y) W_{\alpha}(y) \quad (A.11)$$

so that, cf. (??), (??),

$$\begin{aligned} W_{\alpha}(N_0 + y, v_{\alpha}) - [\hat{T}(\alpha)]^y W_{\alpha}(N_0) &= C(N_0 + y, s) - [\hat{T}(\alpha)]^y C(N_0, s) \\ &\le C(N_0 + y, s) \end{aligned} \quad (A.12)$$

for any $y \in \mathbb{N}$ and for $\alpha$ small enough. Consequently, cf. (??), (??), (??),

$$\begin{aligned} & \sum_{y \in \mathbb{N}} P_V(y) (W_{\alpha}(N_0 + y) - [\hat{T}(\alpha)]^y W_{\alpha}(N_0)) \\ & \le \sum_{y \in \mathbb{N}} P_V(y) C(N_0 + y, s) \\ & = C(N_0, s) + \left(\frac{\rho d}{1 - \rho}\right) (N_0 + 1) + \left(\frac{\lambda^2}{2(1 - \rho)}\right) \left(bd^{(2)} + \frac{db^{(2)}}{1 - \rho}\right) \end{aligned} \quad (A.13)$$

by using the identities $\sum_{y \in \mathbb{N}} y P_V(y) = \lambda d$ and $\sum_{y \in \mathbb{N}} y^2 P_V(y) = \lambda d + \lambda^2 d^{(2)}$.

Next, we compute an upper bound for the term in the second summation in the right-hand side of (??). We shall distinguish between the cases $y > N_0$ and $0 \le y \le N_0$.

Fix $y > N_0$. Since $\{W_{\alpha}, \alpha > 0\}$ satisfies condition C2 we have for all $\alpha > 0$ that

$$W_{\alpha}(N_0) - [\hat{T}(\alpha)]^{N_0-y} W_{\alpha}(y) = -[\hat{T}(\alpha)]^{N_0-y} \left( W_{\alpha}(y) - [\hat{T}(\alpha)]^{y-N_0} W_{\alpha}(N_0) \right) \le 0. \quad (A.14)$$

Fix now $0 \le y \le N_0$. If the $\alpha$-optimal policy serves in state $y$, then (use (??) again and (??))

$$W_{\alpha}(N_0) - [\hat{T}(\alpha)]^{N_0-y} W_{\alpha}(y) = C(N_0, s) - \hat{T}(\alpha)^{N_0-y} C(y, s) \le C(N_0, s). \quad (A.15)$$

for $\alpha$ small enough. If the $\alpha$-optimal policy does not serve in state $y$, then

$$\begin{aligned} & W_{\alpha}(N_0) - [\hat{T}(\alpha)]^{N_0-y} W_{\alpha}(y) \\ & \le C(N_0, s) + \hat{d}(\alpha) [\hat{T}(\alpha)]^{N_0-y} \sum_{y'=0}^{\infty} P_v(y') (W_{\alpha}(y') [\hat{T}(\alpha)]^y - W_{\alpha}(y+y')) \\ & \le C(N_0, s) \end{aligned} \quad (A.16)$$

for $\alpha$ small enough, since by Lemma ?? $W_{\alpha}(y+y') - [\hat{T}(\alpha)]^y W_{\alpha}(y') \ge 0$ for all $(y, y') \in \mathbb{N}^2$, $\alpha > 0$.

Combining (??)-(??) we see that for $\alpha$ small enough $\Delta_{\alpha}(N_0)$ is bounded from above by a finite number that does not depend on $\alpha$. This concludes the proof of Proposition ??.
# B Appendix

We prove in this appendix that Assumptions 1, 3, 4 in [?] hold as well as Assumption 5* introduced in the proof of Theorem ??.

Assumption 1 in [?] holds because $P(t_2 > \delta | X_1 = x, A_1 = a) \ge P(D > \delta) > 0$ for some $\delta > 0$ since $d > 0$.

Assumption 3 holds because $W_\alpha \in \mathcal{K}$ by Proposition ?? which in turn implies by definition of the norm $|| \cdot ||$ that $W_\alpha(x)$ is finite for every $x \in \mathbb{N}$, $\alpha > 0$.

To prove that Assumption 4 holds we use again the policy $v_\alpha$ that resumes service at the first decision epoch (provided the queue is non-empty) and then follows the $\alpha$-discounted optimal policy. Since the policy $v_\alpha$ cannot perform better than the optimal policy, we have for $y \in \mathbb{N}$

$$ 
\begin{aligned}
W_{\alpha}(y) - W_{\alpha}(N_0) &\le W_{\alpha}(y, v_{\alpha}) - W_{\alpha}(N_0), \\
&= W_{\alpha}(y, v_{\alpha}) - [\hat{T}(\alpha)]^{y-N_0} W_{\alpha}(N_0) - (1 - [\hat{T}(\alpha)]^{y-N_0}) W_{\alpha}(N_0). \quad (B.1)
\end{aligned}
$$

We have shown in Proposition ?? that the optimal action in state $N_0$ is to resume service for $\alpha$ small enough. Hence, by (??) and (??) we obtain that for $\alpha$ small enough

$$ 
\begin{aligned}
W_{\alpha}(y, v_{\alpha}) - [\hat{T}(\alpha)]^{y-N_0} W_{\alpha}(N_0) &= C(y, s)\mathbf{1}(y \ge 1) + C(0, v)\mathbf{1}(y = 0) - C(N_0, s)[\hat{T}(\alpha)]^{y-N_0} \\
&\le N(y), \quad y \in \mathbb{N} \qquad (B.2)
\end{aligned}
$$

where $N(y) := C(y, s)\mathbf{1}(y \ge 1) + C(0, v)\mathbf{1}(y = 0)$. Because $1 - [\hat{T}(\alpha)]^{y-N_0}$ is nonnegative for $y \ge N_0$ it is seen from (??) and (??) that for $\alpha$ small enough $W_\alpha(y) - W_\alpha(N_0) \le N(y)$ for $y \ge N_0$.

Consider now the case when $y < N_0$. We have

$$ 
\begin{aligned}
&- (1 - [\hat{T}(\alpha)]^{y-N_0}) W_{\alpha}(N_0) = [\hat{T}(\alpha)]^{y-N_0} (1 - [\hat{T}(\alpha)]^{N_0-y}) W_{\alpha}(N_0) \\
&\le \left( \frac{bN_0}{1-\rho} \right) \alpha W_{\alpha}(N_0) \qquad (B.3)
\end{aligned}
$$

by using the inequality $1 - [\hat{T}(\alpha)]^k \le kb\alpha/(1-\rho)$ for all $\alpha \ge 0$, $k \in \mathbb{N}$. We now show that $\alpha W_\alpha(N_0)$ is uniformly bounded for small values of $\alpha$.

Recall that $\overline{\lim}_{\alpha \to 0} \alpha W_\alpha(x, u) \le \Phi(x, u)$ for every $x \in \mathbb{N}$, $u \in \mathcal{U}$ (see [?, Proposition 1]). On the other hand, $W_\alpha(x) \le W_\alpha(x, u_l)$ for every $l \ge 1$, $x \in \mathbb{N}$ by definition of $W_\alpha$. Hence, for every $l \ge 1$,

$$ \overline{\lim}_{\alpha \to 0} \alpha W_{\alpha}(x) \le \overline{\lim}_{\alpha \to 0} \alpha W_{\alpha}(x, u_l) \le \Phi(x, u_l) < \infty, \quad x \in \mathbb{N} $$

where the last equality follows from Lemma ?? . Therefore, there exist $M > 0$ and $\alpha_0 > 0$ such that

$$ \alpha W_{\alpha}(N_0) \le M \quad \text{for } \alpha \in (0, \alpha_0). \qquad (B.4) $$
In summary, we have shown that for $\alpha$ small enough $W_\alpha(y) - W_\alpha(N_0) \le N(y) + (bN_0/(1-\rho))M := M(y)$ for every $y \in \mathbb{N}$.

The second condition in Assumption 4 requires that $\sum_{y \in \mathbb{N}} P_V(y) M(y) < \infty$. This follows from the definition of $C$ together with the property that $\sum_{y \in \mathbb{N}} y^j P_V(y) < \infty$ for $j = 1, 2$.

We now examine the validity of Assumption 5*. For $\alpha$ small enough and $y \le N_0$ we see from (??) and (??) that

$$W_{\alpha}(y) - W_{\alpha}(N_0) \ge -C(N_0, s). \qquad (B.5)$$

We now address the case when $y > N_0$. Recall that $\{W_\alpha, \alpha > 0\}$ satisfies condition C1 by Lemma ?? . So, for every $y > N_0$ there exists $\beta_y > 0$ such that whenever $\alpha \in (0, \beta_y)$

$$ \begin{aligned} W_{\alpha}(y) - W_{\alpha}(N_0) &= W_{\alpha}(y) - [\hat{T}(\alpha)]^{y-N_0} W_{\alpha}(N_0) + ([\hat{T}(\alpha)]^{y-N_0} - 1) W_{\alpha}(N_0) \\ &\ge C(y, s) - C(N_0, s) + ([\hat{T}(\alpha)]^{y-N_0} - 1) W_{\alpha}(N_0) \\ &\ge C(y, s) - C(N_0, s) - \frac{bM y}{1-\rho} \end{aligned} \qquad (B.6) $$

$$ \ge -\frac{bM^2}{2(1-\rho)} - C(N_0, s) \qquad (B.7) $$

where (??) follows from (??) together with the inequality $1 - [\hat{T}(\alpha)]^k \le kb\alpha/(1-\rho)$ and where the lower bound in (??) is obtained from (??) (more precisely, $C(y, s) \ge (b/(2(1-\rho))) y^2$ for all $y \in \mathbb{N}$ so that $C(y, s) - (b/(1-\rho)) My \ge -(b/(2(1-\rho))) M^2$ for all $y \in \mathbb{N}$). The validity of Assumption 5* follows from (??) and (??).

## 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 for publication.

[2] E. Altman and P. Nain, “Optimal control of the M/G/1 queue with repeated vacations,” INRIA Report no. 1637, Mar. 1992.

[3] E. Cinlar, *Introduction to Stochastic Processes*, Prentice Hall, Englewood Cliffs, N. J., 1975.

[4] Y. N. Doğanata, “NT-vacation policy for M/G/1 queue with starter,” *Communication, Control, and Signal Processing*, Elsevier Science Pub., 1663-1669, 1990.

[5] B. T. Doshi, “Queueing systems with vacations – A survey,” *Queueing Systems*, vol. 1, no. 1, 29-66, 1986.

[6] A. Federgruen and K. C. So, “Optimality of threshold policies in single-server queueing systems with server vacations,” *Adv. Appl. Prob.*, vol. 23, 388-405, 1991.
[7] E. Gelenbe and R. Iasnogorodski, "A queue with server of walking type (Autonomous service)," *Ann. Inst. Henry Poincaré*, vol. XVI, 63-73, 1980.

[8] E. Gelenbe and I. Mitrani, *Analysis and Synthesis of Computer Systems*, Academic Press, London, 1980.

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

[10] O. Kella, "The threshold policy in the M/G/1 queue with server vacations," *Nav. Res. Logist.*, vol. 36, 111-123, 1989.

[11] O. Kella, "Optimal control of the vacation scheme in an M/G/1 queue," *Opns. Res.*, vol. 38, no. 4, 724-728, 1990.

[12] H. Lee and M. M. Srinivasan, "Control policies for the $M^X/G/1$ queueing system," *Management Sci.*, vol. 35, no. 6, 708-721, 1989.

[13] H. Levy and U. Yechiali, "Utilization of idle time in an M/G/1 queueing system," *Management Sci.*, vol. 22, 202-211, 1975.

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

[15] M. Loève, *Probability Theory I*, 4th Ed., Springer-Verlag, New York, 1977.

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

[17] M. Schäl, "Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal," *Z. Wahrscheinlichkeitsth.*, vol. 32, 179-196, 1975.

[18] L. I. Sennott, "Average cost semi-Markov decision processes and the control of queueing systems," *Prob. in the Engineering and Informational Sci.*, vol. 3, 247-272, 1989.

[19] L. I. Sennott, "Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs," *Opns. Res.*, vol. 37, no. 4, 626-636, 1989.

[20] A. J. J. Talman, "A simple proof of the optimality of the best N-policy in the M/G/1 queueing control problem with removable server," *Statistica Neerlandica*, vol. 33, 143-150, 1979.

[21] M. Yadin and P. Naor, "Queueing systems with a removable service station," *Opns. Res. Quat.*, vol. 14, 393-405, 1963.