1. THE GATED, EXHAUSTIVE, PARALLEL SERVICE SYSTEM

We consider the model described in Browne, Coffman, Gilbert, and Wright [3]. Customers arrive at an infinite server system in a Poisson stream at rate λ per unit time. Their service requirements are assumed to be independent and identically distributed (i.i.d.) random variables {σ_i}_i=1,2,…, with common distribution G(x) = P(σ₁ ≤ x). The servers, working in parallel, provide gated and exhaustive service to the queue. Service is gated in that customers are served in stages as follows. At the beginning of a service period, which we call the stage, the gate opens to admit waiting customers that are transferred from the queue to the servers, and then the gate closes. The servers then begin serving all of these customers in parallel (we assume that there is an infinite number of servers available). The stage ends when the service of all customers admitted is complete. A new stage begins immediately by admitting to service all customers that have accumulated during the first stage in front of the gate. In the case where there where no arrivals during the first stage, we assume that the system waits until the first customer arrives. At this point, the gate opens and the customer is admitted immediately to service, thus initiating a service stage with a single customer. In a possible variation to the above model, if at the end of a service stage there are no customers waiting in front of the gate, then the servers take a vacation (of random length), after which they return and a new service stage starts by admitting the customers that have meanwhile accumulated in front of the gate. (Service is exhaustive in that no vacation period ever begins as long as there are customers waiting in line.)

Denote the number of customers served in the nth stage by K_n and the duration of the nth stage by Y_n. Then it is not hard to see [3] that

is a Markov chain with discrete state space (the nonnegative integers), whereas

also constitutes a Markov chain with continuous state space (the nonnegative reals). An analysis of these Markov chains is given in [3,4], together with approximations to the stationary distribution of these chains in a number of cases. A heavy-traffic analysis of such a system has been carried out in Tan and Knessl [8]. In the above-cited articles, however, the stability issue for this system has not been settled completely. Other queuing systems with gated mechanisms have been considered in [2,5,7].

Because the model in question has an infinite number of servers, one expects that there would be no need for a stability condition analogous to that of the single-server queue. In fact, if we assume that the service time distribution has bounded support and set T := inf{x : G(x) = 1} < ∞, then the duration of all service stages is bounded above by T and this guarantees stability. However, if the support of the service time distribution is not bounded, then arbitrarily large service times are possible and the stability of the system is no longer obvious. If this were the ordinary M/G/∞ queue, then the necessary and sufficient condition for the existence of steady state would be the finiteness of the mean service time: Eσ < ∞. In fact, since the performance of this system in terms of delays is worse than that of the corresponding M/G/∞ queue because of the existence of the gating mechanism, one expects that the finiteness of the expected service time is a necessary condition for stability. In this article, we will show, using a Foster–Lyapunov drift criterion, that it is both necessary and sufficient.

To see that this is not a trivial question, let us envision the following scenario described in different terms in Browne et al. [3]. Set M_k := max(σ₁, σ₂,…, σ_k) and let G^k denote the distribution of M_k, where we have, of course, that G^k(x) = (G(x))^k for all x ≥ 0. The duration of a service stage is the maximum of all service times of customers served during this stage, and, thus, if we assume that the first stage serves k₁ customers, its duration, Y₁, has distribution G^k₁. If during Y₁ an unusually large number of customers, k₂ >> k₁ arrives as a result of statistical fluctuations, the second stage, Y₂, will be distributed according to G^k₂ and, thus, be very likely much larger than Y₁. One can imagine such a process escalating, particularly if G is heavy tailed. Browne et al. [3] have shown that this escalation is not possible, provided that the service time distribution G has finite second moment, thus establishing stability under this condition. We show that the finiteness of the first moment of G is, in fact, not only necessary but also sufficient in order to establish the stability of this system.

2. MARKOV CHAIN OF SERVICE STAGES FOR LATTICE SERVICE TIME DISTRIBUTIONS

In order to establish the stability of the system, we will examine the Markov chain of service stage lengths, (Y_n)_n=1,2,…. In fact, in this section we will simplify our task by assuming that the service time distribution G is lattice with lattice size δ > 0 (i.e., that all service times are integer multiples of δ). In particular, we will set g_j := P(σ = jδ), j = 1,2,…. An immediate consequence of this assumption is, of course, that the duration of the nth stage, Y_n, is also an integer multiple of δ. Thus, (Y_n) also becomes a discrete state space Markov chain. For simplicity, we will examine instead (Φ_n), where Φ_n := Y_n /δ, a Markov chain with state space the support of

defined as

.

It is easy to see that (Φ_n) is an irreducible chain on

. Thus, if

is finite, it must be positive recurrent and, hence, the system must be stable since both the stage lengths and the number of customers waiting in the queue are tight. Thus, the only case of interest is when

is not finite.

The transition matrix for (Φ_n) can be evaluated by first computing the conditional probability that the (n + 1)st stage serves K_n+1 = m customers, given the length of the nth stage. This amounts to computing the probability of m Poisson arrivals, taking also into consideration that in the case where we have zero arrivals during the service stage, we wait until the first arrival. Thus,

Also, recalling that g_j := P(σ = jδ) and G_j := P(σ ≤ jδ), we have

Thus, if we denote the transition probability matrix for the Markov chain (Φ_n) by P_ij := P(Φ_n+1 = j|Φ_n = i), combining the above we obtain

Setting β := λδ, the above expression can also be written as

The above double sum can be simplified considerably as follows:

where, in the last equation, we have used the fact that G_j = (G_j−1 + g_j). Thus, from (1) and (2), using the notation

, the transition probability matrix can be written as

We also point out, for future reference, the following inequality satisfied by the transition probabilities:

The above is easy to see, if we note that from the mean value theorem we have

and remember that G_j−1 − G_j = g_j.

3. POSITIVE RECURRENCE, FINITE MEAN STAGE LENGTH, AND STABILITY

In order to establish the stability of the system, we first have to show the positive recurrence of the Markov chain (Φ_n). This problem is not easy to tackle directly because the stationary equations for (Φ_n),

turn out to be intractable. However, it is possible to address this problem using the classical Foster criterion for positive recurrence (see Asmussen [1]). Nonetheless, this is not sufficient for our purposes, as the positive recurrence of (Φ_n) (and hence of (Y_n)) is a necessary but not a sufficient condition for the stability of our system.

To clarify this point, consider an analogous situation in a simpler setting. Suppose that (X_n) is a zero drift simple random walk (with steps ±1) on

. Suppose that X₀ = 0 with probability (w.p.) 1 and define T₀ = 0 and T_n = inf{k > T_n−1 : X_k = 0}. Thus, (T_n) are the corresponding epochs of return to zero. If we denote by Y_n := T_n − T_n−1 the corresponding durations of the excursions from state 0, then, clearly, (Y_n) is an i.i.d. sequence of random variables (with infinite mean). Viewed as a Markov chain, (Y_n) is positive recurrent even though (X_n) is not.

Returning to our system, let us denote by X_t = (U_t,V_t) the process whose first component is the number of customers waiting behind the gate and the second component is the number of customers in service at time t. Also, let {T_n} denote the point process of the epochs when the gate opens and K_n denote the number of customers admitted into the system at epoch T_n. Then, it should be clear that (X_t) is a semiregenerative process (e.g., see [1]) with respect to the Markov renewal process (T_n, K_n). Thus, it is easy to see that the system will be stable (in the sense that it will possess a stationary distribution) if and only if in the synchronous version of the process (where time t = 0 coincides with a typical point T₀ of the Markov renewal process in the sense that K₀ is distributed according to the stationary distribution of the embedded Markov chain), ET₁ − T₀ < ∞. This condition, however, translates to the requirement of positive recurrence for the Markov chain (Φ_n) and the finiteness of the mean of its stationary distribution (5); that is,

4. STABILITY CONDITION

The basic tool for establishing not only the positive recurrence of (Φ_n) but also the finiteness of the first moment of the stationary distribution (6) is the following generalization of the classic criterion of Foster. (This is Proposition 2.9 of Tweedie [10]. See also Meyn and Tweedie [6] for a comprehensive account of Foster–Lyapunov drift criteria in general state space Markov chains.)

Theorem 1 (Foster–Lyapunov Criterion): Suppose that a Markov chain with countable state space, say

, and transition probability matrix P_ij is irreducible and let N be a given natural number. If

is a nonnegative function and

a strictly positive function on the state space such that

where b > 0, then the Markov chain is positive recurrent and its (unique, due to its irreducibility) stationary distribution π satisfies [sum ]_jπ(j) f(j) < ∞. Furthermore, we have [sum ]_jP_ijⁿ f(j) → [sum ]_jπ_j f(j) as n → ∞.

We are now ready to state the following.

Theorem 2: The Markov chain (Φ_n) is positive recurrent with stationary probability π_i that has finite mean

provided that

.

Proof: We will assume that g_j > 0 for infinitely many j's (i.e., {g_j} has an infinite tail); otherwise, the Markov chain (Φ_n) has finite state space and it is obviously positive recurrent. Furthermore, in this case, the mean expected stage length in steady state is also finite and thus the system is stable.

We will use the Foster–Lyapunov drift criterion of Theorem 1 with f (i) = i and V(i) := ci, where c > 1. With this choice, (8) is equivalent to

Taking into account inequality (4), we see that (9) is satisfied provided that the following inequality holds:

By the Dominated Convergence Theorem,

where we have used the dominating function jg_j. (This is a valid dominating function because

. We have also used the fact that G_j > 0 for all

since, by assumption, {g_j} has an infinite tail.) Using again the Dominated Convergence Theorem on the second term of the right-hand side of (11) with the same dominating function, we have

Clearly, (11) and (12) imply that (10) and, hence, (9) hold for all i greater than some

.

The finiteness of [sum ]_jg_jj also immediately guarantees that (7) holds for some b > 0 and all i ≤ N. Thus, appealing to Theorem 1, we conclude that the Markov chain (Φ_n) is positive recurrent when Eσ < ∞ with stationary distribution π and, furthermore, that

. This finiteness of the first moment of the stationary distribution guarantees that the mean stage length is finite in steady state and, thus, that there exists a proper stationary regime for this system. █

Remark 1: Note that we do not claim that when Eσ = ∞, (Φ_n) cannot be positive recurrent.

Thus, in view of the discussion in Section 3, we have also shown the following.

Corollary 1: The condition [sum ]_jg_j j < ∞ is necessary and sufficient for the existence of a stationary distribution of the semiregenerative process (X_t).

Proof: The sufficiency of the moment condition follows directly from the above analysis. As for the necessity, it is enough to argue that the mean stage length is the maximum of a number of service times and, as such, stochastically greater than a service time. Thus, if [sum ]_jg_jj diverges, the mean stage length must be infinite, which implies that a stationary regime cannot exist for the process (X_t) by standard results regarding semiregenerative processes. █

5. NONLATTICE SERVICE TIME DISTRIBUTIONS

When the service time distribution G is not lattice, the above analysis fails. However, a similar analysis could be carried out using drift criteria for Markov chains on general state spaces (see [6]). Alternatively, one could focus on the Markov chain (K_n) of the number of customers served in each stage, which, in every case, has a denumerable state space. However, instead of adopting either of these two approaches, we will sketch a simple argument based on stochastic ordering.

If F and G are two distribution functions on

, we say that F stochastically dominates G if F(x) ≤ G(x) for all

. This stochastic order (also known as strong order) will be denoted by F ≥_st G. For further background on stochastic ordering, we refer the reader to [9]. We begin with the following obvious proposition.

Proposition 1: If

are two service time distributions such that

and if

are the corresponding service stage Markov chains, then

for all

.

Proof: It is immediate by appropriately constructing both chains on the same probability space. █

A distribution F on

is called lattice if there exists δ > 0 such that

. Given δ > 0 and a distribution function

, we define a lattice distribution G_δ by means of

Then, G_δ ≥_st G and, by virtue of Proposition 1, we have Y_n^δ ≥_st Y_n for each

for the corresponding service stage Markov chains. Furthermore, if

, then

. Thus, the finiteness of the first moment of the service time distribution implies the positive recurrence of the countable state space Markov chain (Y_n^δ) and the finiteness of the first moment of its stationary distribution, which, in turn, implies the stability of the original system.