Volume 2011, Issue 1 790253

Research Article

Open Access

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

Yousry H. Abdelkader,

Corresponding Author

Yousry H. Abdelkader

[email protected]

Department of Mathematics, Faculty of Science, Alexandria University, Alexandria, Egypt alexu.edu.eg

Department of Mathematics, Girls College, Dammam University, P.O. Box 838, Dammam 31113, Saudi Arabia ud.edu.sa

Search for more papers by this author

Maram Al-Wohaibi,

Maram Al-Wohaibi

Department of Mathematics, Girls College, Dammam University, P.O. Box 838, Dammam 31113, Saudi Arabia ud.edu.sa

Search for more papers by this author

Yousry H. Abdelkader,

Corresponding Author

Yousry H. Abdelkader

[email protected]

Department of Mathematics, Faculty of Science, Alexandria University, Alexandria, Egypt alexu.edu.eg

Department of Mathematics, Girls College, Dammam University, P.O. Box 838, Dammam 31113, Saudi Arabia ud.edu.sa

Search for more papers by this author

Maram Al-Wohaibi,

Maram Al-Wohaibi

Department of Mathematics, Girls College, Dammam University, P.O. Box 838, Dammam 31113, Saudi Arabia ud.edu.sa

Search for more papers by this author

First published: 24 November 2011

https://doi.org/10.1155/2011/790253

Citations: 4

Academic Editor: Yansheng Liu

Share a link

Email
Wechat
Bluesky

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.

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 into k intervals, and let X_j be the number of customers in each interval. The corresponding order statistics is defined by X_i: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(X^Min), , μ_k:k = E(X^Max), and where X^Min = Min {X_i} and X^Max = Max {X_i}, for 1 ≤ i ≤ k. Also, let T_i 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(T^Min), , ν_k:k = E(T^Max), and where T^Min = Min {T_i} and T^Max = Max {T_i}, 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

()

Then, the governing differential-difference equations of the system under consideration are given by

()

Taking the limit as t → ∞ when ρ = λ/μ < 1 yields

()

See, for example, Gross and Harris [7].

Let Q be the number of customers in the system. Define the cumulative distribution function (cdf) of Q as

()

In steady-state case for M/M/1 queue, we can write

()

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, X_i:k, in a sample of size k in discrete case, and the second theorem deals with the rth moments of X_i:k in a continuous case.

Theorem 2.1. Let S, the support of the distribution, be a subset of nonnegative integers. Then,

()

whenever the moment on the left-hand side is assumed to exist.

Hence, the variance is given by

()

In the case of independent identically distributed (iid) random variables, the expected value and the variance of the maximum are given by

()

Similarly, the expected value and the variance of the minimum are given by

()

where F_n:n(x) = [F(x)]ⁿ and F_1:n(x) = 1 − [1−F(x)]ⁿ.

Theorem 2.2. Let X_i, 1 ≤ i ≤ k be a non-negative r.v.’s with d.f.’s F_i(x). Then, the rth moment of the ith order statistics in a sample of size k is given by

()

In the case of iid random variables, when i = n and i = 1, one gets respectively,

()

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. Let X_i be iid random variables; the cdf for the maximum F_k:k(x) and the minimum F_1:k(x) are given by

()

Proof. From the definitions of the cdf’s of X_k:k and X_1:k, we have

()

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

()

Proof. Using (2.11) and (3.2), we get

()

Applying (2.12) and (3.2), the second-order moment is given by

()

Hence, according to (2.13), the variance of the minimum is given by

()

Theorem 3.3. The mean and the variance of the maximum number of customers in the system are given by

()

Proof. Applying (2.8) and (3.1), then expanding binomially, we obtain

()

Applying (2.9) and (3.1), the second-order moment is given by

()

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

()

Corollary 3.5. The mean and the variance of the maximum queue length are given by

()

According to Lemma 3.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

()

The expected waiting time in the queue is

()

Theorem 3.6. The rth moments of the minimum waiting time in the queue are given by

()

Proof. Using (2.16) and (3.14), we have

()

The following corollary follows from Theorem 3.6.

Corollary 3.7. The mean and the variance of the minimum waiting time are given by

()

Then, the variance is

()

Theorem 3.8. The rth moments of the maximum waiting time in the queue are given by

()

Proof. Using (2.15) and (3.14), we can write

()

The following corollary follows from Theorem 3.8.

Corollary 3.9. The mean and the variance of the maximum waiting time are given by

()

Proof. Set r = 1 and r = 2 in (3.20), and using the definition of the variance, we get (3.22).

Since μ_k:k and

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

()

with conventional

and

()

Similarly, the expected value of the maximum waiting time in the queue during each interval k is computed by

()

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, 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
1	5	4.16666	0.83333
2	2.72727	2.58838	0.1388
3	1.82817	1.80502	0.023148
4	1.37125	1.36739	0.003858
5	1.09697	1.09632	0.000643
6	0.914135	0.914028	0.0001071
7	0.783545	0.783527	0.00001786
8	0.685602	0.685599	2.97687E − 6
9	0.609424	0.609423	4.96145E − 7
10	0.548481	0.548481	8.26908E − 8
11	0.49862	0.49862	1.37818E − 8
12	0.457068	0.457068	2.29703E − 9
13	0.421909	0.421909	3.82887E − 10
14	0.391772	0.391772	6.38263E − 11
15	0.365654	0.365654	1.07789E − 11

Table 2. The expected values of the minimum number of customers in the system and queue.

k	μ_1:k		k	μ_1:k
1	5	4.16667	6	0.503529	0.168631
2	2.27273	1.57828	7	0.38712	0.108038
3	1.37363	0.794923	8	0.303047	0.0704791
4	0.931446	0.449193	9	0.240397	0.0465906
5	0.671899	0.270021	10	0.192614	0.0311082

Table 3. The expected values of the maximum waiting time in the queue.

k	Δν_k	Approx.	k	Δν_k	Approx.
1	0.83333	50 minutes	11	0.09090	5 minutes
2	0.486112	30 minutes	12	0.083333	5 minutes
3	0.33179	20 minutes	13	0.07692	5 minutes
4	0.249807	15 minutes	14	0.071428	5 minutes
5	0.199974	12 minutes	15	0.066667	4 minutes
6	0.166663	10 minutes	16	0.0625	4 minutes
7	0.142856	9 minutes	17	0.05882	3 minutes
8	0.125	7 minutes	18	0.055556	3 minutes
9	0.12	6 minutes	19	0.05263	3 minutes
10	0.1	6 minutes	20	0.05	3 minutes

Remarks 4. The obtained results in Tables 1–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 the rth 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.

References

1 Kinateder K. K. J. and Lee E. Y., A new approach to the busy period of the M/M/1 queue, Queueing Systems. (2000) 35, no. 1–4, 105–115, 1782602, https://doi.org/10.1023/A:1019185826015, ZBL0966.90014.
10.1023/A:1019185826015
Web of Science® Google Scholar
2 Draief M. K. and Mairesse J., Services within a busy period of an M/M/1 queue Dyck paths, Queueing Systems. (2005) 49, no. 1, 73–84, https://doi.org/10.1007/s11134-004-5556-6, 2119658, ZBL1058.60076.
10.1007/s11134-004-5556-6
Web of Science® Google Scholar
3 Guillemin F. and Pinchon D., On the area swept under the occupation process of an M/M/1 queue in a busy period, Queueing Systems. (1998) 29, no. 2–4, 383–398, 1654448, https://doi.org/10.1023/A:1019100617896, ZBL0917.90131.
10.1023/A:1019100617896
Web of Science® Google Scholar
4 Takagi H. and Tarabia A. M. K., Explicit probability density function for the length of a busy period in an M/M/1/K queue, Advances in Queueing Theory and Network Applications, 2009, no. chapter 12, Springer, New York, NY, USA, 213–226, 2768439.
10.1007/978-0-387-09703-9_12
Google Scholar
5 Tarabia A. M. K., A new formula for the transient behaviour of a non-empty M/M/1/∞ queue, Applied Mathematics and Computation. (2002) 132, no. 1, 1–10, https://doi.org/10.1016/S0096-3003(01)00145-X, 1918702, ZBL1043.60083.
10.1016/S0096-3003(01)00145-X
Web of Science® Google Scholar
6 Al Hanbali A. and Boxma O., Busy period analysis of the state dependent M/M/1/K queue, Operations Research Letters. (2010) 38, no. 1, 1–6, https://doi.org/10.1016/j.orl.2009.09.012, 2565806, ZBL1182.90023.
10.1016/j.orl.2009.09.012
Web of Science® Google Scholar
7 Gross D. and Harris C., Fundamentals of Queuing Theory, 2003, 3rd edition, Wiley Series in Probability.
Google Scholar
8 Neuts M. F., The single server queue in discrete time-numerical ananlysis, Naval Research Logistic Quart.(1973) 20, no. 1, 297–304.
10.1002/nav.3800200210
Web of Science® Google Scholar
9 Berger A. W. and Whitt W., Maximum values in queueing processes, Probability in the Engineering and Informational Sciences. (1995) 9, no. 3, 375–409, https://doi.org/10.1017/S0269964800003934, 1365267.
10.1017/S0269964800003934
Google Scholar
10 Brandt A. and Brandt M., Waiting times for M/M systems under state-dependent processor sharing, Queueing Systems. (2008) 59, no. 3-4, 297–319, https://doi.org/10.1007/s11134-008-9086-5, 2439298, ZBL1162.90392.
10.1007/s11134-008-9086-5
Web of Science® Google Scholar
11 Serfozo R. F., Extreme values of birth and death processes and queues, Stochastic Processes and Their Applications. (1987) 27, no. 2, 291–306, 931033, ZBL0637.60098.
10.1016/0304-4149(87)90043-3
Web of Science® Google Scholar
12 Asmussen S., Extreme value theory for queues via cycle maxima, Extremes. (1998) 1, no. 2, 137–168, https://doi.org/10.1023/A:1009970005784, 1814621, ZBL0926.60072.
10.1023/A:1009970005784
Google Scholar
13 Artalejo J. R., Economou A., and Lopez-Herrero M. J., Algorithmic analysis of the maximum queue length in a busy period for the M/M/c retrial queue, INFORMS Journal on Computing. (2007) 19, no. 1, 121–126, 2300591, https://doi.org/10.1287/ijoc.1050.0156.
10.1287/ijoc.1050.0156
Web of Science® Google Scholar
14 Park Y. S., Asymptotic distributions of maximum queue lengths for M/G/1 and GI/M/1 systems, Journal of the Korean Statistical Society. (1994) 24, no. 1, 19–29, 1354317.
Google Scholar
15 Minkevičius S., On extreme value in open queueing networks, Mathematical and Computer Modelling. (2009) 50, 1058–1066, https://doi.org/10.1016/j.mcm.2009.05.025.
10.1016/j.mcm.2009.05.025
Google Scholar
16 Arnold B. C., Balakrishnan N., and Nagaraja H. N., A First Course in Order Statistics, 1992, John Wiley & Sons, New York, NY, USA, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, 1178934.
Google Scholar
17 Barakat H. M. and Abdelkader Y. H., Computing the moments of order statistics from nonidentical random variables, Statistical Methods & Applications. (2004) 13, no. 1, 15–26, https://doi.org/10.1007/s10260-003-0068-9, 2081962, ZBL1056.62012.
10.1007/s10260-003-0068-9
Google Scholar

Citing Literature

All articles

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

Abstract

1. Introduction

2. Model and Description

3. Performance Measures

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

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

4. Numerical Results

5. Conclusions

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

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

Abstract

1. Introduction

2. Model and Description

3. Performance Measures

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

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

4. Numerical Results

5. Conclusions

References

Citing Literature

References

Related

Information