# Computing the Performance Measures in Queueing Models via the Method of Order Statistics

Authors: Yousry H. Abdelkader; Maram Al-Wohaibi
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

This paper focuses on new measures of performance in single-server Markovian queueing
system. These measures depend on the moments of order statistics. The expected value and the variance of the maximum (minimum) number of customers in the system as well as the expected value and the variance of the minimum (maximum) waiting time are presented. Application to an M/M/1 model is given to illustrate the idea and the applicability of the proposed measures.


---

## Body

## 1. Introduction

Queueing systems have found wide applications in modeling and analysis of computer and communication systems, and several other engineering systems in which single server is attached to one or more workstations. The study of queueing systems has often been concerned with the busy period and the waiting time, because they play a very significant role in the understanding of various queueing systems and their management. A busy period in a queuing system normally starts with the arrival of a customer who finds the system empty and ends with the first time at which the system becomes empty again. The length of a busy period of an M/M/1 queue with constrained workload is discussed by Kinateder and Lee [1] using Laplace transform. Draief and Mairesse [2] analyzed the service times of customers in an M/M/1 queue depending on their position in a busy period. They provided a law of the service of a customer at the beginning, at the end, or in the middle of the busy period by considering a family of polynomial generating seires associated with Dyck paths of length 2n. Details about using a busy period in an M/M/1 queue can be found in Guillemin and Pinchon [3] and references therein. Takagi and Tarabia [4] provided an explicit probability density function of the length of a busy period starting with i customers for more general model M/M/1/L, where L is the capacity of the system; see also Tarabia [5]. Al Hanbali and Boxma [6] studied the transient behaviour of a state-dependent M/M/1/L queue during the busy period. Virtual waiting time at time t is defined to be the time that imaginary customers would have to wait before service if they arrived in a queueing system at instant t. Gross and Harris [7, Section 2.3] gave a derivation of the steady-state virtual waiting time distribution for an M/M/c model. The virtual waiting time distribution was first formulated for discrete time queues by Neuts [8] for the single-server case. Berger and Whitt [9] provided various approximation and simulation techniques for several different queueing processes (waiting time, virtual waiting time, and the queue length). For more general queue models in waiting time, see A. Brandt and M. Brandt [10]. A recursive procedure for computing the moments of the busy period for the single-server model can be found in Tarabia [5]. Limit theorems are proved by investigating the extreme values of the maximum queue length, the waiting time and virtual waiting time for different queue models in literature. Serfozo [11] discussed the asymptotic behavior of the maximum value of birth-death processes over large time intervals. Serfozo’s results concerned the transient and recurrent birth-death processes and related M/M/c queues. Asmussen [12] introduced a survey of the present state of extreme value theory for queues and focused on the regenerative properties of queueing systems, which reduced the problem to study the tail of the maximum of the queueing process {X(t)} during a regenerative cycle τ, where {X(t)} is in discrete or continuous time. Artalejo et al. [13] presented an efficient algorithm for computing the distribution for the maximum number of customers in orbit (and in the system) during a busy period for the M/M/c retrial queue. The main idea of their algorithm is to reduce the computation of the distribution of the maximum customer number in orbit by computing certain absorption probabilities. For more details in extreme value in queues, see Park [14] and Minkevičius [15] together with the references contained therein.Our motivation is to obtain some complementary measures of performance of an M/M/1 queue. The expected value and the variance of the minimum (maximum) number of customers in system as well as the expected value and the variance of the minimum (maximum) waiting time are discussed.Let us divide the number of arrival customers intok intervals, and let Xj be the number of customers in each interval. The corresponding order statistics is defined by Xi:k. Three special cases are introduced: (a) i=k, defines the maximum number of customers presented in the system, (b) i=1, defines the minimum number of customers in the system, and (c) i=k=1, defines the regular performance measures. So, our interest is to compute μ1:k=E(XMin), σ1:k2=Var(XMin), μk:k=E(XMax), and σk:k2=Var(XMax) where XMin=Min{Xi} and XMax=Max{Xi}, for 1≤i≤k. Also, let Ti be the waiting time in the interval i. The expected value and the variance of the minimum (maximum) waiting times are computed, respectively, as ν1:k=E(TMin), α1:k2=Var(TMin), νk:k=E(TMax), and αk:k2=Var(TMax) where TMin=Min{Ti} and TMax=Max{Ti}, for 1≤i≤k. The remainder of this paper is organized as follows. The model description and some important theorems in order statistics are given in Section 2. The proposed performance measures are obtained in Section 3. Numerical results and conclusion are presented in Section 4.


## 2. Model and Description

Consider a single-server queue with interarrival time and service time which are exponentially distributed with ratesλ and μ, respectively. Let Q(t) be the number of customers in the system at time t. We define (2.1)pn(t)=Pr{Q(t)=n/Q(0)=i}.
Then, the governing differential-difference equations of the system under consideration are given by(2.2)dp0(t)dt=-λp0(t)+μp1(t),dpn(t)dt=-(λ+μ)pn(t)+μpn+1(t)+λpn-1(t),n≥1.
Taking the limit as t→∞ when ρ=λ/μ<1 yields(2.3)pn=ρn(1-ρ),n=0,1,2,…
See, for example, Gross and Harris [7].LetQ be the number of customers in the system. Define the cumulative distribution function (cdf) of Q as
(2.4)F(x)=Pr{Q≤x}=∑n=0xpn.
In steady-state case for M/M/1 queue, we can write(2.5)F(x)=1-ρx+1.
In the following, we state two of the needed theorems. These two theorems can be found in Arnold et al. [16, page 43] and Barakat and Abdelkader [17], respectively. The first theorem gives expressions for the first two moments of the ith order statistics, Xi:k, in a sample of size k in discrete case, and the second theorem deals with the rth moments of Xi:k in a continuous case.Theorem 2.1.
LetS, the support of the distribution, be a subset of nonnegative integers. Then,
(2.6)E(Xi:k)=μi:k=∑x=0∞[1-Fi:k(x)],E(Xi:k2)=μi:k(2)=2∑x=0∞x[1-Fi:k(x)]+μi:k,
whenever the moment on the left-hand side is assumed to exist.
Hence, the variance is given by(2.7)σi:k2=μi:k(2)-μi:k2.
In the case of independent identically distributed (iid) random variables, the expected value and the variance of the maximum are given by
(2.8)μk:k=∑x=0∞[1-(F(x))k],(2.9)μk:k(2)=2∑x=0∞x[1-(F(x))k]+μk:k,(2.10)σk:k2=μk:k(2)-μk:k2.
Similarly, the expected value and the variance of the minimum are given by
(2.11)μ1:k=∑x=0∞[1-F(x)]k,(2.12)μ1:k(2)=2∑x=0∞x[1-F(x)]k+μ1:k,(2.13)σ1:k2=μ1:k(2)-μ1:k2,
where Fn:n(x)=[F(x)]n and F1:n(x)=1-[1-F(x)]n.Theorem 2.2.
LetXi, 1≤i≤k be a non-negative r.v.’s with d.f.’s Fi(x). Then, the rth moment of the ith order statistics in a sample of size k is given by
(2.14)μi:k(r)=r∫0∞xr-1(1-Fi:k(x))dx.
In the case of iid random variables, when i=n and i=1, one gets respectively,
(2.15)μk:k(r)=r∫0∞xr-1(1-[F(x)]k)dx,(2.16)μ1:k(r)=r∫0∞xr-1(1-F(x))kdx.


## 3. Performance Measures

This section is devoted to introduce the proposed performance measures which are often useful for investigating the behaviour of a queueing system. The mean and the variance of the minimum (maximum) number of customers in system as well as the mean and the variance of the minimum (maximum) waiting times are derived. The following lemma and consequence theorems give a procedure for the computations of these measures.Lemma 3.1.
LetXi be iid random variables; the cdf for the maximum Fk:k(x) and the minimum F1:k(x) are given by
(3.1)Fk:k(x)=(1-ρx+1)k,(3.2)F1:k(x)=1-ρk(x+1).Proof.
From the definitions of the cdf’s ofXk:k and X1:k, we have
(3.3)Fk:k(x)=[F(x)]k,F1:k(x)=1-[1-F(x)]k.
Plugging the value of F(x) from (2.5) into the last two equations, we get (3.1) and (3.2). This completes the proof.


### 3.1. The Mean and the Variance of the Minimum and the Maximum Number of Customers in the System

We are now ready to formulate our results.Theorem 3.2.
The expected value and the variance of the minimum number of customers in the system are given by(3.4)μ1:k=ρk1-ρk,σ1:k2=ρk(1-ρk)2.Proof.
Using (2.11) and (3.2), we get
(3.5)μ1:k=∑x=0∞ρk(x+1)=ρk1-ρk.
Applying (2.12) and (3.2), the second-order moment is given by
(3.6)μ1:k(2)=2∑x=0∞xρk(x+1)+ρk1-ρk=ρk(ρk+1)(1-ρk)2.
Hence, according to (2.13), the variance of the minimum is given by
(3.7)σ1:k2=ρk(ρk+1)(1-ρk)2-(ρk1-ρk)2,σ1:k2=ρk(1-ρk)2.Theorem 3.3.
The mean and the variance of the maximum number of customers in the system are given by(3.8)μk:k=∑i=1k(-1)i+1(ki)ρi1-ρi,(3.9)σk:k2=∑i=1k(-1)i+1(ki)ρi(ρi+1)(1-ρi)2-(∑i=1k(-1)i+1(ki)ρi1-ρi)2.Proof.
Applying (2.8) and (3.1), then expanding (1-ρx+1)k binomially, we obtain
(3.10)μk:k=∑x=0∞(1-∑i=0k(-1)i(ki)(ρx+1)i)=∑x=0∞∑i=1k(-1)i+1(ki)(ρx+1)i,μk:k=∑i=1k(-1)i+1(ki)ρi1-ρi.
Applying (2.9) and (3.1), the second-order moment is given by
(3.11)μk:k(2)=2∑x=0∞x[1-(1-ρx+1)k]+μk:k=2∑x=0∞x[1-(1+∑i=1k(-1)i(ki)(ρx+1)i)]+μk:k=2∑i=1k(-1)i+1(ki)∑x=0∞xρ(x+1)i+μk:k=2∑i=1k(-1)i+1(ki)(ρi)2(1-ρi)2+μk:k=∑i=1k(-1)i+1(ki)ρi(1+ρi)(1-ρi)2.
of σk:k2 in Theorem 2.1, we get (3.9) and hence the proof.Employing the above procedure,similar results can be obtained for the minimum and maximum queue length as stated in the following two corollaries.Corollary 3.4.
The mean and the variance of the minimum queue length are given by(3.12)μ1:k′=ρ2k1-ρk,σ1:k′=ρ2k(3-ρk-ρ2k)(1-ρk)2.Corollary 3.5.
The mean and the variance of the maximum queue length are given by(3.13)μk:k′=∑i=1k(-1)i+1(ki)ρ2i1-ρi,σk:k′2=∑i=1k(-1)i+1(ki)ρ2i(3-ρi)(1-ρi)2-(∑i=1k(-1)i+1(ki)ρ2i1-ρi)2.According to Lemma3.1 and the definitions of the expected value and the variance in Theorem 2.1, the proof of the above formulas can be easily established.


### 3.2. The Minimum and the Maximum Waiting Time in the Queue

Other useful performance measures are the mean and the variance of the minimum and maximum waiting time in the queue. The cumulative probability distribution of the waiting time for the M/M/1 queue is given by(3.14)Wq(t)={(1-ρ),t=0,(1-ρe-μ(1-ρ)t),t>0.
The expected waiting time in the queue is (3.15)Wq=λμ(μ-λ).Theorem 3.6.
Therth moments of the minimum waiting time in the queue are given by
(3.16)υ1:k(r)=Γ(r+1)ρk[kμ(1-ρ)]r.Proof.
Using (2.16) and (3.14), we have
(3.17)υ1:k(r)=r∫0∞tr-1[1-Wq(t)]dt=rρk∫0∞tr-1e-kμ(1-ρ)tdt=rρkΓ(r)[kμ(1-ρ)]r.The following corollary follows from Theorem3.6.Corollary 3.7.
The mean and the variance of the minimum waiting time are given by(3.18)υ1:k=ρk[kμ(1-ρ)],υ1:k(2)=2ρk[kμ(1-ρ)]2.
Then, the variance is
(3.19)α1:k2=υ1:k(2)-(υ1:k)2=ρk(2-ρk)[kμ(1-ρ)]2.Theorem 3.8.
Therth moments of the maximum waiting time in the queue are given by
(3.20)υk:k(r)=∑j=1k(-1)j+1(kj)ρjΓ(r+1)[jμ(1-ρ)]r.Proof.
Using (2.15) and (3.14), we can write
(3.21)υk:k(r)=r∫0∞tr-1(1-(Wq(t))k)dt=r∫0∞tr-1(1-(1-ρe-μ(1-ρ)t)k)dt=r∫0∞tr-1(1-∑j=0k(-1)j(kj)ρje-jμ(1-ρ)t)dt=∑j=1k(-1)j+1(kj)ρjΓ(r+1)[jμ(1-ρ)]r.The following corollary follows from Theorem3.8.Corollary 3.9.
The mean and the variance of the maximum waiting time are given by(3.22)υk:k=∑j=1k(-1)j+1(kj)ρjjμ(1-ρ),αk:k2=∑j=1k(-1)j+1(kj)2ρj[jμ(1-ρ)]2-(∑j=1k(-1)j+1(kj)ρjjμ(1-ρ))2.Proof.
Setr=1 and r=2 in (3.20), and using the definition of the variance, we get (3.22).Sinceμk:k and μk:k′ give the sum of the expected value of the maximum number of customers in the system and queue, we compute the expected value of the maximum number of customers in the system and queue during each interval k, respectively, by (3.23)Δμk=μk:k-μk-1:k-1,Δμk=μk:k-μk-1:k-1,
with conventional μ0:k=μ0:k′=0 and (3.24)ρ=Δμk-Δμk′.
Similarly, the expected value of the maximum waiting time in the queue during each interval k is computed by (3.25)Δυk=υk:k-υk-1:k-1.


## 3.1. The Mean and the Variance of the Minimum and the Maximum Number of Customers in the System

We are now ready to formulate our results.Theorem 3.2.
The expected value and the variance of the minimum number of customers in the system are given by(3.4)μ1:k=ρk1-ρk,σ1:k2=ρk(1-ρk)2.Proof.
Using (2.11) and (3.2), we get
(3.5)μ1:k=∑x=0∞ρk(x+1)=ρk1-ρk.
Applying (2.12) and (3.2), the second-order moment is given by
(3.6)μ1:k(2)=2∑x=0∞xρk(x+1)+ρk1-ρk=ρk(ρk+1)(1-ρk)2.
Hence, according to (2.13), the variance of the minimum is given by
(3.7)σ1:k2=ρk(ρk+1)(1-ρk)2-(ρk1-ρk)2,σ1:k2=ρk(1-ρk)2.Theorem 3.3.
The mean and the variance of the maximum number of customers in the system are given by(3.8)μk:k=∑i=1k(-1)i+1(ki)ρi1-ρi,(3.9)σk:k2=∑i=1k(-1)i+1(ki)ρi(ρi+1)(1-ρi)2-(∑i=1k(-1)i+1(ki)ρi1-ρi)2.Proof.
Applying (2.8) and (3.1), then expanding (1-ρx+1)k binomially, we obtain
(3.10)μk:k=∑x=0∞(1-∑i=0k(-1)i(ki)(ρx+1)i)=∑x=0∞∑i=1k(-1)i+1(ki)(ρx+1)i,μk:k=∑i=1k(-1)i+1(ki)ρi1-ρi.
Applying (2.9) and (3.1), the second-order moment is given by
(3.11)μk:k(2)=2∑x=0∞x[1-(1-ρx+1)k]+μk:k=2∑x=0∞x[1-(1+∑i=1k(-1)i(ki)(ρx+1)i)]+μk:k=2∑i=1k(-1)i+1(ki)∑x=0∞xρ(x+1)i+μk:k=2∑i=1k(-1)i+1(ki)(ρi)2(1-ρi)2+μk:k=∑i=1k(-1)i+1(ki)ρi(1+ρi)(1-ρi)2.
of σk:k2 in Theorem 2.1, we get (3.9) and hence the proof.Employing the above procedure,similar results can be obtained for the minimum and maximum queue length as stated in the following two corollaries.Corollary 3.4.
The mean and the variance of the minimum queue length are given by(3.12)μ1:k′=ρ2k1-ρk,σ1:k′=ρ2k(3-ρk-ρ2k)(1-ρk)2.Corollary 3.5.
The mean and the variance of the maximum queue length are given by(3.13)μk:k′=∑i=1k(-1)i+1(ki)ρ2i1-ρi,σk:k′2=∑i=1k(-1)i+1(ki)ρ2i(3-ρi)(1-ρi)2-(∑i=1k(-1)i+1(ki)ρ2i1-ρi)2.According to Lemma3.1 and the definitions of the expected value and the variance in Theorem 2.1, the proof of the above formulas can be easily established.


## 3.2. The Minimum and the Maximum Waiting Time in the Queue

Other useful performance measures are the mean and the variance of the minimum and maximum waiting time in the queue. The cumulative probability distribution of the waiting time for the M/M/1 queue is given by(3.14)Wq(t)={(1-ρ),t=0,(1-ρe-μ(1-ρ)t),t>0.
The expected waiting time in the queue is (3.15)Wq=λμ(μ-λ).Theorem 3.6.
Therth moments of the minimum waiting time in the queue are given by
(3.16)υ1:k(r)=Γ(r+1)ρk[kμ(1-ρ)]r.Proof.
Using (2.16) and (3.14), we have
(3.17)υ1:k(r)=r∫0∞tr-1[1-Wq(t)]dt=rρk∫0∞tr-1e-kμ(1-ρ)tdt=rρkΓ(r)[kμ(1-ρ)]r.The following corollary follows from Theorem3.6.Corollary 3.7.
The mean and the variance of the minimum waiting time are given by(3.18)υ1:k=ρk[kμ(1-ρ)],υ1:k(2)=2ρk[kμ(1-ρ)]2.
Then, the variance is
(3.19)α1:k2=υ1:k(2)-(υ1:k)2=ρk(2-ρk)[kμ(1-ρ)]2.Theorem 3.8.
Therth moments of the maximum waiting time in the queue are given by
(3.20)υk:k(r)=∑j=1k(-1)j+1(kj)ρjΓ(r+1)[jμ(1-ρ)]r.Proof.
Using (2.15) and (3.14), we can write
(3.21)υk:k(r)=r∫0∞tr-1(1-(Wq(t))k)dt=r∫0∞tr-1(1-(1-ρe-μ(1-ρ)t)k)dt=r∫0∞tr-1(1-∑j=0k(-1)j(kj)ρje-jμ(1-ρ)t)dt=∑j=1k(-1)j+1(kj)ρjΓ(r+1)[jμ(1-ρ)]r.The following corollary follows from Theorem3.8.Corollary 3.9.
The mean and the variance of the maximum waiting time are given by(3.22)υk:k=∑j=1k(-1)j+1(kj)ρjjμ(1-ρ),αk:k2=∑j=1k(-1)j+1(kj)2ρj[jμ(1-ρ)]2-(∑j=1k(-1)j+1(kj)ρjjμ(1-ρ))2.Proof.
Setr=1 and r=2 in (3.20), and using the definition of the variance, we get (3.22).Sinceμk:k and μk:k′ give the sum of the expected value of the maximum number of customers in the system and queue, we compute the expected value of the maximum number of customers in the system and queue during each interval k, respectively, by (3.23)Δμk=μk:k-μk-1:k-1,Δμk=μk:k-μk-1:k-1,
with conventional μ0:k=μ0:k′=0 and (3.24)ρ=Δμk-Δμk′.
Similarly, the expected value of the maximum waiting time in the queue during each interval k is computed by (3.25)Δυk=υk:k-υk-1:k-1.


## 4. Numerical Results

To demonstrate the applicability of the results obtained in the previous sections, some numerical results have been presented in the form of tables showing the effectiveness and the applicability of the proposed measures. We have considered M/M/1 queue withλ=5 and μ=6. Table 1 summarizes the values of Δμk, Δμk′ and ρ for each interval k. Table 2 gives the minimum number of customers in the system (queue) in each interval k. Finally, Table 3 shows the expected values of the maximum waiting time in the queue.Table 1
The expected values of the maximum number of customers in the system and queue.
kΔμkΔμk′ρ=Δμk-Δμk′154.166660.8333322.727272.588380.138831.828171.805020.02314841.371251.367390.00385851.096971.096320.00064360.9141350.9140280.000107170.7835450.7835270.0000178680.6856020.6855992.97687E-690.6094240.6094234.96145E-7100.5484810.5484818.26908E-8110.498620.498621.37818E-8120.4570680.4570682.29703E-9130.4219090.4219093.82887E-10140.3917720.3917726.38263E-11150.3656540.3656541.07789E-11Table 2
The expected values of the minimum number of customers in the system and queue.
kμ1:kμ1:k′kμ1:kμ1:k′154.1666760.5035290.16863122.272731.5782870.387120.10803831.373630.79492380.3030470.070479140.9314460.44919390.2403970.046590650.6718990.270021100.1926140.0311082Table 3
The expected values of the maximum waiting time in the queue.
kΔνkApprox.kΔνkApprox.10.8333350 minutes110.090905 minutes20.48611230 minutes120.0833335 minutes30.3317920 minutes130.076925 minutes40.24980715 minutes140.0714285 minutes50.19997412 minutes150.0666674 minutes60.16666310 minutes160.06254 minutes70.1428569 minutes170.058823 minutes80.1257 minutes180.0555563 minutes90.126 minutes190.052633 minutes100.16 minutes200.053 minutesRemarks 4.
The obtained results in Tables1–3 show that the expected value of the maximum (minimum) number of customers decreases gradually with the increasing number of intervals. Also, it is noted that the system will be almost empty in the 13rd interval. That is, the customer will get the service immediately when she (or he) arrived and will leave the system before the second arrival. This result agrees with the fact that the service rate is greater than the arrival rate. Similar conclusion can be deduced form Table 3. The traffic intensity ρ decreases gradually to zero as the number of intervals increases.


## 5. Conclusions

In this paper, we have considered the Markovian queueing model with a single-server and infinite system capacity. The paper presents some complementary measures of performance which are depending on the methods of order statistics. The expected value and the variance of the minimum (maximum) number of customers in the system (queue) as well as therth moments of the minimum (maximum) waiting time in the queue are derived. Clearly, the expected value of the number of customers in the system (queue) as well as the expected waiting time can be obtained as special cases from our proposed measures when k=1. Although this work is currently restricted to the M/M/1 model, it can be applied to other queueing models.



---

*Source: 790253-2011-11-24.xml*