Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-07T14:52:54.999Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE LAW OF THE iTH WAITING TIME IN A BUSY PERIOD OF G/M/c QUEUES

Published online by Cambridge University Press:  18 December 2007

Opher Baron
Opher Baron
Affiliation:
Rotman School of Management University of Toronto Toronto, ON, Canada M5S 3E6 E-mail: opher.baron@rotman.utoronto.ca
Rights & Permissions [Opens in a new window]

Abstract

We use induction to derive the distribution of the waiting time of the ith waiting customer in a busy period for a G/M/1 queue with a first come–first serve service. A trivial implication gives the law for the ith waiting time in a busy period for a G/M/c queue. Finally, we use the Lindley recursion to relate our results to the distribution of random walks.

Information

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 22 , Issue 1 , January 2008 , pp. 75 - 80
Copyright
Copyright © Cambridge University Press 2008

1. INTRODUCTION

Treatments of the G/M/1 queue can be found in several books on queuing theory (e.g., Asmussen [Reference Asmussen2], Cohen [Reference Cohen3], and Prabhu [Reference Prabhu4]). There are alternative methods to explicitly express the steady-state waiting times in a G/M/1 queue (e.g., Prabhu [Reference Prabhu4, p. 109], starting from the transient behavior of the system, or Asmussen [Reference Asmussen2, p. 228 and 238] based on the Wiener–Hopf factorization identity). The busy period in G/M/1 queues was also characterized (e.g., Cohen [Reference Cohen3, p. 225]) and, recently, it has been studied by Adan, Boxma, and Perry [Reference Adan, Boxma and Perry1] using the sample path approach.

In this study, we characterize the conditional law of the waiting time of the ith customer within a busy period of a G/M/1 queue given that at least i customers were served within this busy period. As we expect, this distribution is a normalized sum of Erlang(μ, j), E jμ, distributions with j = 1, … , i − 1. Therefore, our contribution is the explicit expressions for the probability that on arrival, the ith waiting customer in the busy period sees j customers in the system (or, equivalently, j − 1 customers in the queue).

We also state two straightforward applications for our results. The first is the law for the waiting time of the ith customer in a busy period of a G/M/c queue. The second uses the equivalence of the Lindley recursion, describing the waiting time in a G/G/1 queue with a first come–first serve (FCFS) service discipline, to random walks to describe the distribution of random walks condition on that they do not cross a given threshold.

For completeness, we call to mind that the probability density function (pdf) and cumulative distribution function (cdf) of an Erlang(μ, j) random variable, with j phases, each with mean μ−1, are given by

(1)
f_{E_{j}^{\mu}}\lpar x\rpar = e^{-\mu x}{\mu\, ^{j}x\,^{j-1}\over \lpar \;j-1\rpar !}\comma \quad \forall x\geq 0\comma
(2)
\qquad F_{E_{j}^{\mu}} \lpar x\rpar = 1-e^{-\mu x}\sum_{k=0}^{j-1}{\lpar \mu x\rpar ^{k} \over k!}\comma \quad \forall x\geq 0\comma

respectively, and the superscript μ emphasizes the mean of each phase.

2. WAITING TIME OF THE iTH CUSTOMER WITHIN A BUSY PERIOD

2.1. For the G/M/1 Queue

Consider a G/M/1 queue with interarrival times Z i for i ≥ 1 that are independent and identically distributed (i.i.d.) random variables with a cdf F Z(z) and service requirements S i for i ≥ 1 that are i.i.d. and exponentially distributed with mean μ−1.

We let N + 1 be the number of customers served during a busy period. We number the arrivals during a busy period such that the customer that initiates the busy period (and does not wait) is the i = 0 customer in the busy period. Then the first customer that waits, if such exists, is the i = 1 customer and so on until the i = Nth customer. Note that upon completion of service for the Nth customer, the server is idle. Furthermore, because E(X) < 0, busy periods are i.i.d. and E(N) < ∞ almost surely.

We let W i be distributed as the waiting time of the ith customer in a busy cycle onFootnote 1

(3)
I\lcub N\geq i\rcub =1.

Then, the cdf of W i is defined as

(4)
F_{W_i}\lpar x\rpar =P \lpar W_i\leq x\rpar =E \lpar I\lcub 0 \lt W_i \leq x\rcub \rpar, \quad \forall x\geq 0.

We let

a_i^{\mu}=\vint_{0}^{\infty}e^{-\mu t}{\lpar \mu t\rpar ^{i} \over i!}\; dF_{Z}\lpar t\rpar

be the probability that exactly i customers would be served within an interarrival time if there are an infinite number of customers in the queue. Again, the superscript μ emphasizes the mean service time. Moreover, it is clear that ∑i=0∞a iμ = 1.

Using the memoryless of the service time, W 1, the waiting time of the first customer that waits is exponentially distributed with mean μ−1. In the proof of Theorem 1 we use this fact to express the distribution of W i, for each i ≥ 1. Let $\mathop=\limits^{\rm d}$ denote an equality in distribution; then we have the following theorem.

Theorem 1

Let W ibe a random variable with a cdf defined by Eq. ( 4) for a G/M/1 queue with interarrival times Z with a cdf F Z(z) and exponential service with mean μ−1. Then

(5)
W_i \mathop=\limits^{\rm d}\sum_{j=1}^{i}P\,_{j}^{i}\,E_{j}^{\mu}\comma

where E jμis an Erlang(μ, j) distribution with a pdf and cdf given in Eq. ( 1), P 11 = 1 and P 0i = 0 for each i ≥ 1, and P jifor i ≥ 2 is

(6)
P\,_{j}^{i}=\sum_{k=j-1}^{i-1}P_{k}^{i-1}a_{k-j+1}^{\mu}\comma\; \quad \forall j=1\comma \ldots\comma\, i.

Proof

We argue by induction. For i = 1, the distribution of W 1 is exponential. Thus, P 11 = 1 and $W_1\mathop=\limits^{\rm d}E_{1}^{\mu}$, so the claim holds for i = 1. Now, we assume that for i − 1 ≥ 1,

(7)
W_{i-1}\mathop=\limits^{\rm d}\sum_{j=1}^{i-1}P_{j}^{i-1}E_{j}^{\mu}

and show that the claim holds for i.

We prove the theorem using the following observation. For each j = 1, … , i, we have $W_i\mathop=\limits^{\rm d}E_{j}^{\mu}$, if two independent events happened. The first is that $W_{i-1}\mathop=\limits^{\rm d}E_{k}^{\mu}$ for k = j − 1, … , i − 1,Footnote 2 and the second event is that during the interarrival time of the ith customer, there were exactly l = k + 1 − j service completions; that is, upon arrival, the (i − 1)st customer is the (k + 1)st customer in the system (queue + service), and then k + 1−j service completions take place until the arrival of the ith customer. These two independent events lead to that j customers are seen by the ith arrival. Furthermore, $P\,( W_{i-1}\mathop=\limits^{\rm d}E_{j}^{\mu}\rpar =P_{j}^{i-1}$ for k = j − 1, … , i − 1 and the probability that exactly k + 1 − j services are completed during an interarrival time is a k+1−jμ. Thus, because the ith customer can see j customers in the system only if W i−1 saw at least j − 1, we have

(8)
\eqalignno{P\left( W_i\mathop=\limits^{\rm d}E_{j}^{\mu}\right) &=\sum_{k=j-1}^{i-1}P\left( W_{i-1}\mathop=\limits^{\rm d}E_{k}^{\mu}\right) a_{k+1-j}^{\mu }\cr &=\sum_{k=j-1}^{i-1}P_{k}^{i-1}a_{k+1-j}^{\mu}\comma}

where the last equality follows from the induction assumption in Eq. (7). Observing that the ith customer can see 1 to i customers in the system upon arrival completes the proof.■

We conclude this subsection by establishing that the distribution given for W i in Theorem 1 is proper. This is equivalent to proving that

(9)
\sum_{j=1}^{i}P_{j}^{i}=\sum_{j=1}^{i} \sum_{k=j-1}^{i-1}P_{k}^{i-1}a_{k-j+1}^{\mu}=E \big ( I\lcub N\geq i\rcub \big ) .

To establish Eq. (9), we observe that given $W_{i-1}\mathop=\limits^{\rm d}E_{k}^{\mu}$, the busy cycle ends if there were k + 1 or potentially more service completions during the interarrival time of the ith customer. Thus,

(10)
\eqalignno{P \big ( N \geq i \, \vert \, W_{i-1}\mathop=\limits^{\rm d}E_{k}^{\mu} \big) &=E \bigg ( I \big \{ N \geq i \, \vert \, W_{i-1}\mathop=\limits^{\rm d}E_{k}^{\mu}\big \} \bigg ) \cr&=\sum_{l=0}^{k}a_{l}^{\mu}\comma}

and using Eq. (10),

(11)
\eqalignno{\sum_{j=1}^{i}\sum_{k=j-1}^{i-1}P_{k}^{i-1}a_{k-j+1}^{\mu} &=\sum_{k=0}^{i-1}P_{k}^{i-1}\sum_{j=1}^{k+1}a_{k-j+1}^{\mu}\cr &=\sum_{k=1}^{i-1}P_{k}^{i-1}\sum_{l=0}^{k}a_{l}^{\mu}\cr &=\sum_{k=1}^{i-1}P_{k}^{i-1}P \big (N\geq i\vert W_{i-1}\mathop=\limits^{\rm d} E_{k}^{\mu} \big) \cr &=E\,\lpar I\lcub N\geq i\rcub \rpar \comma}

where the last is from the Total Expectation Theorem. This establishes Eq. (9).

2.2. For G/M/c Queues

Consider a G/M/c queue where each server has an exponential service time with mean μ−1, as was investigated by Asmussen [Reference Asmussen2] and Wolff [Reference Wolff6]. The busy period in this queue is the time from an arrival that makes all c servers busy to the first time when only c − 1 servers are busy. Denoting the waiting time of the ith customer in a busy period of a G/M/c queue by W ic, a similar proof to the one of Theorem 1 establishes the following corollary.

Corollary 1

For a G/M/c queue with interarrival times Z with a cdf F Z (z) and exponential service with mean μ−1, we have

(12)
W_i^{c}\mathop=\limits^{\rm d}\sum_{j=1}^{i}P_{j}^{i}E_{j}^{c\mu}\comma

where E jcμhas an Erlang(cμ, j) distribution with a pdf and cdf given in Eq. ( 1), P 11 = 1, and P 0i = 0 for each i ≥ 1, and P jifor i ≥ 2 is

(13)
P_{j}^{i}=\sum_{k=j-1}^{i-1}P_{k}^{i-1}a_{k-j+1}^{c\mu}\comma \quad \forall j=1\comma \ldots\comma\, i.

2.3. The Busy Period in G/M/1 Queue and Random Walks

For the G/M/1 queue with a FCFS service discipline, let

(14)
X_i = S_i - Z_{i-1}\comma \quad \forall i \geq 1\comma

with Z 0 = 0. Thus, {X i}i=2∞ is a sequence of i.i.d. random variables. Let X be the generic random variable of this sequence and assume that E(X) < 0 (i.e., E(Z) > 1/μ).

Consider the random walk {V i}i=1∞ given by V n = ∑i=1nX i (with V 0 ≡ 0) and observe that because E(X) < 0, V tends to −∞ almost surely (e.g., Ross [Reference Ross5]). A one-sided regulated random walk {Y i}i=1∞ that is regulated at zero is given by

(15)
Y_{0}=0 \quad \hbox{and} \quad Y_{i+1}=\max\!\lcub 0\comma \,Y_i+X_{i+1}\rcub \comma \quad \forall i \geq 0.

Then from the equivalence of the waiting time in a G/G/1 queue with a FCFS service discipline to Eq. (15), known also as the Lindley recursion (e.g., Cohen [Reference Cohen3]), and from Theorem 1, Corollary 2 follows.

Corollary 2

For random walks with steps defined by Eq. ( 14) with S ithat follow and exponential distribution with mean μ−1, the pdfs of {Y i | min0<j≤i{Y j} > 0} and {V i | min0<j≤i{V j} > 0} are identical to those of W igiven in Eq. ( 5) of Theorem 1.

Acknowledgment

The author wishes to thank David Perry and an anonymous referee for useful comments on an earlier draft of this paper. The research was supported by an NSERC grant.

Footnotes

1. We could define W˜i such that P(W˜i = 0 | N < i) = 1 and W˜iI{N ≥ i} = W i, but this makes our notation cumbersome.

2. Of course, with j = 1, k = 1, … , i − 1, so we could define, in general, k = max {j − 1, 1} , … , i − 1. However, we preferred to define P 0i = 0 for each i. Both definitions are equivalent, as is evident in Eq. (8).

References

1.Adan, I., Boxma, O.J., & Perry, D. (2005). The G/M/1 queue revisited. Mathematical Methods in Operations Research 62: 437–452.CrossRefGoogle Scholar
2.Asmussen, S. (2003). Applied probability and queues, 2nd ed.New York: Springer-Verlag.Google Scholar
3.Cohen, J.W. (1982). The single server queue, 2nd ed.Amsterdam: North-Holland.Google Scholar
4.Prabhu, N.U. (1965). Queues and inventories. New York: Wiley.Google Scholar
5.Ross, S.M. (1983). Stochastic processes. Wiley Series in Probability and Mathematical Statistics. New York: Wiley.Google Scholar
6.Wolff, R.W. (1988). Stochastic modeling and the theory of queues. Prentice-Hall International Series in Industrial and Systems Engineering. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar