2. NUMBER OF CUSTOMERS PRESENT IN THE SYSTEM

Let r_j(T) denote the probability that exactly j new customers arrive during an arbitrary time interval of length T. Given that in such a time interval, n batch arrivals take place, the probability Ψ_j(n) of these n batches containing j new customers can be derived by recursion from the convolution formula:

Since the number of batches arriving during an arbitrary time interval of length T is Poisson distributed, the following expression holds for r_j(T):

Our next objective will be to derive a set of equations for p_i(t), the probability of the system holding i customers at time t. Observe that all customers in service at time t will have left the system at time t + D. Consequently, customers present at time t + D either arrived during the time interval (t,t + D] or were already waiting for service at time t. Hence, by conditioning on the number of customers present at time t, we find

The stationary distribution p_i = lim_t→∞ p_i(t) is found by letting t → ∞ in (2.1):

Together with the normalization equation and the capacity utilization equation, (2.2) constitutes an infinite system of linear equations with a unique solution (due to the irreducibility of the system) that can be calculated in several ways. In Tijms [2], a fast Fourier transform method and a geometric tail approach to solving (2.2) are described, both of which are quite efficient.

3. THE WAITING TIME DISTRIBUTION

Customers arriving in (m + 1)st position within their batch will not be served until the first m customers of their batch are being served. This type of customers will be called customers of the m-class. Let W_m denote the waiting time of an arbitrary m-class customer in the stationary system. The corresponding m-class waiting time distribution is denoted by F_m(x):

In order to find an expression for F_m(x), we assume that an arbitrary m-class customer enters the stationary system. We define t = 0 at the arrival of this customer, which will be called the “marked customer.” Let u ≤ D be some positive time lapse. Due to the memoryless property of the arrival process, the system receives, with probability r_n(u), exactly n new customers during the time interval (−u,0), just prior to the arrival of our marked customer.

We will focus on the queuing position of our marked customer at t = D − u ≥ 0, given that n new customers arrive during the time interval (−u,0). Together with the m customers of higher priority, from t = −u onward there will be m + n new customers that entered the system with higher priority than the marked customer. Another group of customers with higher priority are those who were already waiting for service at t = −u. Therefore, we introduce the following definitions:

Let j = L_q(−u) denote the number of customers waiting for service at t = −u. All customers in service at t = −u will have left the system at t = D − u. Consequently, at t = D − u, the system contains exactly j + m + n customers with a higher priority than the marked customer. If j + m + n < kc, the service initiation of the marked customer will take place no later than t = kD − u, implying W_m ≤ kD − u. On the other hand, if j + m + n ≥ kc, the service start of the marked customer will take place after t = kD − u, implying W_m > kD − u. Thus, by conditioning on n, we find

According to PASTA, as proven by Wolff [3,4], it is possible to find the time-average probability of any state of the system by sampling the system at the jump times of some Poisson process A ≡ {A(t), t ≥ 0}. The crux of Wolff's central theorem is that the Poisson process need not necessarily be the arrival process. In fact, any Poisson process will do, provided that it satisfies the Lack of Anticipation Assumption (LAA), implying that its increments A(t + Δt) − A(t) and the evolution of the system {U(s), 0 ≤ s ≤ t} are independent for any fixed t > 0. Therefore, we can also apply PASTA to the Poisson process A_m ≡ {A_m(t), t ≥ 0}, which is counting the arrivals of all batches containing more than m customers. Another Poisson process satisfying LAA is A_m^u ≡ {A_m(t + u), t ≥ 0} for any positive u. Here, all jumps are taking place exactly u time units before the corresponding jumps of A_m. Thus, by applying PASTA to A_m^u in the M^X/D/c system, we find for the right-hand side of equation (3.1),

Now, by defining the cumulative probability

, we can rewrite equation (3.1) as

Since negative queue lengths are impossible, we sum over all n ≤ kc − m − 1 in order to obtain the (unconditional) waiting time distribution of m-class customers:

Substituting x = kD − u, this result can be formulated in terms of x:

Since this expression contains only a finite number of positive terms and since Q_{kc−n−m−1} and r_n(kD − x) can be calculated as described in Section 2, (3.2) does not present any numerical complications, regardless of the traffic intensity ρ.

Our next objective will be to derive an expression for the general waiting time distribution F(x) = P{W ≤ x} for an arbitrary customer of unknown class. With probability

, the marked customer arrives in a batch containing j customers. Given that a customer arrives in a batch of j customers, there is a probability of 1/j that this customer is of the m-class, for m = 0,…,j − 1. (Here, m = j is not possible since m is the number of customers with higher priority that arrived in the same batch as the marked customer.) By conditioning on the batch size j, we find the probability a_m of an arbitrary customer being m-class:

Using these constants a_m, we can write the following expression for the general waiting time distribution: